如何在C++的std::map中获取范围边界[x,y]的最近键迭代器？

要获取范围[x,y]里大于等于x的最小键和小于等于y的最大键，可以利用std::map的有序特性，结合lower_bound和迭代器操作实现：

1. 获取大于等于x的最小键 #

std::map::lower_bound(val)会返回第一个键值不小于val的元素迭代器，正好匹配“大于等于x的最小键”的需求：

std::map<int, char> m{ {-2,'B'}, {1, 'C'},  {2, 'A'}};
int x = -3;

auto it_ge_x = m.lower_bound(x);
// 此时it_ge_x指向键-2的元素（-2是第一个不小于-3的键）

如果it_ge_x == m.end()，说明map中所有键都小于x，不存在符合条件的键。

2. 获取小于等于y的最大键 #

针对“小于等于y的最大键”，需要根据lower_bound(y)的返回值分情况处理：

• 若lower_bound(y)返回m.end()：说明所有键都小于y，直接取map最后一个元素即可；
• 若lower_bound(y)指向的元素键不等于y：说明该元素是第一个大于y的键，前一个元素就是小于y的最大键；
• 若lower_bound(y)指向的元素键等于y：该元素就是目标键。

对应y=3的代码示例：

int y = 3;
auto it_le_y = m.lower_bound(y);

if (it_le_y == m.end()) {
    // 所有元素都小于y，取最后一个元素
    it_le_y = prev(m.end());
} else if (it_le_y->first != y) {
    // 当前元素大于y，取前一个元素
    it_le_y = prev(it_le_y);
}
// 此时it_le_y指向键2的元素

补充说明 #

你之前的代码中，upper_bound(-3)返回指向-2的迭代器是因为upper_bound(val)返回第一个大于val的元素，而-2是第一个大于-3的键，所以和lower_bound(-3)结果一致；lower_bound(3)返回end()是因为所有键都小于3，此时直接取prev(end())就能拿到最大的键2。

内容的提问来源于stack exchange，提问作者Gaurav K