如何在 C++ 中查找可变类型列表的所有组合

Question

我想编写一个 C++ 元函数，给定一个类型列表，没有重复的元素，生成所有可能的子列表，大小为 sizeof...(list) - 1。

更新：我正在寻找元函数 find_all 的通用实现，定义如下。我现在的实现只是专门（硬编码）了最多 5 个元素的列表的结果，这显然根本不是通用的。

下面是一些简单的定义和示例：

给定一个存储类型列表的容器：

template<typename... Ts>
struct type_list{};

其中 "instance" 个：

struct A{};
struct B{};
struct C{};

using ABC = type_list<A, B, C>::type;

并使用元函数，称为 find_all:

using found_result = find_all<ABC>;

结果应该是：

using expected_result = type_list<
  type_list<A, B>,
  type_list<A, C>,
  type_list<B, C>
>;

static_assert(
  std::is_same<
    expected_result,
    found_result
  >::value, "");

如果结果子列表中的元素或子列表本身的顺序不同，则可以接受，前提是顺序是确定的。所以下面的结果也是有效的，例如：

using another_possible_expected_result = type_list<
  type_list<B, A>,
  type_list<B, C>
  type_list<C, A>,
>;

我正在使用 C++11（clang 6.0，Linux x86_64），但使用 C++14 就可以了。

如果有帮助，我也在使用 brigand 元编程库，它具有用于 list/set 处理的有用功能，但我也接受使用其他库的答案。

Answer 1

我对 Brigand 不熟悉，所以我用 Kvasir::mpl 代替。无论如何，该算法应该可以转移到任何 TMP 库：

给定类型列表 [a0, a1, ..., aN]，生成列表：

[a1, a2, a3, ..., aN]
[a0, a2, a3, ..., aN]
[a0, a1, a3, ..., aN]
...
[a0, a1, a2, ..., aN-1]

换句话说，结果列表的第 I 个元素是删除第 I 个元素的原始列表。

在代码中 Kvasir::mpl:

namespace mpl = kvasir::mpl;

// Produce a list of indices into the original list
template <typename C = mpl::listify>
using indices = mpl::size<mpl::make_int_sequence<C>>;

// Given a list, produce a list of functions which, when evaluated on the original list,
// would erase the corresponding element.
template <typename C = mpl::listify>
using erase_each_index = indices< // given the indices,
    mpl::transform<               // transform each index by
        mpl::cfe<mpl::erase>,     // producing mpl::erase<Index>
        C
    >
>;

template <typename C = mpl::identity>
using listify = mpl::cfe<mpl::list, C>;

template <typename Fn, typename Args>
using eager_call = mpl::call<
    mpl::unpack<Fn>,
    Args
>;

template <typename C = mpl::listify>
using penultimate_sized_sublists =  mpl::fork< // each path takes the original list
    // 1. produce a list of functions which erase their index
    erase_each_index<>,
    // 2. produce the original list, wrapped in an extra list
    listify<listify<>>,
    // Both 1 and 2 are passed here. We perform a cartesian product (that's why
    // we wrapped 2 in an extra list) to put the arguments together with the functions
    mpl::product<
        // Evaluate each function against the entire list
        mpl::cfe<eager_call>
    >
>;

Demo on Godbolt:

static_assert(
    std::is_same<
        mpl::call<
            mpl::unpack<penultimate_sized_sublists<>>,
            mpl::list<A, B, C>
        >,
        mpl::list<
            mpl::list<B, C>,
            mpl::list<A, C>,
            mpl::list<A, B>
        >
    >::value,
    ""
);

Answer 2

如果你愿意使用C++14和Boost，我另一个答案中的算法可以很容易地用Boost Hana实现：

#include <utility>
#include <boost/hana.hpp>

namespace hana = boost::hana;

template <typename Tup>
constexpr auto penultimate_sized_sublists(Tup types)
{
    constexpr auto size = hana::size(types);
    // hana::range is unusable with hana::transform,
    // hence the conversion to a hana::tuple
    constexpr auto indices = hana::to_tuple(hana::make_range(hana::size_c<0>, size));

    return hana::transform(indices, [&](auto index) {
        return hana::remove_at(types, index);
    });
}

Demo on Godbolt

如何在 C++ 中查找可变类型列表的所有组合

How to find all combinations of variadic typelist in C++

c++

metaprogramming

variadic-templates

c++11

c++14