classification
Title: Add sorted (ordered) containers
Type: enhancement Stage: resolved
Components: Library (Lib) Versions: Python 3.7
process
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 2016-10-17 16:54 by socketpair. 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.
i.e.

* 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:

https://bitbucket.org/bcsaller/rbtree/
http://newcenturycomputers.net/projects/rbtree.html
https://sourceforge.net/projects/pyavl/
http://www.grantjenks.com/docs/sortedcontainers/

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
https://groups.google.com/forum/#!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 

https://groups.google.com/forum/#!topic/python-ideas/CoRe1gThnd8
msg278819 - (view) Author: Марк Коренберг (socketpair) * Date: 2016-10-17 16:54
@r.david.murray

Please see answres at https://groups.google.com/forum/#!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. http://www.grantjenks.com/docs/sortedcontainers. This will make support of PyPy/IronPython/e.t.c automagically.

Why not to add it to CPython distribution (like asyncio) ?
History
Date User Action Args
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