如何展平异构列表（又名......元组的元组）

Question

我正在尝试使用 C++17 折叠表达式和 C++14 索引技巧来展平由元组和非元组组成的任意输入。

预期结果至少应符合这些要求：

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

我有相对简单的代码来处理除最后一种情况之外的所有情况：

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。显然，它不能很好地处理多重嵌套项。

我还没有找到处理 multiply_nested 案例的更高级形式。我尝试应用 operator>> 以能够使用折叠表达式，但无法获得任何可编译的内容。我最后的尝试可以找到here。核心思想是在折叠表达式中使用 operator>> 将元素 2 乘 2 组合，每次展开之前的结果。

在我看来，我应该可以使用 std::tuple_cat 之类的东西，但由于我无法完全理解的原因，它对我大喊大叫。

所以我的问题是：我错过了什么？如何打开任意深度任意嵌套的类似元组的输入？

Answer 1

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

如上所述，flatten( std::tuple<int>(7) ) 应该不是 7。那是精神错乱。

但如您所愿，我将其添加为 post 处理步骤。

你的操作还是比较理智的。您递归地将 [[x],[y]] 应用于 [x,y]。最后的拆箱是不理智的。通过拆分，代码变得简单，这也是它疯狂的证据。

Live example.

如果您想知道，flat_t 标签类型的存在是为了 (a) 将索引序列与可能的参数分开（这可以通过使用不同的函数名称来完成）和 (b)启用 ADL 查找，这样每个 flatten 的实现都可以看到所有其他的。

Answer 2

我向 SFINAE 求婚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 3

虽然更冗长，但可能更直接一些：部分 class 模板专业化 + if constexpr:

基本方法是特化以下基class:

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

考虑到我们的三个案例：

裸值
一件事tuple
不止一件事tuple

案例 #1，基本案例，相当简单，只是 return 我们得到的：

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

案例 #2 也非常简单，只需递归自身直到我们到达案例 #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));
    }
};

案例 #3 很长，因为可能有子案例，但每个块都非常可读。我们

展平第一个元素（可能递归）
展平其余元素（可能递归）

然后我们有四种情况要考虑：

我们有两个元组（例如，tuple<int, int>, tuple<int, int>）
我们有一个元组和一个值（例如，tuple<int, int>, int）
我们有一个值和一个元组（例如，int, tuple<int, int>）
我们有两个值（例如，int, int）

我们只需要一个辅助函数，它允许我们从元组中剥离元组的头部，return 剩下的部分。

// 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)...);
}

和一些辅助特征：

// 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;

终于实现了：

// 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

最后，我们使用蹦床对最终用户隐藏所有这些细节，方法是将它们推入 details 命名空间并公开以下函数来调用它们：

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

Demo

（包括一些额外的正确性测试）

虽然上面案例 #3 的实现非常简单，但它既冗长又有点低效（编译器评估每个 if constexpr 语句，而它应该只评估一个，但我不想由于嵌套，沿着 else 个分支串起来。

我们可以通过转向两个辅助函数来极大地简化案例 #3，这两个辅助函数检测参数是否为非元组和 return 正确的东西：

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

Answer 4

这是另一个具有两个设计目标的版本：

避免构造临时元组并避免std::tuple_cat
明确确定最终元组中的类型

为了避免临时元组和std::tuple_cat，预测输出元组的最终大小很有用。让我们定义一个名为 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>{}));
}

flatten 函数可以利用 get_rank 为输出元组的元素创建索引序列。此序列与转发的输入元组和类型标记一起传递给 flatten_impl。让我们为接口函数显式提供左值和右值重载，但在内部使用完美转发：

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

此时，我们还需要两个积木：

tuple_element_at_rankpos_t（类似于 std::tuple_element_t，但用于嵌套元组）和
get_at_rankpos（类似于 std::get，但用于嵌套元组）。

每个构建块都应根据元素在展平输出元组中的位置找到嵌套输入元组中元素的 type/value。在每个嵌套级别，这些构建块需要从 rankpos 中提取当前嵌套深度的索引。可以将此通用索引计算移至 extract_index 助手。第一个构建块可能如下所示：

#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;

第二个构建块是与上面相同的胶水代码的重复。除了类型之外，我们还需要处理值（左值、常量左值、右值）。使用完美转发我们可以写：

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

如何展平异构列表（又名......元组的元组）

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

c++

tuples

c++17

flatten

perfect-forwarding

Demo

Demo 2