[Boost-users] How to find a sorting permutation

From: Zeljko Vrba (zvrba_at_[hidden])
Date: 2008-08-20 10:29:08

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<T, size_t>
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?