C# SortedSet Examples

Use the SortedSet type. This type is an optimized set collection.
SortedSet. This is an ordered set collection. We have many elements and want to store them in a sorted order and also eliminate all duplicates from the data structure.
A generic. The SortedSet is part of the System.Collections.Generic namespace. Its performance tends to be worse than a hash table like Dictionary.HashSetSortedList
Add, remove. This program creates a new, empty SortedSet instance. Then it adds 4 elements to the set with the Add method. Next it removes one element with Remove.

Finally: It uses the SortedSet instance in foreach to loop through all the elements. They are stored alphabetically.

Foreach
C# program that adds and removes elements using System; using System.Collections.Generic; class Program { static void Main() { // Created sorted set of strings. SortedSet<string> set = new SortedSet<string>(); // Add 4 elements. set.Add("perls"); set.Add("net"); set.Add("dot"); set.Add("sam"); // Remove an element. set.Remove("sam"); // Print elements in set. foreach (string val in set) // ... Alphabetical order. { Console.WriteLine(val); } } } Output dot net perls
Copy list. Often you may want to create a SortedSet instance from the elements in another collection, such as an array or List. You can do this with the SortedSet constructor.List

Note: In the example, the duplicate element ("perls") is only present once in the SortedSet.

C# program that uses SortedSet constructor using System; using System.Collections.Generic; class Program { static void Main() { // Create list with elements. List<string> list = new List<string>(); list.Add("sam"); list.Add("allen"); list.Add("perls"); list.Add("perls"); // Created sorted set from list. SortedSet<string> set = new SortedSet<string>(list); // Display contents. foreach (string val in set) { Console.WriteLine(val); } } } Output allen perls sam
RemoveWhere. Sometimes you may need to remove all elements from your SortedSet that match a certain condition. You can invoke the RemoveWhere method.

Here: In this example, four names are added to the SortedSet that start with the letter s.

Then: We call RemoveWhere with a lambda that is used as a predicate condition. When the method returns true, the element is removed.

C# program that uses RemoveWhere method using System; using System.Collections.Generic; class Program { static void Main() { // Create sorted set. SortedSet<string> set = new SortedSet<string>(); set.Add("sam"); set.Add("sally"); set.Add("sandra"); set.Add("steve"); set.Add("mark"); set.Add("mark"); // Remove all elements where first letter is "s". set.RemoveWhere(element => element.StartsWith("s")); // Display. foreach (string val in set) { Console.WriteLine(val); } } } Output mark
Add method. We call the Add method to put additional elements into the set. The Add method returns a boolean value that tells us whether or not a new element was added.

Result: If it returns true, a new element was added. If it returns false, the element already existed in the set and was not added again.

C# program that checks result of Add using System; using System.Collections.Generic; class Program { static void Main() { // Test add method. SortedSet<string> set = new SortedSet<string>(); bool a = set.Add("sam"); bool b = set.Add("sam"); bool c = set.Add("sam"); bool d = set.Add("mike"); Console.WriteLine("{0} {1} {2} {3}", a, b, c, d); } } Output True False False True
Count, clear. As with other collections, you can use the Count property and the Clear method on the SortedSet type. Please notice that the Count property can only be read, not assigned to.

Tip: After the Clear() method is called, the Count property will always return zero.

C# program that uses Count and Clear using System; using System.Collections.Generic; class Program { static void Main() { SortedSet<string> set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("a"); // Not successful. Console.WriteLine(set.Count); set.Clear(); Console.WriteLine(set.Count); } } Output 2 0
UnionWith. This returns the union of two collections. If the set contains A, B and C, and the second collection contains C and D, the union will be equal to A, B, C and D.

Result: The UnionWith method adds all the elements into one collection. No duplicates will be found in the SortedSet.

