двоичный_поиск с std :: pair с использованием пользовательского оператора

Я пытаюсь сделать двоичный_исследование, включающее вектор целочисленных пар и целое число следующим образом:

#include <vector>
#include <algorithm>
using namespace std;

typedef vector<pair<size_t,size_t> > int_pairs;

bool operator<(const size_t& l, const pair<size_t,size_t>& r)
{return r.first < l;} // useful for binary search

int main(){
int_pairs pairs_vec;
pairs_vec.push_back(pair <size_t,size_t>(1,2));
pairs_vec.push_back(pair <size_t,size_t>(2,2));
size_t i(2);
binary_search(pairs_vec.begin(),pairs_vec.end(),i);
}

Компилятор говорит мне, что operator< не определено:

erreur: no match for ‘operator<’ (operand types are ‘const long unsigned int’ and ‘std::pair<long unsigned int, long unsigned int>’)

Я делаю это правильно? Я пытался изменить определение оператора разными способами, но, похоже, ничего не получалось.

6

Решение

Причина этого не работает в том, что operator< не поднимается с точки, которую вы называете binary_search, а позже изнутри его тела — и это внутри пространства имен std,

поскольку std::pair уже определяет реляционные операторы в пространстве имен stdони скрывают вашу перегрузку в глобальной области видимости, и она никогда не будет найдена по имени.

Решение состоит в том, чтобы не использовать operator< совсем. Создайте свой собственный класс компаратора, который ни с чем не конфликтует, перегрузите его operator()и использовать другую перегрузку binary_search это позволяет вам указать пользовательский компаратор. Что-то вроде этого:

#include <vector>
#include <algorithm>
using namespace std;

typedef pair<size_t, size_t> my_pair;
typedef vector<pair<size_t,size_t> > int_pairs;

struct Comp {
// important: we need two overloads, because the comparison
// needs to be done both ways to check for equality

bool operator()(my_pair p, size_t s) const
{ return p.first < s; }
bool operator()(size_t s, my_pair p) const
{ return s < p.first; }
};

int main(){
int_pairs pairs_vec;
pairs_vec.push_back(pair <size_t,size_t>(1,2));
pairs_vec.push_back(pair <size_t,size_t>(2,2));
size_t i(2);
binary_search(pairs_vec.begin(),pairs_vec.end(),i, Comp());
}

Примечания стороны:

Ваша попытка operator< был неправ, потому что вы переключили порядок операндов внутри функции. Контракт для компараторов для строгого слабого заказа говорит, что он должен вернуть истину, если первый операнд предшествует второму (это относится ко всем функциям сравнения в стандартной библиотеке).

bool operator<(const size_t& l, const pair<size_t,size_t>& r)
{
return r.first < l; // Wrong!
}

И, как сказано выше в комментарии, если операнды для сравнения имеют разные типы, вам понадобятся две перегрузки. Проверить на равенство с <Вам нужно два теста:

(!(a < b) && (!b < a))
8

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector