This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Title: Add sorted (ordered) containers
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.7
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: Nosy List: abarnert, eric.smith, levkivskyi, r.david.murray, rhettinger, socketpair
Priority: normal Keywords:

Created on 2016-10-13 18:21 by socketpair, last changed 2022-04-11 14:58 by admin. This issue is now closed.

Messages (6)
msg278586 - (view) Author: Марк Коренберг (socketpair) * Date: 2016-10-13 18:21
I mean mutable containers that are always sorted when iterating over them.

* SortedSet (sorted unique elements, implemented using (rb?)tree instead of hash)
* SortedList (sorted elements, the same as SortedSet, but without uniquiness constraint) - actually a (rb?)tree, not a list (i.e. not an array)
* SortedDict (sorted by key when interating) - like C++'s ordered_map

There are many implementations in the net, like:

and also in pip:

pip3 search sorted | grep -Ei '[^a-z]sorted'

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

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

P.S. Did not found if such issue was raised earlier.
msg278593 - (view) Author: Eric V. Smith (eric.smith) * (Python committer) Date: 2016-10-13 19:35
I'm sure this has been discussed before and rejected. I suggest you search the python-ideas mailing list archives, and if you do not find something in the archives, raise the issue on python-ideas.
msg278598 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-10-13 20:03
I'm going to close it as rejected.  If you surprise us and get a positive response on python-ideas we can always reopen.  But, adding a btree would probably require a PEP anyway.
msg278603 - (view) Author: Марк Коренберг (socketpair) * Date: 2016-10-13 20:22!searchin/python-ideas/sorted|sort:relevance/python-ideas/dy3Thu-PXSM/mTqEduXE4GYJ ?

@serhiy.storchaka did not rejected idea.

Anyway, I still can not find message in python-ideas which describe why such idea may be rejected.

Well, I will try to get answer at python-ideas...

Maybe someone can say why this idea is broken in that issue ?
msg278604 - (view) Author: Марк Коренберг (socketpair) * Date: 2016-10-13 20:26
Well, I created discussion at!topic/python-ideas/CoRe1gThnd8
msg278819 - (view) Author: Марк Коренберг (socketpair) * Date: 2016-10-17 16:54

Please see answres at!topic/python-ideas/nPOi2LtVsR4

No one say that adding sorted containers is bad idea. Some people say that specific use-cases require specific solutions, but they also said that it is good to add solution, that is not-so-bad for a gneric case.

The most appropriate solution (as I think) is pure-python sorted containers that are proven to be bug-free and has perfromance comparison against many other libraries. This will make support of PyPy/IronPython/e.t.c automagically.

Why not to add it to CPython distribution (like asyncio) ?
Date User Action Args
2022-04-11 14:58:38adminsetgithub: 72619
2016-10-17 16:54:09socketpairsetmessages: + msg278819
2016-10-13 20:26:34socketpairsetmessages: + msg278604
2016-10-13 20:22:15socketpairsetmessages: + msg278603
2016-10-13 20:03:37r.david.murraysetstatus: open -> closed

nosy: + r.david.murray
messages: + msg278598

resolution: rejected
stage: resolved
2016-10-13 19:35:05eric.smithsetnosy: + eric.smith
messages: + msg278593
2016-10-13 18:58:35levkivskyisetnosy: + levkivskyi
2016-10-13 18:32:06serhiy.storchakasetnosy: + rhettinger, abarnert
2016-10-13 18:21:37socketpaircreate