July 24, 2009 6 Comments
Writing for OS/X or the iPhone? Using NSDictionary to store and access key-value pairs? Ever tried to enumerate them all only to find they come back in some random order?
That’s where I was several precious weeks ago. Of course you could get all the keys and all the values and then sort them all. But that takes CPU cycles, and is wasteful, especially if you have to re-sort after adding just a handful of items.
There are two popular classes of data structures used for implementing dictionaries. Hash tables are optimized for extremely fast gets, inserts and deletions, as long as you’re not changing the number of entries in the dictionary too dramatically. If you do, performance starts dropping, and the hash table has to be resized, the memory reallocated, and the content copied — a costly operation. As for sort order — there isn’t any. The order of elements in the hash table isn’t related to the elements themselves, and may change when the table is resized.
The other popular group of data structures are trees. In particular, self-balancing binary search trees specialize in reasonably fast gets, inserts and deletions. They don’t need to reallocate when some growth threshold is reached. Most importantly, they maintain a clear order between their elements. When used for building a dictionary, a binary search tree uses the sort order of the keys. You could quite efficiently enumerate all or part of the elements in the tree in their increasing or decreasing sort order.
Outside the Cocoa universe, both hash-based and tree based dictionaries are frequently available. Java has HashMap and TreeMap. The .NET Framework has the Dictioanry and SortedDictionary classes. C++ has the tree-based std::map and the hash-based boost::unordered_map. Cocoa’s NSDictionary and NSMutableDictionary are hash-based. If there is a sorted dictionary avaiable in Cocoa, it managed to hide quite well.
So after a prolonged bout of yak shaving, I am posting self-balancing binary search tree implementations of Objective-C SortedDictionary and MutableSortedDictionary classes. They implement the interface of NSDictionary and NSMutableDictioanry, and can be used as drop-in replacements. The new classes are unit-tested, and you can plug in their documentation directly into XCode. And, their sort order is always well defined. When you enumerate a SortedDictionary, you always get entries sorted by key. You can enumerate from the back too. If you query them for their keys and values, they come back sorted. And so on.
You can find the full source code, documentation and unit tests for SortedDictionary and MutableSortedDictionary at http://code.google.com/p/cocoa-sorted-dictionary/. They are available under the rather permissive MIT license, so feel free to hack away.