sorteddict PEP proposal [started off as orderedict]

[Paul Hankin]

On Sep 26, 9:51 am, 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.

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.

--
Paul Hankin