能否通过std::upper_bound实现std::map的高效部分搜索？

你之前的优化方案效率低的核心原因是std::map的迭代器是双向迭代器而非随机访问迭代器，泛型算法std::upper_bound对双向迭代器的复杂度是O(n)，无法利用红黑树的有序结构做二分查找。以下是不同场景下的可行方案：

方案1：C++23 标准无依赖最优方案（推荐） #

如果你可以使用C++23，直接替换std::map为std::flat_map即可完美解决问题：
std::flat_map底层是连续存储的有序数组，迭代器为随机访问迭代器，你原本写的范围upper_bound调用就会自动达到O(log m)（m为begin()到it_1的距离）的理想复杂度：

#include <flat_map>
#include <algorithm>

int main() {
  std::flat_map<int, char> data{{1, 'a'}, {2, 'b'}, {4, 'c'}, {5, 'd'}};
  int key_small = 1, key_big = 3;

  auto it_1 = data.upper_bound(key_big);
  // 这里的std::upper_bound是O(log distance(data.begin(), it_1))复杂度
  auto it_2 = std::upper_bound(data.begin(), it_1, key_small);

  // 后续操作逻辑不变
}

这个方案同时兼容find等其他范围操作，完全符合标准规范，无平台依赖。

方案2：传统std::map的兼容方案 #

如果必须使用传统std::map，当前C++标准没有提供支持范围查找的成员函数，两次调用成员upper_bound的复杂度为O(2logn)，在绝大多数场景下性能差异可以忽略，只有当map容量极大、且key_big远小于最大值时才有优化意义。

如果可以接受libstdc++专属实现（仅作为面试理论参考，不推荐生产环境使用），可以利用其红黑树底层的非公开接口实现范围查找，复杂度可以达到理论最优的O(log m)。

面试考点说明 #

这个问题的核心考察点有两个：

• 区分泛型算法std::upper_bound和std::map成员upper_bound的复杂度差异，明白双向迭代器对泛型算法的性能限制
• 利用key_small <= key_big的前置条件，推导出upper_bound(key_small)一定落在[begin(), it_1]区间内，从而得出理论上只需要O(log m)复杂度的结论

内容的提问来源于stack exchange，提问作者Solomon Jacobs