c++ - Arity of aggregate in logarithmic time

Question

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

Live example.

Please correct me if term "arity" is poor.

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.

Answer 1

A bit of terminology first: we can argue that you are not so much looking for the aggregate initialization arity but the maximum aggregate initialization arity. E.g. the aptly named A2 can be aggregate initialized from 0, 1, and 2 arguments so its maximum arity is 2.

Let’s turn 'is aggregate initializable from N arguments' into a trait (although with a shorter name):

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 {};

(We use accept<Aggr>({ args... }) because that’s the same as checking for Aggr aggr = { args... };, i.e. copy-list-initialization and what people have in mind when they talk about aggregate initialization. Aggr aggr { args.. }; is direct-list-initialization, but you can still check against that if that’s what you care about.)

Now we can find an arity for which initialization fails in not too many instantiations with iterated doubling (i.e. we will check at arity 0, then arity 1, arity 2, arity 4, arity 8, ..., arity 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>
> {};

Now it’s a matter of a binary search inside [0, N) where N is an arity for which initialization fails:

// 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