Proposed implementation for an Ordered Dictionary

Paul Rubin http
Fri Feb 27 00:26:05 CET 2009


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.



More information about the Python-list mailing list