Finding the left-most and right-most points of a list. std::find_if the right way to go?

Question

Hi,

I have a list of Point objects, (each one with x,y properties) and would like to find the left-most and right-most points. I've been trying to do it with find_if, but i'm not sure its the way to go, because i can't seem to pass a comparator instance. Is find_if the way to go? Seems not. So, is there an algorithm in <algorithm> to achieve this?

Thanks in advance.

#include <iostream>
#include <list>
#include <algorithm>

using namespace std;

typedef struct Point{
        float x;
        float y;
} Point;

bool left(Point& p1,Point& p2)
{
        return p1.x < p2.x;

}
int main(){
        Point p1 ={-1,0};
        Point p2 ={1,0};
        Point p3 ={5,0};
        Point p4 ={7,0};

        list <Point> points;

        points.push_back(p1);
        points.push_back(p2);
        points.push_back(p3);
        points.push_back(p4);

        //Should return an interator to p1.
        find_if(points.begin(),points.end(),left);                                                  

        return 0;
}

Answer 1

Use std::min_element and std::max_element instead.

list<Point>::iterator left = std::min_element(points.begin(), points.end(), left);
list<Point>::iterator right = std::max_element(points.begin(), points.end(), left);

I would also change the signature of left to:

bool left(const Point& p1, const Point& p2)

Answer 2

If you use pair<float, float> instead of your own Point, there's no need for a special comparator. There would also be an ordering on the y-axis of points with the same x-coordinate, which can be useful.

There are various ways to imbue typedef pair<float, float> Point; with custom behavior, if you're so inclined. For example,

typedef pair<float, float> Point;

enum AxisUnit { x, y };
float &operator*( Point &p, AxisUnit c ) // "special case" of inner product
     { return c == x? p.first : p.second; }

Point my_point( 2.5, 6.3 );
float x_coord = my_point * x;

Answer 3

even better would be to use the boost minmax element:

http://www.boost.org/doc/libs/1_42_0/libs/algorithm/minmax/index.html

#include <boost/algorithm/minmax_element.hpp>
...
auto res = boost::minmax_element(points.begin(), points.end(), left);

std::cout << "min: " << res.first << std::endl;
std::cout << "max: " << res.second << std::endl;