SortedSet in C#

A SortedSet in C# is a data structure that allows us to store and access elements in sorted order. In this article, we are going to explore how to create and use the SortedSet class in C#. We are also going to look at some of the benefits and drawbacks of using this data structure.

Finally, the article concludes with tips on taking advantage of the C# SortedSet in our applications.

Without further ado, let’s begin!

What Is a SortedSet in C#?

A SortedSet in C# is a collection of unique elements sorted according to their natural ordering or a specified comparator. It allows for fast retrieval of elements and efficient operations on subsets.

The SortedSet<T> class has been available since .NET as part of the System.Collection.Generic namespace.

One notable feature of the SortedSet is its ability to efficiently perform set operations such as union, intersection, and difference, which makes it particularly useful for tasks such as creating a list of unique elements from multiple sets.

SortedSet does not allow null values or permit duplicate elements. Trying to add a duplicate element will not affect the set. 

How to Create a SortedSet in C#?

For most of our examples, we intend to use a SortedSet that contains strings of some of the programming languages used today.

Let’s start by creating an empty SortedSet:

var languages = new SortedSet<string>();

SortedSet Constructor Overloads

We can use these overloads when working with the SortedSet class in C#:

Overload	Description
SortedSet()	We use it to initialize a new instance of the SortedSet class.
SortedSet(IComparer)	Initializes a new SortedSet instance along with a comparer.
SortedSet(IEnumerable)	This overload initializes a new SortedSet instance from elements copied from a specific enumerable collection.
SortedSet(IEnumerable, IComparer)	Creates a new instance of a SortedSet which has elements from an enumerable collection and that uses a specific comparer.
SortedSet(SerializationInfo, StreamingContext)	Initializes a SortedSet instance that contains serialized elements.

To make our article as simple as possible, we are going to implement the first overload, SortedSet() and learn how it works. 

Add Items to a SortedSet

Let’s add a set of programming languages into a SortedSet<string> object:

public SortedSet<string> ProgrammingLanguages() 
{ 
    var languages = new SortedSet<string>(); 

    languages.Add("C"); 
    languages.Add("C++"); 
    languages.Add("C#"); 
    languages.Add("Java"); 
    languages.Add("Scala"); 
    languages.Add("TypeScript"); 
    languages.Add("Python"); 
    languages.Add("JavaScript"); 
    languages.Add("Rust");
    
    return languages;
}

Here, we insert elements into the languages SortedSet by invoking the Add() method.

In some cases, we may want to initialize a  SortedSet directly with values:

var languages = new SortedSet<string> { "C", "C++", "C#", "Java" };

Let’s initialize our SortedSet in the test constructor:

private readonly SortedSetMethods _sortedSet; 
private readonly SortedSet<string> _languages;

public SortedSetInCSharpUnitTests()
{
    _sortedSet = new SortedSetMethods();
    _languages = _sortedSet.ProgrammingLanguages();
}

Next, we can verify that our SortedSet has nine elements and check whether it contains one of the elements (“Java”) and the first element is (“C”):

Assert.IsInstanceOfType(_languages, typeof(SortedSet<string>));
Assert.AreEqual(_languages.Count(), 9);
Assert.IsTrue(_languages.Contains("Java"));
Assert.AreEqual(_languages.First(), "C");

We can successfully prove that _languages is of type SortedSet<string>. We use the inbuilt Count() method to check the number of elements in our SortedSet.

Also, we use the inbuilt Contains() method to check if the SortedSet has a specific element. The method takes the element as a parameter and returns a boolean value indicating whether or not the element is present in the set.

This technique can be helpful for quickly checking if an element exists in the SortedSet without iterating through all of the elements.

Add Duplicate Elements in a SortedSet in C#

A SortedSet does not allow adding duplicate elements. It will not affect the set if we try to add a duplicate element. It uses a hashing structure that ensures that each element can only appear once in the set.

Let’s attempt to add duplicate elements to the _languages SortedSet:

_languages.Add("C");
_languages.Add("C++");
_languages.Add("C#");

Assert.IsInstanceOfType(_languages, typeof(SortedSet<string>));
Assert.AreEqual(_languages.Count(), 9);

When we try to add duplicate values to _languages, its values will not change, as the set already contains those values. Therefore, its count remains nine instead of twelve.

How Does a SortedSet Deal With Object Sorting?

