Click here to Skip to main content
Click here to Skip to main content

SortedSet Collection Class in .NET 4.0

, 22 Jun 2010 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

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.

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)

Share

About the Author

Samir NIGAM
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

 
Generalanother article PinmemberMember 303586517-Jun-10 1:39 
GeneralRe: another article PinmemberSamir NIGAM22-Jun-10 18:39 

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

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

| Advertise | Privacy | Terms of Use | Mobile
Web03 | 2.8.141030.1 | Last Updated 23 Jun 2010
Article Copyright 2010 by Samir NIGAM
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid