In-place permutation (O(n) time, O(1) memory)

#include <iostream>
#include <iterator>
#include <vector>
#include <algorithm>

#include <cstdlib>
#include <cassert>

template< class V >
struct perfect_shuffle_permutation_forward
{

    typedef typename V::iterator I;
    typedef typename V::size_type SIZE;

    void operator () (V & v) const
    {
        operator () (v.begin(), v.size());
    }

    void operator () (I const begin, I const end) const
    {
        operator () (begin, std::distance(begin, end));
    }

    void operator () (I const begin, SIZE const size) const
    {
        if (size < 3) {
            return;
        }
        SIZE sub_size(1);
        while (sub_size * 3 < size) { // std::pwr(3, (int)std::floor(std::log(size) / std::log(3)))
            sub_size *= 3;
        }
        SIZE path(0);
        SIZE rest(size);
        while (sub_size > 0) {
            cycle_leader(begin + (size - rest), sub_size);
            path += sub_size;
            rest -= (sub_size + 1);
            if (!(rest > 1)) {
                break;
            }
            while (!(rest > sub_size)) {
                sub_size /= 3;
            }
        }
        I curr(begin + (size - rest));
        sub_size = 1;
        while (path > 0) {
            while ((path % 3) != 0) {
                --path;
                SIZE const h((sub_size + 1) / 2);
                if (rest > 0) {
                    std::rotate(curr - h, curr, curr + rest);
                    rest += h;
                } else {
                    rest = h;
                }
                curr -= 2 * h;
            }
            path /= 3;
            sub_size *= 3;
        }
    }

private :

    void cycle_leader(I const & begin, SIZE const & size) const
    {
        for (SIZE p(1); p < size; p *= 3) {
            permutation permutation_(p, size);
            I current(begin + p);
            auto const leader(*current);
            while (++permutation_) {
                I const next(begin + permutation_);
                *current = *next;
                current = next;
            }
            *current = leader;
        }
    }

    struct permutation
    {

        permutation(SIZE const & leader_, SIZE  const & size_)
            : leader(leader_)
            , current(leader_)
            , size(size_)
        { ; }

        bool operator ++ ()
        {
            current *= 2;
            if (current > size) {
                current -= size;
            }
            return (current != leader);
        }

        operator SIZE () const
        {
            return current;
        }

    private :

        SIZE const & leader;
        SIZE current;
        SIZE const & size;

    };

};

template< class V >
struct perfect_shuffle_permutation_backward
{

    typedef typename V::iterator I;
    typedef typename V::size_type SIZE;

    void operator () (V & v) const
    {
        operator () (v.begin(), v.size());
    }

    void operator () (I const begin, I const end) const
    {
        operator () (begin, std::distance(begin, end));
    }

    void operator () (I const begin, SIZE const size) const
    {
        SIZE sub_size;
        for (SIZE offset(0); offset + 1 < size; offset += sub_size) {
            sub_size = 1;
            while (offset + sub_size * 3 < size) {
                sub_size *= 3;
            }
            I const current(begin + offset);
            {
                SIZE const rest(size - offset);
                I const first(current + (sub_size + 1) / 2);
                I const middle(current + (rest / 2 + rest % 2));
                I const last(middle + (sub_size + 1) / 2);
                std::rotate(first, middle, last);
            }
            cycle_leader(current, sub_size);
            ++sub_size;
        }
    }

private :

    void cycle_leader(I const & begin, SIZE const & size) const
    {
        for (SIZE p(1); p < size; p *= 3) {
            permutation permutation_(p, size);
            I current(begin + p);
            auto const leader(*current);
            while (++permutation_) {
                I const next(begin + permutation_);
                *current = *next;
                current = next;
            }
            *current = leader;
        }
    }

    struct permutation
    {

        permutation(SIZE const & leader_, SIZE  const & size_)
            : leader(leader_)
            , current(leader_)
            , size(size_)
        { ; }

        bool operator ++ ()
        {
            if ((current % 2) != 0) {
                current += size;
            }
            current /= 2;
            return (current != leader);
        }

        operator SIZE () const
        {
            return current;
        }

    private :

        SIZE const & leader;
        SIZE current;
        SIZE const & size;

    };

};

template< class V >
struct test
{

    typedef typename V::size_type SIZE;
    typedef typename V::value_type F;
    typedef perfect_shuffle_permutation_forward< V > PF;
    typedef perfect_shuffle_permutation_backward< V > PB;

    bool operator () (SIZE const VECTOR_SIZE) const
    {
        V v;
        v.reserve(VECTOR_SIZE);
        for (SIZE i(0); i < v.capacity(); ++i) {
            v.push_back(F(i));
        }

        V w(v);

        //std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
        //std::cout << std::endl;

        PF perfect_shuffle_permutation_forward_;
        perfect_shuffle_permutation_forward_(v);

        //std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
        //std::cout << std::endl;

        PB perfect_shuffle_permutation_backward_;
        perfect_shuffle_permutation_backward_(v);

        //std::copy(v.begin(), v.end(), std::ostream_iterator< F >(std::cout, " "));
        //std::cout << std::endl;

        return ((v.size() == w.size()) && std::equal(v.begin(), v.end(), w.begin()));
    }

};

int main(int argc, char *argv[])
{
    typedef std::vector< int > V;
    test< V > test_;

    for (std::size_t i(1); i <= std::numeric_limits< std::size_t >::max(); i *= 2) {
        std::cout << "@ " << i << std::endl;
        assert(test_(i));
    }

    return EXIT_SUCCESS;
}