我想在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
您想保存原始向量的排列 ,因此您需要另一个向量来构建从{0, ... , n - 1}
to的正确双射{0, ... , n - 1}
:
vector<unsigned int> permutation( vec.size() );
for(unsigned int i = 0; i < vec.size(); ++i)
permutation[i] = i;
我们还没有置换任何东西。现在您不对第二个向量进行排序,而是对排列进行排序:
std::sort(permutation.begin(), permutation.end(), cmp);
如果您使用 C++11,cmp
则可以是 lambda:
[&vec](unsigned int a, unsigned int b) { return vec[a] < vec[b];}
如果你使用 C++03,你需要使用 struct with 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]]
。