ソートと要素のインデックス
ここらへんでハマってとてもつらかったので書いておきます。
ソート後のインデックスから、ソート前のインデックスを知りたい
方法1
インデックスとのペアのコレクションを作り、要素をキーとしてソートする。
char arr[5] = { 'D', 'A', 'C', 'E', 'B' }; pair<char, int> arridx[5]; for (int i = 0; i < 5; i++) arridx[i] = make_pair(arr[i], i); // arridx => { (D, 0), (A, 1), (C, 2), (E, 3), (B, 4) } sort(begin(arridx), end(arridx), [](pair<char, int>& a, pair<char, int>& b) { return a.first < b.first; }); // arridx => { (A, 1), (B, 4), (C, 2), (D, 0), (E, 3) }
方法2
インデックスだけのコレクションを作り、ソートしたいコレクションの対応する要素をキーとしてソートする。
char arr[5] = { 'D', 'A', 'C', 'E', 'B' }; int idx[5]; for (int i = 0; i < 5; i++) idx[i] = i; // idx => { 0, 1, 2, 3, 4 } sort(begin(idx), end(idx), [&arr](int& a, int& b) { return arr[a] < arr[b]; }); // idx => { 1, 4, 2, 0, 3 }
このソートされたインデックスを使って、ソートされた順番で要素にアクセスできる。
for (int i = 0; i < 5; i++) cout << arr[idx[i]] << " "; // => "A B C D E "
ソート前のインデックスから、ソート後のインデックスを知りたい
コレクションが与えられた後、そのインデックスがクエリとして与えられるが、事前に元のコレクションをソートしておく必要がある場合など。上図では、例えば要素 D
について、ソート前のインデックス 0
からソート後のインデックス 3
を得ることができる。
前述の、ソートされたインデックスのコレクションから生成する。
方法1
int after_idx[5]; for (int i = 0; i < 5; i++) after_idx[arridx[i].second] = i; // after_idx => { 3, 0, 2, 4, 1 }
方法2
int after_idx[5]; for (int i = 0; i < 5; i++) after_idx[idx[i]] = i; // after_idx => { 3, 0, 2, 4, 1 }