Proposed implementation for an Ordered Dictionary

Paul Rubin http
Thu Feb 26 18:26:05 EST 2009

Raymond Hettinger <python at> 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

More information about the Python-list mailing list