sorteddict PEP proposal [started off as orderedict]

[Hrvoje Niksic]

Mark Summerfield <m.n.summerfield 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.

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.