Как найти все комбинации variadic typelist в C ++ - PullRequest
Новая
       49

Как найти все комбинации variadic typelist в C ++

0 голосов
/ 05 июля 2018

Я хотел бы написать метафункцию C ++, которая, учитывая список типов без дублированных элементов, генерирует все возможные подсписки размером sizeof...(list) - 1.

Обновление : я ищу общую реализацию метафункции find_all, как определено ниже. Реализация, которую я сейчас имею, просто специализирует (жестко запрограммированный) результат для списков до 5 элементов, что, очевидно, не является универсальным.

Ниже приведены несколько простых определений и пример:

Имеется контейнер, в котором хранится список типов: 

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

И «экземпляр» этого: 

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, которая имеет полезные функции для обработки списков / множеств, но я принимаю ответы, которые также используют другие библиотеки.

Ответы [ 2 ]

0 голосов
/ 06 июля 2018

Если вы хотите использовать 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);
    });
}

Демонстрация по Godbolt

0 голосов
/ 06 июля 2018

Я не знаком с 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>
    >
>;

Демонстрация по 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,
    ""
);
...