使用 lower_bound 的结果作为 upper_bound 的参数（反之亦然）

Question

lower_bound returns 在不丢失排序顺序的情况下可以插入元素的排序向量中的最小位置属性。 upper_bound，最大值。考虑到这一点，是否有任何极端情况：

auto lower = std::lower_bound(vec.begin(), vec.end(), x);
auto upper = std::upper_bound(lower, vec.end(), y); // using lower, as opposed to vec.begin()
for (auto it = lower; it != upper; it++) { /* do work */ }

无法按预期执行？也就是说，不会访问范围 [x, y) 中的每个元素，其中 x < y?

我想知道这个优化（虽然很小）是否真的可行。

Answer 1

tl;dr - 是的，很好。

对于您的原始问题（上限和下限都在搜索相同的键 x），它已经内置为 std::equal_range。

特别注意段落

The returned range is defined by two iterators, one pointing to the first element that is not less than value and another pointing to the first element greater than value. The first iterator may be alternatively obtained with std::lower_bound(), the second - with std::upper_bound().

对于编辑后的问题 - lower_bound(x) .. upper_bound(y) 和 x <= y，先决条件略有变化。

原版只要求输入范围分区，与x比较。现在，我们要求将其与 x 和 y 进行比较分区。尽管如此，总排序仍然非常令人满意，因此假设您的 < 是正常的（即，它提供了所需的严格弱排序），您的排序向量将起作用。

使用 lower_bound 的结果作为 upper_bound 的参数（反之亦然）

Using the result of lower_bound as a parameter for upper_bound (or vice-versa)

c++

lower-bound