15.6. The map class

A map refers to any data structure that maps keys to values. The standard-library map stores each key together with its mapped value in a std::pair.

The containers discussed so far have focused on storing one thing at a time. That is, each stores values of a single type. Maps add a new wrinkle. A map stores pairs of things. Traditionally, the pair stored is referred to as a key-value pair.[1]

Nearly every programming language provides some kind of map implementation. Some languages use the terms associative array or dictionary, but structurally, they are very similar.

Values are retrieved from a map using the key. Each key must be unique. In other words, keys are members of a set. Like a std::set, inserting a second node with the same key has no effect. The mapped value can be updated through operator[] or insert_or_assign. Unlike a std::set, a std::map provides the map::operator[].

The examples on this page use the following shared setup:

#include <iostream>
#include <functional>
#include <map>
#include <set>
#include <string>

std::map<std::string, int> sample_inventory() {
  return {
    {"apple", 12},
    {"kiwi", 4},
    {"lemon", 1},
    {"pear", 4},
    {"peach", 4},
    {"grape", 100},
    {"cocoa", 3}
  };
}

The following complete example demonstrates iteration, updating an existing mapped value, inserting through operator[], and checked access with at:

int main() {
  std::map<std::string, int> name_counts {
    {"Alice", 27},
    {"Bob", 3},
    {"Clara", 1}
  };

  for (const auto& kvp : name_counts) {
    std::cout << kvp.first << ": " << kvp.second << '\n';
  }

  name_counts["Bob"] = 42;       // update an existing value
  name_counts["Darla"] = 9;      // insert a missing key

  std::cout << "Bob is " << name_counts.at("Bob") << '\n';
  std::cout << "Darla is " << name_counts["Darla"] << '\n';
}

operator[] default-initializes a mapped value when the key is absent. Use at when a missing key should be reported instead; at throws std::out_of_range for an absent key. Neither operation changes the key ordering.

The map::insert function follows the same unique-key contract as set::insert: an equivalent key is not inserted and an existing mapped value is not overwritten. Use insert_or_assign when an update is intended.

C++17 Feature

C++17 added insert_or_assign and try_emplace for code that wants to state its insertion or update intent explicitly. insert_or_assign updates an existing mapped value, while try_emplace does nothing when the key already exists and constructs the mapped value only when needed.

int main() {
  auto inventory = sample_inventory();
  inventory.insert_or_assign("kiwi", 10);
  inventory.try_emplace("mango", 6);

  std::cout << inventory.at("kiwi") << ' '
            << inventory.at("mango") << '\n';
}

C++20 Feature

C++20 added map::contains for membership checks when the mapped value is not needed.

int main() {
  const auto inventory = sample_inventory();
  std::cout << std::boolalpha
            << inventory.contains("kiwi") << ' '
            << inventory.contains("mango") << '\n';
}

C++20 Feature

C++20 also provides std::erase_if for removing map entries based on their key-value pairs.

int main() {
  auto inventory = sample_inventory();
  std::erase_if(inventory, [](const auto& entry) {
    return entry.second < 5;
  });

  for (const auto& entry : inventory) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
}

15.6.1. Selected map functions

Access and assignment

at and operator[], insert_or_assign

Capacity

empty, size, and max_size

Modifiers

clear, emplace, insert, try_emplace, erase, and swap

Lookup

count, find, equal_range, upper_bound, lower_bound, and contains

For an ordered map, lookup, insertion, and erasure take \(O(\log N)\) time and the container uses \(O(N)\) storage. A sequential container may be faster for small data sets or workloads that benefit from contiguous storage, so the choice should be based on the operations the program needs.

Note

There is no push_back() for a map.

The map decides where elements go, not you. All access requires either knowing the key or having an iterator.

15.6.2. Map structure

Internally, a map is an ordered tree-like structure. Implementations often use a self-balancing tree such as a Red-black tree; the standard does not require a particular implementation. Each node in the tree is a std::pair.

Map entries are ordered by their keys, using a comparison object that defines a strict weak ordering. The default comparison uses operator<, but the map constructor can receive a custom comparator, just as with a set.

The map's value_type is a pair whose first member is const. A key cannot be changed through an iterator because that could violate the ordering invariant, but the mapped value can be changed.

All map entries are visited in key order according to the map's comparison object. By default, that is ascending order according to operator<. The following example extracts keys into a set and then uses upper_bound to find the first key greater than "kiwi".

int main() {
  const auto inventory = sample_inventory();
  std::set<std::string> inventory_keys;

  for (const auto& entry : inventory) {
    inventory_keys.insert(entry.first);
  }

  std::cout << "All fruit keys:\n";
  for (const auto& key : inventory_keys) {
    std::cout << key << ' ';
  }

  std::cout << "\nKeys greater than kiwi:\n";
  for (auto it = inventory.upper_bound("kiwi");
       it != inventory.end();
       ++it) {
    std::cout << it->first << ' ';
  }
  std::cout << '\n';
}

Maps can use a custom comparator just like sets. This complete example stores the same entries in descending key order:

int main() {
  const auto inventory = sample_inventory();
  const std::map<std::string, int, std::greater<std::string>> reverse_inventory {
    inventory.begin(), inventory.end()
  };

  for (const auto& entry : reverse_inventory) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
}

15.6.3. Variations on std::map

The standard library provides related ordered and unordered containers:

multimap

A map in which duplicate keys are allowed.

unordered_map

A map of unique keys organized by a hash function, not by sorted order. Each key still maps to one mapped value. Added in C++11.

A key type needs a hash function and an equality predicate. The standard library provides these for many built-in and library types. For a user type, provide a std::hash<Key> specialization or a custom hash object, and provide equality through operator== or a custom equality object.

unordered_multimap

An unordered_map in which duplicate keys are allowed.

---

More to Explore

• Standard library containers

• std::map

• std::unordered_map

• Red-black tree on Wikipedia

Footnotes

[1]

Sometimes this is abbreviated as 'KVP'. On cppreference.com you'll see it shortened even further to just P