在上边界STL中使用比较器



我正试图制作一个程序,为最后一个元素提供小于或等于我们给定值的值。

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

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

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

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

在执行时,它给了我最后一个元素,它小于我的m(键值(。这不是与下界的工作原理相反吗?下限应该给我比较的第一个值,或者比较器真的改变了这个值吗?

如果你想把"first"变成"last",你有两个选项。首先,您可以使用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、…、truefalse、…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 = 3m = 4std::lower_bound将迭代器返回到5,即经过最后一个3。换句话说,用<=替换默认<std::lower_bound正是用默认<替换的std::upper_bound。您可以将生成的迭代器提前-1以获得最后一个元素(但要注意像本例中的m = 0这样的角点情况(。

如何更改我想要第一个元素还是最后一个元素

它总是返回比较器为其返回false的第一个元素。您可以反转范围,也可以查找要查找的元素后面的第一个元素。

比较器不得检查是否相等,使用小于。

此外,数据应已排序,或者必须至少根据比较器进行分区。

cf。https://www.cplusplus.com/reference/algorithm/lower_bound/

最新更新