On Mar 19, 2020, at 11:29, Marco Sulla <Marco.Sulla.Python@gmail.com> wrote:
On Mon, 16 Mar 2020 at 22:22, Andrew Barnert via Python-ideas <python-ideas@python.org> wrote:
I think the best solution is to just not have a SortedList. C++, Java, etc. don’t provide anything like that
Guava has TreeMultiset: https://guava.dev/releases/snapshot/api/docs/com/google/common/collect/TreeM...
Sure. And C++ has a sorted multiset too. But std::multiset’s API is similar to set, and of course to the hash-based unordered_multiset; it’s not similar to list or vector (beyond the basic iterability). And that’s the point: a “sorted list” isn’t really like a list, and most languages don’t try to force it. A “sorted multiset” is a more sensible thing, and really is like an (unordered) multiset, and provides the behavior people want from a flat sorted collection that allows duplicates—but a language that doesn’t even bother with unordered multisets* like Python surely doesn’t need to add a sorted multiset just for completeness.
The problem is: is there a use case? I mean, how much time you need to sort a list, add an element and re-sort it?
And even if you do, how often do you need to do list-y things like slice it from the 10th to 19th indices or concatenate two of them, much less whatever it should mean to replace the value at a specific index? The SortedList idea is a mirage. At first glance it seems like an obviously useful parallel to SortedDict and SortedSet in the same way list parallels dict and set, but as soon as you try to think through how it should act and what you’d ever do with it, you realize that’s an illusion, and it’s actually a clunky design with no use case. * Yes, there is collections.Counter. But that doesn’t even provide an analog to the MutableSet API—there’s no add, etc. It’s a dict whose values are counts, which can be used (among other things) to simulate a multiset. If people want a collections.SortedCounter built on top of sorteddict instead of dict, that should be trivial to add.