C++: an ordered index with std::map

Answer range and nearest-key queries with lower_bound and upper_bound.

C++

#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";
}

Output

24 45
range 25..40: 29=Bo 31=Cy
below 30: 29, at or above 30: 31

Explanation

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.

Explore the dry run

Guided walkthroughReady

1#include <iostream>

2#include <iterator>

3#include <map>

4#include <string>

6int main() {

7 std::map<int, std::string> by_age = {{31, "Cy"}, {24, "Ada"}, {45, "Di"}, {29, "Bo"}};

9 std::cout << by_age.begin()->first << " " << by_age.rbegin()->first << "\n";

11 std::cout << "range 25..40:";

12 for (auto it = by_age.lower_bound(25); it != by_age.upper_bound(40); ++it) {

13 std::cout << " " << it->first << "=" << it->second;

14 }

15 std::cout << "\n";

17 auto above = by_age.lower_bound(30);

18 auto below = std::prev(above);

19 std::cout << "below 30: " << below->first << ", at or above 30: " << above->first << "\n";

20}

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

Prepared trace of the published program. Some rows group repeated iterations.
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

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.

C++: an ordered index with std::map

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading