Sorted Dictionary is just a normal Dictionary data structure, but with its keys sorted. Of course, it is obvious that having its elements sorted will make this data structure slightly slower than a normal Dictionary, but it does offer the advantage of making an in memory sorted lookup very easy.
To better understand how a Sorted Dictionary works, let’s create a code where we will add a few elements in random order, and then we will lookup some of the keys:
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Create a new SortedDictionary
SortedDictionary<string, int> sortedDictionary = new SortedDictionary<string, int>();
// Add some elements, in random order
sortedDictionary.Add("zebra", 5);
sortedDictionary.Add("cat", 2);
sortedDictionary.Add("dog", 9);
sortedDictionary.Add("mouse", 4);
sortedDictionary.Add("programmer", 100);
// Check if dictionary contains "dog" key
if (sortedDictionary.ContainsKey("dog"))
Console.WriteLine(true);
// See if it contains "zebra"
if (sortedDictionary.ContainsKey("zebra"))
Console.WriteLine(true);
// Example: see if it contains "ape"
Console.WriteLine(sortedDictionary.ContainsKey("ape"));
// Example: see if it contains "programmer", and if so get the value for "programmer"
int v;
if (sortedDictionary.TryGetValue("programmer", out v))
Console.WriteLine(v);
// Example: print SortedDictionary elements in alphabetic order
foreach (KeyValuePair<string, int> p in sortedDictionary)
Console.WriteLine("{0} = {1}", p.Key, p.Value);
}
}
The output code will look like this:
In the code above, we used the TryGetValue() method, which spared us of using another instruction, bu first checking if the key exists, and then assigning its value to the v variable, when this element was found. Finally, we used a foreach loop to iterate through the elements of the sorted dictionary.
Be aware that the performance of Sorted Dictionary degrades rapidly when we start adding a lot of elements.
Note that 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. The SortedList has different performance characteristics, particularly when inserting or removing elements from the collection.
Tags: data structures, sorted dictionary
