std :: lower_bound和比较器函数有不同类型？ [英] std::lower_bound and comparator function with different types?

问题描述

我有一个结构数组，按照结构的成员排序，如：

I have an array of structures, sorted on a member of a structure, something like:

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））时间，因为数组是排序的。

I want to find the element with a specific .bar value. It might or might not be in the array, and I'd like to do it in O(log(n)) time, since the array is sorted.

code> std :: lower_bound 是我通常会去的，但我需要指定一个比较函数。但是，数组成员的类型（ struct foo ）和搜索的值（ int ）不是因此，我的比较是：

std::lower_bound is what I'd normally go for, but I need to specify a comparison function. However, the type of the members of the array (struct foo) and the searched value (int) are not the same, thus, my comparator is:

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

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

It looks like the first will work with gcc, but I was wondering if the order of the arguments to the comparison function was specified by the standard, or if I'm relying on compiler behavior.

我想避免构造一个 foo 传递到 std :: lower_bound code> foo 是不需要的，可能是昂贵的。我的另一个选择是将自定义迭代器中的 foo * 包装成只暴露.bar成员。

I'd like to avoid constructing a foo to pass to std::lower_bound here, as a full foo isn't required, and could be costly. My other option would be to wrap the foo * in a custom iterator that only exposed the .bar member.

推荐答案

从标准中，25.3.3.1/3，在 std :: lower_bound（）：

From the standard, 25.3.3.1/3, on std::lower_bound():

返回：范围中的最远的迭代器 i ，last] 这样的
，对于范围中的任何迭代器 j
[first，i ）以下
对应的条件保持： * j <
value 或 comp（* j，value）！= false 。

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 实例，然后 $ 。

or you may compare two foo instances and then access bar in both of them.

这篇关于std :: lower_bound和比较器函数有不同类型？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！