c++ - 使用 lower_bound 的结果作为 upper_bound 的参数(反之亦然)

Question

lower_bound 返回排序 vector 中可以插入元素的最小位置，而不会丢失排序顺序属性。 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 .尽管如此，总排序仍然非常令人满意，因此您的排序 vector 将在假设您的 < 的情况下工作。是理智的(即，它提供了所需的严格弱排序)。