二次元vectorの特定キーでのソート

C++で二次元vector vector<vector<T>>を特定のキーでソートしたい

次のような二次元vectorを

	要素0	要素1	要素2
vector[0]	5	2	3
vector[1]	1	4	5
vector[2]	3	3	2
要素0をキーとして昇順ソートして、

	要素0	要素1	要素2
vector[0]	1	4	5
vector[1]	3	3	2
vector[2]	5	2	3

このような結果が得たいなーと思って、色々調べた結果次の方法でソートすることが出来ました。

結論

とりあえず方法が見たい人用に先に書いておきます。

 sort(myVec.begin(),myVec.end(),[](const vector<int> &alpha,const vector<int> &beta){return alpha[0] < beta[0];});

テストコード (C++11)

テスト用に書いたコードを載せておきます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 2次元vectorの中身のセット
void setVec(vector<vector<int>>& v){
    vector<int> tmp;

    tmp.push_back(5);tmp.push_back(2);tmp.push_back(3);
    v.push_back(tmp);
    tmp.clear();

    tmp.push_back(1);tmp.push_back(4);tmp.push_back(5);
    v.push_back(tmp);
    tmp.clear();

    tmp.push_back(3);tmp.push_back(3);tmp.push_back(2);
    v.push_back(tmp);
    tmp.clear();
}

//2次元ベクトルを表示
void printVec(const vector<vector<int>> v){
    for(int i=0;i<v.size();i++){
        for(int j=0;j<v[i].size();j++){
            cout << v[i][j] << " ";
        }
        cout << endl;
    }
}

int main(void){
    vector<vector<int>> myVec;
    setVec(myVec);
    
    cout << " -- 初期状態 -- " << endl;
    printVec(myVec);


    cout << " -- 要素0でソート -- " << endl;
    sort(myVec.begin(),myVec.end(),[](const vector<int> &alpha,const vector<int> &beta){return alpha[0] < beta[0];});
    printVec(myVec);
    
    cout << " -- 要素1でソート -- " << endl;
    sort(myVec.begin(),myVec.end(),[](const vector<int> &alpha,const vector<int> &beta){return alpha[1] < beta[1];});
    printVec(myVec);

    cout << " -- 要素2でソート -- " << endl;
    sort(myVec.begin(),myVec.end(),[](const vector<int> &alpha,const vector<int> &beta){return alpha[2] < beta[2];});    
    printVec(myVec);
}

実行結果

-- 初期状態 --
5 2 3
1 4 5
3 3 2
-- 要素0でソート --
1 4 5
3 3 2
5 2 3
-- 要素1でソート --
5 2 3
3 3 2
1 4 5
-- 要素2でソート --
3 3 2
5 2 3
1 4 5

コードの中身で何をしているのか

今回のsort関数の記述方式は、C++日本語リファレンスサイトによると、

template <class RandomAccessIterator, class Compare>
  void sort(RandomAccessIterator first,
            RandomAccessIterator last,
            Compare comp);                        // (2) C++03

に該当すると考えられます。
第三引数のCompare compに比較対象を記述したいので、vector[][i]を取り出せれば良いことになります。そこで、C++11から利用可能なラムダ式を使って、sort時の比較対象であるvector2つをalpha,betaと置き、それらの値が来たときに中括弧で囲まれた式を用いて結果を返すようにします。

sort(myVec.begin(),myVec.end(),[](const vector<int> &alpha,const vector<int> &beta){return alpha[0] < beta[0];});

ソートの流れを考えると、

1. sort(myVec.begin(),myVec.end(),compare)より、myVec内のmyVec[0]とmyVec[1]が取り出される。
2. ラムダ式に沿って、alphaにmyVec[0],betaにmyVec[1]が入る。
3. alphaとbetaが来たので、中括弧内の判定alpha[0]<beta[0]より真偽値が返される。
4. myVec[0]とmyVec[1]が3.の結果に基づいてソートされる。
5. 以降ソートが終了するまで繰り返し。

ソートを行う時、それぞれのvectorの中身を参照しているため、alphaとbetaの添字を変更することで、ソートをするキーを変更できるよ！っていう話でした。

参考にさせていただいたサイト

c – 整数の多次元ベクトルをソートする
cpprefjp - C++日本語リファレンス　std::sort