Proposed implementation for an Ordered Dictionary

[Raymond Hettinger]

[Paul Rubin]
> What about using a second dictionary (indexed by the incrementing
> counter) instead of a list to record the insertion order?  Then you
> have O(1) deletion, and traversal takes an O(n log n) sorting
> operation.

My first attempt used exactly that approach and it works fine
though it does complicate the code quite a bit and slows down
all of the common operations by a constant factor.


Raymond