C++ 中 lower_bound() 的 comp 参数是什么?

问题描述 投票:0回答:1

我正在尝试为二分搜索方法创建自定义比较函数

lower_bound()
。我尝试阅读文档并搜索,但我无法弄清楚
comp
函数的参数应该如何排序。

首先,在常规二元参数

comp
中,哪一个是
val
(目标值),哪一个是向量中的项?

其次,我怎样才能包含更多的论点?

我有一个

vector<int>
。 我希望我的
comp
做的是获取
val
,减去向量项,如果结果大于整数
y
,则返回true(这不能作为全局变量来完成,因为它经常变化)。

我还想要另一个类似的

comp
来检查结果是否小于
x

我怎样才能构建这样的比较器?

请告诉我是否需要更多说明。我正在寻找的是如何构建比较器的解释。如果这样的教程(有非常清晰的解释)已经存在,请指出我,因为我的搜索没有产生任何有用的东西。

TIA。

编辑:同样,我已经阅读了文档。我不明白他们如何构建

comp
,所以请停止重复文档所说的内容。如果可以的话,请详细解释一下这个概念。我的问题不是缺乏搜索,而是缺乏理解搜索时发现的内容。

c++ stl comparison binary-search lower-bound
1个回答
0
投票

我希望我的 comp 做的是获取 val,减去向量项,如果结果大于整数则返回 true

y

std::lower_bound
及其参数
comp
的要求是向量按相同的
comp
顺序排序。这意味着
comp
必须对订单进行编码。

从技术上讲,您的

comp
正是这样做的。它将整数分为两组:“大于 y”和“不大于 y”。换句话说,y 等于 y-1,y+1 等于y+2。这就是你所说的
std::lower_bound

如果你的向量是这样排序的,那么就不存在未定义的行为。

std::lower_bound
将返回一个迭代器到向量的正确一半。对于
val<=y
,它将是迭代器进入较小的一半,对于
val>y
,它将在另一半中。

但这可能不是您想要的。您似乎正在努力解决的心理问题是,您尝试根据您认为应该返回的内容(返回

comp
)来定义
(x-val)<y
,而不是考虑向量顺序以及要查找的元素。

老实说,你的描述太模糊了,我什至不知道你想找到哪个元素。鉴于

{1, 5, 9, 23}
y=6
,我不知道你想要哪个元素。

© www.soinside.com 2019 - 2024. All rights reserved.