How to flatten heterogeneous lists (aka tuples of tuples of ...)

Question

I am attempting to employ C++17 fold expressions and the C++14 indices trick to flatten an arbitrary input consisting of tuples and non-tuples.

The expected result should at least conform to these requirements:

constexpr auto bare = 42;

constexpr auto single = std::tuple{bare};
constexpr auto nested_simple = std::tuple{single};

constexpr auto multiple = std::tuple{bare, bare};
constexpr auto nested_multiple = std::tuple{multiple};

constexpr auto multiply_nested = std::tuple{multiple, multiple};

static_assert(flatten(bare) == bare);
static_assert(flatten(single) == bare);
static_assert(flatten(nested_simple) == bare);

static_assert(flatten(multiple) == multiple);
static_assert(flatten(nested_multiple) == multiple);

static_assert(flatten(multiply_nested) == std::tuple{bare, bare, bare, bare});

I have relatively simple code to handle all but the last case:

template<typename T>
constexpr decltype(auto) flatten(T&& t)
{
    return std::forward<T>(t);
}

template<typename T>
constexpr decltype(auto) flatten(std::tuple<T> t)
{
    return std::get<0>(t);
}

template<typename... Ts>
constexpr decltype(auto) flatten_multi(Ts&&... ts)
{
    return std::make_tuple(flatten(ts)...);
}

template<typename... Ts, std::size_t... Indices>
constexpr decltype(auto) flatten_impl(std::tuple<Ts...> ts, const std::index_sequence<Indices...>&)
{
    return flatten_multi(std::get<Indices>(ts)...);
}

template<typename... Ts>
constexpr decltype(auto) flatten(std::tuple<Ts...> ts)
{
    return flatten_impl(ts, std::make_index_sequence<sizeof...(Ts)>());
}

Live demo here. Obviously, it doesn't handle multiply nested items well.

The more advanced form to handle the multiply_nested case I haven't found. I tried applying operator>> to be able to use fold expressions, but haven't been able to get anything that compiles. My last attempt can be found here. The core idea is to use operator>> in a fold expression to combine elements 2 by 2, each time unwrapping the previous result.

It seems to me I should be able to use something like std::tuple_cat, but it shouted at me quite loudly for reasons I couldn't decipher completely.

So my question is this: what am I missing? How can I unwrap an arbitrarily deeply arbitrarily nested tuple-like input?

Answer 1

I propose to SFINAE on presence of tuple

// Simple traits
template <typename T> struct is_tuple : std::false_type{};
template <typename... Ts> struct is_tuple<std::tuple<Ts...>> : std::true_type{};

// utility to ensure return type is a tuple
template<typename T>
constexpr decltype(auto) as_tuple(T t) { return std::make_tuple(t); }

template<typename ...Ts>
constexpr decltype(auto) as_tuple(std::tuple<Ts...> t) { return t; }

// Simple case
template<typename T>
constexpr decltype(auto) flatten(T t)
{
    return t;
}

// Possibly recursive tuple
template<typename T>
constexpr decltype(auto) flatten(std::tuple<T> t)
{
    return flatten(std::get<0>(t));
}

// No more recursion, (sizeof...Ts != 1) with above overload
template<typename ...Ts, std::enable_if_t<!(is_tuple<Ts>::value || ...), bool> = false>
constexpr decltype(auto) flatten(std::tuple<Ts...> t)
{
    return t;
}

// Handle recursion
template<typename ...Ts, std::enable_if_t<(is_tuple<Ts>::value || ...), bool> = false>
constexpr decltype(auto) flatten(std::tuple<Ts...> t)
{
    return std::apply([](auto...ts)
                      {
                          return flatten(std::tuple_cat(as_tuple(flatten(ts))...));
                      }, t);
}

Demo

Answer 2

namespace flattenns {
  struct flat_t {};

  template<std::size_t... Is, class...As>
  constexpr auto flatten( std::index_sequence<Is...>, flat_t, std::tuple<As...> as ) {
    return std::tuple_cat( flatten(flat_t{}, std::get<Is>(as))... );
  }
  template<class...As, class...Ts>
  constexpr auto flatten( flat_t, std::tuple<As...> as ) {
    return flatten( std::make_index_sequence<sizeof...(As)>{}, flat_t{}, as );
  }
  template<class T>
  constexpr std::tuple<T> flatten( flat_t, T t ) { return {t}; }

