C++11: Compile-Time Array with Logarithmic Evaluation Depth

C++11: Compile-time Array with Logarithmic Evaluation Depth

If what you're using in the code is a weird form of the indices trick, here's an implementation that has O(log N) instantiations:

// using aliases for cleaner syntax
template<class T> using Invoke = typename T::type;

template<unsigned...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<unsigned... I1, unsigned... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., (sizeof...(I1)+I2)...>{};

template<class S1, class S2>
using Concat = Invoke<concat<S1, S2>>;

template<unsigned N> struct gen_seq;
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>;

template<unsigned N>
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{};

template<> struct gen_seq<0> : seq<>{};
template<> struct gen_seq<1> : seq<0>{};

// example

template<unsigned... Is>
void f(seq<Is...>);

int main(){
  f(gen_seq<6>());
}

Live example.

C++11: Compile Time Calculation of Array

There is a pure C++11 (no boost, no macros too) solution to this problem. Using the same trick as this answer we can build a sequence of numbers and unpack them to call f to construct a std::array:

#include <array>
#include <algorithm>
#include <iterator>
#include <iostream>

template<int ...>
struct seq { };

template<int N, int ...S>
struct gens : gens<N-1, N-1, S...> { };

template<int ...S>
struct gens<0, S...> {
  typedef seq<S...> type;
};

constexpr int f(int n) {
  return n;
}

template <int N>
class array_thinger {
  typedef typename gens<N>::type list;

  template <int ...S>
  static constexpr std::array<int,N> make_arr(seq<S...>) {
    return std::array<int,N>{{f(S)...}};
  }
public:
  static constexpr std::array<int,N> arr = make_arr(list()); 
};

template <int N>
constexpr std::array<int,N> array_thinger<N>::arr;

int main() {
  std::copy(begin(array_thinger<10>::arr), end(array_thinger<10>::arr), 
            std::ostream_iterator<int>(std::cout, "\n"));
}

(Tested with g++ 4.7)

You could skip std::array entirely with a bit more work, but I think in this instance it's cleaner and simpler to just use std::array.

You can also do this recursively:

#include <array>
#include <functional>
#include <algorithm>
#include <iterator>
#include <iostream>

constexpr int f(int n) {
  return n;
}

template <int N, int ...Vals>
constexpr
typename std::enable_if<N==sizeof...(Vals),std::array<int, N>>::type
make() {
  return std::array<int,N>{{Vals...}};
}

template <int N, int ...Vals>
constexpr
typename std::enable_if<N!=sizeof...(Vals), std::array<int,N>>::type 
make() {
  return make<N, Vals..., f(sizeof...(Vals))>();  
}

int main() {
  const auto arr = make<10>();
  std::copy(begin(arr), end(arr), std::ostream_iterator<int>(std::cout, "\n"));
}

Which is arguably simpler.

Filling an array on compiletime under some predicate

The only solution I could come up with is to use a generator for the sequence which is both

• O(log N)
• Filter while generating the sequence

That said, I started with this O(log N) generator and I changed the predicate from a constexpr function to a more convenient std::integral_constant - I hope that is acceptable to you. The result is this:

#include <utility>
#include <iostream>
#include <type_traits>

template<std::size_t...> struct seq{ using type = seq; };

template<class S1, class S2> struct concat;

template<std::size_t... I1, std::size_t... I2>
struct concat<seq<I1...>, seq<I2...>>
  : seq<I1..., I2...>{};

template<template<std::size_t> class pred, std::size_t B, std::size_t N>
struct gen_seq : concat<typename gen_seq<pred, B, N/2>::type, typename gen_seq<pred, B + N/2, N - N/2>::type>::type {};

template<template<std::size_t> class pred, std::size_t B> struct gen_seq<pred, B, 0> : seq<> {};
template<template<std::size_t> class pred, std::size_t B> struct gen_seq<pred, B, 1> : std::conditional<pred<B>::value,seq<B>,seq<>>::type {};

