[Python-3000] ordered dict for p3k collections?

["Martin v. Löwis"]

>> When I program in C++/Qt I use QMap (a sorteddict) very often; the STL
>> equivalent is called map. Both the Qt and STL libraries have dict
>> equivalents (QHash and unordered_map), but my impression is that the
>> sorted data structures are used far more frequently than the unsorted
>> versions.
> 
> Perhaps out of ignorance? Or perhaps the hash implementations have
> suboptimal implementations? Or perhaps because no equivalent to
> sorted() exists?

I feel (without being able to prove it) that C++ (i.e. STL uses a
red-black-tree instead of a hash table for two reasons):
1. it is theoretically better. Hash tables have not O(1), but O(n)
   as the worst case, whereas balanced trees can guarantee O(log n).
   Hash tables have O(1) in the average case only if the hash
   function is good, plus the costs for computing the hash are
   typically higher than the costs for comparison, unless the hash
   is cached.
2. it is often easier for applications to provide sorting. For
   most things you want to search for, coming up with a total order
   is straight-forward; defining a hash operation might not be that
   easy (of course, for identity lookups, hashing is easier).

Regards,
Martin