<div dir="ltr">Related:<div><br></div><div>Nick posted an excellent answer to this question here:  http://stackoverflow.com/questions/5953205/why-are-there-no-sorted-containers-in-pythons-standard-libraries<div><div><br>On Thursday, October 13, 2016 at 4:36:39 PM UTC-4, Марк Коренберг wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir="ltr"><div>I mean mutable containers that are always sorted when iterating over them.</div><div><br></div><div>See <a href="http://bugs.python.org/issue28433" target="_blank" rel="nofollow" onmousedown="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fbugs.python.org%2Fissue28433\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHO6d0NReAyZKy1B8GxxrOiVbF6-A';return true;" onclick="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fbugs.python.org%2Fissue28433\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNHO6d0NReAyZKy1B8GxxrOiVbF6-A';return true;">http://bugs.python.org/<wbr>issue28433</a></div><div><br></div><div>for example:</div><div><br></div><div>* SortedSet (sorted unique elements, implemented using (rb?)tree instead of hash)</div><div>* SortedList (sorted elements, the same as SortedSet, but without uniquiness constraint) - actually a (rb?)tree, not a list (i.e. not an array)</div><div>* SortedDict (sorted by key when interating) - like C++'s ordered_map</div><div><br></div><div>There are many implementations in the net, like:</div><div><br></div><div><a href="https://bitbucket.org/bcsaller/rbtree" target="_blank" rel="nofollow" onmousedown="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fbitbucket.org%2Fbcsaller%2Frbtree\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEOCTj6zFgLweqzdROvJD1HxapFng';return true;" onclick="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fbitbucket.org%2Fbcsaller%2Frbtree\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEOCTj6zFgLweqzdROvJD1HxapFng';return true;">https://bitbucket.org/<wbr>bcsaller/rbtree</a></div><div><a href="http://newcenturycomputers.net/projects/rbtree.html" target="_blank" rel="nofollow" onmousedown="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fnewcenturycomputers.net%2Fprojects%2Frbtree.html\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNGerDk6ord88C7wQdtDWGUHMXlz9w';return true;" onclick="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fnewcenturycomputers.net%2Fprojects%2Frbtree.html\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNGerDk6ord88C7wQdtDWGUHMXlz9w';return true;">http://newcenturycomputers.<wbr>net/projects/rbtree.html</a></div><div><a href="https://sourceforge.net/projects/pyavl" target="_blank" rel="nofollow" onmousedown="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fsourceforge.net%2Fprojects%2Fpyavl\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEue_dAszkFbo4DtSh4wiL5bIxKQQ';return true;" onclick="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fsourceforge.net%2Fprojects%2Fpyavl\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEue_dAszkFbo4DtSh4wiL5bIxKQQ';return true;">https://sourceforge.net/<wbr>projects/pyavl</a></div><div><a href="http://www.grantjenks.com/docs/sortedcontainers" target="_blank" rel="nofollow" onmousedown="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.grantjenks.com%2Fdocs%2Fsortedcontainers\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFiLVLF--7enVT2OGhpZ62h1CA9wA';return true;" onclick="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.grantjenks.com%2Fdocs%2Fsortedcontainers\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFiLVLF--7enVT2OGhpZ62h1CA9wA';return true;">http://www.grantjenks.com/<wbr>docs/sortedcontainers</a></div><div><a href="https://github.com/tailhook/sortedsets" target="_blank" rel="nofollow" onmousedown="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2Ftailhook%2Fsortedsets\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFP3XfukPpbjo7Eq0vQXf4_m2W0Gw';return true;" onclick="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fgithub.com%2Ftailhook%2Fsortedsets\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFP3XfukPpbjo7Eq0vQXf4_m2W0Gw';return true;">https://github.com/tailhook/<wbr>sortedsets</a></div><div><a href="https://pypi.python.org/pypi/skiplist" target="_blank" rel="nofollow" onmousedown="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fpypi.python.org%2Fpypi%2Fskiplist\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFa8YgqRjoz5dFIeDRDHAFK3afscQ';return true;" onclick="this.href='https://www.google.com/url?q\x3dhttps%3A%2F%2Fpypi.python.org%2Fpypi%2Fskiplist\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNFa8YgqRjoz5dFIeDRDHAFK3afscQ';return true;">https://pypi.python.org/pypi/<wbr>skiplist</a></div><div><br></div><div>and also in pip:</div><div><br></div><div>pip3 search sorted | grep -Ei '[^a-z]sorted'</div><div><br></div><div>I think it should be one standardized implementation of such containers in CPython.</div><div><br></div><div>For example, C++ has both ordered_map and unorderd_map.</div><div><br></div><div>Instead of trees, implementation may use SkipList structure, but this is just implementation details.</div><div><br></div><div>Such structres imply fast insertion and deletion, ability to iterate, and also memory efficiency.</div><div><br></div></div></blockquote></div></div></div></div>