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

[Nick Coghlan]

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
deletion.

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.

Cheers,
Nick.

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