A sorted dictionary for Cocoa

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

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.

Oren Trutner

Advertisements

6 Responses to A sorted dictionary for Cocoa

  1. ashraf says:

    still i did not tested. as an earlier programmer in Java I was looking for this thing.
    thanks in advance, if it works šŸ™‚

  2. Christopher Burns says:

    Hi Oren,

    I was just going to build my own SortedDictionary implementation based on Visual Smalltalk’s, but this is saving me from the task.

    I cannot, however, get it to work. I do not see the compiled framework in the download, so adding to my project that way is not working (I am probably missing the point somewhere…).

    And when I try to add the actual source files (I add the SortedDictionary folder just above the Public and Internal folders), compiling fails with a ton of bad references to Cocoa.h.

    What am I missing here?

    Thanks!

    Chris

  3. bob says:

    by the way, the CHDataStructures library (http://cocoaheads.byu.edu/code/CHDataStructures) also contains a sorted dictionary class (CHSortedDictionary)

  4. honggu says:

    thanks!! thanks!! thanks!!

  5. Seho Park says:

    Thank you very much. This is what I am looking for!

  6. eddy says:

    Does this sort it in descending order?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: