Sorted Set is the preferred data structure when we want to have sorted items and also to eliminate duplicate elements. Unfortunately, its performance is worse than that of a Hash Set or a Dictionary. The following program declares a new Sorted Set and adds elements to it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
using System; using System.Collections.Generic; class Program { static void Main() { // Create a new sorted set of strings. SortedSet<string> set = new SortedSet<string>(); // Add 4 elements. set.Add("cat"); set.Add("dog"); set.Add("cow"); set.Add("horse"); // Remove an element. set.Remove("cat"); // Print elements in set. foreach (string element in set) // will print in alphabetical order Console.WriteLine(element); Console.ReadLine(); } } |
Sometimes happens that you may want to create a Sorted Set from the elements contained in another data structure, such as an array or list. This can be accomplished directly using the Sorted Set’s constructor:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
using System; using System.Collections.Generic; class Program { static void Main() { // Create list with elements of type string, with duplicates. List<string> list = new List<string>(); list.Add("cat"); list.Add("dog"); list.Add("chicken"); list.Add("chicken"); // Create a sorted set from list using the constructor. SortedSet<string> set = new SortedSet<string>(list); // Display contents. foreach (string element in set) Console.WriteLine(element); Console.ReadLine(); } } |
The most useful methods of the Sorted Set class are the following:
RemoveWhere() – this method can be used to remove all elements that meet a certain condition. This method uses Linq, of which we haven’t learned yet:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
using System; using System.Collections.Generic; class Program { static void Main() { // Create a sorted set. SortedSet<string> set = new SortedSet<string>(); set.Add("jane"); set.Add("sarah"); set.Add("adam"); set.Add("ben"); set.Add("mark"); set.Add("mark"); // Remove all elements where first letter is "m". set.RemoveWhere(element => element.StartsWith("m")); // Display results foreach (string element in set) Console.WriteLine(element); Console.ReadLine(); } } |
Clear() – Just as in the case of the other data structures we learned so far, Clear() can be used to remove all the elements in the collection.
UnionWith() – As in the case of the Hash Set, this method will return a new collection of sorted elements by merging two other collections, of course, removing the elements that are duplicates.
SymmetricExceptWith() – This method will join two collections by taking all the elements that are unique to one of the collections. So, all the elements that are found in one of the collections, but not in the other.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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 element in set) Console.WriteLine(element); Console.ReadLine(); } } |
ExceptWith() – This is a subtracting method. It will take two collections and will return all the elements that are not present in one of them.
Overlaps() – This useful method tells us if a collection has any elements in common with our Sorted Set. If at least one element is found in both of them, the result is True, otherwise False.
IntersectWith() – Method for merging two collections by taking all the elements that are present in both of them.
Min(), Max() – Since you cannot use an index to access the elements of a Sorted Set, these methods are useful in the sense that they can offer us the first or the last elements of the collection.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
using System; using System.Collections.Generic; class Program { static void Main() { // Declare a new sorted set and add few elements var set = new SortedSet<string>(); set.Add("a"); set.Add("f"); set.Add("z"); set.Add("x"); // Display Min and Max values of the collection Console.WriteLine(set.Min); Console.WriteLine(set.Max); Console.ReadLine(); } } |
The output will be:
IsSubsetOf(), IsSupersetOf(), IsProperSubsetOf() and IsProperSupersetOf() – These are methods that help us compute subsets and supersets. In common language, a subset is a set that is contained entirely inside another set. A superset is the set that contains entirely another set. Aside of that, “proper subset” or “proper superset” refers to the property of not having the same exact count of elements. A superset must have at least one element more than the contained set, and a subset must have at least one element less than the set containing it:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
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)); Console.ReadLine(); } } |
Producing this result:
SetEquals() – An useful methods whenever we want to compare two Sorted Sets and check whether they contain the same elements.
GetViewBetween() – a method for taking all the elements in a Sorted Set, between two of its elements, which we provide as parameters to this method. The returned elements are all the elements that are found between these two elements (including them).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
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 element in view) Console.WriteLine(element); Console.ReadLine(); } } |
The above program will display 4, 5, 7. Why? Because, remember, this is a Sorted Set. So, even if we added the elements in a random order, they will be sorted (numerically, in this case, because we supplied integers). And, after sorting them, the elements that are found between 4 and 7 inclusive, are 4, 5 and 7.
Contains() – Determines whether a Sorted Set contains a certain element.
The most important property of a Sorted Set is:
Count – returns the number of elements in the collection.
Tags: data structures, sorted set
