Calculate limit of a range at compile time

Question

Given you ONLY have as a tool a SFINAE class, that accepts an index and yields std::true_type if it is in range, how could one find the limit? This are the exact requiremants, NOTHING else can be used.

This is an example signature for a struct. L here is for testing. In the real struct there will be typename T as a second parameter, but it is irrelevant to the problem.

template <size_t I, size_t L = 6000>
struct is_in_range : std::integral_constant<bool, (I < L)> {};

For example: you have a range of 6000 elements. is_in_range<2>() will be true, is_in_range<6001>() will be false. I need to find the limit, which is in this case 6000.

I know that you could basically refer to the binary search, but the thing is, it has to be as optimal as possible and generate as little instantiations as possible.

For the template part I see 2 ways:

• template constexpr recursive function (a bad one, bloated code, but I can do that)
• SFINAE (too complex for me)

---

I did not want to overcomplicate the question and constrained it only to the scope of the actual problem (sub-problem). The following is not the part of the question, but rather an insight for the reasons of limitations.

This is not a part of the question and is not subjected for discussion since the problem of reflection in C++ is too complex.

In order to deduce at compile time a member of a structure I use aggregate initialization.

template <typename Allowed>
struct explicitly_convertible
{
   operator Allowed();
}

struct pod
{
   int a;
   int arr[46];
   char c;
   float arr2[38];
};

Implementation does the following:

// checks if this is well-formed to deduce the type of an element
   decltype(pod{{explicitly_convertible<int>()}});

So, as you see, the only way to deduce an array size, is to probe the initialization of T with N elements while aggregate initializating.

In C++ a function or a method can't return an array, so this is not acceptable:

template <typename T, size_t N>
struct non_acceptable
{
   operator T[N]();
}

Answer 1

Returning to this problem, I decided to implement a naive solution. The algorithm "probes" the size for 2 (left and right) boundaries (pseudo):

bound<left, right, delta>:

if right.valid() 
    return bound<right, right + delta * 2, delta * 2>;

if right - left == 1
    return left;

return bound<right - delta, right - delta / 2, delta / 2>;

The actual soultion using recursive specialization: https://godbolt.org/z/9djsdjKE4

#include <cstddef>
#include <type_traits>

template <template <size_t> class OnFound,
    template <size_t> class UnaryPred,
    typename Left, 
    typename Right, 
    size_t Delta = 1>
struct _find_array_size;

template <size_t Index, template <size_t> class UnaryPred, bool = UnaryPred<Index>::value>
struct _probe_size;

template <template <size_t> class OnFound, 
        template <size_t> class UnaryPred,
        size_t Left>
struct _find_array_size<OnFound, UnaryPred, 
                    _probe_size<Left, UnaryPred, true>, 
                    _probe_size<Left + 1, UnaryPred, false>> 
{
    using type = OnFound<Left>;
    constexpr static size_t value = Left;
};

template <template <size_t> class OnFound, 
        template <size_t> class UnaryPred,
        size_t Left,
        size_t Right,
        bool BoolRight,
        size_t Delta>
struct _find_array_size<OnFound, UnaryPred, 
                    _probe_size<Left, UnaryPred, true>, 
                    _probe_size<Right, UnaryPred, BoolRight>,
                    Delta> : std::conditional_t<BoolRight,
                                _find_array_size<OnFound, UnaryPred, _probe_size<Right, UnaryPred>, _probe_size<Right + Delta * 2, UnaryPred>, Delta * 2>,
                                _find_array_size<OnFound, UnaryPred, _probe_size<Right - Delta, UnaryPred>, _probe_size<Right - Delta / 2, UnaryPred>, Delta / 2>>
{
};

template <template <size_t> class OnFound,
        template <size_t> class UnaryPred>
struct find_array_size
{
    constexpr static size_t value = _find_array_size<OnFound, UnaryPred, _probe_size<1, UnaryPred>, _probe_size<2, UnaryPred>>::value;
};

// Testing
template <size_t ArraySize>
struct in_bounds
{
    template <size_t Size>
    using predicate = std::integral_constant<bool, (Size <= ArraySize)>;
};

#include <iostream>

template <size_t> 
struct t_noop;

int main(){

    std::cout << std::boolalpha;
    std::cout << in_bounds<46>::template predicate<45>{} << '\n';
    std::cout << in_bounds<46>::template predicate<46>{} << '\n';
    std::cout << find_array_size<t_noop, in_bounds<1>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<2>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<3>::predicate>::value << '\n';
    
    std::cout << find_array_size<t_noop, in_bounds<4>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<8>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<15>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<16>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<23>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<42>::predicate>::value << '\n';
    std::cout << find_array_size<t_noop, in_bounds<108>::predicate>::value << '\n';

    return 0;
}

Output:

true
true
1
2
3
4
8
15
16
23
42
108

It works though I am not sure if it could be made more optimal from both algorithmic and compilation perspective.