C++ 使用模板元编程计算阶乘

calculating factorial using template meta-programming

提问by Lazer

I do not understand how this piece of code (from Wikipedia)works:

我不明白这段代码（来自维基百科）是如何工作的：

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

template <>
struct Factorial<0> 
{
    enum { value = 1 };
};

// Factorial<4>::value == 24
// Factorial<0>::value == 1
void foo()
{
    int x = Factorial<4>::value; // == 24
    int y = Factorial<0>::value; // == 1
}

• What is this weird template that takes <int N>?
• What is this second weird template <>?
• What are the enumerations for?
• What is the advantage of using this rather than normal runtime factorial calculation?
• How often do you people use this? I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

• 这个奇怪的模板是<int N>什么？
• 第二个奇怪的模板是<>什么？
• 有什么 enum用？
• 使用这个而不是正常的运行时阶乘计算有什么好处？
• 你们多久使用一次这个？我已经使用 C++ 一段时间了，但以前从未使用过它。我错过了 C++ 的多大一部分？

Thanks!

谢谢！

回答by Beno?t

• What is this weird template that takes <int N>?

• 这个奇怪的模板是<int N>什么？

In C++, template arguments can either be types (prefixed with classor typename) or integers (prefixed with intor unsigned int). Here we are in the second case.

在 C++ 中，模板参数可以是类型（以class或为前缀typename）或整数（以int或为前缀unsigned int）。我们这里是第二种情况。

• What is this second weird template <>?

• 这第二个奇怪的是template <>什么？

template<> struct Factorial<0>is a complete specialization of Factorial class template, which means that 0is considered a special value to which corresponds its own version of Factorial.

template<> struct Factorial<0>是 Factorial 类模板的完整特化，这意味着它0被认为是一个特殊值，对应于它自己的 Factorial 版本。

• What are the enums for?

• 枚举有什么用？

enums are the way to compute values in metaprogramming C++

枚举是在元编程 C++ 中计算值的方法

• What is the advantage of using this rather than normal runtime factorial calculation?

• 使用这个而不是正常的运行时阶乘计算有什么好处？

The reason why this code was created in the first place is to create a proof of concept that calculus can be done using metaprogramming. The advantage is that generated code is extremely efficient (calling Factorial<4>::valueis equivalent to simply writing "24" in your code.

之所以创建此代码，首先是为了创建一个概念证明，即可以使用元编程来完成微积分。优点是生成的代码非常高效（调用Factorial<4>::value相当于在代码中简单地写上“24”。

• How often do you people use this? I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

• 你们多久使用一次这个？我已经使用 C++ 一段时间了，但以前从未使用过它。我错过了 C++ 的多大一部分？

Such functionality is rarely achieved using this method, but metaprogramming is used more and more nowadays. See Boost meta-programming libraryto get a hint of what can be done.

这种功能很少使用这种方法实现，但现在越来越多地使用元编程。请参阅Boost 元编程库以了解可以做什么。

回答by utnapistim

What is this weird template that takes <int N>?

这个奇怪的模板是 <int N>什么？

A template declaration can be made on classes/types, on values and on pointers. You do not usually see this form as defining templates rarely uses constants in the template parameters.

可以在类/类型、值和指针上进行模板声明。您通常不会看到这种形式，因为定义模板很少在模板参数中使用常量。

What is this second weird template <>?

这第二个奇怪的模板 <> 是什么？

The best way to think of a template is to do something similar to what the compiler does: consider the template as a class, where you replace the template parameter with an actual value of that type.

考虑模板的最佳方式是做一些类似于编译器所做的事情：将模板视为一个类，在其中将模板参数替换为该类型的实际值。

That is, for:

也就是说，对于：

template <int N>
struct Factorial 
{
    enum { value = N * Factorial<N - 1>::value };
};

Factorial<2>::valueis equivalent to:

Factorial<2>::value相当于：

// generated by the compiler when Factorial<2>::value is encountered in code:
struct Factorial2 { enum { value = 2 * Factorial1::value }; };
struct Factorial1 { enum { value = 1 * Factorial0::value }; };
// not generated by compiler, as it was explicitly defined in the code you ask about:
template <> struct Factorial<0> { enum { value = 1 }; }; // defines Factorial<0>

What are the enums for?

枚举有什么用？

They define an enumeration with a const valueat compile time, allowing you to write client code like the one in your example.

它们value在编译时定义了一个带有 const 的枚举，允许您编写类似于示例中的客户端代码。

What is the advantage of using this rather than normal runtime factorial calculation?

使用这个而不是正常的运行时阶乘计算有什么好处？

The advantage is efficiency. Since the value calculation is expanded on compilation, the runtime cost of Factorial<10>::valueis the same as Factorial<1>::value. In the compiled code, they are both constants. If you were to calculate a factorial in performance-critical code and you knew at compile time which value it is, you should either do this, or calculate it offline and define a constant with the precalculated value in your code.

优点是效率。由于编译时扩展了值计算，因此其运行时成本Factorial<10>::value与 Factorial<1>::value 相同。在编译后的代码中，它们都是常量。如果您要在性能关键代码中计算阶乘，并且在编译时知道它是哪个值，那么您应该这样做，或者离线计算它并在代码中使用预先计算的值定义一个常量。

How often do you people use this?

你们多久使用一次这个？

Is the "this" you refer to the recursive computation of a constant? If so, not often.

“这个”是指常数的递归计算吗？如果是这样，不经常。

Is the "this" the definition of constants in templates? Very often :)

