15.7. The map class

A map refers to any data structure that 'maps' keys to values. The map class is arguably the most popular container in the STL after vector.

All the containers discussed so far focused on storing 1 thing. 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 List, 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, adding a second node with the same key replaces the old value. Unlike a std::set, a std::map provides the map::operator[].

#include <iostream>
#include <map>
#include <string>

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 existing value
  name_counts["Darla"] = 9;       // insert a new value

  // get map values
  std::cout << "Alice is " << name_counts.find("Alice")->second << '\n';
  // or get the key iterator, then print
  auto it = name_counts.find("Alice");
  std::cout << "Alice is " << it->second << '\n';

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

15.7.1. Selected map functions

Access and assignment

operator=, at and operator[]

Capacity

empty, size, and max_size

Modifiers

clear, emplace, insert, erase, swap

Lookup

count, find, equal_range, upper_bound and lower_bound

For large data sets, the lookup functions in a map are faster than their counterparts in a sequential container such as vector.

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.7.2. Map structure

Internally, a map is a sorted complete binary tree. (Technically it is often implemented as a Red-black tree). Each node in the tree is a std::pair.

All nodes are sorted by their keys. Sorting is managed using operator< by default, but this can be configured in the map constructor using a custom compare function or class, just as with a set.

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

using std::string;

void print (std::set<string> keys) {
  for (const auto& key: keys) {
    std::cout << key << ' ';
  }
}

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

  std::set<string> inventory_keys;

  // extract keys from the inventory map
  for (const auto& i: inventory) {
    auto result = inventory_keys.insert(i.first);
    if (!result.second) std::cout << "no insertion\n";
  }

  std::cout << "All fruit keys:\n";
  print (inventory_keys);

  std::set<string> keys;
  auto it = inventory.upper_bound("kiwi");
  while(it != inventory.end()) {
    auto result = keys.insert(it->first);
    if (!result.second) std::cout << "no insertion\n";
    ++it;
  }
  std::cout << "\n\nAll fruit keys greater than 'kiwi':\n";
  print (keys);

}

Using a customer comparator, we can store map items in reverse order:

#include <functional>  // provides std::greater
#include <iostream>
#include <map>
#include <string>

using std::string;

// print inventories with different custom comparators
template <class Comparator>
void print (const string title, const std::map<string, int, Comparator>& x) {
   std::cout << title;
   for (const auto& kvp: x) {
     std::cout << kvp.first << ", " << kvp.second << '\n';
   }
}

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

  print ("Initial inventory:\n", inventory);


  // define a reverse ordered map
  // a lambda is not the best choice here
  const auto greater_than = [] (string lhs, string rhs) { return lhs > rhs;};
  std::map<string, int, decltype(greater_than)> reverse_inventory1 (greater_than);

  // but it works
  for (auto& i: inventory) {
    reverse_inventory1.insert(i);
  }
  print ("\n\nReverse inventory using lambda:\n", reverse_inventory1);


  // STL provides many basic operations wrapped in a std::function
  std::map<string, int, std::greater<string>> reverse_inventory2;
  for (auto& i: inventory) {
    reverse_inventory2.insert(i);
  }
  print ("\nReverse inventory using std::greater:\n", reverse_inventory2);

  return 0;
}

15.7.3. Variations on std::map

The STL provides 3 alternate forms of map class:

multimap

A map in which duplicate keys are allowed.

unordered_map

A map of unique key-value pairs stored based on the key object hash function. Added in C++11.

unordered_multimap

An unordered_map in which duplicate keys are allowed.

---

More to Explore

• STL containers library

• 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