C++ · Intermediate

Maps and Sets in C++

In short: std::map stores key-value pairs sorted by key and std::set stores unique keys sorted, both as balanced trees with logarithmic insertion and lookup. Use a map to count, group or look things up by key, a set to track membership without duplicates, and their unordered_ cousins only when iteration order does not matter.

Sorted keys with fast lookup

A std::map<K, V> from <map> holds pairs with unique keys, arranged as a balanced binary search tree ordered by < on the key. Insertion, lookup and removal each take time proportional to the logarithm of the size, and iterating visits keys in sorted order, which is why the drink counts print alphabetically without a sort step. A std::set<K> from <set> is the same structure without values: a sorted collection of unique keys.

orders[drink] is the most convenient way to update a map: if the key is missing it is inserted with a value-initialised V (0 for int), and a reference to the value is returned, so ++orders[drink] counts in one line. The same convenience is a trap when reading, because extension["garage"] inserts a name that is not present. To look up without inserting use find, which returns an iterator to the pair or end(); count(key), which returns 0 or 1; or at(key), which throws std::out_of_range. The contains member exists only from C++20, so C++17 code uses count or find. insert({key, value}) refuses to overwrite an existing key and reports that through the second of the pair it returns; insert_or_assign (C++17) overwrites.

Elements of a map are std::pair<const K, V>: the key is const because changing it would break the tree's order. A C++17 structured binding, for (const auto& [name, count] : orders), names both halves at once. Through an iterator, it->first is the key and it->second the value.

std::set insertion also returns a pair: an iterator and a bool that is false when the key was already present, which the badge example uses to count repeat scans. Because elements are sorted, *s.begin() is the smallest, *s.rbegin() the largest, and lower_bound(x) finds the first element not less than x in logarithmic time. std::multiset and std::multimap are the variants that allow duplicate keys.

std::unordered_map and std::unordered_set, from headers of the same names, use a hash table instead of a tree: lookups take constant time on average, but the elements sit in an order that depends on the hash function and the table size and can change as the container grows. They are the right choice for pure lookup tables. Never print or otherwise depend on their iteration order; it differs between standard library implementations and between runs with different sizes.

Syntax

#include <map>
#include <set>

std::map<std::string, int> stock;        // key -> value, sorted by key
stock["bolts"] = 40;                      // insert or overwrite
++stock["nuts"];                          // inserts nuts -> 0, then increments
auto it = stock.find("nuts");             // iterator, or stock.end() if absent
if (it != stock.end()) it->second += 5;   // it->first is the key
stock.count("washers");                   // 0 or 1, never inserts
stock.erase("bolts");
for (const auto& [name, qty] : stock) { /* sorted by name */ }

std::set<int> ids;                        // unique keys, sorted
auto [pos, added] = ids.insert(42);       // added is false if 42 was present
ids.count(42);                            // 0 or 1
ids.erase(42);
for (int id : ids) { /* ascending */ }

Keys must support <, or you must supply a comparator as an extra template argument. std::string, numbers and std::pair all work out of the box.

Counting with a map

Drinks ordered at a counter, one word each until the input ends. The map counts them and the loop prints them in key order.

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

int main() {
    std::map<std::string, int> orders;     // drink -> how many times it was ordered
    std::string drink;
    while (std::cin >> drink) {
        ++orders[drink];                   // [] inserts the key with 0 if it is new
    }
    for (const auto& [name, count] : orders) {   // structured binding (C++17)
        std::cout << name << " " << count << "\n";
    }
    std::cout << orders.size() << " distinct drinks\n";
    return 0;
}

espresso 1
latte 3
mocha 1
tea 2
4 distinct drinks

The first time latte appears, orders["latte"] inserts it with 0 and the ++ makes it 1; later occurrences find the existing entry. No sorting code was written, yet the output is alphabetical, because a map's iteration order is its key order. The structured binding gives the pair's two halves readable names instead of first and second.

Looking up without inserting

A directory of phone extensions queried by room name. Compare what find does on a missing key with what [] does.

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

int main() {
    std::map<std::string, int> extension = {
        {"reception", 100}, {"kitchen", 214}, {"workshop", 305}
    };

    std::string query;
    while (std::cin >> query) {
        auto it = extension.find(query);          // does not insert
        if (it == extension.end()) {
            std::cout << query << ": not listed\n";
        } else {
            std::cout << query << ": dial " << it->second << "\n";
        }
    }
    std::cout << "size before: " << extension.size() << "\n";
    int x = extension["garage"];                  // creates garage -> 0 as a side effect
    std::cout << "garage lookup gave " << x << ", size now " << extension.size() << "\n";
    extension.erase("garage");
    std::cout << "count(garage) = " << extension.count("garage") << "\n";
    for (const auto& [room, ext] : extension) std::cout << room << "=" << ext << " ";
    std::cout << "\n";
    return 0;
}

kitchen: dial 214
garage: not listed
workshop: dial 305
size before: 3
garage lookup gave 0, size now 4
count(garage) = 0
kitchen=214 reception=100 workshop=305

find("garage") returns end() and the map is unchanged. extension["garage"] on the same missing key silently creates an entry with 0, which the size confirms; if this were a real directory a phantom room now exists. erase by key removes it again and count verifies. The map was initialised from a brace list in one order and iterates in another, sorted, order.

A set of unique badge ids

