Skip to content
Quantoros

std::map vs. std::unorderedmap — trade-offs and when to use each.

C++Level: IntermediateSTL Containers & Iterators

std::map vs. std::unordered_map — trade-offs and when to use each.

Hints
  • Identify types, object lifetimes and compile-time decisions.
  • Separate language guarantees from a particular compiler's behavior.

Answer

Ordered vs Unordered Containers

:header-rows: 1

    • Feature
    • set/map
    • unordered_set/map
    • Implementation
    • Red-black tree
    • Hash table
    • Lookup
    • O(log n)
    • O(1) average, O(n) worst
    • Insert/Delete
    • O(log n)
    • O(1) average, O(n) worst
    • Ordered iteration
    • Yes
    • No
    • Key requirement
    • Comparable (<)
    • Hashable + equality (==)
    • Memory overhead
    • Tree pointers
    • Hash buckets

When to use ordered (set/map):

  • Need sorted iteration or range queries
  • Keys are not easily hashable
  • Predictable worst-case performance required

When to use unordered (unordered_set/map):

  • Performance is critical and dataset is large
  • Don't need sorted order
  • Keys have good hash distribution

Answer section

Source and licence: C/C++ Interview Cheatsheet — Chang Ning Tsai · MIT

Related questions