How to use SortedDictionary, SortedList, and SortedSet in C#

SortedDictionary, SortedList, and SortedSet are collection classes that store key-value pairs and can be sorted based on the keys. A SortedSet is a collection that is maintained in sorted order. A SortedList is a collection that lets you retrieve the keys and/or values using indexes. A SortedDictionary lacks indexes but offers faster insertion and removal of unsorted data than a SortedList.

This article talks about SortedDictionary, SortedList, and SortedSet, how they differ, and how we can work with them in C#. To work with the code examples provided in this article, you should have Visual Studio 2019 installed in your system. If you don’t already have a copy, you can download Visual Studio 2019 here.

Create a .NET Core console application project in Visual Studio

First off, let’s create a .NET Core console application project in Visual Studio. Assuming Visual Studio 2019 is installed in your system, follow the steps outlined below to create a new .NET Core console application project in Visual Studio.

1. Launch the Visual Studio IDE.
2. Click on “Create new project.”
3. In the “Create new project” window, select “Console App (.NET Core)” from the list of templates displayed.
4. Click Next.
5. In the “Configure your new project” window shown next, specify the name and location for the new project.
6. Click Create.

We’ll use this project to work with SortedDictionary, SortedList, and SortedSet in the subsequent sections of this article.

Use the SortedSet class in C#

The SortedSet class pertaining to the System.Collections.Generic namespace represents a generic collection of objects present in sorted order. It provides support for mathematical operations (intersection, union, etc.) and it is a dynamic collection, meaning that the size of an object of this collection will grow or shrink as you add and remove elements.

A SortedSet contains only unique elements and is used to store data in a collection that needs to be in sorted order. By default, the elements of a SortedSet are in ascending order. The SortedSet class implements the following interfaces:

• IReadOnlyCollection
• IDeserializationCallBack
• IEnumerable
• ISet
• ISerializable

The number of elements that you can store in an instance of a SortedSet is known as its capacity. The following code snippet illustrates how you can create a SortedSet of integers and store values into it.

SortedSet<int> sortedIntegers = new SortedSet<int>();
sortedIntegers.Add(1);
sortedIntegers.Add(5);
sortedIntegers.Add(3);
sortedIntegers.Add(2);
sortedIntegers.Add(4);

The following code snippet shows how you can retrieve the elements of the SortedSet.

foreach (var x in sortedIntegers)
{
    Console.WriteLine(x);
}

Here’s the complete code listing for your reference:

static void Main(string[] args) {
      SortedSet < int > sortedIntegers = new SortedSet < int > ();
      sortedIntegers.Add(1);
      sortedIntegers.Add(5);
      sortedIntegers.Add(3);
      sortedIntegers.Add(2);
      sortedIntegers.Add(4);

      foreach(var x in sortedIntegers) {
            Console.WriteLine(x);
      }
      Console.Read();
}

When you execute the above program, the integers will be displayed in ascending order at the console window as shown in Figure 1:

IDG

The following code snippet shows how you can store strings in a SortedSet of strings and then display them at the console window.

SortedSet<string> sortedStrings = new SortedSet<string>();
sortedStrings.Add("India");
sortedStrings.Add("USA");
sortedStrings.Add("England");
sortedStrings.Add("Australia");
sortedStrings.Add("New Zealand");
foreach (string str in sortedStrings)
{
   Console.WriteLine(str);
}

When you execute the above program, the names of the countries will be displayed at the console window in ascending order as shown in Figure 2:

IDG

Use the SortedList class in C#

A SortedList represents a collection of objects stored as key-value pairs that are sorted by the keys. You can find both a generic and a non-generic version of a SortedList. While the generic version is defined in the System.Collections.Generic namespace, the non-generic version is defined in the System.Collections namespace.

Objects in a SortedList are accessible by using their keys or indexes. The keys in a SortedList must be unique and cannot be null.

While a SortedDictionary is implemented using a red-black binary search tree, a SortedList is implemented using two internal arrays — one array for the keys and one for the values. A SortedList consumes less memory than a SortedDictionary and offers faster, indexed retrieval of keys and values. However, a SortedDictionary provides faster insertion and removal operations than a SortedList, taking O(log n) versus O(n) for a SortedList.

The following code snippet illustrates how you can store data in a SortedList and then retrieve and display the data at the console window.

SortedList<int,string> authorList = new SortedList<int, string>();
authorList.Add(1, "Joydip");
authorList.Add(3, "Steve");
authorList.Add(2, "Michael");
foreach (KeyValuePair<int, string> pair in authorList)
{
    Console.WriteLine("Key: {0}tValue: {1}", pair.Key, pair.Value);
}

When you execute the above program, the output should appear at the console window as shown in Figure 3:

IDG

Use the SortedDictionary class in C#

SortedDictionary represents a collection of KeyValuePair. As noted above, SortedDictionary is implemented as a red-black tree. While inserting and deleting elements from a SortedDictionary takes O(log n) time, a SortedList takes O(n) time for the same operations. Like a SortedList, a SortedDictionary is sorted based on the key.

The following code snippet shows how you can store items in a SortedDictionary and then retrieve and display them at the console window.

SortedDictionary<int, int> keyValuePairs  = new SortedDictionary<int, int>();
keyValuePairs.Add(1, 100);
keyValuePairs.Add(5, 500);
keyValuePairs.Add(3, 300);
keyValuePairs.Add(4, 400);
keyValuePairs.Add(2, 200);
foreach (KeyValuePair<int, int> pair in keyValuePairs)
{
    Console.WriteLine("Key: {0}tValue: {1}", pair.Key, pair.Value);
}

When you execute the above program, the output should appear as shown in Figure 4:

IDG

Regardless of where in the collection you’re adding or removing items, insertion and removal operations in a SortedDictionary take O(log n). Adding or removing items at the end of a SortedList likewise take O(log n)—but only at the end of the list.

If you need to access items using an index or populate sorted data all at once in the collection, you might use a SortedList. If minimizing memory overhead is important and you need more lookups and fewer insert and delete operations, you might opt for a SortedList. A SortedDictionary is a good choice if you will be adding unsorted data. It is also a good option if you plan to add and remove unsorted items from the collection randomly, and memory is not a constraint.

How to do more in C#:

• How to use Parallel.For and Parallel.ForEach in C#
• How to avoid GC pressure in C# and .NET
• How to use target typing and covariant returns in C# 9
• How to use top-level programs in C# 9
• How to use pattern matching in C#
• How to work with read-only collections in C#
• How to work with static anonymous functions in C# 9
• How to work with record types in C#
• How to use implicit and explicit operators in C#
• Singleton vs. static classes in C#
• How to log data to the Windows Event Log in C#
• How to use ArrayPool and MemoryPool in C#
• How to use the Buffer class in C#
• How to use HashSet in C#
• How to use named and optional parameters in C#
• How to benchmark C# code using BenchmarkDotNet