logo标签列表

对数时间内聚合的元数

c++c++11aggregatec++14type-traits
5
如何在对数时间（至少为2的底数）内定义聚合的元数（严格来说，在实例化的对数数量中）？
目前我能做到的是在线性时间内达到所需：
#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”不恰当，请纠正我。

我认为原则上是可能的：首先需要从一开始加倍元数试验，直到SFINAE失败（当然，以柔和的方式），然后使用二分法。

另一个问题是：C50::C50(...)中的类型是什么？ operator type 模板参数没有默认值。 - Tomilov Anatoliy
1
你可以通过在函数体中添加类似于 struct {} dummy = some_type_list<Args...> {}; 的代码来明确地触发错误（希望编译器能够提供足够好的诊断信息），以此来验证 filler 是否正常工作。 - Luc Danton
@LucDanton 真的吗，谢谢。 - Tomilov Anatoliy
2个回答
5
首先需要解释一些术语：我们可以认为您所寻找的不是聚合初始化性质，而是最大聚合初始化性质。例如，名为A2的适当命名的对象可以从0、1和2个参数进行聚合初始化，因此其最大性质为2。
现在让我们将“可从N个参数进行聚合初始化”转换为特征（尽管名称较短）：
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、...、2i处进行检查）：

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

加倍比我回答中的固定范围更好，+1。 - davidhigh
1
@davidhigh，我真的很欣赏你在回答中提供的invariant(N) &&!invariant(N+1)测试快捷方式，这摆脱了需要处理最终情况的两个max_aggregate_arity_impl<Aggr，N，N>和max_aggregate_arity_impl<Aggr，N，N + 1>部分特化的需要。特别是后者是不允许的，所以我不得不采取例如max_aggregate_arity_impl<Aggr，int_pair<N，N + 1>>来规避非类型模板参数的限制。 - Luc Danton
你认为在当今这些日子里使用C++17或20能有什么可以改进的吗？我真的很喜欢你的回答 :) - hellow
2

讨论

正如原问题所述，以下答案检查是否可以使用给定数量的参数调用聚合体的构造函数。对于聚合体，可以使用标准中的以下属性来基于此模式进行二进制搜索：

8.5.1（6）：

如果初始化程序列表中的初始化器数目超过要初始化的成员或元素数，则初始化程序列表是不良形式的。[例子：char cv [4] = {'a'，'s'，'d'，'f'，0}; //错误是不良形式。—结束例子]

和

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"};将ss.a初始化为1，ss.b初始化为"asdf"，ss.c初始化为int{}（即0）的表达式值，ss.d初始化为ss.b [ss.a]的值（即's'），并且在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和b具有相同的值-结束示例]

然而，正如您已经通过问题标题暗示的那样，二进制搜索通常无法处理非聚合体，首先是因为这些通常不能使用少于必要参数的调用方式，其次是因为非聚合体可以具有explicit构造函数，因此通过结构filler进行“转换为任何内容”的技巧将无法奏效。

实现

第一个要素是来自这里的is_callable检查：

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;

请注意，与您的检查不同，此函数可以使用少于必要数量的参数。
下面是一个辅助函数，它接受一个整数参数并返回聚合体是否可以使用相应数量的构造函数参数进行调用：
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);
}

Live on Coliru

@Orient：你说得对，我想把它重命名为is_constructible...然后我想到最好使用std::is_constructible... - davidhigh
1
is_braces_constructible或is_embraceable（http://stackoverflow.com/questions/20885541/is-braces-constructible-type-trait），但我认为自定义的`is_constructible`在这里也足够好。 - Tomilov Anatoliy
好的，我的std::is_constructible尝试没有成功，可能是由于这个问题。 - davidhigh
1
这段代码没有处理各种边角情况（如不可移动类型、无默认构造函数的类型、引用），并且在大括号省略方面处理不一致（对于数组省略，对于其他子聚合体不省略）。此外，你肯定是想说 Low + (Up - Low)/2 吧？ - T.C.
@T.C.：当然是 Low + (Up - Low)/2 了。至于其他方面，你有改进建议吗？无论如何，感谢纠正。 - davidhigh
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接