ReviseAlgo Logo

Standard Template Library (STL)

std::map and std::multimap

Ordered key-value pairs in a red-black tree — O(log n) operations with sorted iteration

Interview: Essential associative container — frequency counting, LRU adjacency lists, and ordered key queries

std::map and std::multimap

std::map<K, V> stores unique key-value pairs in sorted order by key (red-black tree). O(log n) for all operations. std::multimap allows duplicate keys. Iterating produces pairs in ascending key order — unlike unordered_map which has no order guarantee.

operator[] vs at() vs find()

map[key]: returns reference, inserts a default-constructed value if key doesn't exist — silently mutates the map. map.at(key): throws std::out_of_range if key missing. map.find(key): returns iterator to element or end() if not found — non-inserting lookup. Use find() when you don't want unintended insertions.

lower_bound and upper_bound

Because map is sorted, lower_bound(k) and upper_bound(k) enable O(log n) range queries by key — find all entries in a key range, find the nearest key, etc. These don't exist for unordered_map.

Interview Corner

Q: What is the danger of using map[key] for lookup?

A: If the key doesn't exist, map[key] default-constructs a value and inserts it — you've mutated the map. For a read-only lookup, use map.find(key) or map.count(key). Common interview bug: using [] in a const method which won't even compile, or unintentionally growing the map with default values.

Q: When would you use map over unordered_map?

A: Use map when: sorted order matters for the result, you need range queries (lower_bound/upper_bound), guaranteed O(log n) worst case matters more than O(1) average, or the key type has no hash function. Use unordered_map for pure lookup/insert with O(1) average performance and no ordering requirement.

Common Pitfalls

  • Unintended insertions with []: map[key] inserts a default value if key is missing — check with find() first for existence testing.
  • Using [] on a const map: operator[] is non-const — you cannot use it on a const map. Use at() or find() on const maps.

Best Practices

  • Use find() for conditional lookups; use [] only when you want insert-if-not-present behavior.
  • Use emplace() or insert_or_assign() (C++17) for efficient in-place insertion.