Why did the C++ std library have a binary search tree well before a hashmap which is in many ways simpler

Question

Looking at the two data structures and algorithms to handle them, a hashmap is not really any more complicated than a binary search tree and possibly less complicated. And the hashmap has the advantage of constant time access of a key. So why did we get a std::map very early on in the history of the standard library but for std::unordered_map which is a hashmap we had to wait for C++11 ?

Answer 1

Implementing a hashmap is much more complicated, not in actual implementation but in the possible variants you have to pick from:

• open addressing vs. separate chaining,
  • whether the nodes in separate chaining holds one or more items,
• the hash function,
• growth factor,
• whether to keep key and value together,

All of those affect performance in a way where it's not easy to say which one is better in general.

Compared to that the red-black tree is much simpler to create a prototype for that people won't bikeshed endlessly about.

Answer 2

From http://marknelson.us/2011/09/03/hash-functions-for-c-unordered-containers/,

It’s a little bit of an embarrassment to the C++ community that it didn’t have a hash table in the standard library until TR1 was published in 2005. In a perfect world the original standard should have contained hash map and hash set containers. But Alexander Stepanov didn’t include these containers in the original Standard Template Library, and the standardization committee was reluctant to bless containers that didn’t have a decent amount of mileage in the real world.

Standards committees are generally reactive rather than proactive. C was created in 1969 but wasn't standardized until 1989, and C++ was created in 1979 but wasn't standardized until 1998. The C++ committee took some proactive actions in the original version of the C++ standard, some of which turned out to be mistakes. (There were essentially no fully compliant compilers for the original version of the standard.) The 2003 update was primarily a bug fix. The committee was not about to take any proactive actions in 2003 for functionality that hadn't been tested in the field by multiple compiler vendors.

That said, if you were willing to work with functionality that officially wasn't part of the standard but that were blessed as becoming a part of the standard in the future, you had access to an unordered map well before 2011.

Answer 3

From a viewpoint of specification and standardization, a hash table is quite a bit more complex than a tree.

For the tree-based (ordered) containers, the standard only needs to specify that to store an object, you must be able to assign, copy, and compare it¹. All of those are already pretty well-defined concepts, and most built-in types satisfy them (the only obvious exception being floating point NaN's, which don't satisfy a strict weak ordering).

For hashing, you need to specify (at least) some way of hashing types. That, in turn, required more infrastructure, as as std::hash, with specializations for all the built-in types. In the case of std::unordered_*, it also means quite a bit of extra specification around iterators, adding the iterators local to a bucket to the normal iterators used for everything else.

---

^{1. yes, it goes into a little more detail, such as requiring that the comparison satisfy a strict weak ordering, but that's pretty simple too.}