sorting vector with 3D points by a coordinate value -- syntax

Question

hi,

I want to sort points_vec vector as shown in the pseudocode below. I want to sort this vector, by a coordinate value like x or y or z

class A{

  std:vector<double*> points_vec;

  void doSomething();

}

Then, in method A::doSomething, I want sort this vector:

void A::doSomething() {
    std::sort(points_vec.begin(), points_vec.end(), sortPoints());
}

Can someone please show me syntax for the sortPoints() method.. Preferably I want it to be a method of class A. this post creates a struct to do this, not sure if I should create a similar struct within the class. Is there another way to handle this?

thanks

Answer 1

First of all - what you have will break all your points - as you'll sort by single doubles not by "points consisting of 3 doubles".

The best way to do this I think is:

1. Store the points as some Point3D class not a couple doubles
2. Define the less then operator for Point3D
3. Just call std::sort(points_vec.begin(), points_vec.end() );

If you'd want to sort them by in different ways that's when you'd use the sort functor and create different functors with operators() for different purposes.

Answer 2

The simplest way is to provide a functor which is used by the sort algorithm to compare two values. You can write like this:

struct Compare
{
  bool operator()(double* first, double* second) const
 {
   //Compare points here
 }
};

And use like:

std::sort(p.begin(), p.end(), Compare());

EDIT for comment by OP: Yes, this sample code compiles fine:

class A
{
public:
    struct c
    {
        bool operator()(int a, int b) const
        {
            return a < b;
        }
    };
};
int main()
{
    std::vector<int> a1;
    a1.push_back(2);
    a1.push_back(1);
    std::sort(a1.begin(), a1.end(), A::c());

    return 0;
}

Answer 3

You have two options for sorting: either pass a function/functor to sort or define the operator< for your class. Now, your class A seems to be more of a wrapper for a set of coordinates. So, create another class for your co-ordinates.

 struct Point {
     double x_, y_, z_;
     Point(double x, double y, double z) : x_(x), y_(y), z_(z) {}              
     // just an example, you can refine the following as much as you need
     bool operator<(Point const& other) {
         return x < other.x;
     }
 };  

 bool sortOnY(Point const& l, Point const& r) const {
      return l.y < r.y;
 }

 class A {
     std::vector<Point> pts_;
     void doSomething() {
          sort(pts_.begin(), pts_.end());
     }
     // if sorting on y is also required, you will need 
     // to use a custom comparator which can be either 
     // a functor or a function
     void doSomeOtherThing() {
         sort(pts_.begin(), pts_.end(), sortOnY);
     }
 };         

Answer 4

If you want to sort by x or y or z, those are three different functionalities. Which coordinate to sort by is extra information which doesn't really come from std::sort. You need have an object to pass it on.

struct coord_comparison {
    int coord_id; // <= critical information
    bool operator()( double (*l)[3], double (*r)[3] ) {
        return (*l)[ coord_id ] < (*r)[ coord_id ];
    }
    coord_comparison( int id ) { coord_id = id; }
};

Create this struct inside your class or outside, but it needs to be a structure and not a free function, and operator() cannot be static. Call:

std::sort(points_vec.begin(), points_vec.end(), compare_points( 1 /*for y*/) );

Sorting by all 3 coords at once:

You have

std:vector<double*> points_vec;

I'm going to presume that the double* points to an array of 3 coordinates. This is cleaner:

std:vector<double(*)[3]> points_vec;

std::sort's third argument is a functor which compares two sequence objects:

bool compare_coords( double(*l)[3], double(*r)[3] ) {

Fortunately, comparing two sequences is already coded for you by std::less:

    return std::less( *l, *l + ( sizeof *l/sizeof **l ), r );

(perhaps I did more work than necessary to get the size of the array)

    return std::less( *l, *l + 3, r );
}

This function may be useful outside the class, so I'd make it a free function. You need to make it static if it's going to stay inside the class.

Finally, leave off the parens when passing the function to std::sort:

std::sort(points_vec.begin(), points_vec.end(), compare_points );

Answer 5

I don't think this thread would be complete without a mention of Boost.Bind:

struct Point3D {
    double x, y;
    Point3D(double x=0., double y=0.) : x(x), y(y) {
    }
};

int main() {

    std::vector<Point3D> points;
    points.push_back(Point3D(-1.,  2.));
    points.push_back(Point3D( 2., -1.));
    points.push_back(Point3D(-2.,  0.));

    using boost::bind;
    std::sort(points.begin(), points.end(), 
              bind(&Point3D::x, _1) < bind(&Point3D::x, _2));
    // points sorted by x coord

    std::sort(points.begin(), points.end(), 
              bind(&Point3D::y, _1) < bind(&Point3D::y, _2));
    // points sorted by y coord
}

What a shame std::tr1::bind does not support that. But of course, with a C++0x compiler you'll be able to do this:

std::sort(points.begin(), points.end(), 
          [](Point3D const & a, Point3D const & b) { return a.x < b.x; });