对数时间内聚合的数量

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

活生生的例子。

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

我认为原则上是可能的：首先需要从 1 开始进行双倍试验，直到 SFINAE 失败（当然，以软方式），然后使用二分法。

Answer 1

首先介绍一些术语：我们可以说，您并不是在寻找聚合初始化数量，而是在寻找最大聚合初始化数量。例如，适当命名的A2可以从 0、1 和 2 个参数进行聚合初始化，因此其最大数量为 2。

\n\n

让\xe2\x80\x99s 将“可从 N 个参数进行聚合初始化”转换为特征（尽管名称较短）：

\n\n

struct filler { template<typename type> operator type () const; };\n\ntemplate<typename Arg> void accept(Arg);\n\ntemplate<typename Aggr, std::size_t... Indices,\n         typename = decltype( accept<Aggr>({ (static_cast<void>(Indices), filler {})... }) )>\nvoid aggregate_arity_test(std::index_sequence<Indices...>);\n\ntemplate<typename Aggr, int N, typename Sfinae = void>\nstruct has_aggregate_arity: std::false_type {};\n\ntemplate<typename Aggr, int N>\nstruct has_aggregate_arity<Aggr, N, std::void_t<decltype( aggregate_arity_test<Aggr>(std::make_index_sequence<N>()) )>>\n: std::true_type {};\n

\n\n

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

\n\n

现在我们可以找到一个在迭代加倍的实例化中初始化失败的数量（即我们将检查 arity 0，然后检查 arity 1，arity 2，arity 4，arity 8，...，arity 2 i ^）：

\n\n

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

\n\n

现在，\xe2\x80\x99 是一个二分搜索的问题，其中[0, N)是N初始化失败的 arity：

\n\n

// binary search invariant:\n//   has_aggregate_arity<Aggr, Low> && !has_aggregate_arity<Aggr, High>\ntemplate<typename Aggr, int Low, int High>\nstruct max_aggregate_arity_impl\n: std::conditional_t<\n    has_aggregate_arity<Aggr, midpoint(Low, High)>::value\n      && !has_aggregate_arity<Aggr, midpoint(Low, High) + 1>::value,\n    std::integral_constant<int, midpoint(Low, High)>,\n    std::conditional<\n        has_aggregate_arity<Aggr, midpoint(Low, High)>::value,\n        max_aggregate_arity_impl<Aggr, midpoint(Low, High), High>,\n        max_aggregate_arity_impl<Aggr, Low, midpoint(Low, High)>\n    >\n>::type {};\n\n// special case that \'errors\' out (important for SFINAE purposes)\n// as the invariant obviously cannot be maintained\ntemplate<typename Aggr>\nstruct max_aggregate_arity_impl<Aggr, 0, 0> {};\n\ntemplate<typename Aggr>\nstruct max_aggregate_arity\n: max_aggregate_arity_impl<Aggr, 0, find_failing_init_fast<Aggr>::value> {};\n

\n\n

Live On Coliru

\n

Answer 2

讨论

\n\n

（该讨论基于我的另一个答案，我现在将删除它。）

\n\n

与原始问题一样，以下答案检查是否可以使用给定数量的参数调用聚合的构造函数。对于聚合，可以通过使用标准中的以下属性来基于此模式进行二分搜索：

\n\n

\n

8.5.1（6）：

\n\n

如果初始值设定项子句的数量超过要初始化的成员或元素的数量，则初始值设定项列表的格式不正确。[ 示例:\n char cv[4] = { \xe2\x80\x99a\xe2\x80\x99, \xe2\x80\x99s\xe2\x80\x99, \xe2\x80\x99d\xe2\x80\x99 , \xe2\x80\x99f\xe2\x80\x99, 0 }; // 错误格式不正确。\xe2\x80\x94 结束\n 示例]

\n

\n\n

和

\n\n

\n

8.5.1（7）：

\n\n

如果列表中的初始化子句少于聚合中的成员，则每个未显式初始化的成员应从其默认成员初始值设定项(9.2) 进行初始化，或者，如果\n 没有默认成员初始值设定项，来自空的初始值设定项列表\n (8.5.4)。[ 示例：struct S { int a; 常量字符* b；整数c; int d =\nb[a]; }; S ss = { 1, "asdf" }; 用 1 初始化 ss.a，用“asdf”初始化 ss.b，用 int{} 形式的表达式的值初始化 ss.c（即 0），用 ss 的值初始化 ss.d .b[ss.a]（即\xe2\x80\x99s\xe2\x80\x99），并且在\n struct X { int i, j, k = 42; }; X a[] = { 1, 2, 3, 4, 5, 6 }; X b[2] =\n { { 1, 2, 3 }, { 4, 5, 6 } }; a 和 b 具有相同的值 \xe2\x80\x94 end\n 示例 ]

\n

\n\n

但是，正如问题标题所暗示的那样，二分搜索通常不适用于非聚合，首先是因为这些聚合通常无法使用少于必要的参数来调用，其次是因为非聚合聚合可以具有explicit构造函数，因此通过结构的“转换为任何内容”技巧filler将不起作用。

\n\n

执行

\n\n

第一个成分是is_callable来自这里的检查：

\n\n

template<typename V, typename ... Args>\nstruct is_constructible_impl\n{\n    template<typename C> static constexpr auto test(int) -> decltype(C{std::declval<Args>() ...}, bool{}) { return true; }\n    template<typename> static constexpr auto test(...) { return false; }\n    static constexpr bool value = test<V>(int{});\n    using type = std::integral_constant<bool, value>;\n};\n\ntemplate<typename ... Args>\nusing is_constructible = typename is_callable_impl<Args...>::type;\n

\n\n

请注意，此参数也可以使用比所需数量更少的参数（与您的检查不同）。

\n\n

接下来是一个辅助函数，它接受一个整数参数并返回是否可以使用相应数量的构造函数参数来调用聚合：

\n\n

template<typename A, size_t ... I>\nconstexpr auto check_impl(std::index_sequence<I ...>)\n{\n    return is_constructible<A, decltype(I, filler{}) ...>::value;\n}\n\ntemplate<typename A, size_t N>\nconstexpr auto check()\n{\n    return check_impl<A>(std::make_index_sequence<N>{});\n}\n

\n\n

最后是二分查找：

\n\n

template<typename A, size_t Low, size_t Up, size_t i = Low + (Up - Low)/2>\nstruct binary_search\n   : public std::conditional_t<check<A, i>() && !check<A,i+1>()\n                           , std::integral_constant<size_t, i>\n                           , std::conditional_t<check<A, i>()\n                                              , binary_search<A, i, Up>\n                                              , binary_search<A, Low, i> >\n                              >\n{};\n

\n\n

使用它作为

\n\n

int main()\n{\n    static_assert(binary_search<A2,0,10>::value==2);\n}\n

\n\n

Live on Coliru

\n