Sorting List container using template function

Question

I have a header, which consists of different template functions

#include <cmath>

template<class T>
bool lessThan(T x, T y) {

    return (x < y);

}

template<class T>
bool greaterThan(T x, T y) {

    return (x > y);

}

A class

class Point2D {
public:
    Point2D(int x, int y);
protected:
    int x;
    int y;
    double distFrOrigin;

In my driver class, I have an STL List of Point2D: list<Point2D> p2dL. How do I sort p2dL using the template functions lessThan and greaterThan in my header? i.e. Sort the list based on x or y value.

EDIT: And so, based on Anton's comment, I came up with this:

bool Point2D::operator<(Point2D p2d) {

    if (this->x < p2d.x || this->y < p2d.y
            || this->distFrOrigin < p2d.distFrOrigin) {

        return true;

    }

    else {

        return false;

    }

}

Did I do it correctly?

You will need to implement the < operator for your class, otherwise the compiler does not know how to deal with the comparison. — SinisterMJ
– SinisterMJ, Commented Nov 17, 2012 at 8:09
There is no "correct" way to order two 2D points. You have to decide which arbitrary choice suits your problem. — juanchopanza
– juanchopanza, Commented Nov 17, 2012 at 8:59

WhozCraig · Accepted Answer · 2012-11-17 08:59:16Z

First, all three major templates can be exposed using just an operator <() so long as you enforce strict ordering:

template<class T>
bool lessThan(const T& x, const T& y) 
{
    return (x < y);
}

template<class T>
bool greaterThan(const T& x, const T& y) 
{
   return (y < x);
}

template<class T>
bool equals(const T& x, const T& y) 
{
   return !(x < y) || (y < x));
}

Next, your class must implement operator <() to compare a *this against a parameter. A sample appears below:

class Point2D {
public:
    Point2D(int x, int y);

    // sample that orders based on X primary, and Y if X's are equal.
    bool operator <(const Point2D& other) const
    {
        return (x < other.x || (x == other.x && y < other.y));
    }

protected:
    int x;
    int y;
    double distFrOrigin;
};

Lastly. sort your list like so:

// sort ascending
std::sort(p2dl.begin(), p2dl.end(), lessThan<Point2D>);

// sort descending
std::sort(p2dl.begin(), p2dl.end(), greaterThan<Point2D>);

Or as Juan pointed out, use the list-sort directly:

p2dl.sort(lessThan<Point2D>);

Hope that helps.

juanchopanza · Accepted Answer · 2012-11-17 09:03:02Z

1

You can use the std::list::sort method directly, instead of std::sort:

p2dl.sort(lessThan<Point2D>);

But you have to implement lessThan and greaterThan or similar functions in terms of Point types. For example:

template<class T>
bool greaterThan(const T& p1, const T& p2) {

    return (p1.x > p2.y);

}

Note that the above comparison function is just an example, you have to decide how to implement less-than and greater-than with 2D points.

For completeness, here's a lexicographical comparison using std::tie:

template<class T>
bool greaterThan(const T& p1, const T& p2) 
{
    return std::tie(p1.x, p1.y) > std::tie(p2.x, p2.y);
}

edited Nov 17, 2012 at 9:03

answered Nov 17, 2012 at 8:11

juanchopanza

228k35 gold badges421 silver badges493 bronze badges

Collectives™ on Stack Overflow

Sorting List container using template function

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related