[Python-ideas] Sorted collections again?! (Was: Fast sum() for non-numbers)

[Andrew Barnert]

From: Haoyi Li <haoyi.sg at gmail.com>
Sent: Monday, July 8, 2013 6:25 PM


><rant>I would also really like a nice object-oriented sortedlist to be part of the standard library, instead of that nasty C-style heapq stuff.</rant>


See this: http://stupidpythonideas.blogspot.com/2013/07/sorted-collections-in-stdlib.html

I stopped short of writing up a complete proposal, because (a) there are a lot of open questions, and (b) I'd like to hear from the authors of some of the existing PyPI libraries. But the short version is:

 * [Mutable]Sorted[Mappingt|Set|List] and possibly Sorted[Item|Key|Value]View ABCs, which inherit from the non-Sorted and add methods like key_slice.

 * Sorted[Dict|Set|List] concrete classes, all sharing the same implementation, ideally borrowed from existing PyPI library. (Open questions: red-black trees, or something else? can you get timsort-like behavior for already-sorted source data, or for large updates?)

 * Constructor matches [dict|set|list], but with optional key parameter. (Open question: SortedDict(a=1, B=2, c=3, key=str.lower) ambiguity.)