C++：std::tuple を使いインデックス情報を保持しつつソートを行う

std::tuple の基礎
- std::tuple とは
- std::tuple の使い方
インデックス情報を保持しつつソートを行う
- 注意点
- 実装
終わりに

std::tuple の基礎とその簡単な利用例の解説です．

std::tuple の基礎
std::tuple を使ってインデックス情報を保持しつつソート

の 2 点を解説します．std::pair を使えば本記事と同じことができるのですが，タプルの使い方を覚えたいので std::tuple でやります．

std::tuple の基礎

std::tuple とは

std::tuple は、複数の型の値を保持する「タプル」を表現するためのクラスです．

std::pair は 2 つの型の値を保持する「組」を表現することができますが、std::tuple では N 個の型の値を扱うことができます．

std::tuple の使い方

#include <bits/stdc++.h>，using namespace std; をコードの先頭に書いてある前提で話を進めます．

std::tuple の宣言，初期化：tuple<int, char, string> tup = make_tuple(100, 'c', "xyz");
要素へのアクセス（インデックス指定）：int i = get<0>(tup);
要素へのアクセス（型指定）：int i = get<int>(tup);

上記により基本的な扱いはできるようになります．詳しくはリファレンスをお読みください．ちなみに，同じ型をタプル宣言時に指定し（tuple<int, int>など），型指定で要素を取り出そうとするとコンパイルエラーになります．

では簡単な例を見てみます．

#include <iostream>
#include <string>
#include <vector>
#include <tuple>  // std::tuple std::get
#include <algorithm>  // std::sort()

using namespace std;

int main() {
    tuple<int , char , string> tup = make_tuple(100, 'c', "xyz");

    // 位置を指定して要素を取得
    // get<i>(tup)はi番目の要素の参照を返す
    {
        int i = get<0>(tup);
        char c = get<1>(tup);
        string s = get<2>(tup);

        cout << i << "\n";
        cout << c << "\n";
        cout << s << "\n";
    }
    cout << "\n";;

    // 型を指定して取得要素を取得
    {
        int i = get<int>(tup);
        char c = get<char>(tup);
        string s = get<string>(tup);
        
        cout << i << "\n";
        cout << c << "\n";
        cout << s << "\n";
    }

    // 同じ型でタプルを構成した場合
    // コンパイルエラー：error: static_assert failed "type occurs more than once in type list"
    {
        // tuple<int , int, int> tup1 = make_tuple(1, 23, 459);
        // int i = get<int>(tup1);

        // cout << i << "\n";
    }

    return 0;
}

ここまででタプルの基本が分かったと思うので，本題に入っていきます．

インデックス情報を保持しつつソートを行う

std::vector の要素として std::tuple を用いることで，他の情報を保持しつつ要素のソートを行うことができます．その例として，「入力時のインデックス情報を保持しながらのソート」を紹介します（こういう既にライブラリにありそう）．

注意点

std::sort()を使う際の注意点があります．それは，std::tuple を要素にもつ std::vector のソートでは，第一要素，第二要素，... が順に評価される仕様になっている，ということです．例えば，

(3, 5), (3, 3)

という２つのタプルをソートする際は，

第一要素が等しい → 第二要素を比較 → 異なるからソート

という順序で評価されます．そのため，第一要素をインデックスにしてしまうとインデックスの値でソートされてしまいます．この注意を念頭にコードを書いてみます．

実装

実際に入力を受け取り，そのインデックス（順序）の情報を保持しつつソートしてみます．

入力（要素数，配列の中身）

6
30 25 50 20 55 30

コード

#include <iostream>
#include <vector>
#include <tuple>  // std::tuple std::get
#include <algorithm>  // std::sort()

using namespace std;

int main() {
    // input
    int N, num;
    cin >> N;
    vector<tuple<int , int>> vec(N);
    for (int idx = 0; idx < N; ++idx) {
        cin >> num;
        vec[idx] = make_tuple(num, idx);
    }
    
    // ソート前
    cout << "----- before sort -----" << "\n";
    cout << "idx : num" << "\n";
    for (int j = 0; j < N; ++j) {
        cout << get<1>(vec[j]) << " : " << get<0>(vec[j]) << "\n";
    }
    
    sort(vec.begin(), vec.end());
    
    // ソート後
    cout << "\n";
    cout << "----- after sort -----" << "\n";
    cout << "idx : num" << "\n";
    for (int j = 0; j < N; ++j) {
        cout << get<1>(vec[j]) << " : " << get<0>(vec[j]) << "\n";
    }
    
    return 0;
}

出力

----- before sort -----
idx : num
0 : 30
1 : 25
2 : 50
3 : 20
4 : 55
5 : 30

----- after sort -----
idx : num
3 : 20
1 : 25
0 : 30  # idx = 0 idx が早い方が先に来る
5 : 30  # idx = 5
2 : 50
4 : 55

同じ値を持つ場合はインデックスが早い（小さい）方が先に来ることも確認しておきましょう．

ちなみに Python だとnumpy.argsort()を使って上記と同じようなことができます．（画像ですみません）

f:id:pytwbf201830:20190206221822p:plain