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);
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.
(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):
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 ]
and
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 ]
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>{});
}
And finally the binary search:
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> >
>
{};
Use it as
int main()
{
static_assert(binary_search<A2,0,10>::value==2);
}