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

[Terry Reedy]

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.