I routinely find myself yearning for this data structure in almost every project, but I've scoured the web, and inevitably I just find forum postings saying something along the lines of "dictionaries are unordered, idiot". I usually end up just making a list and dictionary, but it strikes me as inelegant. And, if it were truly a common problem, I can't believe someone hasn't made this data structure before. So I must be doing something wrong in the way I'm thinking about these problems. Any idea what it is?
Here's a library for it in Python: <a href="http://www.voidspace.org.uk/python/odict.html" rel="nofollow">http://www.voidspace.org.uk/python/odict.html</a>
I usually want that when what I really need is ordering but for some reason I want key-based/random access to the values.<p>I think Ruby added this recently. I'm not using it yet. A crappy hack can just dump the next/prev key into the value, plus a pointer to the first, and drop them all in a hash. It's not really pretty, but would give you ordering if you want it. Another hack is to store just the keys in a sorted list and keep the values in the hash (but this is equally inelegant to the list+hash hack and it has the same maintenance overhead).<p>I think most of the ordered-hashes are implemented with something like list pointers between the hash keys, but then again I haven't looked too closely under that kimono.<p>Edit: trees are also a good compromise.
As for whether or not the data structure exists, it does. :) The std::map in C++ is a sorted dictionary, for instance.<p>But it can be uncommon to require this, usually for two reasons. One, the data set may be huge. And two, much of your code may not even "care" if the data is sorted. In either of those cases, if automatic sorting occurs, a lot of compute time may be wasted for no net benefit. (A solution is to have data sorted "on demand" within the code that actually cares about sort order.)
Often, an algorithm that requires iteration in a certain order is a sign that you are keeping information implicitly in the ordering instead of explicitly in a more appropriate data structure. You also may be trying to pack lots of unrelated functionality into a single object when multiple objects would serve better.<p>But it's hard to say without better examples, and there are times when you do want order and lookup. Can you give a couple situations where you want ordered dictionaries?
Ruby 1.9 makes Hash ordered by default.<p>The major reason I care about it is that when loading data from yaml files the key order doesn't get messed up. In ruby 1.8 the order got messed up.<p>So yeah.. use ruby 1.9 :)
Seems totally reasonable. The rise of Ruby shows that modern languages should optimize for programmer efficiency first and speed second.<p>Modern scripting languages have several data structures: mostly arrays, hashes and strings. But it is a hassle move data between them.<p>The <i>next</i> language should only have one, the ordered dictionary.<p>x = [],
x << "hi" # 1=>"hi",
x["seven"]=6 # 1=>"hi", "seven"=>6,<p>Etc