一套“足够通用”的表达式模板

• 下载演示项目 - 6.02 Kb
• 下载源代码 - 3.69 Kb

引言

本文——以及随附的源代码——介绍了一个用于计算 C++ 复合类型的通用算术和逻辑表达式的小型 C++ 模板库。该代码实现了在 [Velhuizen] 和 [AngelicaLanger] 中描述的“表达式模板”范例。

除了加、减、乘、除等常规算术运算，以及非、与、或等逻辑运算外，该库还提供了一组小型三角函数、指数和对数函数，主要用于展示如何扩展以适应更复杂的数学结构。

[Velhuizen] 和 [AngelicaLanger] 提供了在编译时递归求值表达式的指南。然而，这些指南只能用于具有特定算术类型的表达式（例如，double），因此缺乏任何模板库所需的通用性。从附带的示例项目和参考文献中提供的源代码可以看出，泛化步骤并不明显。

背景

模板远远超出了“类的参数化对其包含类型”的范畴。这在 C++ 社区中已是常识。我认为，模板之所以成为一种出色的编程工具，是因为它们提供了一个标准接口，用于执行自定义编译，或者更有趣的是，用于指示 C++ 编译器从源代码内部执行某些计算。

就表达式而言，众所周知，编译器通过生成临时变量来计算它们，临时变量的数量根据被解析表达式的复杂性而变化。临时变量代表了在求值过程中创建的表达式树中的内部（非终结符）节点。例如，假设有一个带有重载的 + 和 * 运算符的矩阵类。表达式的求值

A = d*(B + C)

(E1)

对于从左到右的解析，兼容的 A、B 和 C 矩阵对象，以及标量变量 d，将隐式生成两个临时变量

temporary1 = B + C
temporary2 = d*temporary1
A = temporary2

如果 B 和 C 的维度很大，由于大内存块的分配、解除分配和复制，(E1) 的求值性能将大大降低。

理想情况下，人们期望 (E1) 和任何一般表达式，无论多复杂，都会被编译器替换为以下片段

Matrix<double> A, B, C;
double d;
...
for(Matrix<double>::iterator it = A.begin(); it != A.end(); it++)
    A[i] = d*(B[i] + C[i]);

这正是通过表达式模板和涉及表达式的算术运算的适当内联来实现的。

我们可以进一步扩展上述示例，生成任何解析运算。例如，对一个包含 100 个元素的向量使用表达式模板

vector<float> v(100, 1);
for(vector<float>::size_type i = 0; i < v.size(); i++) v[i] = 2*M_PI*i/100;

语句

Sin(v);

(E2)

在编译时被替换为

for(vector<float>::size_type i = 0; i < v.size(); i++) v[i] = sin(v[i]);

以及一个复杂的语句，例如

vector<float> u = Sin(v) + 2*w + z;

(E3)

by

for(size_t i = 0; i < v.size(); i++) v[i] = sin(v[i]) + 2.f*w[i] + z[i];

Boost 库的 lambda-calculus 包实现了相同的编程范例。在那里，目的是能够编写如下语句

vector<float> v, u, w;
...
boost::for_each(IteratorFirst, IteratorLast, v = 2.f*u + w/2.f);

再次消除了临时变量。

使用代码

代码使用非常简单，正如我在测试库时创建的 .cpp 文件所示。以下几点值得注意

CPP 文件在 std::vector 模板的派生类上使用了该库。派生非常简单，正如 Vector.h 头文件中所示。最终，它只添加了一个公共属性，一个指向容器开头的表达式对象，并提供了一个新的赋值运算符和一个 Find 方法，分别返回算术和逻辑运算的结果。逻辑运算始终返回一个 vector<size_t> 对象，其中包含满足逻辑运算的向量元素的索引。

算术和逻辑运算是使用 Vector 类的属性 e（类型为 E<I<iterator> >）执行的。该属性被简单地赋值为基类 vector<...> 的 begin() 返回值。我故意选择这样做是为了清晰起见。然后，E2，例如，必须这样写：

Sin(v.e);

(E4)

通过重写 Sin 以接受 Vector 类型作为参数并在内部构造表达式对象，可以非常容易地实现将 E4 编写为 E2。测试项目中的以下片段定义了两个包含 100 个元素的向量。这些值被视为代表弧度角，等于圆周的 1/100。

// Define vectors with 100 elements each and initial value 0 
DoubleVector v1(100, 0), v2(100, 0); 

// assign angle values to 
v1 for(size_t i = 0; i < v1.size(); i++) v1[i] = 2*M_PI*i/100; 

// Arbitrary arithmetic computations on v1 and v2 
v1 = Sin(v1.e) + Cos(v1.e);
v2 = 1. + Exp(-v1.e) + v1.e/2.;

逻辑运算返回一个 std::vector<size_t>，其中包含满足表达式的向量元素的索引。例如：

vector<size_t> idxs = v2.Find(v1.e > 0.);

库

"Expressions.h" 头文件中包含的模板的核心是 I 和 It 标识模板——表示表达式树中的终结符节点，BE 和 UE 模板——表示表达式树中的非终结符二元和一元运算，以及 E 模板，它在面向对象术语中充当基类。

表达式对象实际表示的类型由所有类中存在的 Traits typedef 解析。表达式求值递归步骤由 EvaluatesTo 和 Satisfies 方法实现，这些方法在 I、It、BE 和 UE 模板的派生类中定义。

最后但同样重要的是：请注意，复合 Vector 模板的元素的迭代求值是通过赋值运算符完成的。整个模板库的唯一作用是内联解析正在求值的表达式。