[Python-3000] ordered dict for p3k collections? (original) (raw)

"Martin v. Löwis" martin at v.loewis.de
Wed Sep 26 20:06:55 CEST 2007

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 unorderedmap), 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

More information about the Python-3000 mailing list