SortedDictionary

This C# type keeps its keys always sorted. It allows you to avoid sorting the keys on your own. Its lookup performance is slower than Dictionary.

SortedDictionary has advantages if you require a sorted lookup table in memory. Usually, a default Dictionary type is simpler and faster.

Example

Here we see the SortedDictionary collection from System.Collections.Generic being used. We add 5 keys in any order, being careful not to add duplicates.

using System;
using System.Collections.Generic;

var sort = new SortedDictionary<string, int>();

// 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);

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

// See if it contains "zebra."
if (sort.ContainsKey("zebra"))
{
    Console.WriteLine(true);
}

// See if it contains "ape."
Console.WriteLine(sort.ContainsKey("ape"));

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

// Print SortedDictionary in alphabetic order.
foreach (KeyValuePair<string, int> p in sort)
{
    Console.WriteLine("{0} = {1}", p.Key, p.Value);
}
True
True
False
100
cat = 2
dog = 9
mouse = 4
programmer = 100
zebra = 5

Some research

Here we review the difference between Dictionary and SortedDictionary. The difference is stated in terms of performance.

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

Performance

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.

5,    0
0,    0
1,    0
22,   2
310,  33
3769, 521
73,   5
132,  6
188,  8
255,  9
340,  9
419,  10

Usage notes

In one of my programs, I needed to maintain a frequency table of various string keys. Instead of Dictionary, I decided to use SortedDictionary.

We used the SortedDictionary collection. SortedDictionary can rapidly degrade performance as the number of elements grows.