11

问题陈述:

我想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++ 标准库排序函数来实现吗?如果没有,还有其他我可以使用的库吗?

4

4 回答 4

9

是的,您可以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);
}
于 2012-11-21T15:44:41.410 回答
5

通常,当需要字典顺序时,为多个字段实现比较运算符(和函数)更清楚地表示为tie

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

塔阿达姆 :)

于 2012-11-21T18:10:03.913 回答
3

C++11开始,您还可以使用lambda 表达式而不是定义比较函数:

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

这样你就可以保持你的代码相当短。

Ideone 上的代码

于 2018-12-10T15:59:09.327 回答
2

std::sort采用自定义比较功能。我没有对此进行测试,但您的可能看起来像:

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;
}
于 2012-11-21T15:44:31.383 回答