Debugging lab: map and set pitfalls

Why this matters

Most map and set bugs do not crash when you write them. The program compiles, runs, and prints numbers that look almost right. The bug shows up later, on a different computer, with a bigger input, or when a teammate adds one line. Learning to find these bugs on purpose saves a lot of time.

This lab gives you five small programs. Each one has a bug that comes from the way std::map, std::unordered_map or std::set works. For each program, you will see the code, the output, the cause, and the fix. The fixes use what the earlier lessons in this module covered: find, contains, erase with its return value, and the difference between ordered and unordered containers. The lesson does not teach those basics again.

Each bug is shown with real output from g++ 15 on Linux. The exact wording of an error message can change between compilers, but the cause does not.

How to run the lab

Compile each program with the same flags:

g++ -std=c++20 -Wall -Wextra -o program program.cpp
./program

The -Wall -Wextra flags turn on warnings. For some bugs, the program compiles and runs with no warning at all. For those bugs you need a second build with the debug mode of the standard library, which checks each iterator and each container operation while the program runs:

g++ -std=c++20 -Wall -Wextra -g -D_GLIBCXX_DEBUG -o program program.cpp
./program

The -D_GLIBCXX_DEBUG flag works with the GNU C++ library, which g++ uses by default on Linux. It makes the program stop with a message when it does something illegal, such as using an iterator that no longer points to a valid element. It runs slower, so use it for testing, not for the final program.

A debug build is not a replacement for thinking. It only reports the problems that run in your test. A bug on a path the test never takes stays hidden.

A method for these bugs

Each bug in this lab has the same shape: the program's output is wrong, or it is right by luck. The method below works on all five.

First, write down what you expected to see and what you saw. The difference tells you which part of the program to read. In bug 1, the expected entry count was 2 and the actual count was 4, so the search was for code that changes the map during a lookup.

Second, find every place the container is changed or read through an iterator. Look at each [], each erase, each insert, and each find. Write the kind of result each one returns: a reference, an iterator, end(), or a bool.

Third, ask what the code assumes. Does it assume a key exists, that the iterator still points to an element, or that the loop visits the keys in a certain order? A wrong assumption is the usual cause.

Fourth, make a small program with only the suspicious lines, and build it with the debug mode. The smaller the program, the easier the message is to read.

Fifth, after the fix, run the same debug build again, and print the container before and after the operation you changed.

Bug 1: a lookup that adds an entry

This program checks a small shop's stock. It should print the items that are in stock and leave the map alone.

#include <map>
#include <iostream>
#include <string>
 
int main() {
    std::map<std::string, int> stock = {{"apple", 3}, {"pear", 0}};
    for (const char* item : {"apple", "kiwi", "fig"}) {
        if (stock[item] > 0) {
            std::cout << item << " in stock\n";
        }
    }
    std::cout << "entries: " << stock.size() << "\n";
    for (const auto& [k, v] : stock) std::cout << k << "=" << v << "\n";
}

The output is:

apple in stock
entries: 4
apple=3
fig=0
kiwi=0
pear=0

The program has only two items in the map at the start, and it asks about two more names, kiwi and fig. After the loop the map has four entries. Nothing was added on purpose.

Why it happens

operator[] on a std::map or an std::unordered_map looks up the key, and if the key is missing, it inserts a new entry with a default value. For an int, the default value is 0. So stock[item] for kiwi inserts kiwi with the value 0, and the if then reads that new 0. The lookup changed the container.

The stock lines are correct, so the bug is easy to miss. Only the entry count and the printed map show it. In a larger program, the extra entries can make a later count or a later loop wrong.

The fix

Use contains to check for a key, and at to read a key that must exist. contains returns true or false and does not insert. at returns the value, and throws an exception if the key is missing. Here is the fixed loop:

for (const char* item : {"apple", "kiwi", "fig"}) {
    if (stock.contains(item) && stock.at(item) > 0) {
        std::cout << item << " in stock\n";
    }
}
std::cout << "entries: " << stock.size() << "\n";

