你可以在一个自定义类型的向量上应用二进制搜索吗？

Question

我做了一个叫做Point的类，它简单地包含了一个x y坐标的元组，我还做了一个Point类型的向量，并添加了点(3,4)。我也做了一个Point类型的向量，并添加了点(3,4)。现在我想用二进制搜索来搜索这个向量中的点，如果它返回true，那么我想打印 "yes"，以确认这个点存在于向量中。不幸的是，find函数不能在Point类型的向量上工作，如何解决这个问题？

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

class Point {
private:
        double xval, yval;
public:
        // Constructor uses default arguments to allow calling with zero, one,
        // or two values.
        Point(double x = 0.0, double y = 0.0) {
                xval = x;
                yval = y;
        }

        // Extractors.
        double x() { return xval; }
        double y() { return yval; }
};

int main()
{
    vector<Point> points;
    points.push_back(Point(3,4));
    if (binary_search(points.begin(),points.end(),Point(3,4)))
    {cout<<"The point exists"<<endl;}

    return 0;
}

Answer 1

向量应该是排序的，你应该提供相同的比较器到 std::binary_search.

要么提供

bool operator < (const Point& lhs, const Point& rhs)
{
    return std::tuple(lhs.x(), lhs.y()) < std::tuple(rhs.x(), rhs.y());
}

或自定义比较器

auto comp = [](const Point& lhs, const Point& rhs){
    return std::tuple(lhs.x(), lhs.y()) < std::tuple(rhs.x(), rhs.y());
};


if (binary_search(points.begin(), points.end(), Point(3,4), comp)) {/**/}

Answer 2

由于你有一个自定义类型的数组，你必须定义一个比较函数，以便告诉你应该遵循哪个标准来考虑一个元素比另一个大。有一个例子在 C++参考文献:

// binary_search example
#include <iostream>     // std::cout
#include <algorithm>    // std::binary_search, std::sort
#include <vector>       // std::vector

bool myfunction (int i,int j) { return (i<j); }

int main () {
  int myints[] = {1,2,3,4,5,4,3,2,1};
  std::vector<int> v(myints,myints+9);                         // 1 2 3 4 5 4 3 2 1

  // using default comparison:
  std::sort (v.begin(), v.end());

  std::cout << "looking for a 3... ";
  if (std::binary_search (v.begin(), v.end(), 3))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  // using myfunction as comp:
  std::sort (v.begin(), v.end(), myfunction);

  std::cout << "looking for a 6... ";
  if (std::binary_search (v.begin(), v.end(), 6, myfunction))
    std::cout << "found!\n"; else std::cout << "not found.\n";

  return 0;
}