<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div>On Jul 6, 2015, at 15:04, Neil Girdhar <<a href="mailto:mistersheik@gmail.com">mistersheik@gmail.com</a>> wrote:</div><div><br></div><blockquote type="cite"><div><div dir="ltr">You can do indexing, insertion, and removal all in logarithmic time (which is basically constant) </div></div></blockquote><div><br></div><div>If you're dealing with dicts of, say, millions of items, then it's "basically constant" with a multiplier of 6-20x worse than the current implementation, and only as long as you never need to scale larger (which is a pretty major concern if you're writing a general-purpose library or something). That's not the same thing as actually constant. There's a reason all the scripting languages have hash-based containers, and that the systems languages that started off with only tree-based containers later added hash-based containers as well.</div><div><br></div><div>Personally, I think it would be great if Python had tree-based sorted containers alongside the existing hash-based arbitrary-ordered ones. Then it would be trivial to add a tree-based insertion-order container to replace the hash-based insertion-order container when it's more appropriate to a specific use (e.g., when you need to efficiently random-access-index it). But, unless you're doing government work or something else that has no access to PyPI, that's already true today, so there's not much to wish for.</div><br><blockquote type="cite"><div><div dir="ltr">by using a B-tree as the underlying data structure. (See e.g. the blist package.)</div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow <span dir="ltr"><<a href="mailto:ericsnowcurrently@gmail.com" target="_blank">ericsnowcurrently@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><span class="">On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar <<a href="mailto:mistersheik@gmail.com">mistersheik@gmail.com</a>> wrote:<br>
</span><span class="">> SortedDict (<a href="http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html" rel="noreferrer" target="_blank">http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html</a>)<br>
> manages to support indexing. Can OrderedDict do the same thing?<br>
<br>
</span>Don't forget that, as the docs describe, an "OrderedDict is a dict<br>
that remembers the order that keys were first inserted". While<br>
obviously there's an implicit sequence for that order, the focus is<br>
still on dict-ness with the sequence exposed through the normal<br>
mapping approach (iteration). If you want to get sequence semantics<br>
then first unpack the order into a sequence type like list or tuple.<br>
Or use some other type than OrderedDict.<br>
<br>
Note that OrderedDict's view types are essentially just dict's view<br>
types with custom iteration. Adding indexing to the views would<br>
complicate things and certainly would not be O(1) like you would<br>
expect indexing to be.<br>
<span class="HOEnZb"><font color="#888888"><br>
-eric<br>
</font></span></blockquote></div><br></div>
</div></blockquote><blockquote type="cite"><div><span>_______________________________________________</span><br><span>Python-ideas mailing list</span><br><span><a href="mailto:Python-ideas@python.org">Python-ideas@python.org</a></span><br><span><a href="https://mail.python.org/mailman/listinfo/python-ideas">https://mail.python.org/mailman/listinfo/python-ideas</a></span><br><span>Code of Conduct: <a href="http://python.org/psf/codeofconduct/">http://python.org/psf/codeofconduct/</a></span></div></blockquote></body></html>