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.

Diamagnet

@GMan: The picture is as I've explained it, want to know if its possible to populate a static array at compile time using only c++. no hidden agendas etc. – Diamagnet

@Diamagnet @GMan's comment is relevant, because you can't do it in C++ nor in C++0x. Provide readers with the context, and the gurus would find you a (alternative)suitable solution for the original problem. – Nippers

@Hippicoder: Well, for example, where do the values in your example come from? What is their relation to the compile-time environment? Are they from a text file? Are they flags saying whether macros are defined? Are they counters of some kind? – Lebbie

Also, do you need to index the values at compile-time or at run-time? – Nippers

Assume a process requires a LUT, depending on the mode of the process the LUTs are the same except for some of the values, all the other values are the same or can be generated by evaluting a simple sequence like f(n) = 2*n or f(n) = 1 + n etc... – Diamagnet

@Hippy, where I work code is being generated all of the time and we have not gone out of business yet. – Organotherapy

I think the first could be done with a recursive template and passing a constant + 1 to each deeper level. I'm looking into that now. – Basis

@Michael Dorgan: I thought about that too, but cant seem to come up with the right way to do it, atm my solution involves getting a value from an enum off-of a templated struct, but still requires me to instantiate n templates which increases the compile time greatly. – Diamagnet

Template meta-programming only gives you recursive structures, the best you could get is an instantation depth of N/M instead of N. – Droppings

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

Droppings

A note regarding template instantiation depth, msvc dies at around 1000, gcc has an option to set the recursive depth, I've been able to create a 512 element lut with this suggestion - compile times are obviously a little longer than having the lut hard-coded in source, but all-in-all it works fine!!! :D – Diamagnet

Amazing! It essentially allows the concatenation / extension of arrays I could not realize in C++03 with metatemplate. I think you should parameterize ArrayHolder with the MetaFunction though, in order to be able to define more than 1 array with a given arity. – Equinoctial

@Matthieu: If the values differ its a different type, if they are the same i don't want a duplicate type here - am i missing something? – Droppings

as a work around for the fairly limited recursion depth some compilers allow, one may add more then one value to the "variadic values list" each step, decreasing the required depth M times, where M is the number of values added. For instance, for M=2 we have: template<size_t N, template<size_t> class F, unsigned... args> struct generate_array_impl { typedef typename generate_array_impl<N-2, F, F<N-1>::value, F<N>::value, args...>::result result; }; But please do not forget to treat the case where N%M != 0 – Pinworm

+100 I was about to throw std::initializer_list for constructors out the window, until I found your answer. It'll certainly be a while until I understand how this works, but I am in awe of this amazing bridge from compile-time to run-time. TYVM. – Furor

What does the ... stand for? – Inexpugnable

@GeorgFritzsche Can this be made to work to hold non-integral types like float or double? – Undressed

@Xocoatzin That is the parameter pack expansion, see e.g. here – Droppings

@hazelnusse Not directly, but can't you use constexpr functions? Alternatives are a bit crude, like basically reimplementing floating point semantics. – Droppings

Why do you need generate_array for? It works pretty much the same if you remove it and use generate_array_impl directly in your test function: typedef generate_array_impl<count, MetaFunc>::result A;. – Supernaturalism

Are there better ways of doing this in 2017? This solution looks terrible. Why can't we just have delayed initialization inside constexpr functions? – Tien

Answer 2

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.

Lindon

This will not compile because of error: overflow in constant expression. Using some other initialization like result[i] = i or decreasing the size to 32 or using unsigned long long instead of long long will make it compile. Love the implicit undefined behavior checks in constexpr annotated functions. But as this is not consteval (C++20), there is no guarantee that this IILE is executed at compile-time afaik. – Annular

Testing it on godbolt, it seems to work well enough though: godbolt.org/z/1n6h3Evvs – Annular

@Annular There is a guarantee. The lambda doesn't have to be consteval as myArray is constexpr, so it has to be initialised at compile time. As long as constexpr auto myArray{whatever}; compiles, whatever had to be known at compile time. Correct me, if I'm wrong. – Lindon

Answer 3

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.

Equinoctial

Check out Georg Fritzsche's answer: using C++0x variadic templates and initialization of static arrays from varadic list he was able to come up with a metatemplate solution! – Equinoctial

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.

Advised

That reinterpret_cast sets undefined behaviour alarm bells ringing in my head. – Ouzo

We can avoid the reinterpret_cast by using &f.i-10 or adding a recursive int* start() function instead. However the question really is "does the compiler insert padding between contained and i in the nested struct?". I see no reason why it would, as NestedStruct<N> and int will have the same alignment requirements. However I don't think there's anything in the spec which would prohibit insertion of padding in this case. (Maybe a better language lawyer than me would know for sure though). – Advised

Answer 5

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

Mccullum

Answer 6

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.

Salpa

Two people have flagged this as spam. It doesn't appear to be spam to me, except your code generator isn't yet available, so mentioning it doesn't help to answer the question. (Editing the answer once your tool is available would be different.) – And I'm also a big fan of code generation, it really will make his life easier. ;) – Eugenle

@Roger: I've edited my answer and removed all references to the product. – Salpa

Now it's definitely worth an upvote! Self-promotion is a tricky business on SO. – Eugenle

The code generator can be array_type user_impl(size_t index); Use std::cout and a comma to generate the array body. You can use #include to include the generated body in the code. Just code it like run-time initialization and then use a host built binary to generate the array. For most users, host, build, and target are all the same. – Archidiaconal

Answer 7

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.

Norikonorina

The values are not present at compile-time - I think if what i wanted was as simple as that I could just as easily written a function to populate a std::vector... thanks for the attempt though. – Diamagnet

@Hippicoder: If the values aren't present at compile-time then how are you going to programmatically assign them at compile-time as your question asks? – Norikonorina

I believe he's trying to say your code isn't generating them at compile time. Your code is creating the array at runtime, and thus doesn't fit his overly tight requirements... – Forecourse

Answer 8

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

Portrait

Answer 9

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

Sukkah

Ok.... how would I get the ith value from the list, with a run-time generated "i" ? ps: please read the comment to Michael Dorgan's solution. – Diamagnet

Answer 10

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

Gulch

Answer 11

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.

Neeley

Answer 12

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.

Hopple

Why would you push something back to runtime that should be calculable at compile time? He has to turn the code into a puzzle because of gaps in the C++ language. – Huesman

Answer 13

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.

Basis

the with range_c and other mpl style arrays is that, they don't have a random access operator, or if they do it requires a compile-time index value. I'd like to be able to use the array as i would a static array at run-time with run-time generated index values. – Diamagnet

Answer 14

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

Mochun