[Python-Dev] PEP 372 -- Adding an ordered directory to collections ready for pronouncement

Nick Coghlan ncoghlan at gmail.com
Wed Mar 4 22:25:20 CET 2009

Lie Ryan wrote:
> Isn't ordered dictionary essentially also an "always sorted" container?
> It is always sorted depending on the order of insertion? I can't see any
> technical reason why the data structure can't accommodate them both. Can
> you point me to a discussion on this?

My phrasing was a little ambiguous - "always sorted for an arbitrary key
function" is better handled with something other than a hash map +
additional bookkeeping due to the effect on the speed of insertion and

With a specifically insertion-ordered dict, only deletion is really
slowed down by the additional bookkeeping: it drops to O(n) due to the
need to find and remove the key being deleted from the sequence of keys
as well as from the hash map).

As Terry noted, supporting arbitrary sort orders would slow down
insertion as well.


Nick Coghlan   |   ncoghlan at gmail.com   |   Brisbane, Australia

More information about the Python-Dev mailing list