对数时间聚合的数量

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

讨论

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

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

8.5.1 (6):

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

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 ]

但是，正如您已经在问题标题中暗示的那样，二分搜索通常不适用于 non-aggregates，首先是因为这些参数通常无法使用少于必要的参数调用，其次由于 non-aggregates 可以有 explicit 构造函数，因此通过结构 filler 的 "conversion-to-anything" 技巧将不起作用。

实施

第一个成分是来自 here 的 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;

请注意，这个参数也可以使用少于必要数量的参数（与您的检查不同）。

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

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

Answer 2

首先是一些术语：我们可以争辩说，您并不是在寻找聚合初始化数量，而是在寻找 maximum 聚合初始化数量。例如。恰当命名的 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

对数时间聚合的数量

Arity of aggregate in logarithmic time

c++

c++11

aggregate

c++14

typetraits

讨论

实施