C++ 在运行时获取模板元编程编译时常量
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/908256/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Getting template metaprogramming compile-time constants at runtime
提问by GManNickG
Background
背景
Consider the following:
考虑以下：
template <unsigned N>
struct Fibonacci
{
enum
{
value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
};
};
template <>
struct Fibonacci<1>
{
enum
{
value = 1
};
};
template <>
struct Fibonacci<0>
{
enum
{
value = 0
};
};
This is a common example and we can get the value of a Fibonacci number as a compile-time constant:
这是一个常见的例子，我们可以将斐波那契数的值作为编译时常量：
int main(void)
{
std::cout << "Fibonacci(15) = ";
std::cout << Fibonacci<15>::value;
std::cout << std::endl;
}
But you obviously cannot get the value at runtime:
但是您显然无法在运行时获得该值：
int main(void)
{
std::srand(static_cast<unsigned>(std::time(0)));
// ensure the table exists up to a certain size
// (even though the rest of the code won't work)
static const unsigned fibbMax = 20;
Fibonacci<fibbMax>::value;
// get index into sequence
unsigned fibb = std::rand() % fibbMax;
std::cout << "Fibonacci(" << fibb << ") = ";
std::cout << Fibonacci<fibb>::value;
std::cout << std::endl;
}
Because fibbis not a compile-time constant.
因为fibb不是编译时常量。
Question
题
So my question is:
所以我的问题是：
What is the best way to peek into this table at run-time? The most obvious solution (and "solution" should be taken lightly), is to have a large switch statement:
在运行时查看此表的最佳方法是什么？最明显的解决方案（和“解决方案”应该掉以轻心）是有一个大的 switch 语句：
unsigned fibonacci(unsigned index)
{
switch (index)
{
case 0:
return Fibonacci<0>::value;
case 1:
return Fibonacci<1>::value;
case 2:
return Fibonacci<2>::value;
.
.
.
case 20:
return Fibonacci<20>::value;
default:
return fibonacci(index - 1) + fibonacci(index - 2);
}
}
int main(void)
{
std::srand(static_cast<unsigned>(std::time(0)));
static const unsigned fibbMax = 20;
// get index into sequence
unsigned fibb = std::rand() % fibbMax;
std::cout << "Fibonacci(" << fibb << ") = ";
std::cout << fibonacci(fibb);
std::cout << std::endl;
}
But now the size of the table is very hard coded and it wouldn't be easy to expand it to say, 40.
但是现在表格的大小是非常硬编码的，并且很难将其扩展为 40。
The only one I came up with that has a similiar method of query is this:
我想出的唯一一个具有类似查询方法的方法是：
template <int TableSize = 40>
class FibonacciTable
{
public:
enum
{
max = TableSize
};
static unsigned get(unsigned index)
{
if (index == TableSize)
{
return Fibonacci<TableSize>::value;
}
else
{
// too far, pass downwards
return FibonacciTable<TableSize - 1>::get(index);
}
}
};
template <>
class FibonacciTable<0>
{
public:
enum
{
max = 0
};
static unsigned get(unsigned)
{
// doesn't matter, no where else to go.
// must be 0, or the original value was
// not in table
return 0;
}
};
int main(void)
{
std::srand(static_cast<unsigned>(std::time(0)));
// get index into sequence
unsigned fibb = std::rand() % FibonacciTable<>::max;
std::cout << "Fibonacci(" << fibb << ") = ";
std::cout << FibonacciTable<>::get(fibb);
std::cout << std::endl;
}
Which seems to work great. The only two problems I see are:
这似乎很好用。我看到的唯一两个问题是：
Potentially large call stack, since calculating Fibonacci<2> requires we go through TableMax all the way to 2, and:
If the value is outside of the table, it returns zero as opposed to calculating it.
潜在的大调用堆栈，因为计算 Fibonacci<2> 需要我们通过 TableMax 一直到 2，并且：
如果该值在表之外，则返回零而不是计算它。
So is there something I am missing? It seems there should be a better way to pick out these values at runtime.
那么有什么我想念的吗？似乎应该有更好的方法在运行时挑选这些值。
A template metaprogramming version of a switch statement perhaps, that generates a switch statement up to a certain number?
一个 switch 语句的模板元编程版本，它可能会生成一个特定数量的 switch 语句？
Thanks in advance.
提前致谢。
采纳答案by rlbond
template <unsigned long N>
struct Fibonacci
{
enum
{
value = Fibonacci<N-1>::value + Fibonacci<N-2>::value
};
static void add_values(vector<unsigned long>& v)
{
Fibonacci<N-1>::add_values(v);
v.push_back(value);
}
};
template <>
struct Fibonacci<0>
{
enum
{
value = 0
};
static void add_values(vector<unsigned long>& v)
{
v.push_back(value);
}
};
template <>
struct Fibonacci<1>
{
enum
{
value = 1
};
static void add_values(vector<unsigned long>& v)
{
Fibonacci<0>::add_values(v);
v.push_back(value);
}
};
int main()
{
vector<unsigned long> fibonacci_seq;
Fibonacci<45>::add_values(fibonacci_seq);
for (int i = 0; i <= 45; ++i)
cout << "F" << i << " is " << fibonacci_seq[i] << '\n';
}
After much thought into the problem, I came up with this solution. Of course, you still have to add the values to a container at run-time, but (importantly) they are not computedat run-time.
经过对问题的深思熟虑，我想出了这个解决方案。当然，您仍然必须在运行时将值添加到容器中，但（重要的是）它们不会在运行时计算。
As a side note, it's important not to define Fibonacci<1>above Fibonacci<0>, or your compiler will get veryconfused when it resolves the call to Fibonacci<0>::add_values, since Fibonacci<0>'s template specialization has not been specified.
作为旁注，重要的是不要在Fibonacci<1>上面定义Fibonacci<0>，否则您的编译器在解析对 的调用时会非常困惑Fibonacci<0>::add_values，因为Fibonacci<0>尚未指定 的模板特化。
Of course, TMP has its limitations: You need a precomputed maximum, and getting the values at run-time requires recursion (since templates are defined recursively).
当然，TMP 有其局限性：您需要预先计算的最大值，并且在运行时获取值需要递归（因为模板是递归定义的）。
回答by madoki
I know this question is old, but it intrigued me and I had to have a go at doing without a dynamic container filled at runtime:
我知道这个问题很老，但它引起了我的兴趣，我不得不尝试在运行时没有填充动态容器的情况：
#ifndef _FIBONACCI_HPP
#define _FIBONACCI_HPP
template <unsigned long N>
struct Fibonacci
{
static const unsigned long long value = Fibonacci<N-1>::value + Fibonacci<N-2>::value;
static unsigned long long get_value(unsigned long n)
{
switch (n) {
case N:
return value;
default:
return n < N ? Fibonacci<N-1>::get_value(n)
: get_value(n-2) + get_value(n-1);
}
}
};
template <>
struct Fibonacci<0>
{
static const unsigned long long value = 0;
static unsigned long long get_value(unsigned long n)
{
return value;
}
};
template <>
struct Fibonacci<1>
{
static const unsigned long long value = 1;
static unsigned long get_value(unsigned long n)
{
return value;
}
};
#endif
This seems to work, and when compiled with optimizations (not sure if you were going to allow that), the call stack does not get to deep - there is normal runtime recursion on the stack of course for values (arguments) n > N, where N is the TableSize used in the template instantiation. However, once you go below the TableSize the generated code substitutes a constant computed at compile time, or at worst a value "computed" by dropping through a jump table (compiled in gcc with -c -g -Wa,-adhlns=main.s and checked the listing), the same as I reckon your explicit switch statement would result in.
这似乎有效，并且当使用优化编译时（不确定您是否允许这样做），调用堆栈不会变深 - 当然对于值（参数）n > N，堆栈上有正常的运行时递归，其中 N 是模板实例化中使用的 TableSize。但是，一旦低于 TableSize，生成的代码将替换在编译时计算的常量，或者最坏的情况是通过跳过跳转表（在 gcc 中使用 -c -g -Wa,-adhlns=main.c 编译）“计算”的值。 s 并检查了列表），就像我认为您的显式 switch 语句会导致的结果一样。
When used like this:
像这样使用时：
int main()
{
std::cout << "F" << 39 << " is " << Fibonacci<40>::get_value(39) << '\n';
std::cout << "F" << 45 << " is " << Fibonacci<40>::get_value(45) << '\n';
}
There is no call to a computation at all in the first case (value computed at compile time), and in the second case the call stack depth is at worst:
在第一种情况下根本没有调用计算（在编译时计算的值），在第二种情况下调用堆栈深度最差：
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=41) Line 18 + 0xe bytes C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=42) Line 18 + 0x2c bytes C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=43) Line 18 + 0x2c bytes C++
fibtest.exe!Fibonacci<40>::get_value(unsigned long n=45) Line 18 + 0xe bytes C++
fibtest.exe!main() Line 9 + 0x7 bytes C++
fibtest.exe!__tmainCRTStartup() Line 597 + 0x17 bytes C
I.e. it recurses until it finds a value in the "Table". (verified by stepping through Disassembly in the debugger line by line, also by replacing the test ints by a random number <= 45)
即它递归直到它在“表”中找到一个值。（通过逐行在调试器中逐行执行反汇编来验证，也通过用随机数替换测试整数 <= 45）
The recursive part could also be replaced by the linear iterative solution:
递归部分也可以用线性迭代解决方案代替：
static unsigned long long get_value(unsigned long n)
{
switch (n) {
case N:
return value;
default:
if (n < N) {
return Fibonacci<N-1>::get_value(n);
} else {
// n > N
unsigned long long i = Fibonacci<N-1>::value, j = value, t;
for (unsigned long k = N; k < n; k++) {
t = i + j;
i = j;
j = t;
}
return j;
}
}
}
回答by sigidagi
If you have C++ compiler which supports variadic templates (C++0x standard ) you can save fibonacii sequence in a tuple at the compile time. At runtime you can access any element from that tuple by indexing.
如果您有支持可变参数模板（C++0x 标准）的 C++ 编译器，您可以在编译时将 fibonacii 序列保存在一个元组中。在运行时，您可以通过索引访问该元组中的任何元素。
#include <tuple>
#include <iostream>
template<int N>
struct Fib
{
enum { value = Fib<N-1>::value + Fib<N-2>::value };
};
template<>
struct Fib<1>
{
enum { value = 1 };
};
template<>
struct Fib<0>
{
enum { value = 0 };
};
// ----------------------
template<int N, typename Tuple, typename ... Types>
struct make_fibtuple_impl;
template<int N, typename ... Types>
struct make_fibtuple_impl<N, std::tuple<Types...> >
{
typedef typename make_fibtuple_impl<N-1, std::tuple<Fib<N>, Types... > >::type type;
};
template<typename ... Types>
struct make_fibtuple_impl<0, std::tuple<Types...> >
{
typedef std::tuple<Fib<0>, Types... > type;
};
template<int N>
struct make_fibtuple : make_fibtuple_impl<N, std::tuple<> >
{};
int main()
{
auto tup = typename make_fibtuple<25>::type();
std::cout << std::get<20>(tup).value;
std::cout << std::endl;
return 0;
}
回答by Jarod42
With C++11: you may create a std::arrayand a simple getter: https://ideone.com/F0b4D3
使用 C++11：您可以创建std::array一个简单的 getter：https: //ideone.com/F0b4D3
namespace detail
{
template <std::size_t N>
struct Fibo :
std::integral_constant<size_t, Fibo<N - 1>::value + Fibo<N - 2>::value>
{
static_assert(Fibo<N - 1>::value + Fibo<N - 2>::value >= Fibo<N - 1>::value,
"overflow");
};
template <> struct Fibo<0u> : std::integral_constant<size_t, 0u> {};
template <> struct Fibo<1u> : std::integral_constant<size_t, 1u> {};
template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
return const_cast<const std::array<std::size_t, sizeof...(Is)>&&>(
std::array<std::size_t, sizeof...(Is)>{{Fibo<Is>::value...}})[n];
}
template <std::size_t N>
constexpr std::size_t fibo(std::size_t n)
{
return n < N ?
fibo(n, make_index_sequence<N>()) :
throw std::runtime_error("out of bound");
}
} // namespace detail
constexpr std::size_t fibo(std::size_t n)
{
// 48u is the highest
return detail::fibo<48u>(n);
}
In C++14, you can simplify some function:
在 C++14 中，你可以简化一些函数：
template <std::size_t ... Is>
constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>)
{
constexpr std::array<std::size_t, sizeof...(Is)> fibos{{Fibo<Is>::value...}};
return fibos[n];
}
回答by jmihalicza
You can generate the switch or a static array using preprocessor metaprogramming techniques. It is a good decision if the complexity does not exceed the limitations of that approach, and you prefer not extending your toolchain with extra steps that generate code or data.
您可以使用预处理器元编程技术生成开关或静态数组。如果复杂性不超过该方法的限制，并且您不希望使用生成代码或数据的额外步骤来扩展您的工具链，那么这是一个很好的决定。
回答by James Caccese
One of the basic tennants of C (and for the most part C++) is that you don't pay for what you don't need.
C（大多数情况下是 C++）的基本特征之一是您无需为不需要的东西付费。
The automatic generation of look-up tables is just not something that the compiler needs to do for you. Even if you need that functionality, not everyone else necessarly does.
查找表的自动生成并不是编译器需要为您做的事情。即使您需要该功能，也并非所有人都需要。
If you want a lookup table, write a program to make one. Then use that data in your program.
如果您想要一个查找表，请编写一个程序来制作一个。然后在您的程序中使用该数据。
Don't use a template metaprogram if you want values to be calculated at runtime, just use a regular program to calculate values.
如果您希望在运行时计算值，请不要使用模板元程序，只需使用常规程序来计算值。
回答by Jean-Baptiste Yunès
This should do the trick...
这应该可以解决问题...
template <int N> class EXPAND {
public:
static const string value;
};
template <> class EXPAND<0> {
public:
static const string value;
};
template <int N> const string EXPAND<N>::value = EXPAND<N-1>::value+"t";
const string EXPAND<0>::value = "t";
int main() {
cout << EXPAND<5>::value << endl;
}
