Related: Nick posted an excellent answer to this question here: http://stackoverflow.com/questions/5953205/why-are-there-no-sorted-container... 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.