C++: an ordered index with std::map
Answer range and nearest-key queries with lower_bound and upper_bound.
On this page
C++ std::map and iterators.
- Answer range and nearest-key queries with lower_bound and upper_bound.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
A database keeps an ordered index so it can answer range queries without scanning every row. std::map is a sorted associative container, usually implemented as a balanced tree, with O(log n) insertion and lookup. Its keys are always visited in order.
lower_bound(k) returns an iterator to the first key not less than k, and upper_bound(k) returns the first key greater than k. Together they select a range. std::prev of lower_bound(k) gives the largest key below k. Always check against begin() and end() before dereferencing in real code.
Code example
#include <iostream>
#include <iterator>
#include <map>
#include <string>
int main() {
std::map<int, std::string> by_age = {{31, "Cy"}, {24, "Ada"}, {45, "Di"}, {29, "Bo"}};
std::cout << by_age.begin()->first << " " << by_age.rbegin()->first << "\n";
std::cout << "range 25..40:";
for (auto it = by_age.lower_bound(25); it != by_age.upper_bound(40); ++it) {
std::cout << " " << it->first << "=" << it->second;
}
std::cout << "\n";
auto above = by_age.lower_bound(30);
auto below = std::prev(above);
std::cout << "below 30: " << below->first << ", at or above 30: " << above->first << "\n";
}24 45 range 25..40: 29=Bo 31=Cy below 30: 29, at or above 30: 31
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
#include <iostream>#include <iterator>#include <map>#include <string> int main() { std::map<int, std::string> by_age = {{31, "Cy"}, {24, "Ada"}, {45, "Di"}, {29, "Bo"}}; std::cout << by_age.begin()->first << " " << by_age.rbegin()->first << "\n"; std::cout << "range 25..40:"; for (auto it = by_age.lower_bound(25); it != by_age.upper_bound(40); ++it) { std::cout << " " << it->first << "=" << it->second; } std::cout << "\n"; auto above = by_age.lower_bound(30); auto below = std::prev(above); std::cout << "below 30: " << below->first << ", at or above 30: " << above->first << "\n";}Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Keys are stored in sorted order: 24, 29, 31, 45. | keys = 24, 29, 31, 45 | — | |
| begin() is the smallest key and rbegin() the largest. | keys = 24, 29, 31, 45 | 24 45 | |
| A range scan from the first key ≥ 25 up to the last key ≤ 40. | visits 29, then 31 | 24 45 range 25..40: 29=Bo 31=Cy | |
| above is 31, so the previous entry is 29. | below = 29, above = 31 | 24 45 range 25..40: 29=Bo 31=Cy below 30: 29, at or above 30: 31 |
Behind the scenes
How C++ processes this code
The C++ compiler produces a native executable. Execution enters main, where objects and function calls perform the work.
Cost and common mistakes
Lookup, insert, lower_bound, and upper_bound are O(log n); a range scan costs O(log n + k) for k results.
- Dereferencing end(), or calling std::prev on begin(), is undefined behaviour.
- std::map keys are unique. Use std::multimap for a non-unique index.
Try it yourself
How would you list ages 30 or older?
Reveal answer and reasoning
Iterate from by_age.lower_bound(30) to by_age.end(); that prints 31 and 45.