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():

Возвращает : самый дальний итератор i в диапазоне [first, last] такой, что длядля любого итератора j в диапазоне [first, i) выполняются следующие соответствующие условия: *j < value или comp(*j, value) != false.

С этого момента вы можете использовать

bool comp(foo a, int b)

илиВы можете сравнить два foo экземпляра и затем получить доступ к bar в обоих.

Answer 2

Это действительно должен быть комментарий к посту Вильгельмтелла, но у меня пока недостаточно очков, чтобы сделать это ...

Я просто хотел отметить, что это также работает для компилятора MS, но вам нужно определить

comp(foo lhs, foo rhs)

в противном случае ваш код не будет компилироваться в режиме отладки.