C++中的多键自定义排序

Question

问题陈述:

我想std::vector使用自定义排序条件对结构进行排序.

结构是:

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

矢量是:

std::vector<Node> vec;

我的自定义排序标准是矢量首先应按顺序排序y,然后排序x(就像在Microsoft Excel中一样).

例:

输入:

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

输出:

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

可以通过任何C++标准库排序功能实现上述排序吗？如果没有,我还可以使用其他库吗？

Answer 1

是的,您可以std::sort使用比较功能来完成.

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

一般而言,实施比较运算符(和函数)为多个字段被更清楚地来表示粘结时词典式排序是必需的.

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

然而,即使这样也会留下一些重复和不一致的路线.以下助手看到了:

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

然后可以简单地应用:

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

Taaadaaam :)