Badge ids scanned at a door, some more than once. The set keeps each id once, and the bool from insert reveals the repeats.

#include <iostream>
#include <set>

int main() {
    std::set<int> badges;                 // unique values, kept sorted
    int id;
    int scans = 0, repeats = 0;
    while (std::cin >> id) {
        ++scans;
        auto result = badges.insert(id);  // pair<iterator, bool>
        if (!result.second) ++repeats;    // false: the badge was already there
    }
    std::cout << scans << " scans, " << badges.size() << " people, "
              << repeats << " repeat scans\n";
    std::cout << "lowest " << *badges.begin() << ", highest " << *badges.rbegin() << "\n";
    auto it = badges.lower_bound(300);    // first badge >= 300
    if (it != badges.end()) std::cout << "first badge >= 300: " << *it << "\n";
    std::cout << (badges.count(150) ? "150 was here" : "150 was not here") << "\n";
    for (int b : badges) std::cout << b << " ";
    std::cout << "\n";
    return 0;
}

7 scans, 5 people, 2 repeat scans
lowest 99, highest 412
first badge >= 300: 305
150 was here
99 150 287 305 412

insert returns a pair whose second is false for the two badges that were already present, so repeats counts them without a separate lookup. Because the set is sorted, begin() and rbegin() are the extremes and lower_bound(300) jumps straight to 305 without scanning. The final loop shows the sorted, duplicate-free contents.

Which container?

Common mistakes

• Using [] to test whether a key exists

  Why it goes wrong: if (m[key] > 0) inserts key with a zero value when it is absent, so the map grows with every failed lookup and later iteration prints phantom entries.

  Fix: Test with count or find, and use [] only when inserting is the intent.

   C++ · fixCopy

  if (m.count(key)) { /* present */ }

• Calling [] on a const map

  Why it goes wrong: operator[] may insert, so it is not a const member; a function taking const std::map<K, V>& cannot use it and the compiler refuses the call.

  Fix: Use find or at on const maps.

• Printing an unordered_map in iteration order

  Why it goes wrong: The order depends on the hash function, the bucket count and the history of insertions; it is not sorted, not insertion order, and differs between library implementations.

  Fix: Use std::map when the output order matters, or copy the keys into a vector and sort them first.

• Expecting a map to remember insertion order

  Why it goes wrong: A map is ordered by key, always. The extension directory was written with reception first and iterates with kitchen first.

  Fix: If insertion order matters, keep a std::vector of keys alongside the map.

Where you use this

Counting is the signature use: word frequencies, votes per candidate, errors per source file. An index is the second: a map from customer id to record, from file name to contents, from a date to that day's sales, all answered in logarithmic time and printed in order. A set answers has-this-been-seen questions, removes duplicates from input in one pass, and its lower_bound finds the next appointment after a given time.

Grouping combines the two ideas: std::map<std::string, std::vector<std::string>> collects every item under its category and iterates the categories alphabetically. When the only operation is lookup by key and the table is large, switch to std::unordered_map for the constant-time average, keeping the ordered version whenever the output must be predictable.

std::set<std::string> seen;
for (const std::string& email : addresses) {
    if (seen.insert(email).second) {
        send(email);            // first time only
    }
}

Key points

• std::map<K, V> and std::set<K> keep keys sorted by < and answer lookups in logarithmic time.
• m[key] inserts a default value if the key is absent; use find, count or at to look up without inserting.
• insert returns a pair; its bool says whether a new element was added.
• Iterate a map with a C++17 structured binding: for (const auto& [k, v] : m).
• Keys are const inside the container; lower_bound finds the first key not less than a value.
• unordered_map and unordered_set are faster on average but have no usable iteration order.

Try it yourself

The program counts every word in the input. Change the printing loop so it prints only the words that appear more than once, each with its count, in alphabetical order.

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

int main() {
    std::map<std::string, int> seen;
    std::string word;
    while (std::cin >> word) ++seen[word];
    for (const auto& [w, n] : seen) {
        std::cout << w << " " << n << "\n";   // only when n > 1
    }
    return 0;
}

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

int main() {
    std::map<std::string, int> seen;
    std::string word;
    while (std::cin >> word) ++seen[word];
    for (const auto& [w, n] : seen) {
        if (n > 1) std::cout << w << " " << n << "\n";
    }
    return 0;
}

Practise this

Exercises for this lesson are in the C++ practice set.

Open the C++ playground

Related lessons

• Vectors in C++ (std::vector)How std::vector works in C++: creating and growing a vector, indexing with [] and at(), passing vectors to functions, erasing elements and building 2D grids.11 minCompleted
• Strings in C++Working with std::string in C++: reading lines and words, length, indexing, concatenation, find and substr, comparison, changing case and converting numbers.10 minCompleted
• Templates in C++How C++ templates generate a function or class for each type you use, how type deduction works, and what C++17 adds with if constexpr and deduction guides.11 minCompleted
• Stack, Queue and Priority Queue in C++How std::stack, std::queue and std::priority_queue work in C++, which element each returns next, how to build a min-heap, and when to use each adaptor.11 minCompleted

Frequently asked questions

How this page was checked. Every program on it was run with GCC 13 (C++17) at build time by the publishing checks, and the output shown is what it printed. Running C++ inside the browser is not available yet, so the Run button is absent rather than pretending; copy the code and run it with GCC 13 (C++17) locally.