  template<class...Ts>
  constexpr auto flatten( flat_t, Ts... ts ) {
    return std::tuple_cat( flatten(flat_t{}, ts)... );
  }
  constexpr std::tuple<> flatten( flat_t ) { return {}; }
}
template<class...Ts>
constexpr auto sane_flatten( Ts...ts ) {
  return flattenns::flatten(flattenns::flat_t{}, ts...);
}

// to take std::tuple<int>(7) -> 7
namespace insanens {
    template<class...Ts>
    constexpr auto unpack_single( std::tuple<Ts...> t ) {return t;}
    template<class T>
    constexpr auto unpack_single( std::tuple<T> t ) {return std::get<0>(t);}
}
template<class...Ts>
constexpr auto insane_flatten( Ts...ts ) {
  return insanens::unpack_single( sane_flatten(ts...) );
}
template<class...Ts>
constexpr auto flatten( Ts...ts ) {
    return insane_flatten(ts...);
}

As noted above, flatten( std::tuple<int>(7) ) should NOT BE 7. That is insanity.

But as you want it, I add it as a post-processing step.

Your operation is otherwise relatively sane. You are recursively applying [[x],[y]] to [x,y]. The final unboxing is not sane. By splitting it off, the code becomes easy, which is also evidence why it is insane.

Live example.

In case you are wondering, the flat_t tag type exists in order to (a) split the index sequence from a possible argument (which could be done by having a different function name) and (b) enable ADL lookup so every implementation of flatten can see all of the other ones.

Answer 3

Here is another version that has two design goals:

1. avoid construction of temporary tuples and avoid std::tuple_cat
2. explicitly determine the types in the final tuple

For avoiding temporary tuples and std::tuple_cat, it is useful to predict the final size of the output tuple. Let us define a helper called get_rank:

#include <cstddef>

#include <tuple>
#include <type_traits>

template<class T>
struct Type {// tag type
  using type = T;
};

template<class T>
constexpr std::size_t get_rank(Type<T>) {
  static_assert(!std::is_const<T>{} && !std::is_volatile<T>{}, "avoid surprises");
  return 1;
}

template<class... Ts>
constexpr std::size_t get_rank(Type< std::tuple<Ts...> >) {
  return (0 + ... + get_rank(Type<Ts>{}));
}

The flatten function can utilize get_rank in order to create an index sequence for the elements of the output tuple. This sequence is passed to flatten_impl together with the forwarded input tuple and a type tag. Let us explicitly provide lvalue and rvalue overloads for the interface function, but use perfect forwarding internally:

#include <cstddef>

#include <tuple>
#include <utility>

// to be implemented
#include "tuple_element_at_rankpos_t.hpp"
#include "get_at_rankpos.hpp"

template<std::size_t... rank_positions, class Tuple, class... Ts>
constexpr auto flatten_impl(
  std::index_sequence<rank_positions...>,
  Tuple&& tuple,
  Type< std::tuple<Ts...> > tuple_tag
) {
  return std::tuple<
    tuple_element_at_rankpos_t< rank_positions, std::tuple<Ts...> >...
  >{
    get_at_rankpos<rank_positions>(std::forward<Tuple>(tuple), tuple_tag)...
  };
}

template<class... Ts>
constexpr auto flatten(const std::tuple<Ts...>& tuple) {
  using TupleTag = Type< std::tuple<Ts...> >;
  constexpr std::size_t rank = get_rank(TupleTag{});
  return flatten_impl(
    std::make_index_sequence<rank>{}, tuple, TupleTag{}
  );
}

template<class... Ts>
constexpr auto flatten(std::tuple<Ts...>& tuple) {
  using TupleTag = Type< std::tuple<Ts...> >;
  constexpr std::size_t rank = get_rank(TupleTag{});
  return flatten_impl(
    std::make_index_sequence<rank>{}, tuple, TupleTag{}
  );
}

template<class... Ts>
constexpr auto flatten(std::tuple<Ts...>&& tuple) {
  using TupleTag = Type< std::tuple<Ts...> >;
  constexpr std::size_t rank = get_rank(TupleTag{});
  return flatten_impl(
    std::make_index_sequence<rank>{}, std::move(tuple), TupleTag{}
  );
}

At this point, we need two more building blocks:

