[Python-ideas] `OrderedDict.sort`

[Andrew Barnert]

On Sep 24, 2013, at 21:27, "Stephen J. Turnbull" <stephen at xemacs.org> wrote:

> Andrew Barnert writes:
> 
>> See http://stupidpythonideas.blogspot.com/2013/07/sorted-collections-in-stdlib.html,
>> which I wrote one or two iterations ago to collect all of the
>> issues, and please let me know if I missed any or you have anything
>> to add.
> 
> A small nit: SortedSequence and SortedDicts should be mappings,
> guaranteeing "fast" (preferably O(1)) access for any key (integral and
> arbitrary, respectively).  Therefore, in the case of a SortedDict the
> user should be no more surprised at a complaint about hashability than
> they should be in the case of a dict (especially considering the name!)
> 
> I'll grant that some users might be perfectly happy with O(log N)
> "reasonably fast" access, but others would not be pleased.

O(log N) is fast enough for the standard mappings in C++, Java, etc., are python users more demanding of performance than C++? I don't know of any language that has a SortedAndHashedDict in it's stdlib, but there are many that have a SortedDict based on a tree. I don't know of any modules on PyPI that offer the former, but multiple popular modules offer the latter. 

Also, given a SortedSequence and a dict, you can trivially build a SortedAndHashedDict if you really want it for something; without SortedSequence, you can't. The other way around isn't true; if you want a SortedDict, without the time and space and requirements burden, a SortedAndHashedSequence is no help.

If you think the name SortedDict is misleading, we could call it something different, with fewer implications. But, given that libraries like blist generally offer the type under a name like SortedDict, and in other languages that offer both tree-based and hash-based collections the names are always parallel (like map and unordered_map in C++), I don't think this is a problem.