Reorder vector using a vector of indices

Question

I'd like to reorder the items in a vector, using another vector to specify the order:

char   A[]     = { 'a', 'b', 'c' }; size_t ORDER[] = { 1, 0, 2 };  vector<char>   vA(A, A + sizeof(A) / sizeof(*A)); vector<size_t> vOrder(ORDER, ORDER + sizeof(ORDER) / sizeof(*ORDER)); 
reorder_naive(vA, vOrder); 
// A is now { 'b', 'a', 'c' } 

The following is an inefficient implementation that requires copying the vector:

void reorder_naive(vector<char>& vA, const vector<size_t>& vOrder)   {        assert(vA.size() == vOrder.size());       vector vCopy = vA; // Can we avoid this?       for(int i = 0; i < vOrder.size(); ++i)           vA[i] = vCopy[ vOrder[i] ];   }   

Is there a more efficient way, for example, that uses swap()?

Answer 1

This algorithm is based on chmike's, but the vector of reorder indices is const. This function agrees with his for all 11! permutations of [0..10]. The complexity is O(N^2), taking N as the size of the input, or more precisely, the size of the largest orbit.

See below for an optimized O(N) solution which modifies the input.

template< class T > void reorder(vector<T> &v, vector<size_t> const &order )  {        for ( int s = 1, d; s < order.size(); ++ s ) {         for ( d = order[s]; d < s; d = order[d] ) ;         if ( d == s ) while ( d = order[d], d != s ) swap( v[s], v[d] );     } } 

Here's an STL style version which I put a bit more effort into. It's about 47% faster (that is, almost twice as fast over [0..10]!) because it does all the swaps as early as possible and then returns. The reorder vector consists of a number of orbits, and each orbit is reordered upon reaching its first member. It's faster when the last few elements do not contain an orbit.

template< typename order_iterator, typename value_iterator > void reorder( order_iterator order_begin, order_iterator order_end, value_iterator v )  {        typedef typename std::iterator_traits< value_iterator >::value_type value_t;     typedef typename std::iterator_traits< order_iterator >::value_type index_t;     typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;          diff_t remaining = order_end - 1 - order_begin;     for ( index_t s = index_t(), d; remaining > 0; ++ s ) {         for ( d = order_begin[s]; d > s; d = order_begin[d] ) ;         if ( d == s ) {             -- remaining;             value_t temp = v[s];             while ( d = order_begin[d], d != s ) {                 swap( temp, v[d] );                 -- remaining;             }             v[s] = temp;         }     } } 

---

And finally, just to answer the question once and for all, a variant which does destroy the reorder vector (filling it with -1's). For permutations of [0..10], It's about 16% faster than the preceding version. Because overwriting the input enables dynamic programming, it is O(N), asymptotically faster for some cases with longer sequences.

template< typename order_iterator, typename value_iterator > void reorder_destructive( order_iterator order_begin, order_iterator order_end, value_iterator v )  {     typedef typename std::iterator_traits< value_iterator >::value_type value_t;     typedef typename std::iterator_traits< order_iterator >::value_type index_t;     typedef typename std::iterator_traits< order_iterator >::difference_type diff_t;          diff_t remaining = order_end - 1 - order_begin;     for ( index_t s = index_t(); remaining > 0; ++ s ) {         index_t d = order_begin[s];         if ( d == (diff_t) -1 ) continue;         -- remaining;         value_t temp = v[s];         for ( index_t d2; d != s; d = d2 ) {             swap( temp, v[d] );             swap( order_begin[d], d2 = (diff_t) -1 );             -- remaining;         }         v[s] = temp;     } }