Lookup with std::map and std::set

A value per key

A std::map<std::string, int> looks a value up by key rather than by position. pages["Dune"] = 412; stores the number under that name, and pages["Dune"] reads it back. The key can be any type the language can order — text and numbers are the everyday choices.

Because the keys are kept in order, printing a map walks them in alphabetical order, which is why a map is a pleasant thing to print. A std::vector cannot do this at all: there, "find the record for Dune" is a loop over every item.

The one trap worth knowing

Reading a key that is not there with square brackets quietly creates it, with a default value of zero or empty text. That is the trap: pages["Nope"] prints 0 and leaves the map one entry larger, so a loop that reads keys will grow the map as it goes.

The honest read is find, which answers an iterator you compare against the map end: if it equals pages.end() there was no such key. Use square brackets when you mean "insert or read", and find when you mean "is it there, and what is its value".

pages.at("Dune") is the checked read: it returns the value when the key exists and throws std::out_of_range when it does not, without inserting anything. That is the third option between the inserting brackets and find, and the right one when a missing key is a bug in the program rather than a case to handle.

A set refuses repeats

A std::set holds keys and nothing else, at most one of each. Adding a value that is already there does nothing and changes nothing — the size stays the same. count answers 1 or 0, which reads well as "is it there", and erase removes a value if present.

Between them, a map and a set cover two very common jobs: counting things by name, and remembering which things you have already seen. Both are kept in order, and both are small enough that the whole of their useful surface fits on this page.

Keys have to be comparable

A map keeps its keys ordered, so the key type has to support <. Text and numbers do. A struct does not until you define the comparison, either as operator< or as a comparison object passed as a third template argument.

Without one, the compiler stops at the line that declares the map, and the error names the missing operator rather than the map — which is why it can take a moment to connect the two. The same requirement applies to a set, since a set is a map with the value standing in for the key.

A map, a set, and the trap

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

int main() {
    std::map<std::string, int> pages;
    pages["Dune"] = 412;
    pages["Emma"] = 474;

    std::cout << "Count: " << pages.size() << '\n';
    std::cout << "Missing: " << pages["Nope"] << '\n';
    std::cout << "After lookup: " << pages.size() << '\n';

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

    std::set<std::string> tags = {"novel", "classic"};
    tags.insert("novel");
    std::cout << "Tags: " << tags.size() << '\n';
    if (tags.count("novel")) {
        std::cout << "has novel\n";
    }
    return 0;
}

Counting, and the cost of a lookup

A std::map is usually a balanced tree, so a lookup takes time proportional to the logarithm of the size. A std::unordered_map is a hash table: a lookup is constant on average, but the keys come out in no particular order and the worst case is linear. Choose by whether you need order or speed, and do not assume the unordered version is faster on small data.

A map is a container of pairs, and the pair is what a loop sees: entry.first is the key and entry.second is the value. The key is what the container is ordered by, so never change it through an iterator; erase the entry and insert a new one instead. Changing a key in place breaks the structure that makes lookup fast.

A set is the same idea with the value standing in for the key. It answers membership, and it refuses repeats. Counting the distinct items in a list is one loop that inserts each item into a set and then reads its size.

Try these next

• Count how often each word appears in a sentence and print the counts in key order.
• Store names in a set, add a duplicate, and print the size before and after.
• Look up a key with find and print a fallback when it is absent.