Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do I reverse the order of element types in a tuple type?

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

like image 354
Me myself and I Avatar asked Jun 18 '13 20:06

Me myself and I


3 Answers

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.

like image 32
Edward Strange Avatar answered Oct 27 '22 06:10

Edward Strange


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>());
}
like image 182
Jonathan Wakely Avatar answered Oct 27 '22 07:10

Jonathan Wakely


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.

like image 30
Matt Bierner Avatar answered Oct 27 '22 05:10

Matt Bierner