在 upper_bound STL 中使用比较器

Question

我想做一个程序，它能给你提供 最后一个元素 小于或等于我们给定的值。

根据 lower_bound 的定义，它给出了第一个大于或等于传递给我们的键值的元素。我创建了一个比较器函数

bool compare(int a, int b) {
    return a <= b;
}

这是在我的下界函数中传递的。

int largest_idx = lower_bound(ic, ic + n, m, compare)

在执行时，它给我的最后一个元素小于等于我的m（键值）。这不是和 lower_bound 的工作原理相反吗？Lower bound应该是给我第一个值进行比较，还是比较器真的改变了这个值？

Answer 1

如果你想把 "第一个 "变成 "最后一个"，你有两个选择。首先，你可以使用 std::upper_bound 然后取前一个元素（见下文）。其次，你可以使用 反向迭代器:

const auto pos = std::lower_bound(
    std::make_reverse_iterator(ic + n),
    std::make_reverse_iterator(ic), m, compare);

其中 compare 是

bool compare(int a, int b) {
    return b < a;
}

有了这个比较器。std::lower_bound() 返回指向第一个元素的迭代器，该元素不大于(=小于或等于) m. 在反转的范围上，这相当于返回指向原始范围中最后一个满足这个标准的元素的迭代器。

简单的例子。

int ic[] = {1, 3, 3, 5};
// pos
// m = 1    ^ 
// m = 2    ^
// m = 3          ^

我如何修改搜索条件（改变 <= 到别的东西）？)

std::lower_bound 找到范围内的第一个元素（被比较器分割成的 true, ..., true, false, ... false)，比较器返回 false. 如果您的标准可以用这种语言重新表述，您可以使用 std::lower_bound.

假设我们有一个范围 1 3 3 5 我们把 < 与 <= (你的版本) compare). 那么我们有。

        1 3 3 5
m = 2   T F F F
m = 3   T T T F
m = 4   T T T F

对于 m = 3 和 m = 4, std::lower_bound 将返回迭代器到 5，即过去的 3. 换句话说： std::lower_bound 默认 < 被替换为 <= 正是 std::upper_bound 默认 < 是。你可以通过以下方式推进结果迭代器 -1 来获取最后一个元素（但要注意拐弯抹角的情况，如 m = 0 在本例中）。)

如何改变我是要第一个元素还是最后一个元素？

它总是返回比较器返回的第一个元素。false. 你可以把范围反过来，或者找到你想找的那个元素后面的第一个元素。

Answer 2

比较器不能检查平等，使用小于。

另外，数据必须已经被排序，或者至少必须根据比较器进行分区。

参考 https:/www.cplusplus.comreferencealgorithmlower_bound