template<std::size_t N>
struct MyData
{
    std::size_t values[N];

    static constexpr std::size_t size()
    { return N; }
};

template<std::size_t... Is>
constexpr MyData<sizeof...(Is)> MyGen(seq<Is...>)
{
    return {{ Is... }};
}

template<template<std::size_t> class pred, std::size_t N>
constexpr auto MyGen() -> decltype(MyGen(typename gen_seq<pred,0,N>::type()))
{
    return MyGen(gen_seq<pred,0,N>());
}

template< std::size_t N > struct my_pred : std::integral_constant< bool, N % 3 == 0 > {};

int main()
{
    auto data = MyGen<my_pred, 10>();
    static_assert( data.size() == 4, "Oops" );

    for ( auto i : data.values )
       std::cout << i << std::endl;

    auto data2 = MyGen<my_pred, 10000>();
    static_assert( data2.size() == 3334, "Oops" );
}

Live example

As you can see in the live example, even 10000 works :)

A version using a constexpr bool pred(std::size_t) is not so convenient (you can't just "call" the method, you need to write some more code for each pred), but it was also possible.

Arity of aggregate in logarithmic time

Discussion

(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.

Implementation

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

Live on Coliru

Getting the number of elements in std::array at compile time

array<T>::size() is constexpr, but you can't use it in this way because a1 isn't a constexpr value. Additionally, it can't be constexpr because string isn't a literal type.

However, you can work around this if you want, by deducing the size_t template parameter. Example:

#include <string>
#include <array>
#include <iostream>
using namespace std;

template<typename>
struct array_size;
template<typename T, size_t N>
struct array_size<array<T,N> > {
    static size_t const size = N;
};

array<string, 42> a1;
array<string, array_size<decltype(a1)>::size> a2;

int main() {
    cout << a2.size() << endl;
}

How can I get the depth of a multidimensional std::vector at compile time?

A classic templating problem. Here's a simple solution like how the C++ standard library does. The basic idea is to have a recursive template that will count one by one each dimension, with a base case of 0 for any type that is not a vector.

#include <vector>
#include <type_traits>

template<typename T>
struct dimensions : std::integral_constant<std::size_t, 0> {};

template<typename T>
struct dimensions<std::vector<T>> : std::integral_constant<std::size_t, 1 + dimensions<T>::value> {};

template<typename T>
inline constexpr std::size_t dimensions_v = dimensions<T>::value; // (C++17)

So then you could use it like so:

dimensions<vector<vector<vector<int>>>>::value; // 3
// OR
dimensions_v<vector<vector<vector<int>>>>; // also 3 (C++17)

Edit:

Ok, I've finished the general implementation for any container type. Note that I defined a container type as anything that has a well-formed iterator type as per the expression begin(t) where std::begin is imported for ADL lookup and t is an lvalue of type T.

Here's my code along with comments to explain why stuff works and the test cases I used. Note, this requires C++17 to compile.

#include <iostream>
#include <vector>
#include <array>
#include <type_traits>

using std::begin; // import std::begin for handling C-style array with the same ADL idiom as the other types

// decide whether T is a container type - i define this as anything that has a well formed begin iterator type.
// we return true/false to determing if T is a container type.
// we use the type conversion ability of nullptr to std::nullptr_t or void* (prefers std::nullptr_t overload if it exists).
// use SFINAE to conditionally enable the std::nullptr_t overload.
// these types might not have a default constructor, so return a pointer to it.
// base case returns void* which we decay to void to represent not a container.
template<typename T>
void *_iter_elem(void*) { return nullptr; }
template<typename T>
typename std::iterator_traits<decltype(begin(*(T*)nullptr))>::value_type *_iter_elem(std::nullptr_t) { return nullptr; }

// this is just a convenience wrapper to make the above user friendly
template<typename T>
struct container_stuff
{
    typedef std::remove_pointer_t<decltype(_iter_elem<T>(nullptr))> elem_t;    // the element type if T is a container, otherwise void
    static inline constexpr bool is_container = !std::is_same_v<elem_t, void>; // true iff T is a container
};

// and our old dimension counting logic (now uses std:nullptr_t SFINAE logic)
template<typename T>
constexpr std::size_t _dimensions(void*) { return 0; }

template<typename T, std::enable_if_t<container_stuff<T>::is_container, int> = 0>
constexpr std::size_t _dimensions(std::nullptr_t) { return 1 + _dimensions<typename container_stuff<T>::elem_t>(nullptr); }

// and our nice little alias
template<typename T>
inline constexpr std::size_t dimensions_v = _dimensions<T>(nullptr);

int main()
{
    std::cout << container_stuff<int>::is_container << '\n';                 // false
    std::cout << container_stuff<int[6]>::is_container<< '\n';               // true
    std::cout << container_stuff<std::vector<int>>::is_container << '\n';    // true
    std::cout << container_stuff<std::array<int, 3>>::is_container << '\n';  // true
    std::cout << dimensions_v<std::vector<std::array<std::vector<int>, 2>>>; // 3
}

How do I store the compile-time dynamically allocated memory so that it can be used in run-time?

Create a lambda that makes a vector, and use another lambda to create an array

#include <array>
#include <vector>
#include <algorithm>

constexpr auto primes_num_vector = [] {
  constexpr int N = 1 << 16;
  std::vector<int> ret;
  bool not_prime[N] = {};
  for (int i = 2; i < N; i++) {
    if (!not_prime[i]) {
      ret.push_back(i);
      for (int j = 2 * i; j < N; j += i) not_prime[j] = true;
    }
  }
  return ret;
};

constexpr auto primes = [] {
  std::array<int, primes_num_vector().size()> ret;
  std::ranges::copy(primes_num_vector(), ret.begin());
  return ret;
}();

What types of expressions are evaluated at compile time?

It's not trivial to write a complete and correct answer the question, since a lot of things are computed at compile-time in C. To answer, one would need to go rather deep into the C standard with lots of "language lawyer" terms used internally by it.

---

First there is the whole pre-processing part as described in translation phases (C17 5.1.1.2). Included in those pre-processing translation phases is for example the #if directive, which has the formal syntax like:

# if constant-expression new-line

Where constant expression is another term for expressions that are always evaluated at compile-time. C defines such expressions in C17 6.6:

A constant expression can be evaluated during translation rather than runtime, and
accordingly may be used in any place that a constant may be.

Constraints

Constant expressions shall not contain assignment, increment, decrement, function-call, or comma operators, except when they are contained within a subexpression that is not evaluated.

Each constant expression shall evaluate to a constant that is in the range of representable
values for its type.

It then categorizes constant expressions into the following types:

• Integer constant expressions

  An integer constant expression shall have integer type and shall only have operands
  that are integer constants, enumeration constants, character constants, sizeof
  expressions whose results are integer constants, _Alignof expressions, and floating
  constants that are the immediate operands of casts. Cast operators in an integer constant expression shall only convert arithmetic types to integer types, except as part of an operand to the sizeof or _Alignof operator.

• Arithmetic constant expressions

  Nearly identical definition as per above except it also allows floating point types. So an integer constant expression is also an arithmetic constant expression. (The arithmetic types in C are all integer and all floating point types.)

• Address constants

  An address constant is a null pointer, a pointer to an lvalue designating an object of static storage duration, or a pointer to a function designator; it shall be created explicitly using the unary & operator or an integer constant cast to pointer type, or implicitly by the use of an expression of array or function type. The array-subscript [] and member-access . and -> operators, the address & and indirection * unary operators, and pointer casts may be used in the creation of an address constant, but the value of an object shall not be
  accessed by use of these operators.

• Implementation-defined forms (compiler-specific language extensions).

---

Related Topics