Skip to content

Sets & Maps

Associative containers store keys (and optional values) in sorted or hashed order for fast lookup.

Ordered (tree-based)

Container Keys Values Notes
std::set<K> unique — sorted, O(log n) ops
std::multiset<K> duplicates — sorted
std::map<K,V> unique mapped sorted by key
std::multimap<K,V> duplicates mapped sorted

Use when you need order statistics, lower_bound, or sorted iteration.

Unordered (hash-based)

Container Average Worst case
std::unordered_set<K> \(O(1)\) \(O(n)\)
std::unordered_map<K,V> \(O(1)\) \(O(n)\)

Custom hash and == for non-primitive keys. Rehashing can invalidate iterators; check problem constraints for anti-hash tests.

When to use which

  • Frequency by key → map or unordered_map.
  • Existence only → set / unordered_set.
  • Need min/max key often → set (begin/end).
  • Integer range small → Frequency Arrays may be faster.