SortedSet
The C# SortedSet
is an ordered set collection. It helps when we have many elements and want to store them in a sorted order, eliminating all duplicates.
This class
is part of the System.Collections.Generic
namespace. Its performance tends to be worse than a hash table like Dictionary
—it does not support hashing.
This program creates a new, empty SortedSet
instance. Then it adds 3 elements to the set with the Add method. Finally it performs operations on the set.
Contains
method to see if the string
"bird" is present in the set.SortedSet
in "foreach
" to loop through all the elements—they are stored alphabetically.using System; using System.Collections.Generic; // Create sorted set. SortedSet<string> set = new SortedSet<string>(); // Add 3 elements. set.Add("carrot"); set.Add("bird"); set.Add("apple"); // Use contains method. Console.WriteLine(set.Contains("bird")); // Print all element in sorted order. foreach (string val in set) { Console.WriteLine(val); }True apple bird carrot
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.
SortedSet
.using System; using System.Collections.Generic; // Create list with elements. var list = new List<string>(); list.Add("x"); list.Add("y"); 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); }perls x y
RemoveWhere
Sometimes you may need to remove all elements from your SortedSet
that match a certain condition. You can invoke the RemoveWhere
method.
SortedSet
that start with the letter s.RemoveWhere
with a lambda that is used as a predicate condition. When the method returns true, the element is removed.using System; using System.Collections.Generic; // 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); }mark
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.
using System; using System.Collections.Generic; // 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);True False False True
Count
, clearAs with other collections, you can use the Count
property and the Clear method on the SortedSet
type. The Count
property can only be read, not assigned to.
using System; using System.Collections.Generic; 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);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.
UnionWith
method adds all the elements into one collection. No duplicates will be found in the SortedSet
.using System; using System.Collections.Generic; 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); }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.
SymmetricExceptWith
method modifies the SortedSet
in-place. You do not need to copy the variable reference.SortedSet
, some methods return a new SortedSet
, and other modify the set in-place.using System; using System.Collections.Generic; 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); }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.
using System; using System.Collections.Generic; 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); }z
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.
using System; using System.Collections.Generic; 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);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.
using System; using System.Collections.Generic; 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); }a x
Min
, maxThe SortedSet
contains elements that are stored in ascending sorted order. So it is trivial for the set to compute its lowest and highest values.
SortedSet
, so these properties are useful.using System; using System.Collections.Generic; // 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);a z
SortedSet
has methods to compute subsets and supersets. These are IsSubsetOf
, IsSupersetOf
, IsProperSubsetOf
and IsProperSupersetOf
.
using System; using System.Collections.Generic; 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));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.
using System; using System.Collections.Generic; 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);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.
using System; using System.Collections.Generic; 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); }4 5 7
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.
SortedSet
from highest to lowest (reverse alphabetical order), you can call Reverse
in a foreach
-loop.using System; using System.Collections.Generic; 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();3 7 8 9 9 8 7 3
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.
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.
Dictionary
and HashSet
) is superior for performance.SortedSet
can replace confusing, custom types with a simple type. This reduces program complexity. SortedSet
is an interesting combination of HashSet
and SortedList
.