сортировать std :: vector без потерь индекс info

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

Вы хотите сохранить перестановку вашего исходного вектора, так что вам нужен другой вектор, который строит правильную биекцию из {0, ... , n - 1} в {0, ... , n - 1}:

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

Мы не permutate что-нибудь еще. Теперь вы не сортировать второй вектор, вместо того, чтобы сортировать перестановку:

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]].