Sorted associative container in Python?

[Terry Reedy]

"Duncan Booth" <duncan at NOSPAMrcp.co.uk> wrote in message
news:Xns938391402C28Cduncanrcpcouk at 127.0.0.1...
> The easiest way is to store the data in the dictionary, but maintain
a
> separate sorted list of the keys. Depending on the ratio of updates
to
> iterations you might either update the sorted list every time a new
key is
> added to the dictionary, which makes dictionary update log n but
your
> iteration is linear, or simply throw the sorted list away when
changing the
> dicionary and rebuild it next time you iterate, this keeps the
constant
> time updates and makes iteration nlogn, but if updates are rare, or
happen
> together probably works out faster in practice.

Its worth noting that the current list.sort() method (starting in
2.2.2, I believe) works well (by design) with nonrandom special cases
such as a sorted list with new items appended.  Slightly simplified,
it will scan the list, notice that the first part is properly sorted,
sorted the added tail, and then merge.

Terry J. Reedy