1

lower_bound returns the minimum position in a sorted vector that an element can be inserted, without losing the sorted order property. upper_bound, the maximum. With this in mind, is there any edge case for which:

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 */ }

Would not perform as expected? That is, would not visit every element in the range [x, y), where x < y?

I wish to know if this optimization (albeit small) is actually viable.

4

1 回答 1

1

tl;博士 - 是的，没关系。

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

特别注意段落

返回的范围由两个迭代器定义，一个指向第一个不小于 value 的元素，另一个指向第一个大于 value 的元素。第一个迭代器也可以用 获得std::lower_bound()，第二个std::upper_bound()迭代器可以用 获得。

对于已编辑的问题 - lower_bound(x) .. upper_bound(y)with x <= y，前提条件略有变化。

原始版本仅要求输入范围相对于与 进行比较进行分区x。现在，我们要求将其与x和进行比较y。尽管如此，总排序仍然足以满足这一点，因此假设您<是理智的，您的排序向量将起作用（即，它提供了所需的严格弱排序）。

于 2015-09-25T17:06:39.437 回答