C++: binary search compile error

Question

Hi:

I have the following lines of code:

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]))

And when I compile my code, I get the following errors:

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

I did #include <algorithm> in the beginning of the file and I can't seem to figure out the error. The following are the containers used in the function call:

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

Thanks.

Answer 1

In order to use binary search, your items must be comparable. R3Point doesn't have built-in comparison, that's the core reason.

Moreover, for using binary_search your list must be already sorted wrt the comparison operation.

Answer 2

You need to implement an operator < for your R3Point class. The binary_search() function will use this operator to determine how to find the target item.

Answer 3

std::binary_search uses a predicate function to compare entries. That's operator < by default, so you need to overload this op for R3Point.

Keep in mind that the input range must be ordered by this op for std::binary_search to work properly (well, that's the nature of a binary search).

See http://www.sgi.com/tech/stl/binary_search.html.

Answer 4

In order to use binary_search you input siquence must be sorted in accordance with certain comparison predicate. Later, this very same comparison predicate must be given (explicitly or implicitly) to binary_search to be used during searching.

So, the questions you should answer in this case are the following

1. Is the input sequence sorted? If it is not, you can stop right here. binary_search cannot be used with unordered sequences.
2. If it is sorted, then what comparison predicate was used to sort it? And how was it passed to the sorting function?

Once you know the comparison predicate and the passing approach, you can do the same with binary_search.

Note, that the comparison is not necessarily implemented through the operator <, as other answers might suggest. It could be a standalone functor-based comparison predicate, for example. Moreover, the fact that binary_search did not pick up the comparison predicate automatically (as would be the case with operator <) suggests the "standalone" approach.

Answer 5

If the R3Point is implemented by you, then you can add operator < for it.

Otherwise, you must implement a comparison functor, and assign it to binary_search.

Remember the following mark: Returns true if an element in the range [first,last) is equivalent to value, and false otherwise.

See here for more information: http://www.cplusplus.com/reference/algorithm/binary_search/