map vs hash_map
- STL map accepts almost any type as its element. It does that by relying only on a less-than operation for comparing elements
- STL map is implemented using red-black balanced tree
- STL hash_map requires an == and a hash function
- STL hash_map is implemented by placing a value at its index, unless another value is already placed there, and 'nearby' if one is.
- map<string, int> m1;
- hash_map<string, int> m2; // hash using Hash<string>
- hash_map<string, int, hfct> m3; // hfct() as hash function
- Prefer a map to hash_map if the elements must be kept in order
- Prefer hash_map to map when speed of lookup is essential
(via The C++ Programming Language, Third Edition by Bjarne Stroustrup, page 497)