Can you apply binary_search on a vector with custom Type?

user_12686179 0
Viewed 206

I have made a class called Point which simply contains a tuple of x y coordinates. I also made a vector of the Type Point and added the point (3,4). Now i want to search this vector for the point with binary search, and if it return true then i want to print "yes", to confirm that the point exists in the vector. Unfortunately, the find function doesnt work on a vector of type Point, how can fix this?

#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;
}
find search c++
2 Answers

Since you have a custom type array, you must define a comparing function in order to tell which criteria should be followed to consider an element greater than the other. There is an example in C++ Reference:

// 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;
}
user_71839480

The vector should be sorted, and you should provide same comparer to std::binary_search.

either provide

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

or custom comparer

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)) {/**/}
user_26845390
Related