我需要存储前N个斐波纳契数的数组。编译时间可以评估数组吗？
const int N = 100;
long long int fib[N] = {0};
fib[0] = 1;
fib[1] = 1;
for(int i = 2; i < N; ++i)
fib[i] = fib[i-2] + fib[i-1];
return 0;
是否有可能使FIB [] constexpr，并在编译时不知怎么评价它？
首先你必须写在编译时版本斐波那契数的算法，所以考虑以下几点：
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};
};
和你可以这样简单地使用它：
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;
个输出值：
1
1
2
3
89
20365011074
但这仍然不是你所期待的。
我不知道你是否可以做constexpr数组（但可能有可能），但你可以做一点点不同。试想一下：
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();
}
};
和用法是这样的：
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;
}
输出：
1
1
2
3
5
8
13
21
34
55
89
144
233
这里重要的是Storage类存储我们的阵列的适当数量元素。
一般Filler类（有两个模板参数）用于可以传递任何F价值的，除0值，因为如果我们达到0指数，我们不想打电话再次fill()成员函数呢，因为我们完成了。所以这就是为什么Filler类存在部分专业化的原因。
希望我能帮到你。
注意fib（10）是55而不是89（它是fib（11））。问题在于fib（0）== 0而不是1.但是这在问题中已经不正确。 –
@AndreasH。当然，你是对的:) –
有一种方法（丑陋的），但我想不出别的。
#include <iostream>
#include <cmath>
constexpr unsigned long long f(int x)
{
return 1/sqrt(5)*pow(((1+sqrt(5))/2),x) - 1/sqrt(5)*pow(((1-sqrt(5))/2),x);
}
#define FIBB1(x) 1
#define FIBB2(x) FIBB1(x-1),1
#define FIBB3(x) FIBB2(x-1),f(x)
#define FIBB4(x) FIBB3(x-1),f(x)
#define FIBB5(x) FIBB4(x-1),f(x)
#define FIBB6(x) FIBB5(x-1),f(x)
#define FIBB7(x) FIBB6(x-1),f(x)
#define FIBB8(x) FIBB7(x-1),f(x)
#define FIBB9(x) FIBB8(x-1),f(x)
#define FIBB10(x) FIBB9(x-1),f(x)
#define FIBB11(x) FIBB10(x-1),f(x)
#define FIBB12(x) FIBB11(x-1),f(x)
#define FIBB13(x) FIBB12(x-1),f(x)
#define FIBB14(x) FIBB13(x-1),f(x)
#define FIBB15(x) FIBB14(x-1),f(x)
#define FIBB16(x) FIBB15(x-1),f(x)
#define FIBB17(x) FIBB16(x-1),f(x)
#define FIBB18(x) FIBB17(x-1),f(x)
#define FIBB19(x) FIBB18(x-1),f(x)
#define FIBB20(x) FIBB19(x-1),f(x)
// ...
#define FIBB93(x) FIBB92(x-1),f(x)
//#define FIBB94(x) FIBB93(x-1),f(x) //unsigned long long overflow, can't calculate more
#define FIBB(x) {FIBB##x(x)}
constexpr unsigned long long fib[93] = FIBB(93);
int main()
{
// all possible fibbonacci numbers for unsigned long long implementation
for(int i=0; i<93; ++i)
std::cout << fib[i] << std::endl;
}
我认为这是C++内建数组的唯一方法。
在您发布的代码示例，有一个像样的机会，编译器可能会展开循环，或至少它的一部分，就其本身而言，如果使用-O3优化。在godbolt上播放时，看起来这不是在N=100发生，而是在N达到约40.在这种情况下它确实发生在编译时，不管它是否是constexpr。
其中还指出 - 在许多机器上，long long int不足以容纳第100个斐波纳契数。斐波纳契数字以指数形式增长，您应该期望第100个数字需要大约100位左右。在典型的机器上，由于整数溢出，写入的代码将显示未定义的行为。
使用模板，你可以做这样的：
// Fibonacci recurrence
template <long int n>
struct fib_pair {
typedef fib_pair<n-1> prev;
static constexpr long int fib_n = prev::fib_n_plus_one;
static constexpr long int fib_n_plus_one = prev::fib_n + prev::fib_n_plus_one;
};
template <>
struct fib_pair<0> {
static constexpr long int fib_n = 0;
static constexpr long int fib_n_plus_one = 1;
};
// List structure
template <long int ... > struct list {};
// Concat metafunction
template <typename A, typename B> struct concat;
template <long int... As, long int... Bs> struct concat<list<As...>, list<Bs...>> {
typedef list<As..., Bs...> type;
};
// Get a sequence from the fib_pairs
template <long int n>
struct fib_seq {
typedef typename fib_seq<n-1>::type prev;
typedef typename concat<prev, list<fib_pair<n>::fib_n>>::type type;
};
template <>
struct fib_seq<0> {
typedef list<0> type;
};
// Make an array from pack expansion
#include <array>
template <typename T> struct helper;
template <long int ... nums>
struct helper <list<nums...>> {
typedef std::array<const long int, sizeof...(nums)> array_type;
static constexpr array_type get_array() {
return {{ nums... }};
}
};
// Easy access
template <long int n>
constexpr std::array<const long int, n + 1> get_fib_array() {
return helper<typename fib_seq<n>::type>::get_array();
}
#include <iostream>
int main() {
for (const long int x : get_fib_array<15>()) {
std::cout << x << std::endl;
}
}
它是std :: array
是的，这是真的，但它并没有真正的不同，我的意思是，如果你愿意，你可以从里面得到'T array [N]'，它是在编译时建立的。 –
它可以工作，但需要时间去了解 –
这是一个C++ 14解决方案（GCC> = 5.0.0，Clang> = 3.5.0），使用模板参数来表示长度。你在constexpr函数中编写了一个命令循环（与原始文章相同）。使用disassembler，即使没有优化（-O0），也可以看到序列作为原始数据嵌入到程序中。
#include <array>
#include <cstddef>
#include <iostream>
#include <type_traits>
#include <utility>
namespace {
// Create an std::array from a C array (internal) via an
// std::index_sequence.
template <typename T, typename TSequence> struct MakeArrayImpl;
template <typename T, std::size_t... TIndices>
struct MakeArrayImpl<T, std::index_sequence<TIndices...>> {
static constexpr std::array<T, sizeof...(TIndices)>
make_array(T values[sizeof...(TIndices)]) {
return std::array<T, sizeof...(TIndices)>{{values[TIndices]...}};
}
};
// Create an std::array from a C array.
template <typename T, std::size_t TLength>
constexpr std::array<T, TLength> make_array(T values[TLength]) {
return MakeArrayImpl<T, std::make_index_sequence<TLength>>::make_array(
values);
}
// Return an std::array of the first numbers in the Fibonacci sequence.
template <std::size_t TLength>
constexpr std::array<long long int, TLength> fibs() {
// Original algorithm.
long long int fib[TLength] = {0};
fib[0] = 1;
fib[1] = 1;
for (std::size_t i = 2; i < TLength; ++i) {
fib[i] = fib[i - 2] + fib[i - 1];
}
return make_array<long long int, TLength>(fib);
}
}
int main() {
// Original algorithm.
const int N = 92;
long long int fib[N] = {0};
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < N; ++i)
fib[i] = fib[i - 2] + fib[i - 1];
// Test constexpr algorithm against original algorithm.
static constexpr auto values = fibs<N>();
static_assert(values.size() == N, "Expected N values in Fibs");
for (int i = 0; i < N; ++i) {
if (fib[i] != values[i]) {
std::cerr << "Mismatch at index " << i << "\n";
std::cerr << "Expected: " << fib[i] << "\n";
std::cerr << "Actual : " << values[i] << "\n";
}
}
}
下面是使用C++库14层的特征的C++ 11溶液[1]（GCC> = 4.9.0，锵> = 3.5.0）使用用于长度的模板参数。你使用递归编写一个循环。使用disassembler，即使没有优化（-O0），也可以看到序列作为原始数据嵌入到程序中。
[1] std::index_sequence如果在标准库中不可用，可以在C++ 11中自己实现。
#include <array>
#include <cstddef>
#include <iostream>
#include <type_traits>
#include <utility>
namespace {
// Create an std::array from a C array (internal) via an
// std::index_sequence.
template <typename T, typename TSequence> struct MakeArrayImpl;
template <typename T, std::size_t... TIndices>
struct MakeArrayImpl<T, std::index_sequence<TIndices...>> {
static constexpr std::array<T, sizeof...(TIndices)>
make_array(T values[sizeof...(TIndices)]) {
return std::array<T, sizeof...(TIndices)>{{values[TIndices]...}};
}
};
// Create an std::array from a C array.
template <typename T, std::size_t TLength>
constexpr std::array<T, TLength> make_array(T values[TLength]) {
return MakeArrayImpl<T, std::make_index_sequence<TLength>>::make_array(
values);
}
// Return an std::array of the first numbers in the Fibonacci sequence.
template <std::size_t TLength>
constexpr std::array<long long int, TLength> fibs() {
// Original algorithm.
long long int fib[TLength] = {0};
fib[0] = 1;
fib[1] = 1;
for (std::size_t i = 2; i < TLength; ++i) {
fib[i] = fib[i - 2] + fib[i - 1];
}
return make_array<long long int, TLength>(fib);
}
}
int main() {
// Original algorithm.
const int N = 92;
long long int fib[N] = {0};
fib[0] = 1;
fib[1] = 1;
for (int i = 2; i < N; ++i)
fib[i] = fib[i - 2] + fib[i - 1];
// Test constexpr algorithm against original algorithm.
static constexpr auto values = fibs<N>();
static_assert(values.size() == N, "Expected N values in Fibs");
for (int i = 0; i < N; ++i) {
if (fib[i] != values[i]) {
std::cerr << "Mismatch at index " << i << "\n";
std::cerr << "Expected: " << fib[i] << "\n";
std::cerr << "Actual : " << values[i] << "\n";
}
}
}
使用矢量 fib; –
MASh
目前如何宣布它有什么问题？ **编译时评估**。顺便说一句，如果你使用C++，那么你可以使用'vector'。 –
我希望它在编译时被预先计算，向量不会帮助我达到此目的。我希望该数组是constexpr。 –