C# program that uses UnionWith method using System; using System.Collections.Generic; class Program { static void Main() { SortedSet<string> set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("x"); List<string> list = new List<string>(); list.Add("a"); list.Add("y"); // Union the two collections. set.UnionWith(list); // Enumerate. foreach (string val in set) { Console.WriteLine(val); } } } Output a x y z
SymmetricExceptWith. This returns all elements that are found in only one collection. If both contain "A," SymmetricExceptWith will remove "A" from the SortedSet instance.

Note: The SymmetricExceptWith method modifies the SortedSet in-place. You do not need to copy the variable reference.

Important: With SortedSet, some methods return a new SortedSet, and other modify the set in-place.

C# program that calls SymmetricExceptWith using System; using System.Collections.Generic; class Program { static void Main() { SortedSet<string> set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("x"); List<string> list = new List<string>(); list.Add("a"); list.Add("y"); // Determine symmetric set. set.SymmetricExceptWith(list); // Display elements. foreach (string val in set) { Console.WriteLine(val); } } } Output x y z
ExceptWith. This removes all elements found in a collection from the SortedSet. The resulting SortedSet will contain all its elements except those that were found in the other collection.
C# program that demonstrates ExceptWith using System; using System.Collections.Generic; class Program { static void Main() { SortedSet<string> set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("x"); List<string> list = new List<string>(); list.Add("a"); list.Add("x"); // Call ExceptWith to remove elements. set.ExceptWith(list); // Display elements. foreach (string val in set) { Console.WriteLine(val); } } } Output z
Overlaps. This tells us whether a collection has any elements in common with the SortedSet. Even if only one element is found in common, the result is True. Otherwise the result is False.
C# program that uses Overlaps method using System; using System.Collections.Generic; class Program { static void Main() { SortedSet<string> set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("x"); List<string> list = new List<string>(); list.Add("a"); list.Add("y"); HashSet<string> hash = new HashSet<string>(); hash.Add("v"); hash.Add("u"); bool a = set.Overlaps(list); // Set and list overlap. bool b = set.Overlaps(hash); // Set and hash do not overlap. Console.WriteLine(a); Console.WriteLine(b); } } Output True False
IntersectWith. This changes the set instance so that it contains only the elements that were present in both collections. The element count is reduced or stays the same.
C# program that calls IntersectWith method using System; using System.Collections.Generic; class Program { static void Main() { var set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("x"); var list = new List<string>(); list.Add("a"); list.Add("x"); // Compute intersection. set.IntersectWith(list); // Enumerate. foreach (string val in set) { Console.WriteLine(val); } } } Output a x
Min, max. The SortedSet contains elements that are stored in ascending sorted order. So it is trivial for the set to compute its lowest and highest values.

Also: You cannot use an indexer with the SortedSet, so these properties are useful.

C# program that demonstrates Min and Max properties using System; using System.Collections.Generic; class Program { static void Main() { // Three-element set. var set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("x"); // Write Min and Max. Console.WriteLine(set.Min); Console.WriteLine(set.Max); } } Output a z
Subsets, supersets. SortedSet has methods to compute subsets and supersets. These are IsSubsetOf, IsSupersetOf, IsProperSubsetOf and IsProperSupersetOf.

Definitions: A subset is contained entirely inside another set. A superset contains entirely another set.

Note: Proper subsets and supersets cannot have the same number of elements. They must have at least one fewer.

Math: Please visit the Wolfram link for information on set theory and proper subsets.

