Multi-Key Custom Sorting in C ++

Question

Formulation of the problem:

I want to sort std::vector structures using my own sorting criteria.

The structure is:

 struct Node { int x; int y; float value; }; 

Vector is:

 std::vector<Node> vec; 

My custom sorting criterion is that the vector must first be sorted by y and then by x (as in Microsoft Excel).

Example:

Input data :

 xy 5 6 2 4 1 1 1 0 8 10 4 7 7 1 5 4 6 1 1 4 3 10 7 2 

Exit:

 xy 1 0 1 1 6 1 7 1 7 2 1 4 2 4 5 4 5 6 4 7 3 10 8 10 

Can the aforementioned sorting be done using any of the sorting functions of the C ++ standard library? If not, is there another library I can use?

Answer 1

Yes, you can do this using std::sort with a comparison function.

 bool comparison(const Node& node1, const Node& node2) { if (node1.y < node2.y) return true; if (node1.y == node2.y) return node1.x < node2.x; return false; } int main() { std::sort(vec.begin(), vec.end(), comparison); } 

Answer 2

In general, the implementation of comparison operators (and functions) for several fields is more clearly expressed in terms of tie , when a lexicographic is required to be ordered .

 static bool compare(Node const& l, Node const& r) { // Note the alignment so that both expressions only differ in their `l` and `r` ? return std::tie(ly, lx) < std::tie(ry, rx); } 

However, even this leaves some duplication and a path to inconsistency. The following assistant sees the following:

 static std::tuple<int&,int&> tuplize(Node const& n) { return std::tie(ny, nx); } 

which can then be applied simply:

 static bool compare(Node const& l, Node const& r) { return tuplize(l) < tuplize(r); } 

Taaadaaam :)

Answer 3

std::sort performs a custom comparison function. I have not tested this, but yours might look something like this:

 bool cmp (const Node& lhs, const Node& rhs) { if ( lhs.y < rhs.y ) return true; else if ( lhs.y == rhs.y ) return ( lhs.x < rhs.x ); else return false; } 

Answer 4

Starting with C ++ 11 , you can also use a lambda expression instead of defining a comparison function:

 std::sort(std::begin(vec), std::end(vec), [](const Node& a, const Node& b) { return ay < by || (ay == by && ax < bx); }); 

That way you can make your code pretty short.

Ideone Code