On Mar 16, 2020, at 11:52, Christopher Barker <python...@gmail.com> wrote:
>
>> On Mon, Mar 16, 2020 at 11:36 AM Andrew Barnert <abarn...@yahoo.com> wrote:
>
>
> Anyway, my only point was that we DO want to consider both performance and
> semantics here -- a Sorted Dict (or SortedList, or ...) has different use
> cases, and thus should have a different semantics (API).
>
> I note that the SortedList, for instance, is not quite a MutableSequence, as
> it doesn't make sense to support .append() and .extend() for that.
Yes, everyone who designs a sorted container library runs into the fact that a
SortedList is a Sequence, and mutable, but not even close to a
MutableSequence—it’s not just append and extend; you can’t even do __setitem__.
In fact, it’s a lot closer to a MutableSet (assuming you use the obvious names
add and update), but it’s not that either, because it’s a multiset rather than
a set.
I believe SortedContainers 2.x’s SortedList inherits MutableSequence anyway,
and raises NotImplementedError on __setitem__, append, etc. Which is a weird
compromise, sometimes confusing but sometimes handy.
I think the best solution is to just not have a SortedList. C++, Java, etc.
don’t provide anything like that, only sorted dicts, sets, and multisets. (C#
does have a SortedList, but it doesn’t act like a list, it acts like an
ItemsView, in Python terms.) And it’s rare that you need something that’s
sorted but also directly indexable; when you do, the answer in those languages
is to write a simple wrapper around a multiset. For an all-encompassing
third-party library, maybe it’s worth trying to do more, but for the stdlib,
just leaving out sorted lists and multisets and maybe even sets seems like the
easiest answer. 90% of the use cases for SortedContainers and its competitors
are dicts. Every thread suggesting to add something similar over the decades,
the use cases are all dicts. We can just add dicts instead of trying to cover
everything anyone might want. And we can, and should, link to SortedContainers
in the docs for people who want more and are willing to read what the
compromises are.
> Not sure if there is anything about a SortedDict that makes it not a
> MutableMapping, though.
There’s no problem there.
IIRC, the original implementation of SortedContainers inherited from
collections.abc.MutableMapping, and the new implementation just inherits dict
(because it’s not a tree of items, it’s a tree of keys on top of a plain old
dict). Which also means it requires keys that are _both_ hashable and
weak-ordered…
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/SYFPLJ7YXH7PQXIM34R23YNFEFYOJDQM/
Code of Conduct: http://python.org/psf/codeofconduct/
