Sorted Data Structure in C#: An Introduction to SortedDictionary, SortedList, and SortedSet

Data structures like Heap, PriorityQueue, and TreeSet, etc. that are able to maintain ordered state are very useful in many scenarios, especially for some complicated cases. Even though C# does not provide implementation of these data structures, it provides excellent alternatives. In this tutorial, I would like to introduce three sorted data structures in C# as well as show how to implement custom Comparer for these sorted data structures.

SortedDictionary

SortedDictionary<TKey, TValue> is a collection of KeyValuePair<TKey, TValue> that maintain sorted state on the key. Like normal data structure Dictionary in C#, it shares some common methods with Dictionary including:

1. Add(TKey, TValue)
2. ContainsKey(TKey)
3. ContainsValue(TValue)
4. Remove(TKey)

The key difference is that, rather than implemented using hashing function, to maintain ordered state, SortedDictionary is based on Binary Search Tree. As a result, operations of both insertion and removal take O(log n).

By default, SortedDictionary sorts KeyValuePairs on the key in ascending. SortedDictionary supports custom comparer on the key as well. In the following implementation of comparer, it sorts KeyValuePairs on the key in descending.

In the following lines of code, I created a demo to verify SortedDictionary.

SortedList

SortedList here is a data structure much more similar with SortedDictionary rather than a list, which is a collection of KeyValuePairs that in order on the key. Similarly, just like data structure Dictionary, SortedList provides some common methods like Dictionary:

1. Add(TKey, TValue)
2. ContainsKey(TKey)
3. ContainsValue(TValue)
4. Remove(TKey)

SortedList provides O(log n) time complexity for KeyValuePair retrieval. Unlike SortedDictionary that is implemented with Binary Search Tree, SortedList is implemented with two internal arrays for keys and values. Therefore, insertion operation and removal operation take O(n), which are slower than SortedDictionary.

So what are the differences between SortedList and SortedDictionary? There is a list:

1. SortedDictionary is implemented with Binary Search Tree, while SortedList is implemented with two internal arrays for keys and values, respectively.
2. SortedList is more memory-efficient than SortedDictionary, and SortedList is faster than SortedDictionary when it needs to go through all items at once.
3. SortedDictionary takes O(log n) time to insert and remove items, while SortedList takes O(n) time for the same operations.
4. Both SortedDictionary and SortedList are sorted on the key.

SortedList supports custom comparer as well, and following an implementation of comparer for SortedList on the key.

In the following sample code, I created a demo to verify SortedList.

SortedSet

Like a HashSet in C#, SortedSet is a collection of unique objects but maintained in order. It provides some common methods like with O(1) time complexity:

1. Add(T)
2. Remove(T)
3. Contains(T)

SortedSet provides two most important properties: Min and Max, which can be used to track the maximum and minimum in SortedSet easily.

Another important method is GetViewBetween(T1, T2), which will return a subset of SortedSet between object T1 and T2, inclusively.

To verify the functionalities of SortedSet, in this demo, I created a Pair class with Key and Value properties. And I created a custom comparer so that SortedSet can sort the Pair objects in order of Key, and then Value. The code sample is as below:

Pair class

Generally speaking, like SortedDictionary and SortedList, SortedSet doesn’t allow duplicate keys by default as well. That’s only to say, assume we have two objects Pair(6,3) and Pair(6,7) in SortedSet, then if we use default Comparer (which means no comparer specified) or if we just compare the Key in Pair in Comparer, then we would get error behaviour with Adding and Removing operations in SortedSet. Therefore, if we want to have Pairs with duplicate Key, then we need to specify what to do when the Keys are the same in two Pair objects. A sample comparer class is as below, and as demonstrated in the Sample code below, it works fine as desired.

PairComparer class

And finally, I verified the SortedSet with above two classes:

SortedSet Demo

Thank you for your time!

Reference:

1. Source code of this demo can be found at my personal github: https://github.com/doctral/Medium-Sorted-Data-Structure.git