I'm all for adding more featureful data structures. At the risk of confusing Nick's folks, I think it's possible to do even better than Sorted/Ordered for many collections. In my experience, the simple Ordered trait alone was not enough of a feature improvement over the simpler builtin, leading me to implement an OrderedMultiDict, for instance. Another, more cogent example would be Boltons' IndexedSet: http://boltons.readthedocs.io/en/latest/setutils.html It's a normal MutableSet, with almost all the same time complexities, except that you can do indexed_set[0] to get the first-added item, etc. Sometimes it helps to think of it as a kind of UniqueList. If we're going for more featureful containers, I say go all-in! Mahmoud On Fri, Oct 14, 2016 at 8:23 AM, Nick Coghlan wrote:

...

Related:

Nick posted an excellent answer to this question here: http://stackoverflow.com/questions/5953205/why-are-

On 14 October 2016 at 06:48, Neil Girdhar wrote: there-no-sorted-containers-in-pythons-standard-libraries

Ah, so this thread is why I've been getting SO notifications for that answer :)

While I think that was a decent answer for its time (as standardising things too early can inhibit community experimentation - there was almost 12 years between Twisted's first release in 2002 and asyncio's provisional inclusion in the standard library in Python 3.4), I also think the broader context has changed enough that the question may be worth revisiting for Python 3.7 (in particular, the prospect that it may be possible to provide this efficiently without having to add a large new chunk of C code to maintain).

However, given that Grant has already been discussing the possibility directly with Raymond as the collections module maintainer though, there's probably not a lot we can add to that discussion here, since the key trade-off is between:

- helping folks that actually need a sorted container implementation find one that works well with typical memory architectures in modern CPUs - avoiding confusing folks that *don't* need a sorted container with yet another group of possible data structures to consider in the standard library

*That* part of my original SO answer hasn't changed, it's just not as clearcut a decision from a maintainability perspective when we're talking about efficient and relatively easy to explain pure Python implementations.

Cheers, Nick.

-- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia _______________________________________________ Python-ideas mailing list Python-ideas@python.org https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/

Those are great articles. One thing that Andrew does recommend would be to standardize the interface to the sorted containers, and add them to collections.abc as SortedDict, and SortedSet. I recently switched from blist to sortedcontainers and it would be nice to have these standardized going forward. Another reason to standardize them is for use with the new type checking. Best, Neil On Thursday, October 13, 2016 at 5:54:09 PM UTC-4, Serhiy Storchaka wrote:

On 13.10.16 23:36, Марк Коренберг wrote:

...

I think it should be one standardized implementation of such containers in CPython.

For example, C++ has both ordered_map and unorderd_map.

Instead of trees, implementation may use SkipList structure, but this is just implementation details.

Such structres imply fast insertion and deletion, ability to iterate, and also memory efficiency.

I recommend to read thorough review articles written by Andrew Barnert:

http://stupidpythonideas.blogspot.com/2013/07/sorted-collections-in-stdlib.h...

http://stupidpythonideas.blogspot.com/2014/04/sortedcontainers.html

_______________________________________________ Python-ideas mailing list Python...@python.org javascript: https://mail.python.org/mailman/listinfo/python-ideas Code of Conduct: http://python.org/psf/codeofconduct/