上限/下限没有像我预期的那样工作，无法理解为什么

Question

这是代码。结果我得到"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;
}

Answer 1

从std::lower_bound：

返回指向区域中第一个元素的迭代器[第一，最后(不比瓦尔少。

第一个元素(从向量的开头开始(不小于3是4，因此lower_bound返回4。

从std::upper_bound：

返回一个迭代器，该迭代器指向区域[first，last(中的第一个元素，该元素的比较大于val。

大于3的第一个元素(从向量的开头开始(是4的，因此upper_bound返回4。

造成这种混淆的原因是upper_bound返回大于给定值的第一个元素，因此通过对称性，我们期望lower_bound返回小于给定值的最后一个元素(从向量的开头开始(。但遗憾的是，std函数不服从这种"预期"的对称性。

Answer 2

知道std::equal_range()返回一对迭代器会更容易理解/记住std::lower_bound()和std::upper_bound()返回的内容，其中第一个迭代器等于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

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

Answer 3

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

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