.Net Sorted Dictionary

Intro

Have you ever sat around and thought to yourself "Gee, I sure could use a list that has an identifier of some sort associated with an object of some sort!". You find the Dictionary class, bust out some code, and you're a happy camper. A month later your customer tells you "Hey lazy coder-boy, your code's too slow!". You dig into things and with a little bit of that special coder magic you find out that putting items in the Dictionary is fine, but reading items from the Dictionary is super-slow! You've got an integer Key and a TWidget (class/object) Value. So now you think to yourself "Gee, I sure wish that Dictionary was faster at finding random Keys!". Well golly folks, I've got a solution for you! SortedDictionary.

Usage

According to MSDN, a SortedDictionary "Represents a collection of key/value pairs that are sorted on the key.". Sorting is great at solving the aforementioned problem of slow seeks/scans, or at least it is in combination with a sorted-list-optimized search algorithm. SortedDictionary gives you automatic sorting and the usage of optimized search algorithms to find your data. If you've ever coded a bubble sort, quick sort, binary search, or one of the other array of searching/sorting algorithms, you'll feel blessed that the .Net framework has already done the plumbing for you. Let's look at a simple sample:

        private void SortedDict()
        {
            var dict = new SortedDictionary<int, string>();
            dict.Add(1234, "hi!");
            dict.Add(4321, "yo!");
            dict.Add(9876, "werd!");
            string value;
            if (dict.TryGetValue(1234, out value))
            {
                //hey, we found the value! alert the media!
            }
        }

This method creates a simple SortedDictionary whose key will be an int and whose value is a string. It then adds the values to the dictionary and attempts to find the specified value in the dictionary. For such a small sampling of data, you aren't likely to gain anything by using a SortedDictionary. There's not set cutoff point, but I don't bother optimizing until I need to for performance reasons and until I have at least 1k items in the list. I was recently working with a list of 500k items and switching from Dictionary to SortedDictionary sped things up by a factor of nearly 10! YMMV.

What's Next?

Tidwell wrote a blog for you guys on the ITCProgBlog just a day or two ago about the basic Dictionary class. This blog here told you about SortedDictionary. There's also a ConcurrentDictionary you could go read about if you like, it'll help you when you get into threading. You could also just write your own samples, and perhaps pontificate presciently on your next project requiring performant code. (ie think of ways to a SortedDictionary in your real-life projects).

Resources

SortedDictionary