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.