“this”是模板中常量的定义吗？常常 ：）

Is the "this" the particularization of a template for a specific type? Very Very Very often. I understood that std::vector has a completely separate implementation in some STL implementations (a std::vector<bool>with 8 elements should not need more than 1 byte for storing the values).

“这个”是特定类型的模板的特殊化吗？非常非常非常经常。我知道 std::vector 在某些 STL 实现中有一个完全独立的实现（std::vector<bool>具有 8 个元素的 a 应该不需要超过 1 个字节来存储值）。

I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

我已经使用 C++ 一段时间了，但以前从未使用过它。我错过了 C++ 的多大一部分？

Not necessarily a big part. If you use boost, it is probable that the code you use is implemented using things like this.

不一定是很大一部分。如果您使用 boost，则您使用的代码很可能是使用这样的东西实现的。

回答by Lazer

I found this answerby Johannes Schaub - litbon a different question very helpful.

我发现这个答案由约翰内斯·绍布- litb在不同的问题非常有帮助。

[ I am copy pasting the answer here, assuming Johannes is okay with it. I'll remove the paste if he doesn't like it]

[我在这里复制粘贴答案，假设约翰内斯对此没有意见。如果他不喜欢，我会删除粘贴]

---

---

Yes, it is a non-type parameter. You can have several kinds of template parameters

是的，它是一个非类型参数。你可以有几种模板参数

• Type Parameters.
  • Types
  • Templates (only classes, no functions)
• Non-type Parameters
  • Pointers
  • References
  • Integral constant expressions

• 类型参数。
  • 类型
  • 模板（只有类，没有函数）
• 非类型参数
  • 指针
  • 参考
  • 积分常数表达式

What you have there is of the last kind. It's a compile time constant (so-called constant expression) and is of type integer or enumeration. After looking it up in the standard, i had to move class templates up into the types section - even though templates are not types. But they are called type-parameters for the purpose of describing those kinds nonetheless. You can have pointers (and also member pointers) and references to objects/functions that have external linkage (those that can be linked to from other object files and whose address is unique in the entire program). Examples:

你所拥有的是最后一种。它是一个编译时常量（所谓的常量表达式）并且是整数或枚举类型。在标准中查找之后，我不得不将类模板移到类型部分 - 即使模板不是类型。但是为了描述这些类型，它们被称为类型参数。您可以拥有指针（以及成员指针）和对具有外部链接的对象/函数的引用（可以从其他对象文件链接到并且其地址在整个程序中是唯一的）。例子：

Template type parameter:

模板类型参数：

template<typename T>
struct Container {
    T t;
};

// pass type "long" as argument.
Container<long> test;

Template integer parameter:

模板整数参数：

template<unsigned int S>
struct Vector {
    unsigned char bytes[S];
};

// pass 3 as argument.
Vector<3> test;

