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?

Alaynaalayne

Note that this constexpr auto nested_simple = std::tuple{single}; doesn't do what you think it does. – Bobbiebobbin

@Bobbiebobbin Good point! All this time I was wondering if make_tuple was superseded by class template argument deduction. I guess not. – Alaynaalayne

Just to clarify: Is it correct that std::tuple<int&> should be flattened to std::tuple<int&> and std::tuple<std::tuple<int, double>&> should be flattened to std::tuple<std::tuple<int, double>&> (i.e., references are untouched)? – Dukas

@Dukas It seems to me, at this moment, yes, references should remain untouched. If a reference was given as input, a reference should come out. – Alaynaalayne

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

Borborygmus

Any way to make this perfect forward... everything possible? I'd like to prevent as many copies (and moves) as possible, and prevent temporaries from materializing in such a flatten operation. – Alaynaalayne

@rubenvb: It should be possible. trick is to SFINAE them for std::tuple so T&& doesn't catch std::tuple& – Borborygmus

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.

Alo

The fact that flattening a single tuple into its element does make sense for my use case (I'm not trying to flatten tuples directly, but a set of classes that can recursively contain instantiations of each other, of which one needs to behave like this). – Alaynaalayne

@Alaynaalayne I have little to tell you except "go learn Haskell and monads". What you are doing is akin to "I want to add two integers together and produce the result. If, however, the integers are 7 and 21, instead produce 0x314159." Sure, there are use cases for that, but it should be done as a separate step and not part of your "add integers" function, and you should double check if your use case is actually sane. Also, modified to reduce recursive depth to recursive depth of tuples, not total length of output. – Alo

The mathematical property I'm modeling is associativity: (a) = a makes sense mathematically. The usual case (a+b)+c = a+b+c is somewhat more useful yes. Besides that tickle of insanity: could fold expressions improve the compile-time performance (i.e. reduce the amount of instantiated recursive templates) in any way or am I barking up the wrong tree in wanting to use that here? – Alaynaalayne

@ruben Except, you are asking for a = something that isn't even an expression. Because (a+b)+c is already in a tuple in this model -- the "outer brakets" of the expression are not written. EXPR(EXPR(a,b),c) = EXPR(a,b,c) is sane, EXPR(a)=EXPR(a) is sane, EXPR(a)=a is way out in left field. I get why you want to do it, and why it feels sane, I'm telling you that way lies dragons. In any case, my recursive depth is O(recursive depth of input), so reducing the recursive depth is only plausible up to a constant factor. Double fold expressions will help there. – Alo

you may well be right (and probably are). Thanks for your time, I haven't figured out exactly what I was missing, but that will come in time once/while I reshape this into my own code and types. – Alaynaalayne

as flatten(42) == 42, it is ok for me that flatten(std::tuple<int>(42)) == 42 (or flatten(std::tuple<std::tuple<int>>(42)) == 42). – Borborygmus

@Borborygmus flatten(42) == std::tuple{42} actually. I rely on that to make the first overload of flatten easier. My flatten is basically recursive monadic bind, I think. – Alo

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>{}
  );
}

Dukas

Interesting approach. I do wonder how much of the temporary tuples remain in C++17 though. Probably a lot due to the tuple's values being shuffled into new tuples. I like the full-blown "let's flatten this thing completely from the get-go" idea. Somewhat like placing a function's return value in its destination at the call site. – Alaynaalayne

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

Joust

Answer 5

Solution to flattening of nested tuples is quite simple (Compiler Explorer). First, let's make it more general and extend it to all tuple-like types. A simplified concept for tuple-like type (more precise/complex examples can be found elsewhere, but this will suffice):

template<class T>
concept tuple_like = requires {std::get<0>(std::declval<T>()); };

Now we can write a function that creates a flat tuple from arguments, which include other tuple-like types. Starting with a single argument, if the argument is not tuple-like, wrap it in tuple, otherwise unwrap the tuple-like type and create a new tuple of unwrapped types:

    constexpr auto make_flat_tuple(auto&& arg, auto&& ...args)
    {
        if constexpr(sizeof...(args) == 0)
        {   // single argument
            if constexpr(!tuple_like<decltype(arg)>)
                return std::tuple{arg};
            else
                return std::apply([](auto&&...t) 
                   { return std::tuple_cat(make_flat_tuple(t)...); }, arg);
        }
        else
            return std::tuple_cat(make_flat_tuple(arg), make_flat_tuple(args...));
    }

And that's all, the following code is now compiling:

auto nested = std::tuple{'a', std::tuple{'b',  std::tuple{std::array{1,2,3},4}}};
auto flat = make_flat_tuple(nested);
assert((flat == std::tuple{'a','b',1,2,3,4}));

Per