On Wed, May 26, 2010 at 12:18:56PM +0530, Ketan Joshi wrote: > Hi guys, > > This could be a wrong forum for such a question, but I am posting it here > anyways. > > I read somewhere that c++ maps are implemented using height balanced trees > (red black trees specifically). > > Why wasn't it implemented using hash tables? wouldn't it have been faster > specially since maps dont allow duplicate keys?
I don't know the original reason, but these days the reason is that std::map was standardized that way :) std::map does not necessarily have to be a red-black tree, but it does have to be an ordered structure of some kind. You see, an ordered structure has different requirements for its key type than a hashtable does. A hashtable needs to be able to hash its keys; an ordered structure needs to be able to compare them. And std::map has been specified to take a comparison function. If you wanted to implement it as a hashtable then you would need a different interface. You don't really notice this difference when making maps of built-in types, but it matters when you want to use your own classes as keys. Perhaps the choice for ordered structures was originally made because C++ provides a standard interface for comparisons (operator<) but does not provide a standard interface for hash functions. (Also, it's easy to write a good comparison function, but hard to write a good hash function. So requiring a comparison function instead of a hash is easier for the template's users.) Another difference in the interface is that std::map offers an iterator that can be used to scan its keys from lowest to highest. Try doing that with a hashtable :) The next version of the C++ standard will probably add an unordered_map template that uses hashing. -- Richard Braakman -- You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
