我需要存儲前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。 –