Proposed implementation for an Ordered Dictionary

[Hrvoje Niksic]

Raymond Hettinger <python at rcn.com> writes:

> Here's a proposed implementation for Py2.7 and Py3.1:
>
>     http://code.activestate.com/recipes/576669/

    Several methods like __contains__() and __getitem__() are not
    overridden, so their performance is just as fast as a regular
    dictionary.

    Methods like __setitem__ and __delitem__ are overridden but have a
    fast path depending on whether or not the key already exists.

It seems that __delitem__ of an existing key is O(n), whereas it's
amortized constant time for dicts.  (__setitem__ is constant time for
both.)  Is there a way to avoid this?

If not, it should probably be documented, since it differs from dict.