TheDeveloperBlog.com


C# SortedSet Examples

SortedSet is an ordered set collection. We have many elements and want to store them in a sorted order and also eliminate all duplicates from the data structure. The SortedSet is part of the System.Collections.Generic namespace.


Add, remove. First, this program creates a new, empty SortedSet instance upon the managed heap. Then it adds four elements to the set with the Add method. Next it removes one element with Remove.

Finally: It uses the SortedSet instance in the foreach-loop construct to loop through all the elements. They are stored alphabetically.

C# program that adds and removes elements

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// Created sorted set of strings.
	SortedSet<string> set = new SortedSet<string>();

	// Add four elements.
	set.Add("perls");
	set.Add("net");
	set.Add("dot");
	set.Add("sam");

	// Remove an element.
	set.Remove("sam");

	// Print elements in set.
	foreach (string val in set) // <-- Alphabetical order.
	{
	    Console.WriteLine(val);
	}
    }
}

Output

dot
net
perls


SortedSet from List. 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 by calling the SortedSet constructor and passing the original collection reference to it.

List

Notice: In the example, the duplicate element ("perls") is only present once in the SortedSet.

C# program that uses SortedSet constructor

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// Create list with elements.
	List<string> list = new List<string>();
	list.Add("sam");
	list.Add("allen");
	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);
	}
    }
}

Output

allen
perls
sam


RemoveWhere. Sometimes you may need to remove all elements from your SortedSet that match a certain condition. You can invoke the RemoveWhere method, with a predicate function argument, to elegantly do this.

In this example, four names are added to the SortedSet that start with the letter s. We then call the RemoveWhere method with a lambda function that is used as a predicate condition. When the method returns true, the element is removed.

LambdasPredicate
C# program that uses RemoveWhere method

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// 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);
	}
    }
}

Output

mark


Add return value. With the SortedSet collection, you 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.

If it returns true, a new element was added. If it returns false, the element already existed in the set and was not added again. No exceptions are thrown if the element already exists.

C# program that checks result of Add

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// 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);
    }
}

Output

True False False True


Count, Clear. As with other collections in the .NET Framework, you can use the Count property and the Clear() method on the SortedSet type. Please notice that the Count property can only be read, not assigned to.

Tip: After the Clear() method is called, the Count property will always return zero.

C# program that uses Count and Clear

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("a"); // Not successful.

	Console.WriteLine(set.Count);
	set.Clear();
	Console.WriteLine(set.Count);
    }
}

Output

2
0


UnionWith 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. The UnionWith method adds all the elements into one collection.

And: No duplicates will be found in the SortedSet after the UnionWith method is called.

C# program that uses UnionWith method

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");

	// Union the two collections.
	set.UnionWith(list);

	// Enumerate.
	foreach (string val in set)
	{
	    Console.WriteLine(val);
	}
    }
}

Output

a
x
y
z

SymmetricExceptWith. This method returns all the elements in the two collections that are found in only one collection—not both collections. So if both contain the letter A, then SymmetricExceptWith will remove the letter A from the SortedSet instance.

Note: The SymmetricExceptWith method modifies the SortedSet in-place. You do not need to copy the variable reference.

C# that calls SymmetricExceptWith

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 val in set)
	{
	    Console.WriteLine(val);
	}
    }
}

Output

x
y
z

ExceptWith removes all the elements found in the selected collection from the SortedSet instance. The resulting SortedSet will contain all its original elements except those that were found in the other collection.

Tip: This essentially gives you a way to subtract another collection's elements from the SortedSet.

C# that demonstrates ExceptWith

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("x");

	// Call ExceptWith to remove elements.
	set.ExceptWith(list);

	// Display elements.
	foreach (string val in set)
	{
	    Console.WriteLine(val);
	}
    }
}

Output

z

Overlaps returns a boolean that tells us whether the target collection has any elements in common with the SortedSet. Even if only one element is found in common, the result is True. If no elements are in common, the result is False.

C# that uses Overlaps method

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");

	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);
    }
}

Output

