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)