To achieve object sorting in a SortedSet<T> object, the SortedSet<T> class has a SortedSet<T>.Comparer property that ensures all the elements in the object are in the correct order. The property implements the IComparer<T> interface, which compares elements and ensures that the SortedSet<T> elements are in the correct order. 

In our case, the SortedSet<T> class uses the default comparer to ensure that we store our programming languages in the correct order.

Iterate Through a SortedSet in C#

We can iterate through a SortedSet object by using a foreach or a for loop statement.

Let’s invoke the languages SortedSet in our main program and iterate through it:

var sortedSet = new SortedSetMethods();
var programmingLanguages = sortedSet.ProgrammingLanguages();

Console.WriteLine("The SortedSet Contains these elements:");

foreach (var language in programmingLanguages) 
{
    Console.WriteLine(language);
}

After executing the program, we can see that our programming languages are in the correct alphabetic order:

The SortedSet Contains these elements:
C
C#
C++
Java
JavaScript
Python
Rust
Scala
TypeScript

Remove All Elements From a SortedSet in C#

What if we want to remove all the elements in a SortedSet? We can make use of the Clear() inbuilt method.

Let’s verify that the Clear() method removes all elements from the _languages set:

_languages.Clear();

Assert.AreEqual(0, _languages.Count());
Assert.IsNull(_languages.FirstOrDefault());

After invoking the Clear() method, we can prove that we removed all the elements from the _languages set as it has a count of zero.  

Copy SortedSet Elements to an Array

The CopyTo() method copies a part of or the entire SortedSet into a one-dimensional array of the same type. The method has some overloads, which give us an option of copying elements at the beginning of the destination array or from a specific index.

To keep our example simple, let’s copy all the elements in the _languages SortedSet into an array by taking advantage of the CopyTo() method:

var languagesArray = new string[9];

_languages.CopyTo(languagesArray);

Assert.AreEqual(languagesArray.Count(), 9);
Assert.AreEqual(languagesArray[0], "C");
Assert.AreEqual(languagesArray[8], "TypeScript");
Assert.IsNotNull(languagesArray);

Alternatively, we can convert a SortedSet into an array by invoking the ToArray() method:

var languagesArray = _languages.ToArray();

Perform Set Difference Between Two SortedSets in C#

This operation performs a set difference operation between two sets. If we perform a set difference between sets A and B, the operation returns the elements in A that are not present in B.

Let’s understand this concept with another example:

var moreLanguages = new SortedSet<string> { "C", "C++", "C#", "Java", "Scala", "Assembly", 
                    "Pascal", "HTML", "CSS", "PHP" };

_languages.ExceptWith(moreLanguages);

Assert.AreEqual(_languages.Count(), 4);
Assert.IsTrue(_languages.Contains("TypeScript"));
Assert.IsTrue(_languages.Contains("Python"));
Assert.IsTrue(_languages.Contains("JavaScript"));
Assert.IsTrue(_languages.Contains("Rust"));
Assert.IsFalse(_languages.Contains("Assembly"));

The ExceptWith() method returns the elements that are in _languages but not in moreLanguages, which are: “TypeScript”, “Python”, “JavaScript” and “Rust”. 

Find Common Elements Between Two SortedSets

An intersection between sets A and B entails finding the common elements. To accomplish such an operation in C#, we use the inbuilt IntersetWith() method. 

Let’s understand how to perform an intersection operation with an example:

var moreLanguages = new SortedSet<string> { "C", "C++", "C#", "Java", "Scala", "Assembly", 
                    "Pascal", "HTML", "CSS", "PHP" };

_languages.IntersectWith(moreLanguages);

Assert.AreEqual(_languages.Count(), 5);
Assert.IsTrue(_languages.Contains("C"));
Assert.IsTrue(_languages.Contains("C++"));
Assert.IsTrue(_languages.Contains("C#"));
Assert.IsTrue(_languages.Contains("Java"));
Assert.IsTrue(_languages.Contains("Scala"));
Assert.IsFalse(_languages.Contains("Assembly"));

Here, the IntersectWith() method modifies the _languages SortedSet by retaining the elements that are common in both _languages and moreLanguages sets. 

How to Check A SortedSet Is a Subset of Another

When we want to check whether a SortedSet instance is a proper subset of another SortedSet instance, we use the IsProperSubsetOf() method. Likewise, we can use the IsProperSupersetOf() method to determine if a SortedSet is a superset of another SortedSet.

Let’s put this theory into practice:

