map vs. hash_map in C++

c++ map hashmap
skydoor picture skydoor · Feb 3, 2010 · Viewed 153.5k times · Source

I have a question with hash_map and map in C++. I understand that map is in STL, but hash_map is not a standard. What's the difference between the two?

Answer

Joe picture Joe · Feb 3, 2010

They are implemented in very different ways.

hash_map (unordered_map in TR1 and Boost; use those instead) use a hash table where the key is hashed to a slot in the table and the value is stored in a list tied to that key.

map is implemented as a balanced binary search tree (usually a red/black tree).

An unordered_map should give slightly better performance for accessing known elements of the collection, but a map will have additional useful characteristics (e.g. it is stored in sorted order, which allows traversal from start to finish). unordered_map will be faster on insert and delete than a map.

Related questions

Determine if map contains a value for a key?

What is the best way to determine if a STL map contains a value for a given key? #include <map> using namespace std; struct Bar { int i; }; int main() { map<int, Bar> m; Bar b = {0}; Bar …

Read More
How to check if std::map contains a key without doing insert?

The only way I have found to check for duplicates is by inserting and checking the std::pair.second for false, but the problem is that this still inserts something if the key is unused, whereas what I want is …

Read More
How to update std::map after using the find method?

How to update the value of a key in std::map after using the find method? I have a map and iterator declaration like this: map <char, int> m1; map <char, int>::iterator m1_it; typedef …

Read More