True
False

IntersectWith changes the set instance so that it contains only the elements that were present in both collections. This means the IntersectWith method will always yield a SortedSet that has an equal number or fewer elements than before.

C# that calls IntersectWith method

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 list = new List<string>();
	list.Add("a");
	list.Add("x");

	// Compute intersection.
	set.IntersectWith(list);

	// Enumerate.
	foreach (string val in set)
	{
	    Console.WriteLine(val);
	}
    }
}

Output

a
x

Min, Max. The SortedSet contains elements that are stored in ascending sorted order. This makes it trivial for the set to compute its lowest and highest (Min and Max) element values. It simply returns the first or last elements.

Also: You cannot use an indexer with the SortedSet, so these properties are useful.

C# that demonstrates Min and Max properties

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// 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);
    }
}

Output

a
z

Subsets, supersets. SortedSet has methods to compute subsets and supersets. These are IsSubsetOf, IsSupersetOf, IsProperSubsetOf and IsProperSupersetOf. A subset is contained entirely inside another set. A superset contains entirely another set.

Proper subsets and proper supersets are the same as regular ones except they cannot have the same number of elements. They must have at least one fewer. Please visit the Wolfram link for information on set theory and proper subsets.

Proper Subset
C# that uses IsSubsetOf, IsSupersetOf

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));
    }
}

Output

IsProperSubsetOf: False
IsSubsetOf: True
IsProperSubsetOf: True
IsSubsetOf: True
IsProperSupersetOf: True
IsSupersetOf: True

SetEquals. How can you determine if another collection contains the same elements? You can use the SetEquals method. In my testing, I found that the SetEquals method treats the second collection as though it has no duplicate elements.

Note: If duplicate elements are present, the two collections may still be considered equal.

C# that demonstrates SetEquals method

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	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 two collections contain the same elements.
	bool a = set.SetEquals(list);
	Console.WriteLine(a);
    }
}

Output

True

GetViewBetween. How can you see what elements a SortedSet instance contains between and including two values? You can use the GetViewBetween method with two arguments: the minimum value, and the maximum value.

Then: You can loop over the SortedSet that is returned in a foreach-loop, or do further operations as needed.

C# that calls GetViewBetween method

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 val in view)
	{
	    Console.WriteLine(val);
	}
    }
}

Output

4
5
7

Contains. If you need to determine if your SortedSet has a certain element in it, you could use a foreach-loop and imperatively scan all the elements. However, the Contains method is often more effective. It is shorter and less prone to errors.

C# that demonstrates Contains method

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	var set = new SortedSet<int>();
	set.Add(8);
	set.Add(7);
	set.Add(8);
	set.Add(9);
	set.Add(3);

	// Use Contains method.
	bool a = set.Contains(9);
	Console.WriteLine(a);
    }
}

Output

True

Reverse. When you add elements to your SortedSet, they are automatically stored in ascending order: lowest to highest values. However, you can call the Reverse method to return the elements in the opposite, reverse order.

And: If you want to loop over your SortedSet from highest to lowest (reverse alphabetical order), you can call Reverse in a foreach-loop.

C# that uses Reverse method on SortedSet

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	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();
    }
}

Output

3 7 8 9
9 8 7 3

Performance. Is the SortedSet collection efficient? This depends of course on your program. However, the SortedSet does not include hashing, meaning that it has to do linear searches for lookups.

Therefore: The SortedSet is much slower than the HashSet for most cases where you need to do lookups.

Internally, the SortedSet is implemented as a tree with a Root node, and a Left and Right node on every node instance. Every node will need to be allocated on the managed heap. This impacts performance in a negative way.

So: For most programs a hashing mechanism (such as that found in Dictionary and HashSet) is superior for performance.

Dictionary

Summary. The SortedSet collection provides a variety of useful functionality. In some cases, it can replace confusing, custom types with a simple type directly from the .NET Framework. This reduces program complexity and minimizes bugs.

Thus: SortedSet represents an interesting combination of the HashSet and the SortedList collections.

HashSetSortedList