var moreLanguages = new SortedSet<string> {"C", "C++", "C#", "Java", "Scala", "TypeScript", 
                    "Python", "JavaScript", "Rust", "Assembly", "Pascal"};

Assert.IsTrue(_languages.IsSubsetOf(moreLanguages));
Assert.IsTrue(_languages.IsProperSubsetOf(moreLanguages));
Assert.IsTrue(moreLanguages.IsSupersetOf(_languages));
Assert.IsTrue(moreLanguages.IsProperSupersetOf(_languages));

We create a larger set moreLanguages that contains more elements, including all the elements in the _languages set. Therefore, _languages is a proper subset of moreLanguages and the latter is the proper superset of the former. 

So, what’s the difference between a proper subset and a normal one? 

In set theory, a subset is a collection of elements within another set. A proper subset, also known as a strictly smaller subset, is a subset that contains strictly fewer elements than the larger set. 
A proper subset will always have fewer elements than the larger set, which may not be true for a subset. For example, if we have the set A = {1, 2, 3}, B = {1, 2} is a proper subset because it contains strictly fewer elements than A. On the other hand, C = {1, 2, 3} would not be considered a proper subset because it has the same number of elements as A.

Determine Whether Two SortedSets Overlap

In some situations, we may want to check whether two SortedSet objects share common elements without evaluating whether they are equal. That’s where we can take advantage of the Overlaps() method to achieve our objective:

var commonLanguages = new SortedSet<string> { "C", "C++", "C#", "Java", "Scala", "TypeScript", 
                      "Python", "JavaScript", "Rust", "Assembly", "Pascal" };
var differentLanguages = new SortedSet<string> { "Assembly", "Pascal", "HTML", "CSS", "PHP" };

Assert.IsTrue(commonLanguages.Overlaps(_languages));
Assert.IsTrue(differentLanguages.Overlaps(commonLanguages));
Assert.IsFalse(differentLanguages.Overlaps(_languages));

We can see that the commonLanguages and _languages SortedSets have common elements. The same case applies to differentLanguages and commonLanguages. However, differentLanguages and languages do not have overlapping elements. 

Remove a Particular Element From a SortedSet

To remove an item from the SortedSet, we can use the Remove() method. Like the Add() method, it takes the object as a parameter and removes it from the SortedSet.

Let’s put our knowledge into practice: 

public SortedSet<string> RemoveElement(SortedSet<string> sortedSet, string valueToRemove) 
{
    _sortedSet.Remove(valueToRemove);

    return sortedSet;
}

Here, the RemoveElement() method takes a SortedSet<string> and a string as parameters and uses the Remove() method to remove an element before returning the updated SortedSet. 

Next, we can verify that our new method successfully removes elements:

var elementToRemove = "Java";

var updatedLanguages = _sortedSet.RemoveElement(_languages, elementToRemove);

Assert.IsFalse(updatedLanguages.Contains(elementToRemove));
Assert.AreEqual(_languages.Count(), 8);

We invoke the RemoveElement() method and pass our SortedSet, and a string (“Java”), which we can prove is removed as the updated SortedSet does not contain that value, and its count decreases by one. 

Remove Elements From a SortedSet Through Predicates

Besides using the inbuilt Remove() method, we can use the RemoveWhere() method that takes a predicate as a parameter to set conditions that determine whether we remove an element. To illustrate this concept, let’s modify our _languages SortedSet to remove programming languages that start with a specific character:

_languages.RemoveWhere(element => element.StartsWith("C"));
Assert.IsFalse(_languages.Contains("C"));
Assert.IsFalse(_languages.Contains("C++"));
Assert.IsFalse(_languages.Contains("C#"));

We can verify that the RemoveWhere() method removes all elements starting with the letter ‘C.’

Reverse Elements of a SortedSet in C#

In some cases, we may want to reverse the order of the elements we have in a SortedSet. We can take advantage of the inbuilt Reverse() method to achieve our goal. The method returns an IEnumerable<T> object, which iterates over the SortedSet in reverse order. 

Let’s illustrate how the Reverse() method works:

var reversedSet = _languages.Reverse();
var firstElement = reversedSet.First();
var lastElement = reversedSet.Last();

Assert.IsInstanceOfType(reversedSet, typeof(IEnumerable<string>));
Assert.AreEqual(firstElement, "TypeScript");
Assert.AreEqual(lastElement, "C");

