我正试图制作一个程序,为最后一个元素提供小于或等于我们给定值的值。
根据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
、…、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
的第一个元素。您可以反转范围,也可以查找要查找的元素后面的第一个元素。
比较器不得检查是否相等,使用小于。
此外,数据应已排序,或者必须至少根据比较器进行分区。
cf。https://www.cplusplus.com/reference/algorithm/lower_bound/