I have a vector of element V that needs to be sorted. I want to also produce a
permutation vector P which reflects the element's position in the original
vector. P is initialized with identity permutation (P[i] == i).
1st possibility: code my own sorting algorithm, and swap elements of P along
with swapping elements of V. This I want to avoid, if at all possible.
2nd possibility: copy elements of V into new vector V' holding pair
and sort that. (pair holds the original element as well as its starting
position in the vector, i.e. .second is again initialized to identity
permutation.) Drawback: extra space and time spent on copying to V'.
3rd possibility: sort elements of P with less_than doing lookups into V to do
its comparison. Drawback: while P holds the correct result, V is left
unsorted; I have to do another pass through V and swap elements according to
the permutation recorded in P, which is not trivial to do in-place.
4th possibility: I'm not sure whether it'd work: have a separate compilation
unit that will provide function sort_vector_of_T, which will take references to
V, T and also provide a specialization of std::swap for T which will then also
swap elements of P). (Separate compilation unit is needed because I don't
want to *globally* redefine std::swap for T)
Is there some non-obvious, efficient and elegant way of achieving what I want?
