Multi-Key Custom Sorting in C++

问题:

Problem Statement:

I want to sort an std::vector of a structure using my custom sorting criteria.

The structure is:

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

The vector is:

std::vector<Node> vec;

My custom sorting criteria is that the vector should first be sorted by y and then by x (just like in Microsoft Excel).

Example:

Input:

x y

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

Output:

x y

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 above mentioned sorting be achieved through any of the C++ Standard Library sorting functions? If not, is there any other library which I can use?

回答1:

Yes, you can do it using std::sort using 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);
}

回答2:

In general, implementing comparison operators (and functions) for multiple fields is more clearly expressed in terms of tie when lexicographical ordering is required.

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(l.y, l.x)
         < std::tie(r.y, r.x);
}

However, even that leaves some duplication and route for inconsistency. The following helper sees to that:

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

which can then be applied simply:

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

Taaadaaam :)

回答3:

Since 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 a.y < b.y || (a.y == b.y && a.x < b.x);
});

This way you can keep your code rather short.

Code on Ideone

回答4:

std::sort takes a custom comparison function. I haven't tested this, but yours might look something like:

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;
}