c++ - 对数时间聚合的数量

Question

如何在对数(至少以二为底)编译时间(严格来说，实例化的对数)中定义聚合的元数？

我目前能做的是在线性时间内实现期望:

#include <type_traits>
#include <utility>

struct filler { template< typename type > operator type (); };

template< typename A, typename index_sequence = std::index_sequence<>, typename = void >
struct aggregate_arity
    : index_sequence
{

};

template< typename A, std::size_t ...indices >
struct aggregate_arity< A, std::index_sequence< indices... >, std::__void_t< decltype(A{(indices, std::declval< filler >())..., std::declval< filler >()}) > >
    : aggregate_arity< A, std::index_sequence< indices..., sizeof...(indices) > >
{

};

struct A0 {};
struct A1 { double x; };
struct A2 { int i; char c; }; 
struct C50 { template< typename ...Args, typename = std::enable_if_t< (sizeof...(Args) < 51) > > C50(Args &&...) { ; } };

static_assert(aggregate_arity<  A0 >::size() == 0);
static_assert(aggregate_arity<  A1 >::size() == 1);
static_assert(aggregate_arity<  A2 >::size() == 2);
static_assert(aggregate_arity< C50 >::size() == 50);

Live example .

如果术语“arity”不好，请纠正我。

我认为这在原则上是可能的:首先需要从一个开始进行双重试验，直到 SFINAE 失败(当然，以软方式)，然后使用二分法。

Answer 1

首先是一些术语:我们可以争辩说，您并不是在寻找聚合初始化参数，而是寻找最大 聚合初始化参数。例如。恰本地命名为A2可以从 0、1 和 2 个参数聚合初始化，因此它的最大元数为 2。

让我们把'is aggregate initializable from N arguments'变成一个特征(尽管名字更短):

struct filler { template<typename type> operator type () const; };

template<typename Arg> void accept(Arg);

template<typename Aggr, std::size_t... Indices,
         typename = decltype( accept<Aggr>({ (static_cast<void>(Indices), filler {})... }) )>
void aggregate_arity_test(std::index_sequence<Indices...>);

template<typename Aggr, int N, typename Sfinae = void>
struct has_aggregate_arity: std::false_type {};

template<typename Aggr, int N>
struct has_aggregate_arity<Aggr, N, std::void_t<decltype( aggregate_arity_test<Aggr>(std::make_index_sequence<N>()) )>>
: std::true_type {};

(我们使用 accept<Aggr>({ args... }) 因为这与检查 Aggr aggr = { args... }; 相同，即复制列表初始化以及人们在谈论聚合初始化时的想法。Aggr aggr { args.. }; 是直接列表初始化，但是如果那是你关心的，你仍然可以检查它。)

现在我们可以通过迭代加倍找到一个初始化失败的元数(即我们将检查元数 0，然后是元数 1、元数 2、元数 4、元数 8、...、元数 2<支持>我):

template<typename Aggr, int Acc = 0>
struct find_failing_init_fast: std::conditional_t<
    has_aggregate_arity<Aggr, Acc>::value,
    find_failing_init_fast<Aggr, Acc == 0 ? 1 : Acc * 2>,
    std::integral_constant<int, Acc>
> {};

现在就是在[0, N)里面进行二分查找的问题了其中 N是初始化失败的元数:

// binary search invariant:
//   has_aggregate_arity<Aggr, Low> && !has_aggregate_arity<Aggr, High>
template<typename Aggr, int Low, int High>
struct max_aggregate_arity_impl
: std::conditional_t<
    has_aggregate_arity<Aggr, midpoint(Low, High)>::value
      && !has_aggregate_arity<Aggr, midpoint(Low, High) + 1>::value,
    std::integral_constant<int, midpoint(Low, High)>,
    std::conditional<
        has_aggregate_arity<Aggr, midpoint(Low, High)>::value,
        max_aggregate_arity_impl<Aggr, midpoint(Low, High), High>,
        max_aggregate_arity_impl<Aggr, Low, midpoint(Low, High)>
    >
>::type {};

// special case that 'errors' out (important for SFINAE purposes)
// as the invariant obviously cannot be maintained
template<typename Aggr>
struct max_aggregate_arity_impl<Aggr, 0, 0> {};

template<typename Aggr>
struct max_aggregate_arity
: max_aggregate_arity_impl<Aggr, 0, find_failing_init_fast<Aggr>::value> {};

Live On Coliru