SortedSet Collection Class in .NET 4.0

Table of Contents

• Introduction
• Default behavior of SortedSet<T> Collection
• Getting Subset of a SortedSet<T> Collection
• Removing element(s) from a SortedSet<T> Collection
• Max and Min Values of a SortedSet<T> Collection
• Union(U), Intersection(∩) and Difference(-) operations
• Merging of two SortedSet<T> Collection
• CopyTo Method SortedSet<T> Collection
• Winding Up
• History

Introduction

.NET 4.0 provides us a new set collection in System.Collections.Generic, called SortedSet<T>. SortedSet<T> is a collection of unique elements and keeps the elements in sorted order implicitly. It is implemented using a self-balancing red-black tree that gives a performance complexity of O(log n) for insert, delete, and lookup. It is used to keep the elements in sorted order, to get the subset of elements in a particular range, or to get the Min or Max element of the set.

Default Behavior of SortedSet<T> Collection

Let’s create an instance of SortedSet<T> collection and initialize it by integers without any particular order, and finally print it using foreach loop. Also note that we’ve added '1' twice and '2' thrice.

var elements = new SortedSet<int>() { 5, 9, 2, 11, 2, 1, 4, 1, 2 };

foreach (int element in elements)  
   Console.Write(string.Format(" {0}", element));

Output: 1 2 4 5 9 11

As we can see, all the elements are in sorted order without repetition of any element. Even if we add an element at runtime, again SortedSet<T> collection maintains set in sorted order. You can see this by the following code snippet:

bool result = elements.Add(17);

foreach (int element in elements)  
           Console.Write(string.Format(" {0}", element)); 

Output: 1 2 4 5 9 11 17

Basically Add method has a return type of bool that can be used to determine whether the element was successfully added (true) or not (false). If it returns false, then it indicates that the set already contains this element.

Getting a Subset of a SortedSet<T> Collection

You can also get a subset of given SortedSet<T> in a particular range.

var subSet = elements.GetViewBetween(2, 9);

foreach (int element in subSet)  
           Console.Write(string.Format(" {0}", element));

Output: 2 4 5 9

Note that the GetViewBetween method returns a view of the original set, i.e., any changes made to the view will be reflected in the original set. E.g if we add 7 to subSet, then it's really added to the original set elements.

var subSet = elements.GetViewBetween(2, 9);

bool result = subSet.Add(7);

foreach (int element in elements)  
   Console.Write(string.Format(" {0}", element)); 

Output: 1 2 4 5 7 9 11

But you can’t add any items to a view outside of the specified bounds, i.e., if we try to add 21 to subSet which is outside the specified bounds 2 and 9 for subSet, then we’ll get ArgumentOutOfRangeException exception.

var subSet = elements.GetViewBetween(2, 9);

bool result = subSet.Add(21);

foreach (int element in elements)  
   Console.Write(string.Format(" {0}", element)); 

Removing Element(s) from a SortedSet<T> Collection

You can remove any particular element from a given SortedSet<T>.

 elements.Remove(1);

 foreach (int element in elements)
    Console.Write(string.Format(" {0}", element)); 

Output: 2 4 5 9 11

Remove method returns true on successful removal, else false.

You can also remove more than one element from a given SortedSet<T> that match the predicate using RemoveWhere method.

elements.RemoveWhere(P => P % 2 == 0);

 foreach (int element in elements)
    Console.Write(string.Format(" {0}", element));

Output: 1 5 9 11

The predicate (P => P % 2 == 0) removes even elements from a given integer SortedSet<T>.

RemoveWhere method returns the total number of elements deleted from a given SortedSet<T>.

int totalRemoved = elements.RemoveWhere(P => P % 2 == 0);

Console.Write(string.Format("Total Elements Removed: {0}", totalRemoved)); 

Total Elements Removed: 2

Max and Min Values of a SortedSet<T> Collection

We can also get Max and Min values of a SortedSet<T> as:

Console.Write(string.Format("Max: {0}, Min: {1}", elements.Max, elements.Min)); 

Output : Max: 11, Min: 1

Union(U), Intersection(∩) and Difference(-) operations