We can prove that we get an IEnumerable<string> object, which iterates over the _languages SortedSet in reverse order. 

How to Check if Two SortedSets Are Equal in C#

In some cases, we may want to compare whether the current SortedSet and another collection contain the same elements. We can use the SetEquals() method to achieve our goal:

var moreLanguages = new SortedSet<string> { "Assembly", "Pascal", "HTML", "CSS", "PHP" };
var languagesCopy = _languages;

Assert.IsFalse(_languages.SetEquals(moreLanguages));
Assert.IsTrue(_languages.SetEquals(languagesCopy));

The moreLanguages object is not equal to the _languages object, so we expect the SetEquals() operation to return false.

Store Unique Elements From Two SortedSets

Sometimes, we may want to modify a SortedSet to store unique elements between two sets. That’s where the SymmetricExceptWith() method comes into play, as we can use it to accomplish our purpose.

Let’s look at using the SymmetricExceptWith() method:

var moreLanguages = new SortedSet<string> { "Assembly", "Pascal", "HTML", "CSS", "PHP" };

_languages.SymmetricExceptWith(moreLanguages);

Assert.AreEqual(_languages.Count(), 14);

The SymmetricExceptWith() method modifies the _languages SortedSet to make it have unique elements from both itself and moreLanguages SortedSet. Therefore, since both sets have unique values, the modified _languages SortedSet now contains fourteen elements. 

How to Search for an Element in a SortedSet in C#

Besides using the inbuilt Contains() method to check whether a SortedSet contains a specific value, we can use the inbuilt TryGetValue (T equalVal, out T actualVal) technique to achieve the same result. The method takes two parameters, the first being the value to search for and the next being what the search finds or the default value when the search doesn’t yield any results. 

Let’s put this theory into practice:

Assert.IsTrue(_languages.TryGetValue("C#", out _));
Assert.IsTrue(_languages.Contains("C#"));
Assert.IsFalse(_languages.TryGetValue("Assembly", out _));
Assert.IsFalse(_languages.Contains("Assembly"));

Here, _languages does not contain “Assembly” but contains “C#” and uses the discard operator to ignore the TryGetValue() method’s return value.  

Perform a Union Between Two SortedSets

When we want to join two sets, we perform a union operation. For example, when we want to perform a union between two sets, A and B, we copy the elements in set B over into set A. 

Let’s perform a UnionWith() operation between _languages and moreLanguages SortedSet to illustrate this concept:

var moreLanguages = new SortedSet<string> { "Assembly", "Pascal", "HTML", "CSS", "PHP" };

_languages.UnionWith(moreLanguages);
Assert.AreEqual(_languages.Count(), 14);

The UnionWith() method copies the elements in moreLanguages SortedSet into the _languages SortedSet hence, the latter now has fourteen elements instead of nine. 

Benefits of Using a SortedSet in C#

First, SortedSet objects facilitate quick insertion and retrieval operations as they have a constant access time of O(1).

Also, we can use the SortedSet class in applications that do not allow duplicate elements, which helps us eliminate data redundancy.

A SortedSet can quickly check if an element is present in the set without iterating through all elements and returns elements in a specific order. 

Overall, a SortedSet in C# can significantly aid in managing and manipulating sorted collections of unique elements.

Drawbacks of Using a SortedSet in C#

Using the SortedSet may not be suitable for all situations where we need to store null values or duplicate elements.

Additionally, the performance benefits of using a SortedSet may not be significant in small collections.

In some cases, accessing and manipulating elements by their index may also be necessary rather than simply iterating through them in sorted order. Another collection type, such as a list, may be more appropriate in such cases.

Overall, it is crucial to carefully evaluate whether the restrictions and advantages of using a SortedSet are suitable for a given situation before implementing it in C# code.

SortedSets vs SortedLists

One similarity between a SortedSet and a SortedList in C# is that both data structures maintain their elements in sorted order. However, a SortedSet does not allow duplicate elements, unlike a SortedList. In addition, a SortedSet has faster insertion and removal times than a SortedList, as the latter internally uses an array structure, which requires shifting elements around during insertion and removal.

Conclusion

SortedSet in C# provides a valuable tool for managing and manipulating sorted collections of unique elements. However, it is essential to carefully consider whether its restrictions and advantages make it suitable for a specific situation before implementing it in code. If you enjoyed this article, feel free to check out our article on a similar topic, HashSet in C#.