Click here to Skip to main content
15,861,168 members
Articles / Programming Languages / C# 4.0

SortedSet Collection Class in .NET 4.0

Rate me:
Please Sign up or sign in to vote.
4.36/5 (22 votes)
22 Jun 2010CPOL5 min read 71.2K   26   22
This article explains the SortedSet Collection class added in Base Class Libraries (BCL) of .NET 4.0

Table of Contents

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.

C#
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><t> collection maintains set in sorted order. You can see this by the following code snippet:

C#
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.

C#
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.

C#
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.

C#
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>.

C#
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.

C#
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>.

C#
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:

C#
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-

C#
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:

C#
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:

C#
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:

C#
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.

C#
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.

C#
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.

C#
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.

C#
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.

Exception.png

Winding Up

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

History

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Technical Lead Infogain India Pvt Ltd
India India


Samir NIGAM is a Microsoft Certified Professional. He is an insightful IT professional with results-driven comprehensive technical skill having rich, hands-on work experience n web-based applications using ASP.NET, C#, AJAX, Web Service, WCF, jQuery, Microsoft Enterprise Library , LINQ, MS Entity Framework, nHibernate, MS SQL Server & SSRS.



He has earned his master degree (MCA) from U.P. Technical University, Lucknow, INDIA, his post graduate dipoma (PGDCA ) from Institute of Engineering and Rural Technology, Allahabad, INDIA and his bachelor degree (BSc - Mathematics) from University of Allahabad, Allahabad, INDIA.



He has good knowledge of Object Oriented Programming, n-Tier Architecture, SOLID Principle, and Algorithm Analysis & Design as well as good command over cross-browser client side programming using JavaScript & jQuery,.



Awards:



Comments and Discussions

 
GeneralMy vote of 5 Pin
raddevus29-Jan-20 11:21
mvaraddevus29-Jan-20 11:21 
QuestionMerging Sorted Sets Pin
Tim Arheit24-Jan-15 4:23
Tim Arheit24-Jan-15 4:23 
GeneralMy vote of 5 Pin
Dom P29-Jun-10 4:33
Dom P29-Jun-10 4:33 
GeneralRe: My vote of 5 Pin
Samir NIGAM14-Aug-10 6:48
Samir NIGAM14-Aug-10 6:48 
GeneralVery Nice Article Pin
Sandeep Shekhar23-Jun-10 0:33
Sandeep Shekhar23-Jun-10 0:33 
GeneralRe: Very Nice Article Pin
Samir NIGAM23-Jun-10 0:46
Samir NIGAM23-Jun-10 0:46 
GeneralMy vote of 2 Pin
Paulo Zemek22-Jun-10 4:26
mvaPaulo Zemek22-Jun-10 4:26 
GeneralRe: My vote of 2 Pin
Samir NIGAM22-Jun-10 4:43
Samir NIGAM22-Jun-10 4:43 
GeneralRe: My vote of 2 Pin
Paulo Zemek22-Jun-10 7:05
mvaPaulo Zemek22-Jun-10 7:05 
GeneralRe: My vote of 2 Pin
Samir NIGAM22-Jun-10 18:37
Samir NIGAM22-Jun-10 18:37 
Generalanother article Pin
ZEugene17-Jun-10 1:39
ZEugene17-Jun-10 1:39 
GeneralRe: another article Pin
Samir NIGAM22-Jun-10 18:39
Samir NIGAM22-Jun-10 18:39 
GeneralGood article! PinPopular
ricmrodrigues16-Jun-10 1:16
ricmrodrigues16-Jun-10 1:16 
GeneralRe: Good article! Pin
Samir NIGAM16-Jun-10 20:04
Samir NIGAM16-Jun-10 20:04 
GeneralMy vote of 2 Pin
archippus15-Jun-10 3:36
archippus15-Jun-10 3:36 
GeneralRe: My vote of 2 Pin
Samir NIGAM15-Jun-10 23:15
Samir NIGAM15-Jun-10 23:15 
QuestionResponse.write? Pin
urza2310-Jun-10 8:43
urza2310-Jun-10 8:43 
May I ask where does the Response class come from?

I never heard of it before, so it confuses me. Whats the difference from Console.Write(.. ?

Thanks
AnswerRe: Response.write? Pin
Samir NIGAM11-Jun-10 16:39
Samir NIGAM11-Jun-10 16:39 
GeneralNice Pin
Viral Upadhyay9-Jun-10 18:19
Viral Upadhyay9-Jun-10 18:19 
GeneralRe: Nice Pin
Samir NIGAM10-Jun-10 0:36
Samir NIGAM10-Jun-10 0:36 
GeneralTip/Trick Pin
AspDotNetDev9-Jun-10 9:39
protectorAspDotNetDev9-Jun-10 9:39 
GeneralRe: Tip/Trick Pin
Samir NIGAM10-Jun-10 0:37
Samir NIGAM10-Jun-10 0:37 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.