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 std::array using math formula in compile time

Here's a non-confusing approach: wrap the calculation in a function:

template <int N>
constexpr std::array<double, N> generate()
{
    std::array<double, N> arr{};
    for (int i = 0; i < N; ++i)
        arr[i] = complexFormula(i);
    return arr;
}

Usage example:

constexpr std::array<double, 10000> arr = generate<10000>();

(live demo)

This works because, since C++14, loops are allowed in a constexpr function, and variables can be modified as long as their lifetime starts within the evaluation of the constant expression.

C++: int calculations during compile time (not during running time)

Is this calculation done during compile time?

Yes, compilers did a lot optimizations and calculations for you, the initialization in your code is ok even without any optimization, and it's the result of pre-calculation of compiler.

Generally, calculation here includes the constexpr, const type declaration and so on, which are already in the definition of language itself(see constant expression).

compile-time const and example

just see the output of the example.

compile-time constexpr and example

The constexpr specifier declares that it is possible to evaluate the value of the function or variable at compile time.

This is how array can be initialized, an array declaration is as below:

noptr-declarator [ expr(optional) ] attr(optional)

here, expr is:

an integral constant expression (until C++14) a converted constant expression of type std::size_t (since C++14), which evaluates to a value greater than zero

which are all constant expression, which says:

an expression that can be evaluated at compile time.

So, using the so-called pre-calculation to initialize an array is ok.

Here's also a follow-up: there're also a lot of ways to save more calculations and time by let them done during compile time, and they are shown in the link above.

Just to mention something different: As for optimizations, you can see the difference between the assembly codes of version -O0 and -O3 when calculating the sum from 1 to 100, it's a jaw-breaker -- you'll see the result 5050 is in the assembly code in the -O3 version, it's also a kind of compile-time calculation, but not enabled for all kinds of situation.

Is it possible to evaluate array on compilation time?

First of all you have to write Fibonacci algorithm in compile time version, so consider following:

template <size_t N>
struct Fibo {
    static constexpr const size_t value {Fibo<N-2>::value + Fibo<N-1>::value};
};

template <>
struct Fibo<0> {
    static constexpr const size_t value {1};
};

template <>
struct Fibo<1> {
    static constexpr const size_t value {1};
};

and you can use this as simply as that:

std::cout << Fibo<0>::value << std::endl;
std::cout << Fibo<1>::value << std::endl;
std::cout << Fibo<2>::value << std::endl;
std::cout << Fibo<3>::value << std::endl;
std::cout << Fibo<10>::value << std::endl;
std::cout << Fibo<50>::value << std::endl;

and output values are:

1
1
2
3
89
20365011074

But this is still not you are looking for.

I do not know if you can make constexpr array (but probably there is a possibility), but you can do it slightly different. Consider:

template <size_t N>
struct Storage {
    static size_t data[N+1];
};

template <size_t N> size_t Storage<N>::data[N+1] {};

template <size_t N, size_t F>
struct Filler {
    static constexpr void fill () {
        Storage<N>::data[F] = Fibo<F>::value;
        Filler<N, F-1>::fill ();
    }
};

template <size_t N>
struct Filler<N, 0> {
    static constexpr void fill () { 
        Storage<N>::data[0] = Fibo<0>::value;
    }
};

template <size_t N>
struct Calc {
    static constexpr void calc () {        
        Filler<N, N>::fill ();
    }
};

and the usage would be like this:

constexpr const size_t N = 12;

Calc<N>::calc ();
size_t* ptr = Storage<N>::data;

for (int i = 0; i <= N; ++i) {
    std::cout << ptr[i] << std::endl;
}

and output:

What is important here is the Storage class which stores our array with appropriate number of elements.

General Filler class (with two template parameters) is used for any F value that can be passed, except value of 0. Because if we reach the 0 index, we don't want to call once again fill() member function, because we are done. So that's the reason why partial specialization of Filler class exists.

Hope I can help with this.

C++ calculate and sort vector at compile time

A std::vector<int> does not have any constexpr constructors (because dynamic memory allocation is disallowed for constexpr). So you can't sort a std::vector<int> at compile-time.

You can create a std::array<int, N> at compile-time for a constant N, but you'd have to write your own sorting routine because std::sort is not constexpr either.

You can also write a Boost.MPL compile-time vector or list and use the sort routine of that. But this won't scale as well as std::array.

Another angle of attack might be to store the vector into a static variable and do the sorting at program initialization. Your program just takes a bit longer to start, but it won't affect the rest of its main functionality.

