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.

Some notes

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

An 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.

A summary

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