std :: lower_bound和比较器函数有不同的类型？

Question

我有一个结构数组,按结构的成员排序,如:

struct foo
{
    int bar;
    double baz;
};

// An array of foo, sorted on .bar
foo foos[] = { ........ };
// foos[0] = {0, 0.245}
// foos[1] = {1, -943.2}
// foos[2] = {2, 304.222}
// etc...

我想找到具有特定.bar值的元素.它可能会也可能不会在数组中,我想在O(log(n))时间内完成它,因为数组是排序的.

std::lower_bound我通常会这样做,但我需要指定一个比较函数.但是,array(struct foo)的成员类型和搜索的value(int)不一样,因此,我的比较器是:

bool comp(foo a, int b)
{
    // ...
}
// --- or ---
bool comp(int a, foo b)
{
    // ...
}

看起来第一个可以使用gcc,但我想知道比较函数的参数的顺序是否由标准指定,或者我是否依赖于编译器行为.

我想避免构建一个foo传递到std::lower_bound这里,因为foo不需要完整,并且可能是昂贵的.我的另一个选择是将foo *自定义迭代器包装在只暴露.bar成员的自定义迭代器中.

Answer 1

从标准25.3.3.1/3开始std::lower_bound():

返回:i范围中的最远迭代器,[first, last]以便对于范围中的任何迭代器j, [first, i)以下相应条件成立:*j < value或comp(*j, value) != false.

从那以后,你可以使用

bool comp(foo a, int b)

或者您可以比较两个foo实例,然后bar在两个实例中进行访问.