Why std::map is red black tree and not hash table ?

Question

This is very strange for me, i expected it to be a hash table.

I saw 3 reasons in the following answer (which maybe correct but i don't think that they are the real reason). Hash tables v self-balancing search trees

1. Although hash might be not a trivial operation. I think that for most of the types it is pretty simple.

2. when you use map you expect something that will give you amortized O(1) insert, delete, find , not log(n).

3. i agree that trees have better worst case performance.

I think that there is a bigger reason for that, but i can't figure it out. In c# for example Dictionary is a hash table.

Answer 1

It's largely a historical accident. The standard containers (along with iterators and algorithms) were one of the very last additions before the feature set of the standard was frozen. As it happened, they didn't have what they considered an adequate definition of a hash-based map at the time, and there wasn't time to add it before features were frozen, so the original specification included only a tree-based map.

C++ 11 added std::unordered_map (as well as std::unordered_set and multi versions of both), which is based on hashing though.

Answer 2

The reason is that map is explicitly called out as an ordered container. It keeps the elements sorted and allows you to iterate in sorted order in linear time. A hashtable couldn't fulfill those requirements.

In C++11 they added std::unordered_map which is a hashtable implementation.