C++ / STANDARD CONTAINERS
std::map and ordered key lookup
Use std::map to keep keys sorted, look them up without accidentally inserting, and answer range queries with lower_bound and upper_bound.
What you will learn
- Answer range and predecessor queries with lower_bound, upper_bound and equal_range
- Reach for find, at or contains when a missing key must not be inserted
- Write a strict-weak-ordering comparator, knowing it also defines key equivalence
- Erase safely while iterating with it = m.erase(it), and rely on stable references
Understanding std::map and ordered key lookup
std::map is an ordered associative container, in every real implementation a balanced binary search tree, and the invariant it maintains is that an in-order walk hands back keys in comparator order. Every lookup is a descent that compares your key against roughly log2(n) stored keys, so a million entries cost about twenty comparisons instead of one hash. The comparator is also the definition of key identity: two keys are the same key exactly when comp(a,b) and comp(b,a) are both false, which is why a case-insensitive comparator makes "Alpha" and "ALPHA" land in a single element.
That sortedness is the whole reason to accept the cost. lower_bound(k) returns the first element whose key is not less than k, upper_bound(k) the first strictly greater, and together they delimit a half-open range you can iterate; because map iterators are bidirectional, decrementing upper_bound(k) lands on the greatest key ≤ k. Predecessor, successor and everything-between queries like these have no counterpart in a hash table, which stores keys in an order no caller may depend on.
Each element lives in its own allocated node holding a std::pair<const Key, T>, and rebalancing only rewires pointers between nodes. Insertion therefore never moves existing elements: pointers, references and iterators to them stay valid, and only erase invalidates, only for the element removed. The Key half is const because editing a key in place would leave the node in the wrong position and silently break every later search, so renaming a key means erase plus insert, or extract and edit the node handle in C++17.
<iostream>
<map>
<stdexcept>
<string>
int main() {
std::map<std::string, int> pop{
{"oslo", 709}, {"bergen", 291}, {"trondheim", 213}, {"tromso", 77}
};
// in-order walk: keys come out sorted by std::less<std::string>
for (const auto& [city, thousands] : pop)
std::cout << city << ' ' << thousands << '\n';
// count/find only look; operator[] inserts a value-initialised int
std::cout << "count(stavanger) before: " << pop.count("stavanger") << '\n';
std::cout << "value via []: " << pop["stavanger"] << '\n';
std::cout << "count(stavanger) after: " << pop.count("stavanger") << '\n';
try {
pop.at("narvik");
} catch (const std::out_of_range&) {
std::cout << "at(narvik) threw out_of_range\n";
}
// half-open range query: every key in ["o", "u")
auto first = pop.lower_bound("o");
auto last = pop.lower_bound("u");
for (auto it = first; it != last; ++it)
std::cout << "in [o,u): " << it->first << '\n';
}
A std::map is a sorted tree, so lookup is a chain of key comparisons rather than a hash, and the order it maintains is itself queryable through lower_bound and upper_bound.
Worked examples
The comparator defines order and equality
A case-insensitive comparator collapses two spellings into one key, and std::greater reverses the traversal order.
<algorithm>
<cctype>
<functional>
<iostream>
<map>
<string>
struct CaseInsensitive {
bool operator()(const std::string& a, const std::string& b) const {
return std::lexicographical_compare(
a.begin(), a.end(), b.begin(), b.end(),
[](unsigned char x, unsigned char y) {
return std::tolower(x) < std::tolower(y);
});
}
};
int main() {
std::map<std::string, int, CaseInsensitive> m;
m["Alpha"] = 1;
m["ALPHA"] = 2; // equivalent key: assigns into the existing node
m["beta"] = 3;
std::cout << "size: " << m.size() << '\n';
for (const auto& [k, v] : m)
std::cout << k << " = " << v << '\n';
std::map<int, char, std::greater<int>> desc{{1, 'a'}, {3, 'c'}, {2, 'b'}};
for (const auto& [k, v] : desc)
std::cout << "desc " << k << " -> " << v << '\n';
}
Example explained
Line 1std::tolower is fed an unsigned char, since passing a negative char value to it is undefined.
Line 2m["ALPHA"] finds the existing element because neither spelling compares less than the other, so the value becomes 2 while the stored key text stays "Alpha".
Line 3size() is 2, not 3: the comparator decided the two keys are one key, and string equality never entered into it.
Line 4std::greater<int> makes the tree's in-order walk descend, so 3 comes out first.
Predecessor lookup with upper_bound
Finding the most recent event at or before a timestamp by stepping one position back from upper_bound.
<iostream>
<map>
<string>
int main() {
std::map<int, std::string> log{
{100, "boot"}, {250, "login"}, {400, "upload"}, {900, "shutdown"}
};
auto at_or_before = [&](int t) -> const std::string* {
auto it = log.upper_bound(t); // first key strictly greater than t
if (it == log.begin()) return nullptr; // nothing at or before t
--it; // last key <= t
return &it->second;
};
for (int t : {90, 100, 399, 1000}) {
const std::string* s = at_or_before(t);
std::cout << t << ": " << (s ? *s : "none") << '\n';
}
}
Example explained
Line 1upper_bound(100) skips the exact match at 100 and returns 250, so decrementing gives the element with key 100 rather than the one before it.
Line 2The it == log.begin() guard is required because decrementing begin() is undefined behaviour.
Line 3For t = 1000 upper_bound returns end(), which is still decrementable on a non-empty map because map iterators are bidirectional.
Line 4A hash-based map cannot answer this without scanning everything, since it keeps no order to step back through.
Insert without overwriting, and stable references
try_emplace, insert_or_assign, reference stability across insertion, and the safe erase-while-iterating form.
<iostream>
<map>
<string>
int main() {
std::map<std::string, int> votes;
auto [it1, fresh1] = votes.try_emplace("ada", 1);
auto [it2, fresh2] = votes.try_emplace("ada", 99); // key exists: nothing happens
std::cout << "fresh1=" << fresh1 << " fresh2=" << fresh2
<< " ada=" << it2->second << '\n';
votes.insert_or_assign("ada", 5); // overwrite on purpose
++votes["bob"]; // value-initialised 0, then incremented
std::cout << "ada=" << votes["ada"] << " bob=" << votes["bob"] << '\n';
int& ref = votes["ada"];
votes.emplace("zoe", 7); // no element is relocated
ref += 10;
std::cout << "ada after inserts=" << votes.at("ada") << '\n';
for (auto it = votes.begin(); it != votes.end(); ) {
if (it->second < 5) it = votes.erase(it);
else ++it;
}
for (const auto& [name, n] : votes)
std::cout << name << ' ' << n << '\n';
}
Example explained
Line 1try_emplace returns {iterator, bool}; the second call reports false, leaves the value at 1, and never even constructs the 99.
Line 2insert_or_assign makes the opposite choice, replacing the value and reporting whether the key was new.
Line 3ref stays usable after emplacing "zoe" because the new node is linked in beside the others, so ref += 10 edits the live element.
Line 4it = votes.erase(it) is the loop-safe form: erase invalidates only the removed iterator and returns its successor.
Important notes
Logarithmic lookup is a standard guarantee, but each step chases a pointer into a separate allocation, so when you never need order an unordered_map usually wins in wall-clock time.
Declaring std::map<std::string, int, std::less<>> enables heterogeneous lookup, letting find("literal") or find(a_string_view) compare directly instead of building a temporary std::string; contains is C++20, while try_emplace and insert_or_assign are C++17.
Common mistakes
Probing membership with if (m[key]) or reading a value through operator[]: it inserts the key with a value-initialised value, so the map silently grows and a later size() or iteration reports entries nobody added, and the same call refuses to compile on a const map.
Writing the comparator as return a <= b: that makes comp(a,a) true, so equivalent keys compare less than each other in both directions, the strict weak ordering requirement is violated, and the container enters undefined behaviour where find can miss keys that are present.
Writing m.erase(it); ++it; in a loop: erase invalidates that iterator, so incrementing it afterwards is undefined and typically yields garbage keys or a crash rather than skipping an element.
Try it yourself
Change, predict, then run
Build std::map<int, std::string> grades{{0,"F"},{60,"D"},{70,"C"},{80,"B"},{90,"A"}} and print the grade for scores 55, 60, 89 and 100 by calling upper_bound(score) and stepping the iterator back one. Then try score -1 and make the begin() case print "invalid" instead of stepping past the front.
Open the C++ workspaceCheck your understanding
You hold int& r = m["alpha"] from a std::map, then insert many new keys, which forces the tree to rebalance. What is true about r afterwards?
- r is still valid, because rebalancing only relinks nodes and never moves the stored pair
- r may dangle, because rebalancing can relocate elements to new memory
- r is valid only if the map was given enough capacity up front
- r now refers to whatever element ended up occupying that position in the tree
Show answer
Every map element is a separately allocated node holding pair<const Key, T>; rebalancing changes parent and child pointers, so the address of the pair never changes and r keeps naming the same value. The dangling option imports std::vector's rule, where reallocation genuinely moves elements, and the capacity option describes a container that reserves storage, which a node-based tree never does.