JuliaLang/julia — pull request #2558 by kmsquire (2013-03-13 18:07:20+00:00)
Title: RFC: Alternative version of OrderedDict

* Copy and modification of Dict
* More performant, uglier

This is an alternate version of #2556. It has a bit better delete performance, but is also a bit uglier, as it copies most of the `Dict` type directly. #2548 attempted to deal with this by abstracting much of the current `Dict` implementation, but that didn't go over too well, largely because the `Dict` implementation has seen some significant changes in the recent past, and the abstraction depended a lot on the current implementation.

Really, the idea `OrderedDict` would have the interface of the other version, and the performance of this one, but I couldn't see how to do that, so I thought I would both up and ask for suggestions.

Another alternative would be to implement a version based on linked lists, which could have reasonable performance, at the cost of some flexibility in the current interface (e.g., both of these versions allow the `OrderedDict` to act largely like an Array of (key,value) tuples, allowing sorting, numerical-index based retrieval, dequeue-like operations, etc.).

If either of these move forward, I would love some specific feedback on whether to allow integer indexing for `OrderedDicts` with nonnumerical keys (e.g., `od["key"]` looks up by hashing "key", and `od[1]` returns the first (key,value) pair, but only for nonnumerical keys).

There is also `getitem(od, 1)` for doing numerical-index based lookup, and `indexof(key)` to get the numerical index of a particular key. Suggestions for better names for these are welcome.