Why this matters
Most map programs loop over every item. They count words, print a report, remove expired entries or move items into another container. A loop like that looks simple, and it usually works, which is why beginners do not notice the two things that can go wrong.
The first thing is order. A std::map gives its items in sorted key order. A std::unordered_map gives them in an order that depends on how its internal table happens to be arranged. That arrangement is not something the C++ standard promises. A program that prints items in whatever order the loop reaches them can print a different order after a small change to the code, or after the map grows.
The second thing is change. If you insert or erase items while a loop is walking through the map, the loop's bookmark can end up pointing at an item that no longer exists or at an item the map has moved. The program may then skip items, visit one item twice, print wrong values or crash. The mistakes section shows real output from a crash and from a debug build that reports the bad step.
This lesson covers both points. It does not repeat the basics of the two containers, which the earlier lessons in this module cover, and it does not cover custom key types, which come in the lesson before this one.
The idea: a map has an order only if the container promises one
The two map containers in this module have different rules about order, and the difference is the first thing to remember.
A std::map keeps its keys sorted using operator<. The standard guarantees that a loop over the map visits the keys from smallest to largest. You can rely on it.
A std::unordered_map stores items in buckets, the slots of an internal array, as the hash lesson explained. A loop walks the buckets, so the order depends on the hash of each key and on how many buckets the table has. The standard makes no promise about this order. It can change when you insert an item that makes the table grow, and it can differ between two compilers or two versions of the same library.
Here is a program that shows both containers with the same keys:
#include <iostream>
#include <map>
#include <string>
#include <unordered_map>
int main() {
std::map<int, int> sorted;
for (int k : {5, 1, 3}) {
sorted[k] = k * 10;
}
std::cout << "std::map keys:";
for (const auto& [key, value] : sorted) {
std::cout << ' ' << key;
}
std::cout << "\n";
std::unordered_map<std::string, int> fruit;
for (const char* name : {"apple", "banana", "cherry", "date"}) {
fruit[name] = 1;
}
std::cout << "unordered_map keys (insert order apple, banana, cherry, date):";
for (const auto& [key, value] : fruit) {
std::cout << ' ' << key;
}
std::cout << "\n";
std::unordered_map<int, int> forward;
std::unordered_map<int, int> backward;
for (int k = 1; k <= 20; ++k) {
forward[k] = 0;
}
for (int k = 20; k >= 1; --k) {
backward[k] = 0;
}
std::cout << "forward keys:";
for (const auto& [key, value] : forward) {
std::cout << ' ' << key;
}
std::cout << "\n";
std::cout << "backward keys:";
for (const auto& [key, value] : backward) {
std::cout << ' ' << key;
}
std::cout << "\n";
}The output on g++ 15.2 with its standard library is:
std::map keys: 1 3 5
unordered_map keys (insert order apple, banana, cherry, date): date cherry banana apple
forward keys: 20 19 18 17 16 15 14 1 2 3 4 5 6 7 8 9 10 11 12 13
backward keys: 1 2 3 4 5 6 7 20 19 18 17 16 15 14 13 12 11 10 9 8The std::map output is sorted, as the standard requires. The std::unordered_map output is not sorted. Its order for the fruit names is the reverse of the insert order, but that is a coincidence of the hash values and the bucket count. The two integer maps hold the same twenty keys, yet they print in different orders because they were filled in different orders and grew through different steps.
Look at the middle of the forward output. The numbers 14 to 1 come before 2 to 13. The table grew as the keys went in, and each growth step moved the keys to new buckets. The final order reflects where the keys ended up, not the order you inserted them in.
So treat the order of an unordered map as random. Do not write a test that expects a particular order, and do not write output that a reader expects to be sorted unless you sort it yourself.
Example 1: sort the keys before printing
When you need a sorted report from an unordered map, copy the keys into a vector and sort the vector. The map stays fast for lookups, and the report is in order.
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
std::unordered_map<std::string, int> words{{"pear", 2}, {"apple", 5}, {"fig", 1}, {"kiwi", 0}};
std::vector<std::string> names;
for (const auto& [word, count] : words) {
names.push_back(word);
}
std::sort(names.begin(), names.end());
for (const auto& name : names) {
std::cout << name << "=" << words[name] << "\n";
}
}The output is:
apple=5
fig=1
kiwi=0
pear=2The loop over words collects the names in whatever order the table gives. The std::sort call puts them in alphabetical order. The second loop reads the values by name with words[name]. Every name is already in the map, so operator[] returns the stored value and does not add anything.
If you do not need the speed of an unordered map, use std::map instead. Then the order is correct without the extra vector.
What a loop does when the map changes
A range-based loop such as for (const auto& [key, value] : words) uses iterators behind the scenes. An iterator is an object that points at one item in a container, like a bookmark that remembers a page. The loop moves the bookmark forward one item at a time, and stops when it reaches the end.
Changing a container can make some of these bookmarks unusable. A bookmark that no longer points at a valid item is called invalid. Using an invalid iterator is undefined behavior. That term means the C++ standard does not say what happens. The program can crash, print wrong values, skip items, or appear to work. The result can change from one run to another and from one compiler to another, which makes these bugs hard to find.
Which iterators become invalid depends on the container and the change. The standard gives these rules for the two maps:
| Change | std::map | std::unordered_map |
|---|---|---|
| Insert one item | No iterator becomes invalid. | If the table grows, every iterator becomes invalid. |
| Erase one item | Only the iterator to that item becomes invalid. | Only the iterator to that item becomes invalid. |
Two details matter in practice. An insert into an unordered map does not always grow the table, so a loop that inserts may work for a while and then fail when the table grows. Also, the rules say that references and pointers to items stay valid across a rehash (the table rebuilding itself with more buckets) in both containers. Only iterators are at risk.
The next three examples use the rules above.
Example 2: insert into a std::map while looping
A std::map keeps its items sorted, so a new key is placed somewhere else in the order. The iterator in the loop is not affected by the insert. The loop will visit the new key if the new key comes after the current item. The example below relies on that rule, and it stops by checking the key value.
#include <iostream>
#include <map>
int main() {
std::map<int, int> chain{{1, 0}};
std::cout << "std::map, insert while looping:";
for (auto& [key, value] : chain) {
std::cout << ' ' << key;
if (key < 5) {
chain[key + 1] = 0;
}
}
std::cout << std::endl;
}The output is:
std::map, insert while looping: 1 2 3 4 5The loop starts at key 1. It inserts key 2, which comes after 1 in the sorted order, so the loop reaches it next. Key 2 inserts key 3, and so on up to key 5, which does not insert anything because key < 5 is false. The loop ends after printing 5. The new keys were visited because they came after the current position.
The same logic says that a key inserted before the current position is not visited in this loop. A beginner can confuse these two cases, which is why the example uses a key that is clearly after the current one. Do not rely on this pattern for real work. It is defined behavior for std::map, but it is hard to read, and it is easy to write a loop that never ends when the stop condition is wrong.
Notice that the example uses std::endl. The line is flushed to the terminal right away. This matters for the mistakes section, where a crash would otherwise hide the output printed before it.
Example 3: erase inside a loop, the right way
To remove items while looping, the loop must take the next iterator from the erase call. The erase function returns an iterator to the item after the one it removed. The loop then uses that iterator and does not move it again.
#include <iostream>
#include <map>
int main() {
std::map<int, int> scores{{1, 4}, {2, 7}, {3, 6}, {4, 9}, {5, 2}, {6, 8}};
for (auto it = scores.begin(); it != scores.end();) {
if (it->second % 2 == 0) {
it = scores.erase(it);
} else {
++it;
}
}
std::cout << "std::map after erasing even values:";
for (const auto& [key, value] : scores) {
std::cout << ' ' << key << '=' << value;
}
std::cout << std::endl;
}The output is:
std::map after erasing even values: 2=7 4=9When the value is even, erase removes the item and gives back an iterator to the next item, which the loop stores in it. The loop does not add one to it in that branch, because the value of it already points at the next item. When the value is odd, the loop moves on with ++it. The for loop has no step expression, so each branch moves the iterator exactly once.
C++20 gives a shorter way for the same job. The function std::erase_if works on both std::map and std::unordered_map:
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> counts{{1, 2}, {2, 3}, {3, 4}, {4, 5}};
std::erase_if(counts, [](const auto& entry) { return entry.second % 2 == 0; });
std::cout << "unordered_map after std::erase_if, size " << counts.size() << std::endl;
}The output is:
unordered_map after std::erase_if, size 2Two of the four entries have even values, so two entries are removed and two remain. Prefer std::erase_if when the condition is a simple test on each item. Use the iterator loop when the work for each item is longer than one test, for example when the removed item must be copied somewhere else first.
Example 4: move items between two maps
The third example combines the two patterns. It moves every low score from one unordered map into another. Inserting into inactive does not touch the loop over active, so the only container the loop changes is active.
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
std::unordered_map<std::string, int> active{{"ana", 80}, {"ben", 30}, {"cy", 45}, {"dee", 90}};
std::unordered_map<std::string, int> inactive;
for (auto it = active.begin(); it != active.end();) {
if (it->second < 50) {
inactive.insert(*it);
it = active.erase(it);
} else {
++it;
}
}
std::vector<std::string> left;
for (const auto& [name, score] : active) {
left.push_back(name);
}
std::sort(left.begin(), left.end());
std::vector<std::string> moved;
for (const auto& [name, score] : inactive) {
moved.push_back(name);
}
std::sort(moved.begin(), moved.end());
std::cout << "active:";
for (const auto& name : left) {
std::cout << ' ' << name;
}
std::cout << "\ninactive:";
for (const auto& name : moved) {
std::cout << ' ' << name;
}
std::cout << "\n";
}The output is:
active: ana dee
inactive: ben cyThe loop is the same shape as Example 3. The new part is inactive.insert(*it), which copies the key and value of the current item into the other map before erase removes it from active. The order of the two steps matters. If the item were erased first, *it would refer to a removed item.
The output is sorted by the two extra loops at the end. Without them, the names could come out in any order, as Example 1 showed.
Common mistakes
Using an iterator after erasing its item
The most common crash comes from calling erase on an item in a range-based loop. The range-based loop keeps its own iterator, which now points at a removed item. The next ++ step is the failure.
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> bad{{1, 1}, {2, 2}, {3, 3}, {4, 4}};
for (const auto& [key, value] : bad) {
if (value % 2 == 0) {
bad.erase(key);
}
}
std::cout << "bad loop finished, size " << bad.size() << std::endl;
}On the default build with g++ -std=c++20 -Wall, this program compiled without a warning. It ended with exit status 139, which means a segmentation fault. No line was printed, because the program stopped before it reached the output line. The crash is the program's way of saying that it read memory it should not use.
Building with the debug mode of the standard library shows the exact cause. The flag is -D_GLIBCXX_DEBUG, and the debug build checks each iterator step. This is what the run printed, cut to the important lines. The address after @ changes on each run:
Error: attempt to increment a singular iterator.
Objects involved in the operation:
iterator "this" @ 0x7ffe0265cc60 {A singular iterator is one that no longer points at a valid item. The message says the loop tried to move it with ++. The fix is Example 3: take the iterator from erase and do not add one to it again. Debug mode is a good habit to use while you test loops that change a container. It is slower, but it reports bad steps that the normal build may hide.
Inserting into an unordered map inside a loop over it
An insert into an std::unordered_map can make the table grow. When it grows, every iterator becomes invalid, so the loop's next step uses a bookmark that no longer matches the table. The following program inserts 100 keys the first time it visits an item.
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m{{0, 0}, {1, 1}, {2, 2}};
int visited = 0;
bool added = false;
for ([[maybe_unused]] const auto& entry : m) {
++visited;
if (!added) {
added = true;
for (int k = 100; k < 200; ++k) {
m[k] = k;
}
}
}
std::cout << "visited " << visited << " entries, size " << m.size() << std::endl;
}A map with three items should be visited three times, but the program printed this on g++ 15.2:
visited 28 entries, size 103The loop visited 28 entries, which is neither the three original items nor the 103 items now in the map. The standard does not say what should happen here, so this number is a symptom of undefined behavior and not a rule you can count on. The debug build printed the same line and did not stop, so debug mode does not catch every bad step either. The fix is the same as before: do not insert into the map inside the loop. Collect the keys you want to add into a vector, then insert them after the loop ends.
Reading with operator[] adds a key
The operator[] function returns the value for a key. When the key is missing, it inserts the key with a default value first. A loop that reads a missing key therefore changes the map. This program shows the effect:
#include <iostream>
#include <map>
#include <string>
int main() {
std::map<std::string, int> seen;
std::cout << "seen.size() before: " << seen.size() << "\n";
int value = seen["x"];
std::cout << "value read: " << value << ", size now " << seen.size() << "\n";
std::cout << "contains x: " << seen.contains("x") << "\n";
}The output is:
seen.size() before: 0
value read: 0, size now 1
contains x: 1The read added the key x with the value 0. If you only want to test whether a key is present, use contains or find. Those functions do not change the map. Use at when a missing key is an error, because at throws an exception instead of inserting.
Writing a test that expects a particular hash order
Suppose a test prints the words of an unordered map and compares the text with a stored copy. The test passes today, and fails after a change in the number of items, the hash function, or the library version. The fix is to sort before comparing, or to use a std::map when the order is part of the result. This is not a crash, so there is no error message to look for. It is the most common reason an unordered map appears to behave differently between two runs of a program that did not change.
Practice
Exercise 1
Write a program that counts the letters in the string "banana" using an std::unordered_map<char, int>. Print the counts sorted by letter.
Show the answer
#include <algorithm>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
std::unordered_map<char, int> counts;
for (char c : std::string{"banana"}) {
++counts[c];
}
std::vector<char> letters;
for (const auto& [letter, count] : counts) {
letters.push_back(letter);
}
std::sort(letters.begin(), letters.end());
for (char letter : letters) {
std::cout << letter << "=" << counts[letter] << "\n";
}
}The output is a=3, b=1, and n=2, one per line. The map is unordered, so the vector of letters is sorted before printing.
Exercise 2
Remove every entry with a value of 0 from an std::unordered_map<std::string, int> named stock, using a loop with an iterator. Do not use std::erase_if.
Show the answer
for (auto it = stock.begin(); it != stock.end();) {
if (it->second == 0) {
it = stock.erase(it);
} else {
++it;
}
}The erase call returns the iterator to the next item, and the loop stores it in it. The loop adds one only when nothing was erased.
Exercise 3
The loop below is meant to remove zero values from stock. Explain what goes wrong, and fix it.
for (auto& [name, count] : stock) {
if (count == 0) {
stock.erase(name);
}
}Show the answer
The loop keeps its own iterator to the item it is on. Erasing that item makes the iterator invalid, and the next step of the loop uses it. The result is undefined behavior, which here showed up as a crash. The fix is the iterator loop from Exercise 2, or std::erase_if(stock, [](const auto& entry) { return entry.second == 0; });.
Exercise 4
Why does the loop in Example 2 visit the keys 2 to 5 after inserting them, while the same idea on an std::unordered_map is unsafe?
Show the answer
A std::map is sorted, and inserting a key does not invalidate any iterator. So the loop's bookmark stays valid, and the loop reaches the new keys that come after it. An std::unordered_map can grow when an insert happens. A growth step invalidates every iterator, so the loop's next step uses a bookmark that is no longer valid. The result is undefined behavior, which can mean wrong output or a crash.
Exercise 5
Predict the order of the keys printed by a loop over an std::unordered_map<int, int> that holds the keys 1, 2 and 3, and explain whether your prediction is guaranteed.
Show the answer
No prediction is guaranteed. On one build the order may be 1, 2, 3, and on another it may be different. The standard does not promise an order for an unordered map. If the output must be in order, sort the keys first or use a std::map.
Summary
- A
std::mapvisits its keys in sorted order, as the standard guarantees. Astd::unordered_maphas no promised order. - Sort the keys into a vector before printing a report from an unordered map.
- An iterator is a bookmark into a container, and some changes make it invalid.
- To erase inside a loop, use
it = map.erase(it)and moveitforward only when nothing was erased. Or usestd::erase_iffor a simple test. - Inserting into an unordered map can grow the table and invalidate every iterator. Collect the new items and insert them after the loop.
- Reading with
operator[]adds a missing key. Usecontainsorfindto test for a key.