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 ，但我似乎无法弄清楚出错误。以下是函数调用中使用的容器：

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

谢谢。

Answer 1

为了使用二分搜索，您的项目必须具有可比性。 R3Point 没有内置比较，这是核心原因。

此外，要使用binary_search，您的列表必须已经通过比较操作进行排序。

Answer 2

您需要为您的 R3Point 类实现一个运算符 <。 binary_search() 函数将使用此运算符来确定如何查找目标项。

Answer 3

std::binary_search 使用谓词函数来比较条目。默认情况下这是运算符<，因此您需要为R3Point重载此操作。

请记住，输入范围必须通过此操作进行排序，std::binary_search 才能正常工作（这就是二分搜索的本质）。

请参阅http://www.sgi.com/tech/stl/binary_search.html。

Answer 4

为了使用binary_search，您输入的序列必须根据特定的比较谓词排序。稍后，必须将这个完全相同的比较谓词（显式或隐式）提供给 binary_search 以便在搜索期间使用。

因此，在这种情况下您应该回答以下问题：

1. 输入序列是否已排序？如果不是，您可以在这里停止。 binary_search 不能与无序序列一起使用。
2. 如果已排序，那么使用什么比较谓词对其进行排序？它是如何传递给排序函数的？

一旦您了解了比较谓词和传递方法，您就可以使用 binary_search 执行相同的操作。

请注意，正如其他答案可能暗示的那样，比较不一定是通过运算符 实现的。例如，它可以是一个独立的基于函子的比较谓词。此外，binary_search 没有自动选取比较谓词（如 operator < 的情况）这一事实表明了“独立”方法。

Answer 5

如果R3Point是您自己实现的，那么您可以为其添加operator<。

否则，您必须实现一个比较函子，并将其分配给binary_search。

请记住以下标记：

如果[first,last)范围内的元素与值等价，则返回true，反之false > 否则。