c++ - Reorder vector according to a vector of indices - update -

this update previous question reordering in place there confusion vector of indices. calling vector reordered va, , vector of indices vi, va should reordered in order, va[vi[0]], va[vi[1]], va[vi[2], ... . example usage initialize vi set of va.size() indices, 0 va.size()-1, sort vi according va (compare using va[vi[...]]). reorder function used sort va according vi.

consider initial va permutation of sorted va. after sorting vi according va, reordering va according vi "unpermutes" va sorted permutation. example functions shown below, reordering va reorders vi it's initialized state (0 va.size()-1).

the example below shows non-working version of reorder called reorderfail() followed working version called reorder(). both functions return vi it's original state of 0 va.size()-1, reorderfail() fails reorder va because it's missing level of indirection needed "unpermute" va.

#include <algorithm> #include <vector>  using namespace std;  template <class t> void reorderfail(vector<t>& va, vector<size_t>& vi)   {    size_t i, j;     for(i = 0; < va.size(); i++ ){          while(i != (j = vi[i])){             swap(va[i], va[j]);             swap(vi[i], vi[j]);         }     } }  template <class t> void reorder(vector<t>& va, vector<size_t>& vi)   { size_t i, j, k;     for(i = 0; < va.size(); i++){          while(i != (j = vi[i])){             k = vi[j];             swap(va[j], va[k]);             swap(vi[i], vi[j]);         }     } }  int main( ) { char a[]   = { 'b', 'c', 'a' }; size_t i[] = {  2 ,  0 ,  1  };  // order should a[2] a[0] a[1] size_t size = sizeof(a) / sizeof(*a);      vector<char>   va(size);     vector<size_t> vi(size);      va.assign(a, + size);     vi.assign(i, + size);     reorderfail(va, vi);    // returns va = {'c', 'a', 'b'};      va.assign(a, + size);     vi.assign(i, + size);     reorder(va, vi);        // returns va = {'a', 'b', 'c'};      return(0); }