65.9K
CodeProject 正在变化。 阅读更多。
Home

C++ 模板元编程入门

moliate
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.92/5 (96投票s)

2003年3月7日

9分钟阅读

viewsIcon

384084

downloadIcon

1552

滥用编译器实现极早期的绑定

背景

不久前，我正在开发一个程序，该程序使用一个大型查找表来进行一些计算。该表的内容取决于我必须调整才能使我的代码获得最佳性能的大量参数。每次更改一个参数，整个表都必须重新计算……

我写了一个函数，可以将表的内容转储到标准输出。这样，我就可以用新的参数设置编译我的程序，将表从屏幕上复制粘贴到我的源代码中，最后重新编译整个项目。我并不介意这样做——前二十次。之后，我认为一定有更好的方法。确实有。引入模板元编程。

什么是模板元编程 (TMP)

模板元编程是一种泛型编程技术，它使用非常早期的绑定。编译器充当解释器或“虚拟计算机”，发出构成最终程序的指令。它可以用于静态配置、自适应程序、优化等等。



在本文中，我打算解释如何使用 C++ 模板类来生成编译时生成的代码。

不同类型的元模板

我区分两种元模板——一种是计算常量值，另一种是生成代码。区别在于第一种永远不应该生成在运行时执行的指令。

计算值的模板

假设您想计算字节中设置的位数。如果您在运行时执行此操作，您的函数可能看起来像这样
int bits_set(unsigned char byte)
{int count = 0;
 for (int i = 0; i < 8; i++)
    if ( (0x1L << i) & byte ) 
        count++;
 
 return count;
}
在字节在编译时已知的情况下，也可以使用 TMP 由编译器完成此操作
template< unsigned char byte > class BITS_SET
{
public:
    enum {
     B0 = (byte & 0x01) ? 1:0,
     B1 = (byte & 0x02) ? 1:0,
     B2 = (byte & 0x04) ? 1:0,
     B3 = (byte & 0x08) ? 1:0,
     B4 = (byte & 0x10) ? 1:0,
     B5 = (byte & 0x20) ? 1:0,
     B6 = (byte & 0x40) ? 1:0,
     B7 = (byte & 0x80) ? 1:0
    };
public:
 enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7};
};

我将 `enum` 用于临时变量和结果，因为它们更容易使用，并且枚举量的类型是 `const int`。另一种方法是使用类中的 `static const int`。

您现在可以在代码中使用 `BITS_SET<15>::RESULT` 并获得常量 `4`。在这种情况下，编译器会将行 `enum{RESULT = B0+B1+B2+B3+B4+B5+B6+B7};` 计算为 `enum{RESULT = 1+1+1+1+0+0+0+0};`，最后计算为 `enum{RESULT = 4};`。

也可以使用循环来计算值。使用 TMP，我们依赖于模板定义中的递归。以下代码是编译时阶乘计算器
template< int i >
class FACTOR{
  public:
      enum {RESULT = i * FACTOR<I-1>::RESULT};
};

class FACTOR< 1 >{
  public:
      enum {RESULT = 1};
};
如果我们例如这样写
int j = FACTOR< 5 >::RESULT;

在我们的代码的某个地方，编译器将生成类似以下汇编代码的行

; int j = FACTOR< 5 >::RESULT;
mov    DWORD PTR _j$[ebp], 120            ; 00000078H - a constant value!

这是如何工作的？当我们实例化 `FACTOR<5>` 时，这个类的定义依赖于 `FACTOR<4>`，它又依赖于 `FACTOR<3>` 等等。编译器需要创建所有这些类，直到达到模板特化 `FACTOR<1>`。这意味着整个递归由编译器完成，而最终程序只包含一个常量。

展开循环/特化函数的模板

模板元程序在由编译器解释时可以生成有用的代码，例如大规模内联算法，其循环被展开。结果通常是应用程序速度的大幅提升。

例如，看一下计算数字 1..1000 之和的以下代码

int sum = 0;
for (int i = 1 ; i <= 1000; i++)
     sum += i;

我们实际上进行了 2000 次加法，而不是 1000 次（因为我们必须为每次循环将 `i` 增加一）。此外，我们还对变量 `i` 执行了 1000 次测试操作。另一种方法是这样编写代码

