upper_bound 和 lower_bound 如何与 C++ 中的比较器一起使用？

Question

我只是想知道 C++ 标准库中的 lower_bound 和 upper_bound 函数如何使用比较器工作。使用 cppreference.com 中提供的文档，我无法理解它们实际上是如何工作的。例如

vector<int> arr = {1, 1, 2, 2, 3, 3, 4, 4, 5, 5};

auto it1 = lower_bound(arr.begin(), arr.end(), 3, less<int>());
auto it2 = lower_bound(arr.begin(), arr.end(), 3, less_equal<int>());
auto it3 = lower_bound(arr.begin(), arr.end(), 3, greater<int>());
auto it4 = lower_bound(arr.begin(), arr.end(), 3, greater_equal<int>());
auto it5 = lower_bound(arr.begin(), arr.end(), 3, equal_to<int>());
auto it6 = lower_bound(arr.begin(), arr.end(), 3, not_equal_to<int>());

// Output in comments
cout << it1 - arr.begin() << endl;      // 4
cout << it2 - arr.begin() << endl;      // 6
cout << it3 - arr.begin() << endl;      // 0
cout << it4 - arr.begin() << endl;      // 10
cout << it5 - arr.begin() << endl;      // 6
cout << it6 - arr.begin() << endl;      // 4

auto it7 = upper_bound(arr.begin(), arr.end(), 3, less<int>());
auto it8 = upper_bound(arr.begin(), arr.end(), 3, less_equal<int>());
auto it9 = upper_bound(arr.begin(), arr.end(), 3, greater<int>());
auto it10 = upper_bound(arr.begin(), arr.end(), 3, greater_equal<int>());
auto it11 = upper_bound(arr.begin(), arr.end(), 3, equal_to<int>());
auto it12 = upper_bound(arr.begin(), arr.end(), 3, not_equal_to<int>());

cout << it7 - arr.begin() << endl;      // 6
cout << it8 - arr.begin() << endl;      // 4
cout << it9 - arr.begin() << endl;      // 10
cout << it10 - arr.begin() << endl;     // 0
cout << it11 - arr.begin() << endl;     // 4
cout << it12 - arr.begin() << endl;     // 6

对于 lower_bound 他们使用：(*it < val) [ (comp(*it, val)) for comparator]
对于 upper_bound 他们使用：(!(val < *it)) [ (!comp(val, *it)) for comparator) ]

有人可以解释他们使用比较器获得所有所需输出的工作吗？

Answer 1

std::lower_bound 要求相对于比较器对输入范围进行分区 - 也就是说，comp(element, value) returns true 的所有元素必须位于 true 的元素之前它 returns false。在您的示例中，只有使用 less 和 less_equal 的调用才能满足此要求；其他调用表现出未定义的行为。

std::upper_bound 要求输入范围根据表达式 !comp(value, element) 进行分区 - 同样，它 returns true 的所有元素必须先于它 returns false。在您的示例中，只有使用 less 和 less_equal 的调用才能满足此要求；其他调用表现出未定义的行为。

涉及 less 和 less_equal 的调用行为与记录的一样，并产生预期结果。

upper_bound 和 lower_bound 如何与 C++ 中的比较器一起使用？

How do upper_bound and lower_bound work with comparator in c++?

c++

std

comparator

lower-bound

upperbound