Reorder vector using a vector of indices [duplicate]

by

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;
    }
}

More Related Contents:

  1. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  2. Erasing elements from a vector
  3. Why can’t I make a vector of references?
  4. What is the easiest way to initialize a std::vector with hardcoded elements?
  5. Alternative to vector
  6. Why isn’t vector a STL container?
  7. Best way to extract a subvector from a vector?
  8. When vectors are allocated, do they use memory on the heap or the stack?
  9. reduce the capacity of an stl vector
  10. How to sum up elements of a C++ vector?
  11. How to avoid memory leaks when using a vector of pointers to dynamically allocated objects in C++?
  12. Does vector::erase() on a vector of object pointers destroy the object itself?
  13. Where can I get a “useful” C++ binary search algorithm?
  14. How to get a random element from a C++ container?
  15. how do you insert the value in a sorted vector?
  16. c++ sort keeping track of indices [duplicate]
  17. How to use std::sort with a vector of structures and compare function?
  18. std::vector, default construction, C++11 and breaking changes
  19. Initial capacity of vector in C++
  20. std::vector iterator invalidation
  21. How to make elements of vector unique? (remove non adjacent duplicates)
  22. How to downsize std::vector?
  23. C++ convert vector to vector
  24. Getting a vector into a function that expects a vector
  25. Can std::vector emplace_back copy construct from an element of the vector itself?
  26. Why is a C++ Vector called a Vector? [closed]
  27. Why there is no std::copy_if algorithm?
  28. C++ STL: Array vs Vector: Raw element accessing performance
  29. Checking if all elements of a vector are equal in C++
  30. How to cheaply assign C-style array to std::vector?

Leave a Comment