Upper/lower 边界没有像我预期的那样工作，不明白为什么

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:

Returns an iterator pointing to the first element in the range [first,last) which does not compare less than val.

不小于 3 的第一个元素（从向量的开头开始）是 4，因此 lower_bound returns 4 .

来自 std::upper_bound:

Returns an iterator pointing to the first element in the range [first,last) which compares greater than val.

大于 3 的第一个元素（从向量的开头开始）是 4，因此 upper_bound returns 4。

造成这种混淆的原因是因为 upper_bound return 是第一个大于给定值的元素，所以根据对称性我们期望 lower_bound 到 return小于给定值的最后一个元素（从向量的开头开始）。但遗憾的是，std 函数不遵守此 "expected" 对称性。

Answer 2

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

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

Answer 3

知道 std::equal_range() return 是一对迭代器，understand/remember 什么 std::lower_bound() 和 std::upper_bound() return 会更容易，其中第一个等于std::lower_bound()returns，第二个等于std::upper_bound()returns.

因此，这里是使用参数 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() returns - 最后一个元素后面的迭代器。

Upper/lower 边界没有像我预期的那样工作，不明白为什么

Upper/lower bounds don't work as I expect, can not understand why

c++

lower-bound

upperbound