C++: бинарный поиск компиляции ошибка

Question

У меня есть следующие строки кода:

if(std::binary_search(face_verts.begin(), face_verts.end(), left_right_vert[0]) && 
     std::binary_search(face_verts.begin(), face_verts.end(), left_right_vert[1])) 

И когда я компилирую мой код, я получаю следующие ошибки:

In file included from /usr/include/c++/4.4/algorithm:62, 
       from R3Mesh.cpp:10: 
/usr/include/c++/4.4/bits/stl_algo.h: In function ‘bool std::binary_search(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<R3Point*, std::vector<R3Point, std::allocator<R3Point> > >, _Tp = R3Point]’: 
R3Mesh.cpp:1335: instantiated from here 
/usr/include/c++/4.4/bits/stl_algo.h:2762: error: no match for ‘operator<’ in ‘__val < __i.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = R3Point*, _Container = std::vector<R3Point, std::allocator<R3Point> >]()’ 
/usr/include/c++/4.4/bits/stl_algo.h: In function ‘_FIter std::lower_bound(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<R3Point*, std::vector<R3Point, std::allocator<R3Point> > >, _Tp = R3Point]’: 
/usr/include/c++/4.4/bits/stl_algo.h:2761: instantiated from ‘bool std::binary_search(_FIter, _FIter, const _Tp&) [with _FIter = __gnu_cxx::__normal_iterator<R3Point*, std::vector<R3Point, std::allocator<R3Point> > >, _Tp = R3Point]’ 
R3Mesh.cpp:1335: instantiated from here 
/usr/include/c++/4.4/bits/stl_algo.h:2442: error: no match for ‘operator<’ in ‘__middle.__gnu_cxx::__normal_iterator<_Iterator, _Container>::operator* [with _Iterator = R3Point*, _Container = std::vector<R3Point, std::allocator<R3Point> >]() < __val’ 
make: *** [R3Mesh.o] Error 1 

Я сделал #include <algorithm> в начале файла, и я не могу понять ошибку. Ниже перечислены контейнеры, используемые при вызове функции:

vector <R3Point > face_verts; 
vector <R3Point > left_right_vert; 

Спасибо.

Answer 1

Для использования binary_search вы вводите siquence должно быть отсортировано по номеру в соответствии с определенным предикатом сравнения. Позже, этот самый предикат сравнения должен быть задан (явно или неявно) до binary_search, который будет использоваться во время поиска.

Таким образом, вопросы, которые вы должны ответить в данном случае являются следующие

1. отсортирован ли входная последовательность? Если это не так, вы можете остановиться прямо здесь. binary_search не может использоваться с неупорядоченными последовательностями.
2. Если он отсортирован, то какой предикат сравнения использовался для его сортировки? И как это было передано функции сортировки?

Как только вы знаете предикат сравнения и подход прохождения, вы можете сделать то же самое с binary_search.

Обратите внимание, что сравнение не обязательно осуществляется через operator <, как могли бы предложить другие ответы. Например, это может быть автономный предикат сравнения на основе функтора. Более того, тот факт, что binary_search не взял автоматический предикат сравнения (как в случае с operator <), предлагает «автономный» подход.

Answer 2

Чтобы использовать бинарный поиск, ваши товары должны быть сопоставимы. R3Point не имеет встроенного сравнения, это основная причина.

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

Answer 3

Вам необходимо ввести operator < для вашего класса R3Point. Функция binary_search() будет использовать этот оператор для определения того, как найти целевой объект.

Answer 4

std::binary_search использует функцию предиката для сравнения записей. Это operator < по умолчанию, поэтому вам нужно перегрузить этот op для R3Point.

Имейте в виду, что диапазон ввода должен быть упорядочен этим оператором std::binary_search для правильной работы (ну, это характер бинарного поиска).

См. http://www.sgi.com/tech/stl/binary_search.html.

Answer 5

Если R3Point реализован вами, то для этого вы можете добавить operator<.

В противном случае вы должны реализовать функтор сравнения и назначить его binary_search.

Запомнить the following mark:

Возвращает true если элемент в диапазоне [first,last) является эквивалентного к значению, и false в противном случае.