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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
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