• tuple_element_at_rankpos_t (like std::tuple_element_t, but for nested tuples) and
• get_at_rankpos (like std::get, but for nested tuples).

Either building block shall find the type/value of an element in the nested input tuple based on the element's position in the flattened output tuple. At each nesting level, these building blocks need to extract the index for the current nesting depth from the rankpos. This common index computation can be moved to an extract_index helper. The first building block may look like this:

#include <cassert>
#include <cstddef>

#include <array>
#include <tuple>
#include <utility>

template<class... Ts>
constexpr auto extract_index(
  std::size_t rankpos, Type< std::tuple<Ts...> >
) {
  static_assert(sizeof...(Ts) >= 1, "do not extract from empty tuples");

  constexpr auto ranks = std::array{get_rank(Type<Ts>{})...};

  std::size_t index = 0;
  std::size_t nested_rankpos = rankpos;

  while(nested_rankpos >= ranks[index]) {
    nested_rankpos -= ranks[index++];
    assert(index < sizeof...(Ts));
  }

  return std::pair{index, nested_rankpos};
}

////////////////////////////////////////////////////////////////////////////////

template<std::size_t rankpos, class T>
constexpr auto tuple_element_at_rankpos_tag(
  Type<T> /* element_tag */
) {
  static_assert(rankpos == 0);
  return Type<T>{};
}

template<std::size_t rankpos, class... Ts>
constexpr auto tuple_element_at_rankpos_tag(
  Type< std::tuple<Ts...> > tuple_tag
) {
// constexpr auto [index, nested_rankpos] = extract_index(rankpos, tuple_tag);
  constexpr std::pair pair = extract_index(rankpos, tuple_tag);
  constexpr std::size_t index = pair.first;
  constexpr std::size_t nested_rankpos = pair.second;

  using NestedType = std::tuple_element_t< index, std::tuple<Ts...> >;

  return tuple_element_at_rankpos_tag<nested_rankpos>(
    Type<NestedType>{}
  );
}

template<std::size_t rankpos, class Tuple>
using tuple_element_at_rankpos_t = typename decltype(
  tuple_element_at_rankpos_tag<rankpos>(Type<Tuple>{})
)::type;

The second building block is a repetition of the same glue code as above. In addition to the type we need to handle the values (lvalue, const lvalue, rvalue). Using perfect forwarding we may write:

template<std::size_t rankpos, class Element, class T>
constexpr decltype(auto) get_at_rankpos(
  Element&& element,
  Type<T> /* element_tag */
) {
  static_assert(rankpos == 0);
  return std::forward<Element>(element);
}

template<std::size_t rankpos, class Tuple, class... Ts>
constexpr decltype(auto) get_at_rankpos(
  Tuple&& tuple,
  Type< std::tuple<Ts...> > tuple_tag
) {
// constexpr auto [index, nested_rankpos] = extract_index(rankpos, tuple_tag);
  constexpr std::pair pair = extract_index(rankpos, tuple_tag);
  constexpr std::size_t index = pair.first;
  constexpr std::size_t nested_rankpos = pair.second;

  using NestedType = std::tuple_element_t< index, std::tuple<Ts...> >;

  return get_at_rankpos<nested_rankpos>(
    std::get<index>(std::forward<Tuple>(tuple)),
    Type<NestedType>{}
  );
}

Answer 4

Something perhaps a little more straightforward, although more verbose: partial class template specialization + if constexpr:

The basic approach is to specialize the following base class:

template<class... T>
struct flatten
{};

To account for our three cases:

1. A bare value
2. A tuple of one thing
3. A tuple of more than one thing

---

Case #1, the base case, is fairly straightforward, just return what we get:

//base case: something that isn't another tuple
template<class T>
struct flatten<T>
{
    template<class U>
    constexpr decltype(auto) operator()(U&& _value){
        return std::forward<U>(_value);
    }
};

Case #2 is also pretty straightforward, just recurse on itself until we reach Case #1

// recursive case 1 : plain old tuple of one item
template<class T>
struct flatten<std::tuple<T>>
{
    template<class U>
    constexpr decltype(auto) operator()(U&& _tup){
        return flatten<std::remove_cvref_t<T>>{}(std::get<0>(_tup));
    }
};

Case #3 is long because of the possible sub-cases, but each block is pretty readable. We