The output is:

apple in stock
entries: 2

The fix uses contains first, so at is only called for a key that exists. The && checks the first condition, and skips the second when it is false, so the call to at never sees a missing key.

If a key must exist and it is missing, at throws an exception at the point of the mistake. The message depends on the container:

map: map::at
unordered_map: unordered_map::at

Those two lines come from a small test that catches the std::out_of_range exception and prints e.what().

The const version

If the map is passed as a const reference, operator[] is not allowed at all, because it might insert. The compiler stops you:

constmap.cpp:4:21: error: passing ‘const std::map<std::__cxx11::basic_string<char>, int>’ as ‘this’ argument discards qualifiers [-fpermissive]

The line return m["apple"]; is the cause. The compiler message says the function is not allowed to change the map, and operator[] would change it. Use m.at("apple") instead. A compile error like this is a useful warning, because it marks a lookup that could insert.

Bug 2: erasing while looping

This program removes every entry whose visit count is 0. The loop walks through the map from the first entry to the last, and calls erase for each match.

#include <map>
#include <iostream>
 
int main() {
    std::map<int, int> visits = {{1, 0}, {2, 5}, {3, 0}, {4, 7}};
    for (auto it = visits.begin(); it != visits.end(); ++it) {
        if (it->second == 0) {
            visits.erase(it);
        }
    }
    for (const auto& [k, v] : visits) std::cout << k << "=" << v << "\n";
}

Run in the normal way, the program crashed here. Both a plain build and a -O2 build ended with a segmentation fault and printed nothing:

(no output)

Now build the same file with the debug mode, as shown in the section on running the lab. The program stops, and the address after @ changes on each run:

