Proposed implementation for an Ordered Dictionary

[Paul Rubin]

Raymond Hettinger <python at rcn.com> writes:
> I don't see any fast/clean way.  It's possible to tracking pending
> deletions and do them all at once but that's a bit messy and slow.

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.