読者です 読者をやめる 読者になる 読者になる

C++11のtupleをvectorに突っ込んでソート


このエントリーをはてなブックマークに追加

Update(2015/06/26): コメントのご指摘に従い、私の勘違いを修正(tupleを比較方法の指定なしでソートすることはできないと勘違いしていた)

C++11から新たに導入されたtuple(タプル)を、vectorに突っ込んでソートする方法について調べました。

比較方法の指定なしでソート

以下のように、比較方法の指定なしでstd::sort()を使うと、自動的に第一要素、第二要素、…と順に比較した結果に基づいてソートされるようです。

    std::vector<int, std::string, double> vec;

    ... // vecに適当な値を入れる

    sort(vec.begin(), vec.end(), mycompare);

カスタムソートその1: 比較関数を書く

お好みの方法でtupleのソート順を定義する方法を二つご紹介します。

まず一つ目は比較関数を書く方法です。構造体のソートを行うときにもよく使う方法です(参考:C++で構造体をソートする4つの方法(おまけあり) - minus9d's diary)。以下のコード例では、タプルの第一要素、第二要素、第三要素の順に比較を行っています(バグがなければ)。

typedef std::tuple<int, std::string, double> mytuple;

// タプルの最初の要素から順番に比較 もしその要素が同じなら次の要素で比較
bool mycompare( const mytuple &lhs, const mytuple &rhs )
{
    if (std::get<0>(lhs) != std::get<0>(rhs)) return std::get<0>(lhs) < std::get<0>(rhs);
    if (std::get<1>(lhs) != std::get<1>(rhs)) return std::get<1>(lhs) < std::get<1>(rhs);
    return std::get<2>(lhs) < std::get<2>(rhs);
}

int main() {
    std::vector<mytuple> vec;

    ... // vecに適当な値を入れる

    sort(vec.begin(), vec.end(), mycompare);
}

カスタムソートその2: ラムダ式を書く

方法1の比較関数の部分をラムダ式で書き捨てする方法です。C++11の普及に従ってこれから目にすることが増えそうな書き方です。

    sort(vec.begin(),
         vec.end(),
         [](mytuple const &lhs, mytuple const &rhs) {
             if (std::get<0>(lhs) != std::get<0>(rhs)) return std::get<0>(lhs) < std::get<0>(rhs);
             if (std::get<1>(lhs) != std::get<1>(rhs)) return std::get<1>(lhs) < std::get<1>(rhs);
             return std::get<2>(lhs) < std::get<2>(rhs);
         }
        );

コード全文

#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>

// C++11のタプルをvectorに突っ込んでソート

typedef std::tuple<int, std::string, double> mytuple;

// タプルの最初の要素から順番に比較 もしその要素が同じなら次の要素で比較
bool mycompare( const mytuple &lhs, const mytuple &rhs )
{
    if (std::get<0>(lhs) != std::get<0>(rhs)) return std::get<0>(lhs) < std::get<0>(rhs);
    if (std::get<1>(lhs) != std::get<1>(rhs)) return std::get<1>(lhs) < std::get<1>(rhs);
    return std::get<2>(lhs) < std::get<2>(rhs);
}

void print_vector( std::vector<mytuple>& vec )
{
    for( auto& element : vec ) {
        std::cout << std::get<0>(element) << ", " << std::get<1>(element) << ", " << std::get<2>(element) << std::endl;
    }
    std::cout << std::endl;
}

int main() {
    std::vector<mytuple> vec{
        std::make_tuple(50, "ccc", 7.5),
        std::make_tuple(30, "kkk", 8.5),
        std::make_tuple(20, "ddd", 9.5),
        std::make_tuple(50, "aaa", 7.5),
        std::make_tuple(20, "ddd", 3.5),
        std::make_tuple(50, "ccc", 2.5),
        std::make_tuple(30, "zzz", -1.5)
            };

    // 比較関数を使ってソートする場合
    sort(vec.begin(), vec.end(), mycompare);
    print_vector(vec);

    // いったんシャッフル
    std::shuffle(std::begin(vec), std::end(vec), std::default_random_engine());

    // ラムダ式を使ってソートする場合
    sort(vec.begin(),
         vec.end(),
         [](mytuple const &lhs, mytuple const &rhs) {
             if (std::get<0>(lhs) != std::get<0>(rhs)) return std::get<0>(lhs) < std::get<0>(rhs);
             if (std::get<1>(lhs) != std::get<1>(rhs)) return std::get<1>(lhs) < std::get<1>(rhs);
             return std::get<2>(lhs) < std::get<2>(rhs);
         }
        );
    print_vector(vec);

    return 0;
}

出力結果

どちらの方法でも正しくソートできているようです。

20, ddd, 3.5
20, ddd, 9.5
30, kkk, 8.5
30, zzz, -1.5
50, aaa, 7.5
50, ccc, 2.5
50, ccc, 7.5

20, ddd, 3.5
20, ddd, 9.5
30, kkk, 8.5
30, zzz, -1.5
50, aaa, 7.5
50, ccc, 2.5
50, ccc, 7.5

参考