Rotate a given number of variables in-place

Question

A very simple but useful algorithm: rotate the values of a given number of variables in-place to the left so that the first variable gets the value of the second, the second gets the value of the third, etc... and the last variable gets the value of the first one.

#include <type_traits>
#include <utility>

template<typename Head, typename... Tail>
struct are_same:
    std::conjunction<std::is_same<Head, Tail>...>
{};

template<typename T, typename... Args>
auto rotate_left_inner(T& first, T& second, Args&... args)
    -> T&
{
    first = std::move(second);
    if constexpr (sizeof...(Args) == 0) {
        return second;
    } else {
        return rotate_left_inner(second, args...);
    }
}

template<typename Head, typename... Tail>
auto rotate_left(Head& first, Tail&... args)
    -> void
{
    static_assert(are_same<Head, Tail...>::value,
                  "elements passed to rotate_left shall have the same type");

    if constexpr (sizeof...(Tail) > 0) {
        auto tmp = std::move(first);
        auto& last = rotate_left_inner(first, args...);
        last = std::move(tmp);
    }
}

This function can be used as follows:

int a=0, b=1, c=2, d=3, d=4;
rotate_left(a, c, e);
rotate_left(b, d);
// Now (a, b, c, d, e) = (2, 3, 4, 1, 0)

The code above generated the same assembly than the hand-rolled version when I gave it five integers to rotate in the compiler explorer, with both GCC and Clang.

I wanted to make a companion rotate_right function, but repeatedly finding the last element of a template parameter pack is not as easy, so the easiest solution for a programmer is to pass the variables to rotate to rotate_left in reverse order.

Do you see any way to improve this simple algorithm? Anything that I might be missing?

Answer 1

Issues (for me)

I get a couple of errors when I try and compile.

This error I have a feeling is caused because you are using a more up to date compiler (I presume this is a C++17 feature).

if constexpr (sizeof...(Tail) > 0) {
   ^^^^^^^^^

This problem causes my second error (because I remove constexpr to make it compile):

rt.cpp:12:6: note: candidate function template not viable: requires at least 2 arguments, but 1 was provided
auto rotate_left_inner(T& first, T& second, Args&... args)

Assuming that constexpr forces that expression to be evaluated at compile time and thus removes that whole block of code. Then it should compile.

Review

You and I differ on how we like to express the return value. I believe we have already had the discussion. So I just want to point it out for other readers.

// You
auto rotate_left(Head& first, Tail&... args)
    -> void

// Me
void rotate_left(Head& first, Tail&... args)

But I don't see anything wrong with yours either, its a simple stylistic thing.

Personally I don't like recursive template meta programming. Two reasons:

• This was because when templates were first introduced there was a recursive limit on most compilers. I think this is purely historical now as most compilers have really huge recursive limits now.

• Recursive template functions needed a terminating version of the function. But this new constexpr if statement seems to be in response to that. So you no longer need a special case and it can be handled by the compiler.

So it looks like both my reasons for disliking recursive template functions have been addressed by the new version of the language.

But I still prefer the style of the unrolling the argument loop in a function. So I present my version of the same function to show readers how it is done without using recursion (template iterative style).

#include <type_traits>
#include <utility>
#include <tuple>


template<typename T, std::size_t... index>
void rotate_left_inner(T&& tuple, std::index_sequence<index...> const&)
{
    auto tmp = std::move(std::get<0>(tuple));
    auto mover = {0, (std::get<index>(tuple) = std::move(std::get<index + 1>(tuple)), 0)...};
    std::get<sizeof...(index)>(tuple) = std::move(tmp);
}

template<typename... List>
void rotate_left(List&... args)
{
    rotate_left_inner(std::tie(args...), std::make_index_sequence<sizeof...(args) - 1>());
}

#include <iostream>

int main()
{
    int t1 = 5;
    int t2 = 6;
    int t3 = 7;

    rotate_left(t1, t2, t3);
    std::cout << t1 << " " << t2 << " " << t3 << "\n";

    rotate_left(t1);
    std::cout << t1 << " " << t2 << " " << t3 << "\n";
}