[Python-ideas] Add sorted (ordered) containers

[Марк Коренберг]

I mean mutable containers that are always sorted when iterating over them.

See http://bugs.python.org/issue28433

for example:

* 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
https://github.com/tailhook/sortedsets
https://pypi.python.org/pypi/skiplist

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.

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.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20161013/726e8431/attachment.html>