Template pointer parameter (passing a pointer to a function)

模板指针参数（传递指向函数的指针）

template<void (*F)()>
struct FunctionWrapper {
    static void call_it() { F(); }
};

// pass address of function do_it as argument.
void do_it() { }
FunctionWrapper<&do_it> test;

Template reference parameter (passing an integer)

模板参考参数（传递一个整数）

template<int &A>
struct SillyExample {
    static void do_it() { A = 10; }
};

// pass flag as argument
int flag;
SillyExample<flag> test;

Template template parameter.

模板模板参数。

template<template<typename T> class AllocatePolicy>
struct Pool {
    void allocate(size_t n) {
        int *p = AllocatePolicy<int>::allocate(n);
    }
};

// pass the template "allocator" as argument. 
template<typename T>
struct allocator { static T * allocate(size_t n) { return 0; } };
Pool<allocator> test;

A template without any parameters is not possible. But a template without any explicit argument is possible - it has default arguments:

没有任何参数的模板是不可能的。但是没有任何显式参数的模板是可能的 - 它具有默认参数：

template<unsigned int SIZE = 3>
struct Vector {
    unsigned char buffer[SIZE];
};

Vector<> test;

Syntactically, template<>is reserved to mark an explicit template specialization, instead of a template without parameters:

在语法上，template<>保留用于标记显式模板特化，而不是没有参数的模板：

template<>
struct Vector<3> {
    // alternative definition for SIZE == 3
};

---

---

回答by jopa

It's recursion performed by the compiler, where

它是由编译器执行的递归，其中

template <>
struct Factorial<0>
{
}

is exit point of the recursion.

是递归的退出点。

At first Factorial<4>is resolved. There is no specialization of Factorialfor the value 4, so the first definition Factorial<>is used. It's value is then calculated with Factorial<3>::value, where the previous step is repeated.

一开始Factorial<4>就解决了。没有专业化Factorial为值4，所以第一个定义Factorial<>被使用。然后用 计算它的值Factorial<3>::value，重复上一步。

This will go on, until N==1, then for N-1, the specialization Factorial<0>comes into play, where the value is set to 1. The recursion stops here and the compiler can go upwards and calculates the remaining values of Factorial<N>.

这将继续，直到 N==1，然后对于 N-1，特化Factorial<0>开始发挥作用，其中值设置为 1。递归到此停止，编译器可以向上并计算 的剩余值Factorial<N>。

回答by Peter

What is the advantage of using this rather than normal runtime factorial calculation?

使用这个而不是正常的运行时阶乘计算有什么好处？

It's faster - theoretically the compiler will expand the set of templates at compile time such that Factorial<n>::valueis simply a single constant. In some vanishingly small number of cases, that might make quite a difference.

它更快 - 理论上编译器将在编译时扩展模板集，使其Factorial<n>::value只是一个常量。在一些极少数情况下，这可能会产生很大的不同。

The down side to it is that it has to be calculated at compile time, so if your nis determined at runtime then you can't use that method.

它的缺点是它必须在编译时计算，所以如果你n是在运行时确定的，那么你不能使用该方法。

How often do you people use this? I have been using C++ for a while now, but never used this before. How big a part of C++ was I missing out on?

你们多久使用一次这个？我已经使用 C++ 一段时间了，但以前从未使用过它。我错过了 C++ 的多大一部分？

A case like that, not often at all. Template metaprogramming is potentially very powerful, but the number of cases where this example is useful and important enough for performance are tiny.

像这样的情况，根本不常见。模板元编程可能非常强大，但是这个示例对性能有用且足够重要的情况很少。

But it is a useful technique in C++ since it allows the language to do a lot of powerful tricks that would otherwise be out of reach. I'd venture that it's much more common to take advantage of template metaprogramming that someone else has done for you - eg. Boost uses it quite heavily and can do some very clever things as a result. It's powerful, but can also obfuscate code if not done well.

但它在 C++ 中是一种有用的技术，因为它允许语言执行许多否则无法实现的强大技巧。我敢说，利用其他人为您完成的模板元编程更为常见 - 例如。Boost 大量使用它，因此可以做一些非常聪明的事情。它很强大，但如果做得不好，也会混淆代码。