int sum = 0;
sum += 1;
sum += 2;
...
sum += 1000;

模板元程序展开循环的方式就是这样。现在我们执行正好一千次加法，但这种方法也有代价。代码大小会增加，这意味着理论上我们可能会因增加页错误次数而对性能产生负面影响。但在实践中，代码通常会被多次调用并且已经加载到缓存中。

循环展开

使用递归模板可以轻松定义循环展开，类似于计算值

template< int i >
class LOOP{
  public:
    static inline void EXEC(){
      cout << "A-" << i << " ";
            LOOP< i-1 >::EXEC();
       cout << "B-" << i << " ";
    }
};

class LOOP< 0 >{
  public:
    static inline void EXEC(){
      cout << "A-" << i;
      cout << "\n"; 
       cout << "B-" << i;
    }
};

下面显示了 `LOOP< 8 >::EXEC()` 的输出

A-8 A-7 A-6 A-5 A-4 A-3 A-2 A-1 A-0
B-0 B-1 B-2 B-3 B-4 B-5 B-6 B-7 B-8

同样，需要注意的是，生成的二进制代码中没有循环。循环展开自身以生成类似代码

cout << "A-" << 8 << " ";
cout << "A-" << 7 << " ";
...
cout << "A-" << 0;
cout << "\n"; 
cout << "B-" << 0;
...
cout << "B-" << 7 << " ";
cout << "B-" << 8 << " ";

在类 `LOOP< 0 >` 中可以找到一个不相关但有趣的事情。看看 `LOOP< 0 >::EXEC()` 如何使用 `i`。这个标识符已经声明在模板 `LOOP< int i >` 中，但仍然可以从“特殊情况” `LOOP< 0 >` 中访问。我不知道这是否是标准的 C++ 行为。

除了循环，还可以构造其他语句

IF - 语句

template< bool Condition >
class IF {
public:
    static inline void EXEC(){
    cout << "Statement is true";
    }
};

class IF< false > {
public:
    static inline void EXEC(){
    cout << "Statement is false";
    }
};

 

SWITCH - 语句

template< int _case >
class SWITCH {
public:
    static inline void EXEC(){
        cout << " SWITCH - default ";
    }
};

class SWITCH< 1 > {
    public:
    static inline void EXEC(){
        cout << " SWITCH - 1 ";
    }
};

class SWITCH< 2 > {
    public:
    static inline void EXEC(){
        cout << " SWITCH - 2 ";
    }
};

...

两个类的用法示例

SWITCH< 2 > myTwoSwitch; // store for delayed execution
myTwoSwitch.EXEC();
IF< false >::EXEC();
myTwoSwitch.EXEC();

输出将是：" SWITCH - 2 Statement is false SWITCH - 2 "

使用元元模板

可以为特定类型的操作定义通用模板，例如 if 或 for 语句。我喜欢称之为元元模板，因为操作是在模板本身外部的类中定义的。即使这可能很有用，但在复杂情况下它会使代码非常难以理解。而且，编译器需要几年时间才能充分利用这些类型的构造。目前我更喜欢使用专用模板，但对于简单的情况，元元模板可能很有用。下面给出了最简单的此类构造（if 语句）的示例代码
template< bool Condition, class THEN, class ELSE > struct IF
{
    template< bool Condition > struct selector
    {typedef THEN SELECT_CLASS;}; 
 
    struct selector< false >
    {typedef ELSE SELECT_CLASS;};     

 typedef selector< Condition >::SELECT_CLASS RESULT;
};

用法示例

struct THEN
{
 static int func() 
 {cout << "Inside THEN";
  return 42;
 }
};

struct ELSE
{
 static int func() 
 {cout << "Inside ELSE";
  return 0;
 }
};

int main(int argc, char* argv[])
{
 int result = IF< 4 == sizeof(int), THEN, ELSE >::RESULT::func();
 cout << " - returning: " << result;
}

在 32 位架构上，这将向标准输出打印 "Inside THEN - returning: 42"。请注意，如果 `func()` 没有定义在 `ELSE` 内部，这将是一个简单的编译时断言，在 `4 != sizeof(int)` 时中断编译。

