sorteddict PEP proposal [started off as orderedict]

[Mark Summerfield]

On 26 Sep, 09:51, Hrvoje Niksic <hnik... at xemacs.org> wrote:
> Duncan Booth <duncan.bo... at invalid.invalid> writes:
> > I that's the point though: you can't write one implementation that has good
> > performance for all patterns of use
>
> 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.


Basically, as implemented, I have to invalidate if there is any change
to a key _or_ to a value because if cmp or key functions are specified
they could be using the key, the value, or even both. (If key and cmp
were both None and reverse was False, I could use the bisect module
and maintain the keys in sorted order at all times in that case, but
then performance would vary considerably depending on use which I
think would be v. confusing for users.)

You are quite right that using a balanced tree (red-black, AVL, or
b*tree) would provide decent performance in all the use cases. There
appear to be two on PyPI (rbtree and pyavl), but both seem to be C
extensions. Antoon Pardon has a pure Python AVL tree, but whether he
could or would produce a version that had the sorteddict API, I don't
know.