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 required a sorted lookup table in memory.

Benchmark results

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

This C# article looks into the SortedDictionary collection. It has a benchmark.

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.

Program that uses SortedDictionary [C#]

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.

Next steps. In part 7 above, we use the foreach loop on the SortedDictionary variable. This invokes the custom enumerator on the SortedDictionary class, which returns a sequence of KeyValuePairs. The keys are always sorted.

SortedDictionary collection

Here we review the difference between Dictionary and SortedDictionary. As always, checking the documentation on MSDN is important, even for experts. MSDN states that "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."

Uses

In one of my programs, I needed to maintain a frequency table of various string keys used. 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.

By using SortedDictionary instead of custom Dictionary sorting code, you can reduce the footprint, code size, of your .NET program. This also reduces the chance of bugs creeping into your custom code.

Requirements: Maintain key/value pairs that must be displayed. Must be printed. Must be written to disk. Consider: SortedDictionary

Requirements: Maintain key/value pairs that are stored internally. Not meant to be displayed. Consider: Dictionary

Requirement: Optimization and performance. Use: Dictionary

Benchmark

To test the performance of the data structures, I devised a benchmark that looped through 10, 100, 1000, 10000, 100000, and finally 1000000 elements. 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.

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

Note: First row has 10 elements, then each following row has 10 times more. Times in ms.

Results. Performance was awful and it degraded when there were more than 10000 elements to the point of failure. The Add method was consistently slower in all tests.

SortedList class

There is also a SortedList collection in the System.Collections.Generic namespace, which provides essentially the same functionality as the SortedDictionary but with a different internal implementation. The SortedList has different performance characteristics, particularly when inserting or removing elements from the collection.

Summary

We saw some examples and researched the SortedDictionary collection from System.Collections.Generic at MSDN, using the C# programming language and the .NET Framework. Further, we saw a benchmark of SortedDictionary that shows that it can rapidly degrade performance as the number of elements grows.