You can easily apply Union(U), Intersection(∩) and Difference(-) set operations on given SortedSet<T> Collections. Lets consider two sets A & B-

var A = new SortedSet<int>() { 1, 2, 3, 4, 5, 11, };
var B = new SortedSet<int>() { 6, 7, 8, 9, 10, 11 };

You can take Union of A & B through Union method as:

var union = A.Union(B);

foreach (int element in union)
   Console.Write(string.Format(" {0}", element));

Output (AUB): 1 2 3 4 5 11 6 7 8 9 10

You can take Intersection of A & B through Intersect method as:

var intersection = A.Intersect(B);

foreach (int element in intersection)
   Console.Write(string.Format(" {0}", element));

Output (A∩B): 11

You can take Difference of A & B through Except method as:

var difference = A.Except(B);

foreach (int element in difference)
   Console.Write(string.Format(" {0}", element));

Output (A-B): 1 2 3 4 5

Merging of two SortedSet<T> Collection

You can merge two SortedSet<T> Collections through Zip method by using the specified predicate function.

var merged = A.Zip(B, (P, Q) => P + Q);

foreach (int element in merged)
   Console.Write(string.Format(" {0}", element));

Output: 7 9 11 13 15 22

CopyTo Method of SortedSet<T> Collection

It is a very useful method. It has three constructors - CopyTo(T()), CopyTo(T(), Int32) & CopyTo(T(), Int32, Int32).

CopyTo(T()): It copies the complete SortedSet<T> to a compatible one-dimensional array, starting at the beginning of the target array.

var target = new SortedSet<int>() {13, 2, 4, 10, 1, 7 };

int[] array = new int[10];

target.CopyTo(array);

for (int n = 0; n < array.Length; ++n)
   Console.Write(string.Format("Index: {0}, Value: {1}<br />", n, array[n]));

Output:
Index: 0, Value: 1
Index: 1, Value: 2
Index: 2, Value: 4
Index: 3, Value: 7
Index: 4, Value: 10
Index: 5, Value: 13
Index: 6, Value: 0
Index: 7, Value: 0
Index: 8, Value: 0
Index: 9, Value: 0

CopyTo(T(), Int32): It copies the complete SortedSet<T> to a compatible one-dimensional array, starting at the specified array index.

target.CopyTo(array, 3);

for (int n = 0; n < array.Length; ++n)
   Console.Write(string.Format("Index: {0}, Value: {1}<br />", n, array[n]));

Output:
Index: 0, Value: 0
Index: 1, Value: 0
Index: 2, Value: 0
Index: 3, Value: 1
Index: 4, Value: 2
Index: 5, Value: 4
Index: 6, Value: 7
Index: 7, Value: 10
Index: 8, Value: 13
Index: 9, Value: 0

CopyTo(T(), Int32, Int32): It copies a specified number of elements from SortedSet<T> to a compatible one-dimensional array, starting at the specified array index.

target.CopyTo(array, 3, 4);

for (int n = 0; n < array.Length; ++n)
   Console.Write(string.Format("Index: {0}, Value: {1}<br />", n, array[n]));

Output:
Index: 0, Value: 0
Index: 1, Value: 0
Index: 2, Value: 0
Index: 3, Value: 1
Index: 4, Value: 2
Index: 5, Value: 4
Index: 6, Value: 7
Index: 7, Value: 0
Index: 8, Value: 0
Index: 9, Value: 0

If compatible one-dimensional array doesn't have sufficient space to hold SortedSet<T> Collection's elements, then you'll face ArgumentException exception.

Winding Up

So we’ve seen that it is a very useful addition in Base Class Libraries (BCL) of .NET 4.0.

History

• 23^rd June, 2010 -- Article updated (Modified table of contents and added information about CopyTo method
• 22^nd June, 2010 -- Article updated (Modified table of contents, added information about union, intersection & difference set operations and merging of two sets
• 16^th June, 2010 -- Article updated (Modified table of contents, formatted article and added information about element(s) removal)
• 10^th June, 2010 -- Article updated (Added table of contents)
• 10^th June, 2010 -- Original version posted