17370845950

std::equal_range在有序序列中查找目标值的全部出现范围，返回[first, second)区间，first为首个不小于目标值的迭代器，second为首个大于目标值的迭代器；必须确保输入已排序，否则行为未定义。

std::equal_range 用来找一个值在有序容器中的所有出现位置范围

它返回一对迭代器：std::pair，其中 first 是第一个不小于目标值的迭代器（等价于 std::lower_bound），second 是第一个大于目标值的迭代器（等价于 std::upper_bound）。两者合起来，就框出了所有等于该值的连续元素区间。

必须用在已排序的序列上，否则行为未定义

这是最容易踩的坑：如果传入的 [first, last) 范围没排好序，std::equal_range 的结果完全不可靠，甚至可能崩溃。它不检查排序性，只按二分逻辑跑。

• 常见错误：对 std::vector 调用前忘了 std::sort(v.begin(), v.end())
• 注意：自定义比较器（如 std::greater）必须和排序时用的一致
• std::set、std::map 等关联容器天然有序，可直接用

和 lower_bound + upper_bound 手动组合相比，性能没优势但更简洁

从算法复杂度看，std::equal_range 是单次 O(log n) 二分查找，而分别调用 lower_bound 和 upper_bound 是两次 O(log n)，实际中编译器可能优化掉部分重复计算，但语义上 equal_range 更准确表达“我要整个相等区间”这个意图。

示例：

std::vector v = {1, 2, 2, 2, 3, 4, 4};
auto range = std::equal_range(v.begin(), v.end(), 2);
// range.first  → 指向索引 1（第一个 2）
// range.second → 指向索引 4（第一个 >2 的元素，即 3）
int count = std::distance(range.first, range.second); // 得到 3

返回值是 pair，别直接解引用 second 迭代器

range.second 指向的是“超出相等范围”的位置，它本身不指向目标值。解引用 range.second 可能越界（比如目标值在末尾，second == end()），或指向别的值。真正有效的元素范围是 [range.first, range.second)。

• 安全遍历写法：for (auto it = range.first; it != range.second; ++it)
• 不要写 *range.second，除非你先确认 range.second != v.end()
• 空范围时 range.first == range.second，此时 distance 为 0

C++ 标准库没有提供“自动计数”或“批量修改”接口，拿到 equal_range 后具体怎么处理那块区间，得自己写循环或配合 std::erase、std::replace 等操作 —— 这部分最容易被忽略，也是业务逻辑真正开始的地方。