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

一般に、複数のフィールドに比較演算子（および関数）を実装することは、辞書式順序が必要な場合に、タイの観点からより明確に表現されます。

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 :)

于 2012-11-21T18:10:03.913 に答える
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 に答える