sort std::vector without losing index info

c++, sorting, stdvector

Solution

You want to save the permutation of your original vector, so you need another vector which 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 didn't permutate anything yet. Now you don't sort the second vector, instead you sort the permutation:

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

If you use C++11, `cmp` can be a lambda:

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

If you use C++03 you'll 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);

The sorted vector can then be traversed with `vec[permutation[i]]`.

Problem

I want to sort a `std::vector` using stored values without losing the index info. For example, ``` 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 ```

Original source