实际示例

随附一个小型类，用于执行通用的 CRC（Cyclic Redundancy Codes - 一组简单的哈希算法）计算。该类使用一组参数，这些参数在标头顶部使用 ` #define ` 定义。我选择 CRC 作为本文示例的主要原因是 CRC 算法通常使用基于一组参数的查找表，这使得示例与我最初的问题有些相似。

该类在编译时生成一个包含 256 个条目的查找表。实现相当直接，我希望源代码中的注释足以解释该类的用法。在某些情况下，我使用了宏，而 TMP 本来可以作为一种解决方案。这样做的原因是可读性，这是选择技术时的一个重要因素。
如果您想进一步了解 CRC 算法，我建议阅读 Ross N. Williams 的《A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS》。我已在示例中包含了该文本的逐字副本。

编译此文件时要记住的一件事是，源代码使用了大量的编译器堆内存。我不得不使用编译器选项 '/Zm400' 来增加内存分配限制。这是 TMP 的一个缺点——它确实将编译器推向了极限。

编码约定

编译器不喜欢被滥用，如上所述。一点也不。它会进行一番挣扎。警告和错误将从模糊不清的 C1001 - INTERNAL COMPILER ERROR 不等。而且你无法像调试运行时程序那样调试元模板程序。

因此，使用定义明确的编码约定对于 TMP 比其他编程技术更重要。下面我给出了一些我发现很有用的规则。

通用建议

由于模板元编程在某种程度上类似于宏，我更倾向于为所有 TMP 类使用大写名称。同时尽量使名称具有描述性。这样做的主要原因是因为公共变量/函数通常具有不具描述性的名称（见下文）。TMP 类是定义操作的类，而不是成员函数/变量。

同时尽量将 TMP 类限制为单个操作。模板元编程本身就足够具挑战性了，无需尝试泛化类以支持多种操作。这通常只会导致代码膨胀。

变量/函数名

我通常更倾向于在 TMP 类中定义以下两种公共操作中的一种或两种：
  • RESULT 用于计算值的模板
  • EXEC() 用于循环展开/函数简化。
通常，一个函数或一个成员变量是模板元程序需要向程序员公开的唯一内容。为所有可能的类为操作类型提供一个单一的名称是有意义的。另一个优点是，您可以查看一个模板类，并立即知道它是一个模板元程序还是一个普通的模板类。

我应该在我的程序中使用 TMP 吗？

模板元编程是一种伟大的技术，当正确使用时。另一方面，它可能会导致代码膨胀和性能下降。下面是一些何时使用 TMP 的经验法则。

当...时使用 TMP

  • 宏不够用。您需要比宏更复杂的东西，并且需要在编译之前展开它。
  • 使用具有预定循环次数的递归函数。在这种情况下，可以避免函数调用和设置堆栈变量的开销，并且运行时将显着减少。
  • 使用可以在编译时展开的循环。例如，MD5 和 SHA1 等哈希算法包含定义良好的块处理循环，可以使用 TMP 展开。
  • 在计算常量值时。如果您在程序中有依赖于其他常量的常量，它们可能是 TMP 的候选。
  • 当程序需要移植到其他平台时。在这种情况下，TMP 可能是宏的替代品。

不要在...时使用 TMP

  • 当宏就够用时。在大多数情况下，宏就足够了。并且宏通常比 TMP 更容易理解。
  • 您想要一个小的可执行文件。模板（尤其 TMP）通常会增加代码大小。
  • 您的程序已经花费了很长时间来编译。TMP 可能会显着增加编译时间。
  • 您处于严格的截止日期。如上所述，编译器在处理模板元程序时将非常不友好。除非您打算进行的更改非常简单，否则您可能希望节省几个小时的痛苦。

致谢和参考

  1. 感谢 Joaquín M López Muñoz 介绍 TMP。
  2. Ross N. Williams 撰写了一篇关于 CRC 算法的出色教程：“A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS”。我已将该文本的逐字副本包含在上面的示例（zip 压缩包？）中。
© . All rights reserved.