[Python-ideas] Add sorted (ordered) containers

[Neil Girdhar]

Related:

Nick posted an excellent answer to this question here: 
 http://stackoverflow.com/questions/5953205/why-are-there-no-sorted-containers-in-pythons-standard-libraries

On Thursday, October 13, 2016 at 4:36:39 PM UTC-4, Марк Коренберг wrote:
>
> 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/c0a71b50/attachment.html>