C# SortedDictionary

SortedDictionary keeps its keys always sorted.

It allows you to avoid sorting the keys on your own. Its lookup performance is slower than Dictionary. It has advantages if you require a sorted lookup table in memory.

Benchmark results

Dictionary lookup time:       Close to O(1)
SortedDictionary lookup time: O(log n)     

Example. Here we see the SortedDictionary collection from System.Collections.Generic being used. We add five keys in any order, being careful not to add duplicates. Then we test various keys for their existence.

C# program that uses SortedDictionary

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
	// 1
	// New SortedDictionary
	SortedDictionary<string, int> sort =
	    new SortedDictionary<string, int>();

	// 2
	// Add strings and int keys
	sort.Add("zebra", 5);
	sort.Add("cat", 2);
	sort.Add("dog", 9);
	sort.Add("mouse", 4);
	sort.Add("programmer", 100);

	// 3
	// Example: see if it doesn't contain "dog"
	if (sort.ContainsKey("dog"))
	{
	    Console.WriteLine(true);
	}

	// 4
	// Example: see if it contains "zebra"
	if (sort.ContainsKey("zebra"))
	{
	    Console.WriteLine(true);
	}

	// 5
	// Example: see if it contains "ape"
	Console.WriteLine(sort.ContainsKey("ape"));

	// 6
	// Example: see if it contains "programmer",
	// and if so get the value for "programmer"
	int v;
	if (sort.TryGetValue("programmer", out v))
	{
	    Console.WriteLine(v);
	}

	// 7
	// Example: print SortedDictionary in alphabetic order
	foreach (KeyValuePair<string, int> p in sort)
	{
	    Console.WriteLine("{0} = {1}",
		p.Key,
		p.Value);
	}
    }
}

Output

True
True
False
100

cat = 2
dog = 9
mouse = 4
programmer = 100
zebra = 5

Steps. In part 6 above, we use the TryGetValue method on the SortedDictionary, which is excellent for avoiding another key lookup. If the key exists, TryGetValue returns true and it fills the out parameter.

TryGetValue

Then: In part 7 above, we use the foreach loop on the SortedDictionary variable.

And: This invokes the custom enumerator, which returns a sequence of KeyValuePairs. The keys are always sorted.

Research. Here we review the difference between Dictionary and SortedDictionary. As always, checking the documentation on MSDN is important, even for experts. The difference is stated in terms of performance.

The SortedDictionary(TKey, TValue) generic class is a binary search tree with O(log n) retrieval, where N is the number of elements in the dictionary.

Dictionary Class: MSDN

Uses. In one of my programs, I needed to maintain a frequency table of various string keys. Instead of Dictionary, I decided to use SortedDictionary, so when I needed to print the SortedDictionary to a file, I wouldn't need to sort it again.

Tip: By using SortedDictionary instead of custom Dictionary sorting code, you can reduce the footprint of your .NET program.

Performance. To test the performance of the data structures, I devised a benchmark that looped through various element counts. I tested how long it took to add that many keys, and how long it took to find a key when there are that many keys.

Note: The first row has 10 elements. And then each following row has 10 times more. The times are in milliseconds.

Result: Performance was awful and it degraded when there were more than 10000 elements to the point of failure.

Add element benchmark: SortedDictionary, Dictionary

5,    0
0,    0
1,    0
22,   2
310,  33
3769, 521

ContainsKey benchmark: SortedDictionary, Dictionary

73,   5
132,  6
188,  8
255,  9
340,  9
419,  10

SortedList. There is also a SortedList collection in the System.Collections.Generic namespace. This provides essentially the same functionality as the SortedDictionary but with a different internal implementation.

Note: The SortedList has different performance characteristics, particularly when inserting or removing elements from the collection.

SortedList

Summary. We saw some examples and researched the SortedDictionary collection from System.Collections.Generic at MSDN. We also saw a benchmark of SortedDictionary that shows that it can rapidly degrade performance as the number of elements grows.

Related Links