c++ - 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 是我通常会使用的，但我需要指定一个比较函数。但是，数组成员的类型(struct foo)和搜索的值(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() 上:

Returns: The furthermost iterator i in the range [first, last] such that for any iterator j in the range [first, i) the following corresponding conditions hold: *j <
value or comp(*j, value) != false.

由此，你可以使用

bool comp(foo a, int b)

或者你可以比较两个 foo实例，然后访问 bar在他们两个中。