Skip to content
Tutorials Center
My learning

Topics

C++ Reference ยท Containers

C++ std::map class

Reference for std::map: sorted key-value pairs with unique keys, O(log n) lookup, ordered iteration, custom comparators, lower_bound and upper_bound.

std::map<Key, T> stores key-value pairs sorted by key. Keys are unique: inserting a key that already exists does not replace it. Lookup, insertion and removal take O(log n) time, and iterating from begin() to end() visits the pairs in ascending key order. It is typically implemented as a balanced binary search tree (a red-black tree in libstdc++).

Each element is a std::pair<const Key, T>: the key is const because changing it would break the ordering. Use std::map when you need sorted iteration, range queries (lower_bound, upper_bound), or iterators and references that survive insertions and erasures of other elements. For plain lookups, std::unordered_map is usually faster.

C++
#include <map>
std::map<std::string, int> age = {{"Ann", 31}, {"Bob", 25}};
age["Cy"] = 40;          // inserts

Try it

C++ Sorted iteration and structured bindings

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

C++ Range queries and a custom comparator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with std::cin or std::getline), it gets the next line from this box.

Syntax

C++
template <class Key, class T,
          class Compare = std::less<Key>,
          class Allocator = std::allocator<std::pair<const Key, T>>>
class map;

T& operator[](const Key& k);        T& at(const Key& k);
iterator find(const Key& k);        bool contains(const Key& k) const;      // contains: C++20
size_type count(const Key& k) const;
iterator lower_bound(const Key& k); iterator upper_bound(const Key& k);
std::pair<iterator, iterator> equal_range(const Key& k);
size_type erase(const Key& k);      iterator erase(const_iterator pos);
Name Description
Key Key type. Must be comparable with Compare.
T Mapped (value) type.
Compare A strict weak ordering. Two keys are "equal" when neither is less than the other.
k The key to look up, insert or erase.

Returns: find returns end() when the key is missing; count returns 0 or 1; erase(key) returns how many elements were removed; lower_bound returns the first element with key not less than k, upper_bound the first with key greater than k.

Errors / undefined behavior: at() throws std::out_of_range for a missing key. Dereferencing end() is undefined. A comparator that is not a strict weak ordering (for example <=) causes undefined behavior.

Usage notes

  • operator[] inserts. m[k] creates a default-constructed value when k is missing, so reading with it changes the map and does not work on a const map. Use find, at or contains to look without inserting. See map access functions.
  • Complexity: find, insert, erase, lower_bound and operator[] are O(log n); iteration is O(n) total; size() is O(1).
  • Stable iterators: inserting never invalidates iterators or references; erasing invalidates only those to the erased element.
  • Key equivalence, not equality: keys are compared only with Compare. A case-insensitive comparator makes "A" and "a" the same key.
  • Modifying keys: keys are const. To rename a key, extract the node (extract, C++17) and change node.key(), or erase and re-insert. See node handles.
  • Heterogeneous lookup: with a transparent comparator such as std::less<>, you can look up a std::string key with a std::string_view without building a string (C++14 for find).
  • Memory: one node allocation per element; poor cache locality. A sorted std::vector of pairs or std::flat_map is more compact for read-mostly data.
  • Ordered, but not sortable: you cannot call std::sort on a map; the order is the key order.