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

Terry Reedy tjreedy at udel.edu
Wed Mar 4 17:41:47 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?

Appending an item at the end of a sequence is O(1), no search required. Inserting an item at a random 'sorted' point requires at best an O(logN) search. Insertion itself is O(1) to O(N) depending on the structure.

More information about the Python-Dev mailing list