对数时间的集合数 [英] Arity of aggregate in logarithmic time
问题描述
如何在对数（至少以二为底）的编译时间（严格来说，以对数的实例化数量）中定义集合的arity？
How to define arity of an aggregate in logarithmic (at least base two) compilation time (strictly speaking, in logarithmic number of instantiations)?
我能做什么当前要在线性时间内达到期望的值：
What I can do currently is to achieve desired in a linear time:
#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一词不佳，请纠正我。
Please correct me if term "arity" is poor.
我认为原则上是有可能的：首先，需要从一次开始直到SFINAE失败（肯定以柔和的方式）加倍进行Arity审判，然后使用二等分法。
I think it is possible in principle: firstly one need to double arity trials starting from one until SFINAE failed (surely, in soft manner), then use bisection.
推荐答案
讨论
（该讨论基于我的另一个答案，我现在将其删除。）
Discussion
(The discussion is based on another answer of mine which I will delete now.)
与原始问题一样，以下答案检查是否可以在给定数量的参数的情况下调用聚合的构造函数。对于聚合，可以通过使用标准中的以下属性在此模式下进行二进制搜索：
As in the original question, the following answer checks whether the invocation of the constructor of the aggregate is possible with a given number of arguments. For aggregates, one can base a binary search on this pattern by using the following properties from the standard:
8.5.1（6）：
8.5.1 (6):
如果初始化子句
的数量超过要初始化的成员或元素的数量，则初始化列表格式错误 。 [示例：
char cv [4] = {‘a’，’s，’d’，‘f’，0}； //错误格式错误。 — end
示例]
An initializer-list is ill-formed if the number of initializer-clauses exceeds the number of members or elements to initialize. [ Example: char cv[4] = { ’a’, ’s’, ’d’, ’f’, 0 }; // error is ill-formed. — end example ]
和
8.5.1（7）：
8.5.1 (7):
如果列表中的初始化器子句少于总计的
成员， ，则每个未显式初始化的
成员都应从其默认成员初始值设定项（9.2）进行初始化，或者，如果
没有默认成员初始值设定项，则应从一个空的初始值设定项列表
（ 8.5.4）。 [示例：struct S {int a; const char * b; int c; int d =
b [a]; }; S ss = {1， asdf};用1初始化ss.a，用
asdf初始化ss.b，用int {}形式的表达式的值（即
为0）初始化ss.c，用ss.d初始化ss.b [ss.a]的值（即's'），在
中，结构X {int i，j，k = 42; }; X a [] = {1，2，3，4，5，6}; X b [2] =
{{1，2，3}，{4，5，6}}; a和b具有相同的值— end
示例]
If there are fewer initializer-clauses in the list than there are members in the aggregate, then each member not explicitly initialized shall be initialized from its default member initializer (9.2) or, if there is no default member initializer, from an empty initializer list (8.5.4). [ Example: struct S { int a; const char* b; int c; int d = b[a]; }; S ss = { 1, "asdf" }; initializes ss.a with 1, ss.b with "asdf", ss.c with the value of an expression of the form int{} (that is, 0), and ss.d with the value of ss.b[ss.a] (that is, ’s’), and in struct X { int i, j, k = 42; }; X a[] = { 1, 2, 3, 4, 5, 6 }; X b[2] = { { 1, 2, 3 }, { 4, 5, 6 } }; a and b have the same value — end example ]
但是，正如问题标题所暗示的那样，a二进制搜索通常不适用于非聚合，首先是由于通常无法使用比必要数量少的参数来调用非聚合，其次是由于非聚合可以具有 explicit 构造函数，这样通过结构 filler 进行转换为任何东西的技巧将不起作用。
However, as you already implied by the question title, a binary search will in general not work with non-aggregates, first due to the fact that those are usually not callable with less parameters than necessary, and next due to the fact that non-aggregates can have explicit constructors so that the "conversion-to-anything" trick via the struct filler won't work.
第一个成分是来自
First ingredient is an is_callable check from here:
template<typename V, typename ... Args>
struct is_constructible_impl
{
template<typename C> static constexpr auto test(int) -> decltype(C{std::declval<Args>() ...}, bool{}) { return true; }
template<typename> static constexpr auto test(...) { return false; }
static constexpr bool value = test<V>(int{});
using type = std::integral_constant<bool, value>;
};
template<typename ... Args>
using is_constructible = typename is_callable_impl<Args...>::type;
请注意，此参数还可以使用少于必需数量的参数（与您的支票不同）。
Note that this one is usable also with a fewer number of parameters than necessary (unlike your check).
接下来是一个辅助函数，该函数接受一个整数参数并返回是否可以使用相应数量的构造函数参数调用该聚合：
Next a helper function which takes an integer argument and returns whether the aggregate is callable with the corresponding number of constructor arguments:
template<typename A, size_t ... I>
constexpr auto check_impl(std::index_sequence<I ...>)
{
return is_constructible<A, decltype(I, filler{}) ...>::value;
}
template<typename A, size_t N>
constexpr auto check()
{
return check_impl<A>(std::make_index_sequence<N>{});
}
最后是二进制搜索：
template<typename A, size_t Low, size_t Up, size_t i = Low + (Up - Low)/2>
struct binary_search
: public std::conditional_t<check<A, i>() && !check<A,i+1>()
, std::integral_constant<size_t, i>
, std::conditional_t<check<A, i>()
, binary_search<A, i, Up>
, binary_search<A, Low, i> >
>
{};
用作
int main()
{
static_assert(binary_search<A2,0,10>::value==2);
}
这篇关于对数时间的集合数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