Since sorting is O(N log N), you might even have a two-step build and write the sorted vector to a file, and either compile/link it to your main program, or load it in O(N) at program startup into a static variable.

Determine positions in array at compile-time in c

Rather than trying to kludge C to do something it was not meant to do, a better and common method is to prepare data for a C program by writing a program that prepares the data. That is, write some other program that counts the data in the parts and writes the C code necessary to initialize both DATA and PART_IDX.

Another option is:

Put all the data each part in a separate “.h” file, such as files “part1.h”, “part2.h”, “part3.h”.
To initialize DATA, include all of those header files in its initializer list.
To calculate the indices for the parts, use sizeof to calculate the numbers of elements in proxy arrays containing the preceding parts.

Example:

“part1.h” contains 10, 11, 12,.

“part2.h“ contains 20, 21,.

“part3.h” contains 30, 31, 32, 33,.

The C file is:

const unsigned char DATA[] =
{
    #include "part1.h"
    #include "part2.h"
    #include "part3.h"
};

const unsigned int PART_IDX [] =
{
    0,

    sizeof (const unsigned char []) {
        #include "part1.h"
    } / sizeof (const unsigned char),

    sizeof (const unsigned char []) {
        #include "part1.h"
        #include "part2.h"
    } / sizeof (const unsigned char),
};

#include <stdio.h>

int main(void)
{
    for (int i = 0; i < 3; ++i)
        printf("Part %d begins at index %d with value %d.\n",
            i, PART_IDX[i], DATA[PART_IDX[i]]);
}

Force a constexpr function to be compiled at compile time, even if calculation inside contains a non-const array, by making the returned obj constant?

From what i know, a constexpr function is definitely evaluated at compile time, when every value inside the function is const and used functions are constexpr which also only use const values. Furthermore, an other post stated, that it's possible to force a compile time compilation by making the returned obj const.

All of these statements are wrong. See below.

No, a call to a constexpr function is only guaranteed to be evaluated at compile-time if it is called in a context requiring a (compile-time) constant expression. The initializer of obj2 is not such a context, even if it is const.

You can force the initializer to be compile-time evaluated by declaring obj2 as constexpr. (Which however has very different meaning than const!)

Even then it is not going to work, because calculations<double, size>(obj1) is not actually a constant expression. obj1 is not a compile-time constant without declaring it constexpr as well. Similarly this doesn't work because test1 is not a constant expression without declaring it constexpr as well.

Then you also need to make the constructor of Array constexpr and you need to actually fill the values of test1 inside calculations, because accessing uninitialized values causes undefined behavior and undefined behavior makes expressions not constant expressions.

So all in all:

template<int Size, typename T>
struct Array{
    T array[Size];
    constexpr Array(const T * a) {
        for(int i = 0; i < Size; i++){
            array[i] = a[i];
        }
    }
};

template<typename T, int size>
class Example{

private:
    Array<size, T> _array;
    public:
        constexpr explicit Example(T * arr):_array(arr){};
        constexpr explicit Example(const T * arr):_array(arr){};
};

template<typename D, int size, typename ...buf, typename T>
constexpr auto calculations(const T & myObj){
    D test1[2];
    test1[0] = 0;
    test1[1] = 1;
    // calculation fills arr
    return Example<D, size>(test1);
}

int main(){
    const int size = 2;
    constexpr double test1[size] = {1,2};
    constexpr auto obj1 = Example<double, size>(test1); //compile time
    //obj2 calculations during compile time or run-time?
    constexpr auto obj2 = calculations<double, size>(obj1);
}

In C++20 there will be an alternative keyword consteval which one can use instead of constexpr on a function to force it to always be evaluated at compile-time. Currently there is no way to do that without making e.g. the destination of the return value a constexpr variable.

In fact your original code has undefined behavior. Because Array does not have a constexpr constructor, objects of that type can never be constructed in constant expressions. And because Example uses that type, it cannot be used in constant expressions either. This makes it illegal to put constexpr on its constructor, because a function declared constexpr causes undefined behavior if there isn't at least one valid set of template arguments and function arguments that would produce a constant expression. (The same then applies to calculations as well, because it uses Example.

So you must put constexpr on the constructor of Array in any case if your program is supposed to be well-formed.

Whether variables created inside the constant expression (e.g. inside calculations) are const does not matter at all.

How to get an array size at compile time?

If your standard-library is C++17-compatible, just use std::size(xyz).

If your standard-library doesn't already provide that, it's easy to implement yourself, the constexpr-specifier is C++11.

C++11: Compile Time Calculation of Array