3

这是代码。结果我得到“4 4”。不明白为什么它不是“2 4”（根据上下界的定义）。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    vector<int> v = {1, 2, 4, 5};
    vector<int>::iterator s , f;
    s = lower_bound(v.begin(), v.end(), 3);
    f = upper_bound(v.begin(), v.end(), 3);
    cout << (*s) << " " << (*f);
    return 0;
}
4

3 回答 3

6

来自std::lower_bound：

返回一个迭代器，该迭代器指向范围 [first,last)中的第一个元素，该元素的比较不小于val。

不小于3is的第一个元素（从向量的开头开始）4因此lower_bound返回4.

来自std::upper_bound：

返回一个迭代器，指向范围[first,last)中比较大于val的第一个元素。

大于3is4并因此upper_bound返回的第一个元素（从向量的开头开始） 4。

这种混淆的原因是因为upper_bound返回大于给定值的第一个元素，因此通过对称性，我们期望lower_bound返回小于给定值的最后一个元素（从向量的开头）。但可惜的是，该std函数不遵守这种“预期”的对称性。

于 2018-08-21T18:20:32.423 回答
4

知道返回一对迭代器会更容易理解/记住什么std::lower_bound()并返回，其中第一个等于返回的，第二个等于返回的。std::upper_bound()std::equal_range()std::lower_bound()std::upper_bound()

因此，当使用参数调用它们时，这里有不同的情况4：

1 2 3 4 4 4 4 5 E
      |       |
      F       S    - first points to the first element, second to the one behind last, representing range which contains 4

1 2 3 4 5 E
      | |
      F S  same for one element

1 2 3 4 E
      | |
      F S  same as before, but 4 is the last element

1 2 3 5 E
      |
      F==S  first == second, which means range for elements equal to 4 is empty

1 2 3 E
      |
      F==S same as before but there is no element greater than 4

WhereE表示container.end()返回的内容 - 最后一个元素后面的迭代器。

于 2018-08-21T18:50:19.280 回答
3

lower_bound和的命名upper_bound很不幸，因为它会引起混淆。这些名称指的是搜索具有多个元素的序列时的结果，这些元素与您正在搜索的元素完全相同；lower_bound将迭代器返回到开头，并upper_bound在结尾返回一个。

当元素不是序列的一部分时，它们都会返回一个迭代器，指向大于您正在搜索的元素的第一个元素。end如果没有更大的，这可能是迭代器。

于 2018-08-21T18:21:00.650 回答