Programmatically create static arrays at compile time in C++

Question

One can define a static array at compile time as follows:

const std::size_t size = 5;    
unsigned int list[size] = { 1, 2, 3, 4, 5 };

Question 1 - Is it possible by using various kinds of metaprogramming techniques to assign these values "programmatically" at compile time?

Question 2 - Assuming all the values in the array are to be the same barr a few, is it possible to selectively assign values at compile time in a programmatic manner?

eg:

const std::size_t size = 7;        
unsigned int list[size] = { 0, 0, 2, 3, 0, 0, 0 };

1. Solutions using C++0x are welcome
2. The array may be quite large, few hundred elements long
3. The array for now will only consist of POD types
4. It can also be assumed the size of the array will be known beforehand, in a static compile-time compliant manner.
5. Solutions must be in C++ (no script, no macros, no pp or code generator based solutions pls)

UPDATE: Georg Fritzsche's solution is amazing, needs a little work to get it compiling on msvc and intel compilers, but nonetheless a very interesting approach to the problem.

Answer 1

The closest you can get is using C++0x features to initialize local or member arrays of templates from a variadic template argument list.
This is of course limited by the maximum template instantiation depth and wether that actually makes a notable difference in your case would have to be measured.

Example:

template<unsigned... args> struct ArrayHolder {
    static const unsigned data[sizeof...(args)];
};

template<unsigned... args> 
const unsigned ArrayHolder<args...>::data[sizeof...(args)] = { args... };

template<size_t N, template<size_t> class F, unsigned... args> 
struct generate_array_impl {
    typedef typename generate_array_impl<N-1, F, F<N>::value, args...>::result result;
};

template<template<size_t> class F, unsigned... args> 
struct generate_array_impl<0, F, args...> {
    typedef ArrayHolder<F<0>::value, args...> result;
};

template<size_t N, template<size_t> class F> 
struct generate_array {
    typedef typename generate_array_impl<N-1, F>::result result;
};

Usage for your 1..5 case:

template<size_t index> struct MetaFunc { 
    enum { value = index + 1 }; 
};

void test() {
    const size_t count = 5;
    typedef generate_array<count, MetaFunc>::result A;

    for (size_t i=0; i<count; ++i) 
        std::cout << A::data[i] << "\n";
}

Answer 2

Well your requirements are so vague it's difficult to do anything about them... The main issue is of course: where do those value come from ?

Anyway a build in C++ can be thought of as 4 steps:

• Pre-build steps: script generation of header/source from other formats
• Preprocessing
• Template instantiations
• Compilation proper

If you wish to rule out the script generation, then you're left with 2 alternatives: Preprocessing and Meta-template programming.

There is just no way I know of for meta-template programming to do the trick here, because as far as I know it's not possible to concatenate two arrays at compile time. Thus we are left with the savior of the day: Preprocessor Programming

I would suggest using a full-fledged library to help us out: Boost.Preprocessor.

Of particular interest here:

• BOOST_PP_FOR
• BOOST_PP_REPEAT

Now if only we knew where to pick the values from, we could give more meaningful examples.

Answer 3

Since C++17 you can use a constexpr lambda an invoke it in place. The only "downside" is that you will have to use std::array instead of c-style array:

constexpr auto myArray{[]() constexpr{
    std::array<MyType, MySize> result{};
    for (int i = 0; i < MySize; ++i)
    {
       result[i] = ...
    }
    return result;
}()};

As an example that's how you could create an array with powers of two:

constexpr auto myArray{[]() constexpr{
    constexpr size_t size = 64;
    std::array<long long, size> result{};
    result[0] = 1;
    for (int i = 1; i < size; ++i)
    {
       result[i] = result[i - 1] * 2;
    }
    return result;
}()};

As you can see, you can even reference the previous cells of the array.

This technique is called IILE or Immediately Invoked Lambda Expression.

Answer 4

How about building a nested struct using templates, and casting that as an array of the right type. The example below works for me, but I have a feeling I'm either treading in or walking very close to undefined behaviour.

#include <iostream>

template<int N>
struct NestedStruct
{
  NestedStruct<N-1> contained;
  int i;
  NestedStruct<N>() : i(N) {}
};

template<>
struct NestedStruct<0> 
{
  int i;
  NestedStruct<0>() : i(0) {}
};

int main()
{
  NestedStruct<10> f;
  int *array = reinterpret_cast<int*>(&f);
  for(unsigned int i=0;i<10;++i)
  {
    std::cout<<array[i]<<std::endl;
  }
}