• Flatten the first element (possibly recurses)
• Flatten the rest of the elements (possible recurses)

And then we have four cases to consider:

1. We have two tuples (e.g., tuple<int, int>, tuple<int, int>)
2. We have a tuple and a value (e.g., tuple<int, int>, int)
3. We have a value and a tuple (e.g., int, tuple<int, int>)
4. We have two values (e.g., int, int)

We just need one helper function that allows us to strip the head off a tuple and return the rest of it.

// helper for getting tuple elements except the first one
template<template<class...> class Tup, class... T, size_t... indices>
constexpr auto get_rest_of_tuple(const Tup<T...>& _tup, std::index_sequence<indices...>){
   return std::make_tuple(std::get<indices + 1>(_tup)...);
}

and some helper traits:

// some type traits to use for if constexpr
template<class T>
struct is_tuple : std::false_type{};
template<class... T>
struct is_tuple<std::tuple<T...>> : std::true_type{};
template<class T>
constexpr bool is_tuple_v = is_tuple<T>::value;

Finally the impl:

// recursive case 2: tuple of more than one item
template<class First, class Second, class... Rest>
struct flatten<std::tuple<First, Second, Rest...>>
{
    template<class Tup>
    constexpr decltype(auto) operator()(Tup&& _tup){
        auto flattened_first = flatten<std::remove_cvref_t<First>>{}(std::get<0>(_tup));
        auto restTuple = get_rest_of_tuple(_tup, std::make_index_sequence<sizeof...(Rest)+1>{});
        auto flattened_rest = flatten<std::remove_cvref_t<decltype(restTuple)>>{}(restTuple);
        // both are tuples
        if constexpr(is_tuple_v<decltype(flattened_first)> && is_tuple_v<decltype(flattened_rest)>)
        {
            return std::tuple_cat(flattened_first, flattened_rest);
        }
        // only second is tuple
        if constexpr(!is_tuple_v<decltype(flattened_first)> && is_tuple_v<decltype(flattened_rest)>)
        {
            return std::tuple_cat(std::make_tuple(flattened_first), flattened_rest);
        }
        //only first is tuple
        if constexpr(is_tuple_v<decltype(flattened_first)> && !is_tuple_v<decltype(flattened_rest)>)
        {
            return std::tuple_cat(flattened_first, std::make_tuple(flattened_rest));
        }
        // neither are tuples
        if constexpr(!is_tuple_v<decltype(flattened_first)> && !is_tuple_v<decltype(flattened_rest)>)
        {
            return std::tuple_cat(std::make_tuple(flattened_first), std::make_tuple(flattened_rest));
        }
    }
};
} // namespace detail

Finally, we use trampolining to hide all these details from the end user by shoving them into a details namespace and exposing the following function to call into them:

template<class T>
constexpr decltype(auto) flatten(T&& _value){
    return detail::flatten<std::remove_cvref_t<T>>{}(std::forward<T>(_value));
}

Demo

(includes some additional tests for correctness)

---

While the impl of Case #3 above is pretty straightforward it is both verbose and a bit inefficient (the compiler evaluates each of those if constexpr statements when it should only evaluate one, but I didn't want to string along else branches because of the nesting).

We can pretty vastly simplify Case #3 by diverting to two helper functions that detect whether the argument is a tuple of not and return the right thing:

template<class U, std::enable_if_t<!is_tuple_v<U>, int> = 0>
constexpr decltype(auto) flatten_help(U&& _val){
    return std::make_tuple(_val);
}

template<class... T>
constexpr decltype(auto) flatten_help(const std::tuple<T...>& _tup){
    return _tup;
}

// recursive case 2: tuple of more than one item
template<class First, class Second, class... Rest>
struct flatten<std::tuple<First, Second, Rest...>>
{
    template<class Tup>
    constexpr decltype(auto) operator()(Tup&& _tup){
        auto flattened_first = flatten<std::remove_cvref_t<First>>{}(std::get<0>(_tup));
        auto restTuple = get_rest_of_tuple(_tup, std::make_index_sequence<sizeof...(Rest)+1>{});
        auto flattened_rest = flatten<std::remove_cvref_t<decltype(restTuple)>>{}(restTuple);
        return std::tuple_cat(flatten_help(flattened_first), flatten_help(flattened_rest));
    }
};

Demo 2