How do I reverse the order of element types in a t

Question

How do I reverse the types in a tuple? For example, I want reverse_tuple<std::tuple<int, char, bool>>::type to be std::tuple<bool, char, int>. I tried doing the following but it didn't work. What did I do wrong?

#include <type_traits>
#include <tuple>

template <typename... Ts>
struct tuple_reverse;

template <typename T, typename... Ts>
struct tuple_reverse<std::tuple<T, Ts...>>
{
    using type = typename tuple_reverse<
                            std::tuple<
                               typename tuple_reverse<std::tuple<Ts..., T>>::type
                            >
                          >::type;
};

template <typename T>
struct tuple_reverse<std::tuple<T>>
{
    using type = std::tuple<T>;
};

int main()
{
    using result_type = std::tuple<int, bool, char>;
    static_assert(
        std::is_same<
            tuple_reverse<var>::type, std::tuple<char, bool, int>
        >::value, ""
    );
}

Here are my errors:

prog.cpp: In instantiation of ‘struct tuple_reverse<std::tuple<char, int, bool> >’:
prog.cpp:15:34: recursively required from ‘struct tuple_reverse<std::tuple<bool, char, int> >’
prog.cpp:15:34: required from ‘struct tuple_reverse<std::tuple<int, bool, char> >’
prog.cpp:29:31: required from here
prog.cpp:15:34: error: no type named ‘type’ in ‘struct tuple_reverse<std::tuple<int, bool, char> >’
prog.cpp: In function ‘int main()’:
prog.cpp:30:9: error: template argument 1 is invalid

Answer 1

I came across this question while working on the reversing template parameters for arbitrary types.

Jonathan Wakely's answer works great for tuples but in case anyone else ever needs to reverse any type, i.e. T<P1, P2, ..., Pn> to T<Pn, Pn-1, ..., P1>, here is what I came up with (Reversal logic taken from here).

namespace Details
{
    /// Get the base case template type `T<>` of a templated type `T<...>`
    template<typename>
    struct templated_base_case;

    template <template<typename...> class T, typename... TArgs>
    struct templated_base_case<T<TArgs...>>
    {
        using type = T<>;
    };

    /// Inner reverse logic.
    ///
    /// Reverses the template parameters of a templated type `T` such
    /// that `T<A, B, C>` becomes `T<C, B, A>`.
    ///
    /// Note that this requires `T<>` to exist.
    template<
        typename T,
        typename = typename templated_base_case<T>::type>
    struct reverse_impl;

    template<
        template <typename...> class T,
        typename... TArgs>
    struct reverse_impl<
        typename templated_base_case<T<TArgs...>>::type,
        T<TArgs...>>
    {
        using type = T<TArgs...>;
    };

    template<
        template<typename...> class T,
        typename first,
        typename... rest,
        typename... done>
    struct reverse_impl<
        T<first, rest...>,
        T<done...>>
    {
        using type = typename reverse_impl <T<rest...>, T<first, done...>>::type;
    };

    /// Swap template parameters of two templated types.
    ///
    /// `L<A, B, C> and R<X, Y, Z>` become `L<X, Y, Z> and R<A, B, C>`.
    template<typename L, typename R>
    struct swap_template_parameters;

    template<
        template<typename...> class L,
        template<typename...> class R,
        typename... x,
        typename... y>
    struct swap_template_parameters<L<x...>, R<y...>>
    {
        using left_type = L<y...>;
        using right_type = R<x...>;
    };
}

/// Parameter pack list of types
template <typename... Args>
struct type_list { };

/// Reverses the arguments of a templates type `T`.
///
/// This uses a `type_list` to allow reversing types like std::pair
/// where `std::pair<>` and `std::pair<T>` are not valid.
template<typename T>
struct reverse_type;

template<template<typename...> class T, typename... TArgs>
struct reverse_type<T<TArgs...>>
{
    using type = typename Details::swap_template_parameters<
        T<TArgs...>,
        typename Details::reverse_impl<type_list<TArgs...>>::type>::left_type;
};

Some of the implementation logic can be combined, but I tried to make it as clear as possible here.

reverse_type can be applied to tuples:

using my_tuple = std::tuple<int, bool, char>;

static_assert(
    std::is_same<
        typename reverse_type<my_typle>::type,
        std::tuple<char, bool, int>>::value,
    "");

Or other types:

/// Standard collections cannot be directly reversed easily
/// because they take default template parameters such as Allocator.
template<typename K, typename V>
struct simple_map : std::unordered_map<K, V> { };

static_assert(
    std::is_same<
        typename reverse_type<simple_map<std::string, int>>::type,
        simple_map<int, std::string>>::value,
    "");

Slightly more detailed explanation.

Answer 2

Untested.

template < typename Tuple, typename T >
struct tuple_push;

template < typename T, typename ... Args >
struct tuple_push<std::tuple<Args...>, T>
{
    typedef std::tuple<Args...,T> type;
};

template < typename Tuple >
struct tuple_reverse;

template < typename T, typename ... Args >
struct tuple_reverse<std::tuple<T, Args...>>
{
    typedef typename tuple_push<typename tuple_reverse<std::tuple<Args...>>::type, T>::type type;
};

template < >
struct tuple_reverse<std::tuple<>>
{
    typedef std::tuple<> type;
};

Something there abouts anyway.

This also only reverses the type, which seems to be what you're after. Reversing an actual tuple would involve functions, not metafunctions.

Answer 3

Out of interest, did you really want to reverse a tuple type, or just treat each element in reverse order (as is more often the case in my projects)?

#include <utility>
#include <tuple>
#include <iostream>

namespace detail {