Proper Subset: wolfram.com
C# program that uses IsSubsetOf, IsSupersetOf using System; using System.Collections.Generic; class Program { static void Main() { var set = new SortedSet<string>(); set.Add("a"); set.Add("z"); set.Add("x"); var list1 = new List<string>(); list1.Add("a"); list1.Add("z"); list1.Add("x"); var list2 = new List<string>(); list2.Add("a"); list2.Add("z"); list2.Add("x"); list2.Add("y"); Console.WriteLine("IsProperSubsetOf: {0}", set.IsProperSubsetOf(list1)); Console.WriteLine("IsSubsetOf: {0}", set.IsSubsetOf(list1)); Console.WriteLine("IsProperSubsetOf: {0}", set.IsProperSubsetOf(list2)); Console.WriteLine("IsSubsetOf: {0}", set.IsSubsetOf(list2)); var list3 = new List<string>(); list3.Add("a"); list3.Add("z"); Console.WriteLine("IsProperSupersetOf: {0}", set.IsProperSupersetOf(list3)); Console.WriteLine("IsSupersetOf: {0}", set.IsSupersetOf(list3)); } } Output IsProperSubsetOf: False IsSubsetOf: True IsProperSubsetOf: True IsSubsetOf: True IsProperSupersetOf: True IsSupersetOf: True
SetEquals. This tells us if 2 collections have the same elements. In my testing, I found that the SetEquals method treats the second collection as though it has no duplicate elements.

Note: If duplicate elements are present, the 2 collections may still be considered equal.

C# program that demonstrates SetEquals method using System; using System.Collections.Generic; class Program { static void Main() { var set = new SortedSet<string>(); set.Add("s"); set.Add("a"); set.Add("m"); var list = new List<string>(); list.Add("s"); list.Add("a"); list.Add("m"); // See if the 2 collections contain the same elements. bool a = set.SetEquals(list); Console.WriteLine(a); } } Output True
GetViewBetween. How can you see what elements a SortedSet instance contains between and including 2 values? You can use GetViewBetween with 2 arguments: the minimum and maximum values.

Then: You can loop over the SortedSet that is returned in a foreach-loop, or do further operations as needed.

C# program that calls GetViewBetween method using System; using System.Collections.Generic; class Program { static void Main() { var set = new SortedSet<int>(); set.Add(5); set.Add(7); set.Add(8); set.Add(9); set.Add(4); // Call GetViewBetween method. SortedSet<int> view = set.GetViewBetween(4, 7); foreach (int val in view) { Console.WriteLine(val); } } } Output 4 5 7
Contains. If you need to determine if your SortedSet has a certain element in it, you could use a foreach-loop and imperatively scan all the elements. However, Contains is clearer.
C# program that demonstrates Contains method using System; using System.Collections.Generic; class Program { static void Main() { var set = new SortedSet<int>(); set.Add(8); set.Add(7); set.Add(8); set.Add(9); set.Add(3); // Use Contains method. bool a = set.Contains(9); Console.WriteLine(a); } } Output True
Add. When you add elements to your SortedSet, they are automatically stored in ascending order: lowest to highest values. With Reverse() we get the elements in the opposite, reverse order.

And: If you want to loop over your SortedSet from highest to lowest (reverse alphabetical order), you can call Reverse in a foreach-loop.

C# program that uses Reverse method on SortedSet using System; using System.Collections.Generic; class Program { static void Main() { var set = new SortedSet<int>(); set.Add(8); set.Add(7); set.Add(8); set.Add(9); set.Add(3); foreach (int val in set) { Console.Write(val); Console.Write(' '); } Console.WriteLine(); // Use Reverse. foreach (int val in set.Reverse()) { Console.Write(val); Console.Write(' '); } Console.WriteLine(); } } Output 3 7 8 9 9 8 7 3
Performance. Is SortedSet efficient? This depends of course on your program. A key point is that the SortedSet does not include hashing. To look up a node, a logarithmic search is needed.
Therefore, SortedSet is slower than HashSet for lookups. In micro-benchmarks, SortedSet is much slower than HashSet, but in real programs this difference may not be relevant.
Internally, the SortedSet is implemented as a tree with a Root, Left and Right node on every node instance. Every node is allocated on the managed heap. This reduces performance.

Hashing: For most programs a hashing mechanism (such as that found in Dictionary and HashSet) is superior for performance.

Dictionary

Credit: Thanks to Mark Minich for helping clarify the performance information. SortedSet has a logarithmic search.

A summary. SortedSet can replace confusing, custom types with a simple type. This reduces program complexity. SortedSet is an interesting combination of HashSet and SortedList.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
HomeSearch
Home
Dot Net Perls