Triangularizing a tuple

Question

I’ve been trying to upgrade (and slightly adapt) this solution from 2012 using modern features of C++.

My goal is actually slightly simpler than in that question; I’d like this:

triangularize_t<T0, T1, ..., TN-1, TN>

To be equivalent to this:

std::tuple<
  std::tuple<>,
  std::tuple<T0>,
  std::tuple<T0, T1>,
  ...
  std::tuple<T0, T1, ..., TN-1>
>

Such that std::tuple_element_t<N, result> has N elements. The type TN should not appear anywhere in the output.

Here’s what I’ve worked up to so far:

template <class _Tuple, class _Seq>
struct _tuple_head;
template <class _Tuple, size_t... _N>
struct _tuple_head<_Tuple, std::index_sequence<_N...>> {
    using type = std::tuple<std::tuple_element_t<_N, _Tuple>...>;
};


template <class _Tuple, class _Seq>
struct _triangularize_impl;
template <class _Tuple, size_t... _N>
struct _triangularize_impl<_Tuple, std::index_sequence<_N...>> {
    using type = std::tuple<typename _tuple_head<_Tuple, std::make_index_sequence<_N>>::type...>;
};


template <class... _Pack>
struct triangularize {
    using type = _triangularize_impl<std::tuple<_Pack...>, std::index_sequence_for<_Pack...>>;
};


template <class... _Pack>
using triangularize_t = typename triangularize<_Pack...>::type;

However, it doesn’t quite seem to be expanding the way I’d expect it to. Using triangularize_t<int, float> as a test, error messages seem to report that the output for std::get<0> and 1 return these types (identical for some reason).

_triangularize_impl<tuple<std::__1::tuple<int, float> >, __make_integer_seq<integer_sequence, unsigned long, 1UL> >

_triangularize_impl<tuple<std::__1::tuple<int, float> >, __make_integer_seq<integer_sequence, unsigned long, 1UL> >

What have I missed here?

Answer 1

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.

Answer 2

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.

Answer 3

We can avoid having to use any index_sequences by utilizing partial specialization with multiple parameter packs.

#include <tuple>

template <typename Tuple, typename LastTuple, typename First, typename... Rest>
struct triangulate;

template <typename Tuple, typename LastTuple, typename Last>
struct triangulate<Tuple, LastTuple, Last> {
    using type = Tuple;
};

template <typename First, typename Second, typename... TupleTypes, typename... LastTupleTypes, typename... Rest>
struct triangulate<std::tuple<TupleTypes...>, std::tuple<LastTupleTypes...>, First, Second, Rest...> {
    using next = std::tuple<LastTupleTypes..., First>;
    using type = typename triangulate<std::tuple<TupleTypes..., next>, next, Second, Rest...>::type;
};

template <typename... T>
using triangularize_t = typename triangulate<std::tuple<std::tuple<>>, std::tuple<>, T...>::type;

Passing the end product as the first parameter (std::tuple<std::tuples...>>), and the second parameter is the last std::tuple<...> we used.

We then recursively add the next parameter to the last tuple, and add that tuple to the end of the end-result.