    template<class F, class Tuple, std::size_t...Is>
    auto invoke_over_tuple(F &&f, Tuple &&tuple, std::index_sequence<Is...>) {
        using expand = int[];
        void(expand{0,
                    ((f(std::get<Is>(std::forward<Tuple>(tuple)))), 0)...});
    }


    template<class Sequence, std::size_t I>
    struct append;
    template<std::size_t I, std::size_t...Is>
    struct append<std::index_sequence<Is...>, I> {
        using result = std::index_sequence<Is..., I>;
    };

    template<class Sequence>
    struct reverse;

    template<>
    struct reverse<std::index_sequence<>> {
        using type = std::index_sequence<>;
    };

    template<std::size_t I, std::size_t...Is>
    struct reverse<std::index_sequence<I, Is...>> {
        using subset = typename reverse<std::index_sequence<Is...>>::type;
        using type = typename append<subset, I>::result;
    };
}

template<class Sequence>
using reverse = typename detail::reverse<Sequence>::type;

template
        <
                class Tuple,
                class F
        >
auto forward_over_tuple(F &&f, Tuple &&tuple) {
    using tuple_type = std::decay_t<Tuple>;
    constexpr auto size = std::tuple_size<tuple_type>::value;
    return detail::invoke_over_tuple(std::forward<F>(f),
                                     std::forward<Tuple>(tuple),
                                     std::make_index_sequence<size>());
};

template
        <
                class Tuple,
                class F
        >
auto reverse_over_tuple(F &&f, Tuple &&tuple) {
    using tuple_type = std::decay_t<Tuple>;
    constexpr auto size = std::tuple_size<tuple_type>::value;
    return detail::invoke_over_tuple(std::forward<F>(f),
                                     std::forward<Tuple>(tuple),
                                     reverse<std::make_index_sequence<size>>());
};

int main()
{
    auto t = std::make_tuple("1", 2, 3.3, 4.4, 5, 6, "7");
    forward_over_tuple([](auto &&x) { std::cout << x << " "; }, t);
    std::cout << std::endl;

    reverse_over_tuple([](auto &&x) { std::cout << x << " "; }, t);
    std::cout << std::endl;
}

Answer 4

What you did wrong was here:

using type = typename tuple_reverse<
                        std::tuple<
                           typename tuple_reverse<std::tuple<Ts..., T>>::type
                        >
                      >::type;

Looking at it from the inside out, you reorder the tuple elements: tuple<Ts..., T>, then you try to reverse that, then you put the result in a tuple, then you try to reverse that ... huh?! :)

This means each time you instantiate tuple_reverse you give it a tuple of the same size, so it never finishes, and recursively instantiates itself forever. (Then, if that recursion even finished, you put the resulting tuple type into a tuple, so you have a single-element tuple containing an N-element tuple, and reverse that, which does nothing because reversing a single-element tuple is a no-op.)

You want to peel off one of the elements, then reverse the rest, and concatenate it back again:

using head = std::tuple<T>;
using tail = typename tuple_reverse<std::tuple<Ts...>>::type;

using type = decltype(std::tuple_cat(std::declval<tail>(), std::declval<head>()));

And you don't need to wrap it in a tuple and reverse it again :)

And you should also handle the empty tuple case, so the whole thing is:

template <typename... Ts>
struct tuple_reverse;

template <>
struct tuple_reverse<std::tuple<>>
{
    using type = std::tuple<>;
};

template <typename T, typename... Ts>
struct tuple_reverse<std::tuple<T, Ts...>>
{
  using head = std::tuple<T>;
  using tail = typename tuple_reverse<std::tuple<Ts...>>::type;

  using type = decltype(std::tuple_cat(std::declval<tail>(), std::declval<head>()));
};

I'd do it differently though.

To get just the type, using C++14

template<typename T, size_t... I>
struct tuple_reverse_impl<T, std::index_sequence<I...>>
{
  typedef std::tuple<typename std::tuple_element<sizeof...(I) - 1 - I, T>::type...> type;
};

// partial specialization for handling empty tuples:
template<typename T>
struct tuple_reverse_impl<T, std::index_sequence<>>
{
  typedef T type;
};

template<typename T>
struct tuple_reverse<T>
: tuple_reverse_impl<T, std::make_index_sequence<std::tuple_size<T>::value>>
{ };

Or you can write a function to reverse an actual tuple object, then use decltype(reverse(t)) to get the type. To reverse a tuple-like object in C++14:

template<typename T, size_t... I>
auto
reverse_impl(T&& t, std::index_sequence<I...>)
{
  return std::make_tuple(std::get<sizeof...(I) - 1 - I>(std::forward<T>(t))...);
}

template<typename T>
auto
reverse(T&& t)
{
  return reverse_impl(std::forward<T>(t),
                      std::make_index_sequence<std::tuple_size<T>::value>());
}

In C++11 use <integer_seq.h> and add return types and use remove_reference to strip references from the tuple type (because tuple_size and tuple_element don't work with references to tuples):

template<typename T, typename TT = typename std::remove_reference<T>::type, size_t... I>
auto
reverse_impl(T&& t, redi::index_sequence<I...>)
-> std::tuple<typename std::tuple_element<sizeof...(I) - 1 - I, TT>::type...>
{
    return std::make_tuple(std::get<sizeof...(I) - 1 - I>(std::forward<T>(t))...);
}

template<typename T, typename TT = typename std::remove_reference<T>::type>
auto
reverse(T&& t)
-> decltype(reverse_impl(std::forward<T>(t),
                        redi::make_index_sequence<std::tuple_size<TT>::value>()))
{
    return reverse_impl(std::forward<T>(t),
                        redi::make_index_sequence<std::tuple_size<TT>::value>());
}