C++: an ordered index with std::map
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.
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";
}