On Mar 16, 2020, at 11:52, Christopher Barker <pythonchb@gmail.com> wrote:
On Mon, Mar 16, 2020 at 11:36 AM Andrew Barnert <abarnert@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…