CODEWITHSUNDEEP
c++
user974967
user974967

Reputation: 2946

operator< for list sorting

I have a simple Position struct:

struct Position
{
    int x;
    int y;
};

I also have a list of Positions:

std::list<Position> positons;

I'm trying to sort the list using list::sort() and need to define operator< for Positions objects. I tried keeping it simple creating something like:

bool operator<(const Position& one, const Position& two)
{
    return one.x < two.x && one.y < two.y;
}

But that doesn't work. How do I determine that one class/struct object as a whole is less than another? How would I do it for my Position struct?

EDIT When I call positions.sort(), I get a debug assertion failed which says: Expression: invalid operator<

Upvotes: 1

Views: 221

Answers (4)

Mankarse
Mankarse

Reputation: 40613

Your current definition does not establish a strict weak order. Try something like:

bool operator<(const Position& one, const Position& two)
{
    return std::tie(one.x, one.y) < std::tie(two.x, two.y);
}

This uses std::tie to create two std::tuple<int const&, int const&> objects containing references to the x and y elements of one and two, and then compares the two tuples using operator< (which performs a lexicographical comparison).

std::tie requires C++11, but a similar result can be achieved with boost::tuple.

Upvotes: 3

Potatoswatter
Potatoswatter

Reputation: 137780

The simplest solution would be to forgo the struct and use

typedef std::array< int, 2 > Position; // C++11, access pos[0] and pos[1]

or

typedef std::pair< int, int > Position; // C++03, access pos.first and pos.second

These classes have operator< (and all the other operators you might need) predefined. You can't call the coordinates .x and .y, but it's better than reinventing the wheel.

If you really want, there's also a trick to call the members of std::array as x and y, in a fashion:

enum coord_name { x, y, z };

template< typename lhs_t >
auto operator ->* ( lhs_t &&lhs, coord_name rhs )
    -> decltype( lhs[ + rhs ] )
    { return lhs[ + rhs ]; }

Position coords;
std::array< float, 3 > coords_3d_floating;

// usage:
coords->*x = 8;
coords->*y = coords_3d_floating->*z * 1.5;

This requires C++11.

Upvotes: 0

Aesthete
Aesthete

Reputation: 18850

You could sort your positions by distance from origin, or magnitude, like so:

std::vector<Position> Foo;
std::sort(Foo.begin(), Foo.end(), [](Position& a, Position& b) {return (abs(a.x) + abs(a.y)) <  (abs(b.x) + abs(b.y)); });

Upvotes: 2

Denis Ermolin
Denis Ermolin

Reputation: 5546

You can sort by x and then by y. Also define it as free function:

bool function(const Position& one, const Position& two)
{
    return one.x < two.x || (one.x == two.x && one.y < two.y);
}

Or as operator:

bool operator<(const Position& other)const
{
    return x < other.x || (x == other.x && y < other.y);
}

Upvotes: 1

Related Questions