C++ Map

Lookup by key

A vector answers “what is at index 2?” A map answers “what value sits under this key?” The key might be a part name, a user id, or a word. You do not walk the whole list to find it.

Include <map>. The type is map<Key, Value>. This chapter usesmap<string, int>: a string key and an integer value. StudyGrid compiles these programs as C++17.

Insert with []

stock["nails"] = 40; creates the key if it is new, or replaces the value if it already exists. Reading stock["screws"] returns that integer. If you read a missing key with [], the map inserts it with a default value (0 for int). That surprise is why the next section uses count before you treat a key as present.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
  map<string, int> stock;
  stock["nails"] = 40;
  stock["screws"] = 12;
  cout << stock["nails"] << endl;
  cout << stock["screws"] << endl;
  return 0;
}

Output is 40 then 12.

insert and count

insert adds a pair when the key is new. If the key is already there, insert leaves the old value alone. That differs from [], which overwrites. count(key) returns1 when the key exists and 0 when it does not. A map never stores two copies of the same key, so the answer is never 2.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
  map<string, int> stock;
  stock.insert({"bolts", 8});
  stock.insert({"bolts", 99});
  cout << stock["bolts"] << endl;
  cout << stock.count("bolts") << endl;
  cout << stock.count("glue") << endl;
  return 0;
}

Output is 8, then 1, then 0. The second insert did not replace 8 with 99. There is still no "glue" key, so count is 0.

Iterate in key order

A range-for on a map visits each pair. item.first is the key. item.second is the value. std::map keeps keys sorted, so the loop is not “insertion order.” It is sorted order of the keys.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
  map<string, int> stock;
  stock["screws"] = 12;
  stock["nails"] = 40;
  stock["bolts"] = 8;
  for (auto item : stock) {
    cout << item.first << " " << item.second << endl;
  }
  return 0;
}

The three lines print as bolts, nails, screws — alphabetical, not the order you assigned. C++17 also lets you writefor (auto [key, value] : stock); first and second are enough here.

String keys, integer values

The pattern is the same for any key type that can be ordered. Strings are the usual choice for names. Integers work as keys too (map<int, string> for an id to a label). This listing tallies votes by candidate name.

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
  map<string, int> votes;
  votes["Ada"] = 0;
  votes["Linus"] = 0;
  votes["Ada"] = votes["Ada"] + 1;
  votes["Ada"] = votes["Ada"] + 1;
  votes["Linus"] = votes["Linus"] + 1;
  cout << "Ada " << votes["Ada"] << endl;
  cout << "Linus " << votes["Linus"] << endl;
  if (votes.count("Bjarne") == 0) {
    cout << "no Bjarne" << endl;
  }
  return 0;
}

Output is Ada 2, Linus 1, then no Bjarne.

Ordered map

std::map is an ordered map: keys stay sorted, lookup is logarithmic, and a loop is alphabetical (or numeric) by key. If you do not need that order and you want average constant-time lookup, C++ also hasunordered_map in <unordered_map>. This tutorial stays withstd::map.

When a map is the wrong tool

If you only have a list and you always walk it from the front, keep a vector. If you need unique values with no extra payload, a set is the smaller type: just the keys. That is the next chapter.