🎓 A1Learner
🔍
0 of 34 lessons completed

C++ Maps in Depth

Map search is the set of tools a map gives for finding pairs by their key. This lesson uses find, lower_bound, count, and erase, and shows what at does with a missing key.

find hits and misses

find returns a position when the key is present. The same call returns the end position when the key is absent, and the program prints a line for that case.

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

int main() {
  std::map<std::string, int> prices;
  prices["Pen"] = 3;
  prices["Notebook"] = 7;
  prices["Ruler"] = 4;
  auto hit = prices.find("Pen");
  if (hit != prices.end()) {
    std::cout << hit->first << " " << hit->second << "\n";
  }
  auto miss = prices.find("Glue");
  if (miss == prices.end()) {
    std::cout << "Glue not found" << "\n";
  }
  return 0;
}

lower_bound finds the next key

lower_bound looks for the first key that is not less than the probe. No key C sits in this map, so the search lands on the next key in sorted order.

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

int main() {
  std::map<std::string, int> ages;
  ages["Ana"] = 25;
  ages["Bo"] = 28;
  ages["Hana"] = 31;
  ages["Mina"] = 29;
  auto pos = ages.lower_bound("C");
  std::cout << "First not less than C: " << pos->first << "\n";
  return 0;
}

count answers present or absent

count gives 1 for a key in the map. count gives 0 for a key the map does not hold.

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

int main() {
  std::map<std::string, int> ages;
  ages["Ana"] = 25;
  ages["Bo"] = 28;
  ages["Hana"] = 31;
  std::cout << "Hana: " << ages.count("Hana") << "\n";
  std::cout << "Zoe: " << ages.count("Zoe") << "\n";
  return 0;
}

erase reports how many it removed

erase by key returns the number of pairs removed. A present key removes one pair, and an absent key removes none.

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

int main() {
  std::map<std::string, int> ages;
  ages["Ana"] = 25;
  ages["Bo"] = 28;
  ages["Hana"] = 31;
  std::cout << "Removed: " << ages.erase("Bo") << "\n";
  std::cout << "Removed: " << ages.erase("Zoe") << "\n";
  std::cout << "Size: " << ages.size() << "\n";
  return 0;
}

at with a missing key ends the program

This program asks at for a key the map does not hold. The program stops with an error, and the first line of that error is the output below.

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

int main() {
  std::map<std::string, int> prices;
  prices["Pen"] = 3;
  prices["Ruler"] = 4;
  std::cout << prices.at("Glue") << "\n";
  return 0;
}

Example

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

int main() {
  std::map<std::string, int> prices;
  prices["Apple"] = 2;
  prices["Banana"] = 1;
  prices["Cherry"] = 4;
  prices["Date"] = 3;
  auto found = prices.find("Banana");
  std::cout << found->first << " " << found->second << "\n";
  auto bound = prices.lower_bound("C");
  std::cout << "First not less than C: " << bound->first << "\n";
  std::cout << "Fig: " << prices.count("Fig") << "\n";
  return 0;
}

Key points

  • find gives a position for a key, or the end position when the key is absent.
  • Reading through a found position gives the key and the value of its pair.
  • lower_bound gives the first key that is not less than a probe key.
  • count gives 1 when a key is present and 0 when a key is absent.
  • erase by key removes a pair and returns how many pairs it removed.
  • at reads the value for a key and throws an error when the key is missing.

In this example, the price book holds four fruits in sorted key order. find reads the pair for Banana and prints its price of 1. lower_bound with the probe C lands on Cherry, and count answers 0 for the missing key Fig.

Note

A map keeps its keys in sorted order, so its search results follow that order.

Try it Yourself

Edit the code, then press Run.

Running is simulated

Exercise

A map holds the keys Ana, Bo, and Hana. What does lower_bound("C") give?