And of course you could argue that the array is not initialised at compile time (which I think is impossible) but the values that will go into the array are calculated at compile time, and you can access them as you would a normal array... I think that's as close as you can get.

Answer 5

Do you really need to do it at compiler time? It would be much easier to do at static initialization time. You could do something like this.

#include <cstddef>
#include <algorithm>

template<std::size_t n>
struct Sequence
{
    int list[n];

    Sequence()
    {
        for (std::size_t m = 0; m != n; ++m)
        {
            list[m] = m + 1;
        }
    }
};

const Sequence<5> seq1;

struct MostlyZero
{
    int list[5];

    MostlyZero()
    {
        std::fill_n(list, 5, 0); // Not actually necessary if our only
                                 // are static as static objects are
                                 // always zero-initialized before any
                                 // other initialization
        list[2] = 2;
        list[3] = 3;
    }
};

const MostlyZero mz1;

#include <iostream>
#include <ostream>

int main()
{
    for (std::size_t n = 0; n != 5; ++n)
    {
        std::cout << seq1.list[n] << ", " << mz1.list[n] << '\n';
    }
}

You could push the lists outside of the structs if you wanted but I thought it was a bit cleaner like this.

Answer 6

Something like Boost.Assignment could work for standard containers. If you really need to use arrays, you can use it along Boost.Array.

Answer 7

Sometime (not always) such array is generated from array of types. For example if you already have variadic class list (like template) and want to store encapsulated uint32_t value you can use:

uint32_t tab[sizeof(A)]= {A::value...};

Answer 8

the 1't question. You can do it like that.

template <int num, int cur>
struct ConsequentListInternal {
    enum {value = cur};
    ConsequentListInternal<num-1,cur+1> next_elem;
};

template <int cur>
struct ConsequentListInternal<0, cur> {
    enum {value = cur};
};

template <int v>
struct ConsequentList {
    ConsequentListInternal<v, 0> list;
};

int main() {
    ConsequentList<15> list;
    return 0;
}

Answer 9

Just use a code generator. Build one or more templates that can generate the code you want, using a table or even math functions. Then include the file you generated in your app.

Seriously, a code generator would make your life much easier.

Answer 10

There's a lot of things you can do with meta-programming. But first I'd like to ask: why would you want to do this in your case? I could understand if you needed to declare such an array in different places, so that it'd demand rewriting the same things multiple times. Is this your case?

By saying "define programmatically" I suggest the following:

#define MyArr(macro, sep) \
    macro(0) sep \
    macro(0) sep \
    macro(2) sep \
    macro(3) sep \
    macro(0) sep \
    macro(0) sep \
    macro(0)

By now we've defined all the values you wanted in the most abstract way. BTW if those values actually mean something for you - you could add it to the declaration:

#define MyArr(macro, sep) \
    macro(0, Something1) sep \
    macro(0, Something2) sep \
    // ...

Now let's breath life into the above declaration.

#define NOP
#define COMMA ,
#define Macro_Count(num, descr) 1
#define Macro_Value(num, descr) num

const std::size_t size = MyArr(Macro_Count, +); 
unsigned int list[size] = { MyArr(Macro_Value, COMMA) };

You can also handle the situation where most of your array entries are the same, with some perverted creativity :)

But you should always ask yourself: is this really worth it? Because, as you can see, you turn the code into a puzzle.

Answer 11

from boost,

boost::mpl::range_c<int,1,5>

Will generate a list of sorted numbers from 1 to 5 at compile time. For the second, you mention no criteria for which values would be changed. I'm pretty sure you can't undef then redef a new var once a list is created.

Answer 12

use template recursive

template<uint64_t N>
constexpr uint64_t Value()
{
    return N + 100;
}

// recursive case
template<uint64_t N, uint64_t... args>
struct Array : Array<N - 1, Value<N - 1>(), args...> {
};

// base case
template<uint64_t... args>
struct Array<0, Value<0>(), args...> {
    static std::array<uint64_t, sizeof...(args) + 1> data;
};

template<uint64_t... args>
std::array<uint64_t, sizeof...(args) + 1> Array<0, Value<0>(), args...>::data = {Value<0>(), args...};

int main()
{
    Array<10> myArray;
    for (size_t i = 0; i < myArray.data.size(); ++i) {
        cout << myArray.data[i] << endl;
    }

    return 0;
}

Answer 13

array<int, SIZE> t