/usr/include/c++/15/debug/safe_iterator.h:392:
...
Error: attempt to increment a singular iterator.
Objects involved in the operation:
    iterator "this" @ 0x7fffa5d35c30 {
      type = std::_Rb_tree_iterator<std::pair<int const, int> > (mutable iterator);
      state = singular;
      ...

The word singular means the iterator no longer points to any valid element.

Why it happens

erase(it) removes the entry that it points to, and frees its memory. After that call, it still holds the address of the freed entry. The loop then runs ++it, which reads the freed entry to find the next one. That read is illegal. The C++ standard says the iterator is invalid after the erase, so the program has undefined behaviour. Undefined behaviour means the program may do anything, including print the right answer by luck or crash.

The normal build can crash, as it did here, or print the right answer. What it does depends on what the freed memory still holds. A different run, a different compiler, or a bigger map can give a different result.

Be careful with the address sanitizer, a tool that g++ can turn on with -fsanitize=address to catch bad memory use. In my run, it did not report this program at all, and it did report a plain use-after-free in a short test. Use the debug mode for iterator bugs.

The fix

erase returns an iterator to the entry after the one that was removed. Store that iterator, and move forward only when nothing was erased:

for (auto it = visits.begin(); it != visits.end(); ) {
    if (it->second == 0) {
        it = visits.erase(it);
    } else {
        ++it;
    }
}

The output is the same as before, and the debug build runs without a message. The loop has no ++it in its header, because the increment now happens in the else branch. A common mistake is to keep the ++it in the header, which moves the iterator twice after an erase.

Bug 3: assuming the order

This program stores a few fruit prices in an std::unordered_map, then prints them. The author expected them to come out in sorted order.

#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
 
int main() {
    std::unordered_map<std::string, int> u;
    for (const char* k : {"pear", "apple", "fig", "kiwi", "banana"}) u[k] = 1;
    for (const auto& [k, v] : u) std::cout << k << " ";
    std::cout << "\n";
    std::map<std::string, int> m(u.begin(), u.end());
    for (const auto& [k, v] : m) std::cout << k << " ";
    std::cout << "\n";
}

The output is:

banana kiwi fig apple pear 
apple banana fig kiwi pear 

The first line is the order that the unordered_map gave. The second line is sorted, because std::map keeps its keys in order.

Why it happens

An unordered_map stores its entries in buckets. The order of the buckets depends on a hash function, which turns each key into a number. The library decides the hash function and the number of buckets, and it can change them when the map grows. The order you see when you loop is not part of the contract. It can differ between compilers, versions, and runs with different keys or sizes.

A std::map is a tree that keeps the keys in order by the comparison function. Its loop always visits the keys from smallest to largest, using the default std::less.

The bug is in the test, not in the map. If a test compares the printed output with an expected text, it passes on one machine and fails on another. The code may look right, and the test may pass for months, until the library changes its hash function.

The order also changes as you edit the map. This small program prints the map after three inserts, after an erase and an insert of the same key, and after twenty more inserts:

#include <iostream>
#include <string>
#include <unordered_map>
 
void show(const std::unordered_map<std::string, int>& m) {
    for (const auto& [k, v] : m) std::cout << k << " ";
    std::cout << "\n";
}
 
int main() {
    std::unordered_map<std::string, int> u;
    u["pear"] = 1; u["apple"] = 2; u["fig"] = 3;
    show(u);
    u.erase("apple");
    u["apple"] = 4;
    show(u);
    for (int i = 0; i < 20; ++i) u["item" + std::to_string(i)] = i;
    show(u);
}

The output is:

fig apple pear 
fig apple pear 
item17 item16 item14 item12 item11 item18 item15 item10 pear item13 apple item0 fig item9 item4 item1 item6 item19 item5 item3 item8 item2 item7 

The first line is not in insertion order. The key pear went in first, but it comes out last. The erase and insert of apple did not change the order in this run, yet the twenty extra inserts scrambled everything. A loop that depends on the order can work for three keys and fail for thirty.

The fix

If the output must be sorted, make it sorted. Either use std::map, or copy the entries into a vector and sort the vector. The second choice keeps the fast lookups of unordered_map:

#include <algorithm>
#include <utility>
#include <vector>
 
std::vector<std::pair<std::string, int>> rows(u.begin(), u.end());
std::sort(rows.begin(), rows.end());
for (const auto& [k, v] : rows) std::cout << k << "=" << v << "\n";

With the map from the first program, the output is:

apple=1
banana=1
fig=1
kiwi=1
pear=1

That output is in sorted order on every compiler, because the sort decides the order, not the hash table. The vector holds pair values, and std::sort compares pairs by the key first, so the keys decide the order.

Use std::map or std::set when the code needs an order from the start, such as when it finds the smallest or largest key. Use unordered_map and unordered_set when only lookup speed matters.

Bug 4: reading the end iterator

find returns an iterator to the entry, or to end() when the key is missing. The end() iterator is a marker past the last element. It does not point to any entry. Reading through it is illegal.

#include <iostream>
#include <map>
#include <string>
 
int main() {
    std::map<int, std::string> names = {{1, "ann"}};
    auto it = names.find(2);
    std::cout << it->second << "\n";
}

A normal build of this program runs without an error message and prints nothing, not even a newline:

(no output)

The program has no way to show the right value, because the key 2 is not in the map. The code reads memory past the last entry. The value it prints depends on whatever happens to be in that memory.

With the debug mode, the program stops at the line that reads the value:

Error: attempt to dereference a past-the-end iterator.

The fix

Check the result of find before using it:

auto it = names.find(2);
if (it != names.end()) {
    std::cout << it->second << "\n";
} else {
    std::cout << "no name for 2\n";
}

Put the check next to the find call. The same rule applies to lower_bound and upper_bound, which can also return end().

Bug 5: changing an element of a set

A std::set keeps its elements in sorted order, and each element is its own key. If you could change an element in place, the set would break its own order. So the standard library makes the element read-only through the iterator.

#include <set>
 
int main() {
    std::set<int> s = {1, 2, 3};
    *s.begin() = 9;
}

The compiler stops with this error:

setmod.cpp:5:16: error: assignment of read-only location ‘s.std::set<int>::begin().std::_Rb_tree_const_iterator<int>::operator*()’

Why it happens

The element 1 sits at the front of the set. If you change it to 9 in place, the set holds 9 in front of 2 and 3, and every search that depends on the order goes wrong. The compiler blocks the write to protect that order.

The fix

Remove the old element, then insert the new one:

s.erase(1);
s.insert(9);

The set is sorted again after the insert, so s now holds 2, 3, 9. For a std::map, the key is also read-only, but the value is not, so m[key] = value or it->second = value is allowed. The rule is that you cannot change a key in place.

Common mistakes

Reading a count with operator[]. if (m[k] > 0) inserts k when it is missing. Use contains or find.

Erasing in a range-for loop. A range-for loop hides its iterator, so it cannot store the iterator that erase returns. Use an explicit loop with it = container.erase(it).

Using the old iterator after an insert into an unordered container. An insert can rehash the table, which moves the buckets. After a rehash, all iterators into an unordered_map are invalid, although references to an element stay valid. Store the key and look it up again after the insert.

Expecting a particular order from unordered_map. Sort the output, or use std::map.

Dereferencing end(). Always compare the result of find with end() first.

Trying to change a key. For std::set, erase and insert again. For std::map, change only the value.

Using a comparison that is not consistent. A comparison function must give the same answer for the same pair of keys every time, and it must treat "equal" as a single rule. If it does not, the search and insert in a map or set can break. This lab does not run that case.

Practice

Exercise 1: find the hidden insert

What does this program print?

#include <iostream>
#include <map>
 
int main() {
    std::map<int, int> m;
    m[5];
    std::cout << m.size() << "\n";
}

Show the answer

It prints 1. The expression m[5]; does not do anything with the value, but operator[] still inserts the key 5 with the value 0. The map has one entry.

Exercise 2: remove the even numbers from a set

Write a loop that removes every even number from a std::set<int> called s. Use the value that erase returns.

Show the answer

for (auto it = s.begin(); it != s.end(); ) {
    if (*it % 2 == 0) {
        it = s.erase(it);
    } else {
        ++it;
    }
}

With s holding 1 through 6, the loop leaves 1, 3 and 5. The erase call returns an iterator to the element after the removed one, so the loop never uses an invalid iterator.

Exercise 3: a missing key in a score table

A program stores scores in an std::unordered_map<std::string, int>. It looks up "ben", and prints the score. Ben has no score yet, and the program should print 0 without changing the map. Write the lookup.

Show the answer

auto it = scores.find("ben");
int score = (it != scores.end()) ? it->second : 0;
std::cout << score << "\n";

The find call does not insert anything, so the map keeps the same size. The conditional operator picks the stored value when the key exists, and 0 otherwise.

Exercise 4: a value read after an erase

This code is wrong. Explain why, then fix it.

std::unordered_map<int, int> m = {{7, 42}};
auto it = m.find(7);
m.erase(7);
std::cout << it->second << "\n";

Show the answer

The iterator it points to the entry for key 7. The call m.erase(7) removes that entry, so it is invalid. Reading it->second reads freed memory. The fix is to read the value first, then erase through the iterator:

auto it = m.find(7);
int v = it->second;
m.erase(it);
std::cout << v << "\n";

This prints 42, and the map is empty after the erase.

Exercise 5: remove the zero entries in one call

Remove every entry whose value is 0 from an std::unordered_map<int, int> called z, without writing a loop.

Show the answer

std::erase_if(z, [](const auto& p) { return p.second == 0; });

std::erase_if is a C++20 function for maps and sets. It calls the lambda for each entry, and removes the entries where it returns true. It does the iterator work for you, so no iterator can be left invalid.

Summary

• operator[] inserts a missing key, so use contains or find when you only want to look.
• Store the iterator that erase returns, and move forward only when nothing was erased.
• An unordered_map has no order you can rely on. Sort the output, or use std::map.
• Compare the result of find with end() before you read it.
• A set element cannot be changed in place. Erase it and insert the new value.
• Build with -D_GLIBCXX_DEBUG to find the iterator bugs that a normal build hides.