Triangularizing a tuple

Maybe someone can make it in a simpler way... but what about as follows?

template <typename T, std::size_t ... Is>
auto gtt_helper (std::index_sequence<Is...>)
 -> std::tuple<std::tuple_element_t<Is, T>...>;

template <typename ... Ts, std::size_t ... Is>
auto getTriTuple (std::index_sequence<Is...>)
 -> std::tuple<decltype(gtt_helper<std::tuple<Ts...>>
                        (std::make_index_sequence<Is>{}))...>;

template <typename ... Ts>
using triTuple
  = decltype(getTriTuple<Ts...>(std::index_sequence_for<Ts...>{}));

The following is a full compiling C++14 example

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

template <typename T, std::size_t ... Is>
auto gtt_helper (std::index_sequence<Is...>)
 -> std::tuple<std::tuple_element_t<Is, T>...>;

template <typename ... Ts, std::size_t ... Is>
auto getTriTuple (std::index_sequence<Is...>)
 -> std::tuple<decltype(gtt_helper<std::tuple<Ts...>>
                        (std::make_index_sequence<Is>{}))...>;

template <typename ... Ts>
using triTuple
  = decltype(getTriTuple<Ts...>(std::index_sequence_for<Ts...>{}));

int main () 
 {
   using T0 = triTuple<char, int, long, long long>;
   using T1 = std::tuple<std::tuple<>,
                         std::tuple<char>,
                         std::tuple<char, int>,
                         std::tuple<char, int, long>>;

   static_assert( std::is_same<T0, T1>::value, "!" );
 }

To respond to your question ("What have I missed here?"), you have missed a typename and a ::type in triangularize

It seems to me that the right version should be

template <class... _Pack>
struct triangularize {
// ..........VVVVVVVV  add typename
using type = typename _triangularize_impl<std::tuple<_Pack...>,
                                          std::index_sequence_for<_Pack...>>::type ;
// and add ::type ..........................................................^^^^^^
};

Unfortunately, your (corrected) code seems to works with clang++ but not with g++; I suspect a g++ bug but I'm not sure.


With Boost.Mp11 this is... unfortunately not a one-liner. It takes a couple lines instead.

We define one function to perform a single action: given a list of everything and the next element, append that one (that is, this takes us from the Nth solution to the N+1st solution):

template <typename L, typename T>
using add_one = mp_push_back<L, mp_push_back<mp_back<L>, T>>;

And now fold over that - which just applies that binary function for each argument in turn:

template <typename... Ts>
using triangularize_t = mp_fold<mp_list<Ts...>, tuple<tuple<>>, add_one>;

And check that it's correct:

static_assert(std::is_same_v<triangularize_t<>,
    tuple<tuple<>>>);
static_assert(std::is_same_v<triangularize_t<int>,
    tuple<tuple<>, tuple<int>>>);
static_assert(std::is_same_v<triangularize_t<int, char>,
    tuple<tuple<>, tuple<int>, tuple<int, char>>>);

We can generalize this to work on any class template instead of solely tuple by changing triangularize to use an input list and deduce its initial value from the input argument:

template <typename L>
using triangularize_t = mp_fold<L, mp_push_back<mp_clear<L>, mp_clear<L>>, add_one>;

Which also allows:

static_assert(std::is_same_v<triangularize_t<mp_list<int, char>>,
    mp_list<mp_list<>, mp_list<int>, mp_list<int, char>>>);

Or whatever other lists you might want to use (notably not variant, since variant<> is ill-formed).


With Boost.Mp11 this is a one-liner. I just didn't try hard enough last time. Also this solution matches OP's exact specification:

template <typename... Ts>
using triangularize_t =
    mp_transform_q<
        mp_bind_front<mp_take, std::tuple<Ts...>>,
        mp_rename<mp_iota_c<sizeof...(Ts)>, std::tuple>
        >;

Lemme explain what this does, assuming Ts... is <int, char>.

  • mp_iota_c<sizeof...(Ts)> gives the sequence mp_list<mp_int<0>, mp_int<1>>.
  • mp_rename swaps out one "list" type for another, in this case mp_list for std::tuple so you get std::tuple<mp_int<0>, mp_int<1>>.
  • mp_bind_front<mp_take, std::tuple<Ts...>> creates a metafunction on the fly that will take an argument and apply it to mp_take on the full tuple<Ts...>. mp_take takes the first N things from the given list. If we passed in mp_int<1> to this, on our initial tuple<int, char>, we'd get tuple<int>.
  • mp_transform_q calls the provided metafunction on each element in the list. We take our tuple<mp_int<0>, mp_int<1>> and expand it out into tuple<mp_take<tuple<int, char>, mp_int<0>>, mp_take<tuple<int, char>, mp_int<1>>> which is tuple<tuple<>, tuple<int>>. As desired.

To change this into my other answer (which triangularizes <int> into tuple<tuple<>, tuple<int>>), we can change sizeof...(Ts) into sizeof...(Ts)+1.

To extend this to support any list type (not just tuple), we can change the metafunction here to take a list instead of a pack and use the provided list type as a solution. In some respects, this makes the solution easier:

template <typename L>
using triangularize_t =
    mp_transform_q<
        mp_bind_front<mp_take, L>,
        mp_append<mp_clear<L>, mp_iota<mp_size<L>>>
        >;

template <typename... Ts>
using triangularize_t = triangularize_list<std::tuple<Ts...>>;

The awkward part here is the mp_append<mp_clear<L>, mp_iota<mp_size<L>>>. Basically, we need the sequence list to have the same list type as the original list. Before, we could use mp_rename because we know we needed a tuple. But now, we don't have the list as a class template - just have an instance of it. There might be a better way to do this than mp_append<mp_clear<L>, U>... but this is what I have so far.

Tags:

C++

C++17

Recent Posts