As mentionned, with C++17 you can use constexpr

vector<int> countBits(int num) {
    static constexpr int SIZE = 100000;
    static constexpr array<int, SIZE> t {[]() constexpr {
            constexpr uint32_t size = SIZE;
            array<int, size> v{};
            for (int i = 0; i < size; i++)
                v[i] =  v[i>>1] + (i & 1); // or simply v[i] = __builtin_popcount(i);
            return v;}()};

    vector<int> v(t.begin(), t.begin() + num + 1);
    return v;
}

However you will have to use the c++ array type.

---

int t[SIZE]

If you really want to use a C array int [SIZE], different from array<int, SIZE> use the following trick:

Declare a global array and then compute values inside the main to create the static array at compile time:

int w[100000] = {0};

vector<int> countBits(int num) {
    vector<int> v(w, w + num + 1);
    return v;
}

int main(void) {
    for (int i = 0; i < 100000; i++)
        w[i] = __builtin_popcount(i);
}

---

Results

Output at runtime (awful indeed):

OK  ( 591 cycles)        0,1,1, -> 0,1,1,
OK  ( 453 cycles)        0,1,1,2,1,2, -> 0,1,1,2,1,2,
OK  ( 455 cycles)        0,1,1,2,1,2,2,3,1,2,... -> 0,1,1,2,1,2,2,3,1,2,...

Average Output with the constexpr array:

OK  (   1 cycles)        0,1,1, -> 0,1,1,
OK  (   2 cycles)        0,1,1,2,1,2, -> 0,1,1,2,1,2,
OK  (  24 cycles)        0,1,1,2,1,2,2,3,1,2,... -> 0,1,1,2,1,2,2,3,1,2,...

Average Output with the second method (slightly faster as we get rid of the overhead of C++ array):

OK  (   0 cycles)        0,1,1, -> 0,1,1,
OK  (   1 cycles)        0,1,1,2,1,2, -> 0,1,1,2,1,2,
OK  (  23 cycles)        0,1,1,2,1,2,2,3,1,2,... -> 0,1,1,2,1,2,2,3,1,2,...

---

Benchmark

I benchmarked with:

#include <vector>
#include <string>
#include <cstdint>
#include <array>
#include <iostream>
#include <ctime>
#include <iterator>
#include <sstream>

using namespace std;

vector<int> nums = {2, 5};
vector<vector<int>> expected = {{0,1,1}, {0,1,1,2,1,2}}; // feel free to add more tests

for (int i = 0; i < expected.size(); i++) {
        clock_t start = clock();
        vector<int> res = countBits(nums[i]);
        double elapsedTime = (clock() - start);
        printf("%s  \033[30m(%4.0lf cycles)\033[0m\t %s -> %s\n", (expected[i] == res) ? "\033[34mOK" : "\033[31mKO", elapsedTime, toString(res).c_str(), toString(expected[i]).c_str());
}

Answer 14

Over time, the capabilities of constexpr functions, methods and lambdas have greatly improved in C++. With C++17, you may use for loops and if conditions to actually calculate the contents of an constexpr array at compile time. See this example for a prime number sieve:

#include <array>
#include <cmath>

template<unsigned N>
constexpr auto primesieve() {
    std::array<bool, N+1> primes {};
    // From C++20, the init loop may be written as:   primes.fill(true);
    for(unsigned n = 0; n <= N; n++) {
        primes[n] = true;
    }
    unsigned maxs = sqrt(N);
    for(unsigned n = 2; n <= maxs; n++) {
        if(primes[n]) {
            for(unsigned j = n + n; j <= N; j += n) {
                primes[j] = false;
            }
        }
    }
    return primes;
};

extern constexpr std::array<bool, 20> myprimes { primesieve<19>() };

When you look at the assembly output of this code, you will see only the data bytes of the myprimes array, but not a single processor instruction. All calculations are performed at compile time, even if optimization is turned off.

However, as others have already written: Interpreting C++ code in the compiler is much slower than running compiled C++ code. So those initializations, that can reasonably be done at compile time, would take at most a few milliseconds at run time.

But const / constexpr initialization has many advantages. Namely they go to constant memory, that is shared between different processes running the same application. On the other hand, dynamic initialization at run time goes to private memory of each process.

And the capabilities are further improving. C++20 even adds support for std::string and std::vector in constexpr functions. However, you are not able to return non-empty strings and vectors from constexpr functions, and until now, only the Microsoft compiler has implemented this feature.