Sort std :: vector without losing index information

Question

I want to sort std::vector using stored values ​​without losing index information. For instance,

 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

You want to save the permutation of the original vector, so you need another vector that builds the correct bijection from {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; 

We have not mixed up anything yet. Now you are not sorting the second vector, instead you are sorting the permutation:

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

If you are using C ++ 11, cmp could be lambda:

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

If you are using C ++ 03, you need to use 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); 

Then the sorted vector can be traversed using vec[permutation[i]] .