c++ - インデックス情報を失わずに std::vector を並べ替える

Question

std::vectorインデックス情報を失うことなく、保存された値を使用して並べ替えたい。例えば、

std::vector <int> vec;
vec.resize(3);
vec[0] = 20;
vec[1] = 10;
vec[2] = 6;
std::sort(vec.begin(), vec.end());
// Here I want to know the order of indices after sort operation which is 2, 1, 0

Answer 1

元のベクトルの順列を保存したいので、 from から{0, ... , n - 1}へ の正しい全単射を構築する別のベクトルが必要です{0, ... , n - 1}。

vector<unsigned int> permutation( vec.size() );
for(unsigned int i = 0; i < vec.size(); ++i)
    permutation[i] = i;

まだ何も順列していません。ここで、2 番目のベクトルを並べ替えるのではなく、順列を並べ替えます。

std::sort(permutation.begin(), permutation.end(), cmp);

C++11 を使用する場合はcmp、ラムダにすることができます。

[&vec](unsigned int a, unsigned int b) { return vec[a] < vec[b];}

C++03 を使用する場合は、次のように構造体を使用する必要がありますbool operator()(unsigned int, unsigned int)。

struct comparator{
   comparator(vector& v) : lookup(v){}
   bool operator()(unsigned int a, unsigned int b){
       return lookup[a] < lookup[b];
   }
   vector& lookup;
};

comparator cmp(vec);

ソートされたベクトルは、 でトラバースできますvec[permutation[i]]。