c++中如何使用std::equal_range查找元素范围_c++有序序列查找【汇总】_技术教程

std::equal_range查找有序序列中所有等于给定值的元素构成的左闭右开区间；返回pair，first为lower_bound位置，second为upper_bound位置，要求比较器与排序时一致。

std::equal_range 在有序序列中查什么

std::equal_range 不是找“某个元素是否存在”，而是找“所有等于给定值的连续元素在有序序列中的左闭右开区间”。它返回一个 std::pair，其中 first 是第一个不小于目标值的位置（等价于 lower_bound），second 是第一个大于目标值的位置（等价于 upper_bound）。两者之间就是所有匹配元素的范围。

必须确保输入范围已按相同比较规则排序，否则行为未定义 —— 这不是函数能帮你检查的，编译器也不会报错，运行时可能返回错误迭代器甚至崩溃。

怎么调用 std::equal_range（含比较器细节）

最常用的是默认升序版本，但容易忽略自定义比较器必须和排序时一致。比如你用 std::sort(v.begin(), v.end(), std::greater()) 排了降序，那查的时候也得传 std::greater()，否则结果无效。

对 std::vector 升序排列：直接用 std::equal_range(v.begin(), v.end(), 42)
对自定义类型，比如 struct Person { int age; }; ，按 age 升序排过，则查 age=25 必须用 std::equal_range(v.begin(), v.end(), 25, [](const Person& a, int b) { return a.age —— 注意这个 lambda 只比较 Person 和 int，不能写成两个 Person
如果容器是 std::set 或 std::map，优先用成员函数 equal_range()（如 s.equal_range(42)），它通常比算法版本更快，且自动使用容器内部比较器

查不到元素时 equal_range 返回什么

当目标值完全不存在时，first 和 second 迭代器相等，指向该值“应该插入”的位置（维持有序性）。这不是错误，是正常行为。

std::vector v = {1, 3, 5, 7};
auto range = std::equal_range(v.begin(), v.end(), 4);
// range.first == range.second == iterator to 5
// 所以 range.second - range.first == 0 → 没有 4

判断是否找到元素，别用 range.first != v.end()，而要看长度：if (range.first != range.second)。因为即使没找到，first 也可能合法（比如插在末尾前），但只要两者相等，就说明无匹配项。

性能与边界注意事项

std::equal_range 是 O(log n) 时间复杂度，底层用两次二分查找。但它不会做任何额外分配或拷贝，纯迭代器操作 —— 所以只要迭代器合法，它就很轻量。

对 std::list 使用会退化成 O(n)，因为不支持随机访问；此时应改用 std::forward_list 配合 std::lower_bound + 手动扫描，或换容器
迭代器失效风险：若在查找过程中另一线程修改了容器（如 push_back、erase），结果未定义。多线程下需加锁或用并发安全容器（如 tbb::concurrent_vector，但其不支持 equal_range）
浮点数慎用：用 == 判断相等本身就不稳定，equal_range 基于严格弱序，若比较器用 std::abs(a - b) 会破坏传递性，导致结果不可靠