C++でpairのvectorを使って配列を簡約形式（Reduced Form）に変換する方法

このチュートリアルでは、pairのvector（std::vector<std::pair>）を活用して、配列を簡約形式（reduced form）に変換するC++プログラムについて解説します。

簡約形式とは？

簡約形式とは、配列内の各要素を、その大小関係（順位）を保ったまま「0」から「n-1」までの連続した整数に置き換えた配列のことです。

例えば、次のような配列が与えられたとします。

{10, 20, 15, 12, 11, 50}

この配列を簡約形式に変換すると、最小値の「10」が「0」、2番目に小さい「11」が「1」となり、以下のようになります。

{0, 4, 3, 2, 1, 5}

要素同士の相対的な順序はそのまま維持されるため、データのランク付けや座標圧縮など、さまざまな場面で応用できるテクニックです。

変換の考え方（アルゴリズム）

pairのvectorを使うことで、この変換をシンプルかつ効率的に行えます。手順は以下の通りです。

1. 各要素とその元のインデックスを組み合わせたpairを作成し、vectorに格納します。
2. vectorを要素の値を基準にソートします。
3. ソート後の順番（＝順位）を、pairに記録しておいた元のインデックスの位置へ書き戻します。

C++サンプルコード

#include <bits/stdc++.h>
using namespace std;

// 配列を簡約形式に変換する関数
void convert(int arr[], int n) {
    // pairのvectorを作成
    vector <pair<int, int> > v;
    // 要素とそのインデックスをvectorに格納
    for (int i = 0; i < n; i++)
        v.push_back(make_pair(arr[i], i));
    // 値を基準にソート
    sort(v.begin(), v.end());
    // ソート後の順位を元のインデックス位置に書き戻す
    for (int i = 0; i < n; i++)
        arr[v[i].second] = i;
}

// 配列を出力する関数
void print_array(int arr[], int n) {
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}

int main() {
    int arr[] = {10, 20, 15, 12, 11, 50};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "元の配列 :\n";
    print_array(arr, n);
    convert(arr, n);
    cout << "\n変換後の配列:\n";
    print_array(arr, n);
    return 0;
}

実行結果

元の配列 :
10 20 15 12 11 50
変換後の配列:
0 4 3 2 1 5

コードの解説

ポイントはconvert関数の処理です。

• make_pair(arr[i], i)：配列の値とインデックスをセットにすることで、ソート後に「どの位置の要素だったか」を記憶できます。
• sort(v.begin(), v.end())：pairはfirst（値）を基準にソートされるため、小さい順に並び替えられます。
• arr[v[i].second] = i：ソート後の位置i（＝順位）を、pairに保存しておいた元のインデックスv[i].secondの場所に代入します。

計算量はソートが支配的となるため、全体の時間計算量はO(n log n)となります。要素の値そのものではなく相対的な順位だけが必要な場合に、非常に有用な手法なので、ぜひ覚えておきましょう。