Choosing between std::map and std::unordered_map [duplicate]

by

As already mentioned, map allows to iterate over the elements in a sorted way, but unordered_map does not. This is very important in many situations, for example displaying a collection (e.g. address book). This also manifests in other indirect ways like: (1) Start iterating from the iterator returned by find(), or (2) existence of member functions like lower_bound().

Also, I think there is some difference in the worst case search complexity.

  • For map, it is O( lg N )

  • For unordered_map, it is O( N ) [This may happen when the hash function is not good leading to too many hash collisions.]

The same is applicable for worst case deletion complexity.

More Related Contents:

  1. How to specialize std::hash::operator() for user-defined type in unordered containers?
  2. What is the default hash function used in C++ std::unordered_map?
  3. error for hash function of pair of ints
  4. C++ unordered_map using a custom class type as the key
  5. How to remove from a map while iterating it?
  6. How std::unordered_map is implemented
  7. How do I combine hash values in C++0x?
  8. Compile time string hashing
  9. Generic hash for tuples in unordered_map / unordered_set
  10. C++ – Why is boost::hash_combine the best way to combine hash-values?
  11. Why is std::unordered_map slow, and can I use it more effectively to alleviate that?
  12. Hash an arbitrary precision value (boost::multiprecision::cpp_int)
  13. Why can’t I replace std::map with std::unordered_map
  14. std::function vs template
  15. Why is the destructor of a future returned from `std::async` blocking?
  16. How to return a std::string.c_str()
  17. When is a private constructor not a private constructor?
  18. Reading from ifstream won’t read whitespace
  19. Is there a non-atomic equivalent of std::shared_ptr? And why isn’t there one in ?
  20. When is overloading pass by reference (l-value and r-value) preferred to pass-by-value?
  21. Do I really need to implement user-provided constructor for const objects?
  22. Is it valid to bind non-const lvalue-references to rvalues in C++ 11?(modified)
  23. Using `std::function` to call non-void function
  24. What’s the difference between parentheses and braces in c++ when constructing objects
  25. cc1plus: error: unrecognized command line option “-std=c++11” with g++
  26. How do I pass multiple ints into a vector at once?
  27. Is it wise to ignore gcc/clang’s “-Wmissing-braces” warning?
  28. Can std::vector emplace_back copy construct from an element of the vector itself?
  29. Should all/most setter functions in C++11 be written as function templates accepting universal references?
  30. enum vs constexpr for actual static constants inside classes

Leave a Comment