>> 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 _______________________________________________ Python-3000 mailing list Python-3000@python.org http://mail.python.org/mailman/listinfo/python-3000 Unsubscribe: http://mail.python.org/mailman/options/python-3000/archive%40mail-archive.com
