C++11: Compile Time Calculation of Array
Suppose I have some constexpr function f:
constexpr int f(int x) { ... }
And I have some const int N known at compile time:
Either
#define N ...;
or
const int N = ...;
as needed by your answer.
I want to have an int array X:
int X[N] = { f(0), f(1), f(2), ..., f(N-1) }
such that the function is evaluated at compile time, and the entries in X are calculated by the compiler and the results are placed in the static area of my application image exactly as if I had used integer literals in my X initializer list.
Is there some way I can write this? (For example with templates or macros and so on)
Best I have: (Thanks to Flexo)
#include <iostream>
#include <array>
using namespace std;
constexpr int N = 10;
constexpr int f(int x) { return x*2; }
typedef array<int, N> A;
template<int... i> constexpr A fs() { return A{{ f(i)... }}; }
template<int...> struct S;
template<int... i> struct S<0,i...>
{ static constexpr A gs() { return fs<0,i...>(); } };
template<int i, int... j> struct S<i,j...>
{ static constexpr A gs() { return S<i-1,i,j...>::gs(); } };
constexpr auto X = S<N-1>::gs();
int main()
{
cout << X[3] << endl;
}
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.
Boost.Preprocessor can help you. The restriction, however, is that you have to use integral literal such as 10 instead of N (even be it compile-time constant):
#include <iostream>
#include <boost/preprocessor/repetition/enum.hpp>
#define VALUE(z, n, text) f(n)
//ideone doesn't support Boost for C++11, so it is C++03 example,
//so can't use constexpr in the function below
int f(int x) { return x * 10; }
int main() {
int const a[] = { BOOST_PP_ENUM(10, VALUE, ~) }; //N = 10
std::size_t const n = sizeof(a)/sizeof(int);
std::cout << "count = " << n << "\n";
for(std::size_t i = 0 ; i != n ; ++i )
std::cout << a[i] << "\n";
return 0;
}
Output (ideone):
count = 10
0
10
20
30
40
50
60
70
80
90
The macro in the following line:
int const a[] = { BOOST_PP_ENUM(10, VALUE, ~) };
expands to this:
int const a[] = {f(0), f(1), ... f(9)};
A more detail explanation is here:
- BOOST_PP_ENUM
If you want the array to live in static memory, you could try this:
template<class T> struct id { typedef T type; };
template<int...> struct int_pack {};
template<int N, int...Tail> struct make_int_range
: make_int_range<N-1,N-1,Tail...> {};
template<int...Tail> struct make_int_range<0,Tail...>
: id<int_pack<Tail...>> {};
#include <array>
constexpr int f(int n) { return n*(n+1)/2; }
template<class Indices = typename make_int_range<10>::type>
struct my_lookup_table;
template<int...Indices>
struct my_lookup_table<int_pack<Indices...>>
{
static const int size = sizeof...(Indices);
typedef std::array<int,size> array_type;
static const array_type& get()
{
static const array_type arr = {{f(Indices)...}};
return arr;
}
};
#include <iostream>
int main()
{
auto& lut = my_lookup_table<>::get();
for (int i : lut)
std::cout << i << std::endl;
}
If you want a local copy of the array to work on, simply remove the ampersand.
There are quite a few great answers here. The question and tags specify c++11, but as a few years have passed, some (like myself) stumbling upon this question may be open to using c++14. If so, it is possible to do this very cleanly and concisely using std::integer_sequence; moreover, it can be used to instantiate much longer arrays, since the current "Best I Have" is limited by recursion depth.
constexpr std::size_t f(std::size_t x) { return x*x; } // A constexpr function
constexpr std::size_t N = 5; // Length of array
using TSequence = std::make_index_sequence<N>;
static_assert(std::is_same<TSequence, std::integer_sequence<std::size_t, 0, 1, 2, 3, 4>>::value,
"Make index sequence uses std::size_t and produces a parameter pack from [0,N)");
using TArray = std::array<std::size_t,N>;
// When you call this function with a specific std::integer_sequence,
// the parameter pack i... is used to deduce the the template parameter
// pack. Once this is known, this parameter pack is expanded in
// the body of the function, calling f(i) for each i in [0,N).
template<std::size_t...i>
constexpr TArray
get_array(std::integer_sequence<std::size_t,i...>)
{
return TArray{{ f(i)... }};
}
int main()
{
constexpr auto s = TSequence();
constexpr auto a = get_array(s);
for (const auto &i : a) std::cout << i << " "; // 0 1 4 9 16
return EXIT_SUCCESS;
}