sorteddict PEP proposal [started off as orderedict]

[Mark Summerfield]

On 26 Sep, 11:27, Hrvoje Niksic <hnik... at xemacs.org> wrote:
> Mark Summerfield <m.n.summerfi... at googlemail.com> writes:
> > 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 [...]
>
> No argument here, as long as the limitation is understood to be a
> consequence of the current implementation model.  Seriously proposing
> a sorteddict that is a mere syntactic sugar over dict dooms the PEP to
> rejection.

On the Py3K list GvR made it clear that sorteddict wouldn't be in
Python until an implementation had been in popular use for some
time... so I will not put forward a PEP for it.

> Major programming language libraries have included sorted mapping and
> set types for a while now, making the performance and complexity
> constraints generally well understood.  We should make use of that
> knowledge when designing sorteddict.

I know! I use Python and C++ and Qt, so what with the STL and Qt's
containers I'm used to having far more containers to choose from than
Python offers. I think Python could do with both sorteddict and
sortedset in the collections module, but to get decent performance
will require a balanced tree (or a skiplist) implementation, and I
don't have the time to do that. Apart from Antoon Pardon's AVL tree,
there's also Chris Gonnerman's RBTree, also pure Python, with a dict
API and that seems to accept a cmp function, but again, I don't know
whether it could be adapted to the sorteddict((mapping | sequence |
nothing), cmp=None, key=None, reverse=None) API that Paul Hankin
described.