sorteddict PEP proposal [started off as orderedict]

[Hrvoje Niksic]

Paul Hankin <paul.hankin at gmail.com> writes:

>> An implementation of sorted dict using a balanced tree as the
>> underlying data structure would give decent performance in all the
>> mentioned use cases.  For example, red-black trees search, insert,
>> and delete in O(log n) time.
>
> But dicts do search, insert and delete in O(1) time, so using some
> variety of balanced tree will give you much worse performance when
> you're doing regular dict operations.

I wouldn't call it "much worse"; while O(log(n)) is worse than O(1),
it's still very fast, which is why popular programming language
libraries have an ordered mapping type based on balanced trees.  Also
note that dict performance can degrade with hash collisions, while
trees can maintain complexity guarantees on all operations.

In the end, it's a tradeoff.  Hash tables offer O(1) access, but lack
ordering.  Balanced trees offer ordering at the price of O(log n)
access.  Both have their uses, but neither is syntactic sugar for the
other.