1.1 STL的理念
那么什么是STL呢？到目前为止，它作为标准 C ++的一部分已经快十年了，因此你的确应该知道它，但是如果你不熟悉现代的C++，那么我就有必要对它的想法和语言使用方式作一些简单的介绍。
我们来考虑一个问题：把对象存储在容器中，并编写算法来操作这些对象。我们按照直接、独立和概念的混合表现方式来考虑这个问题。自然地，我们希望能够在多种容器（例如列表、向量、映射）中存储多种类型（例如整型、Point、Shape）的对象，并在容器中的对象上 应用 大量的算法（例如排序、检索、积聚）。此外，我们希望使用的这些对象、容器和算法都是静态类型安全的、尽可能地快速、尽可能地简洁、不冗长、易于阅读。同时实现这些目标并不容易。实际上，为了解决这个难题，我差不多花费了十年还是没有找到成功的方法。
STL解决方案是以带元素类型的参数化容器以及与容器完全分离的算法为基础的。容器的每种类型都提供一种迭代子（iterator）类型，只使用这些迭代子就可以实现对容器中所有元素的访问。通过这种方式，我们可以编写算法来使用迭代子而不用知道提供迭代子的容器的信息。每种迭代子类型与其它类型都是完全独立的，除非要为必要的操作（例如*和++）提供了相同语义（semantics）。我们可以用图形来说明。
我们来看一个很恰当的例子，它在不同的容器中查找不同类型的元素。首先，下面是两个容器：
| vector<int> vi; // 整型向量 list<double> vd; // 双精度型列表 |
目前存在一些向量和列表概念的标准类库，它们是作为模板实现的。假如你已经用相应的元素类型值恰当地初始化过它们，那么在vi中查找第一个值为7的元素和在vd中查找第一个值为3.14的元素的语法如下：
| vector<int>::iterator p = find(vi.begin(),vi.end(),7); list<double>::iterator q = find(vd.begin(),vd.end(),3.14); |
其基本的想法是，你能够把任何容器的（所有）元素都作为一个元素序列（sequence）。容器"知道"第一个元素在哪儿，最后一个元素在哪儿。我们把指向一个元素的对象称为"迭代子"。接着我们就可以使用一对迭代子（begin()和end()）来表示容器中的元素，其中begin()指向第一个元素，end()指向最后一个元素前面。
end()迭代子指向最后一个元素后面，而不是指向最后一个元素，这就使空序列不会成为一种特殊情况。
你能对迭代子做什么样的操作？你可以得到迭代子指向的元素的值（像指针一样使用*），可以使迭代子指向下一个元素（像指针一样使用++），可以比较两个迭代子，看它们是否指向同一个元素（使用==或!=）。令人惊讶的是，这已经足以实现find()（查找功能）了：
| template<class Iter, class T> Iter find(Iter first, Iter last, const T& val) { while (first!=last && *first!=val) ++first; return first; } |
这是一个简单的--真的非常简单的--模板函数。熟悉C和C++指针的人应该发现这些代码很容易阅读的：first!=last检查我们是否到了序列末尾，*first!=val检查我们是否找到了值val。如果没有找到，我们增加first迭代子，使它指向下一个元素并重复。因此，当find()返回的时候，它的值要么指向值为val的第一个元素，要么指向最后一个元素后面（end()）。于是我们可以编写下面的代码：
| vector<int>::iterator p = find(vi.begin(),vi.end(),7); if (p != vi.end()) { // 我们找到了 7 // … } else { // vi 中没有 7 // … } |
这是非常非常简单的。它简单得像数学书的前面几页，速度也很快。但是，我知道自己不是唯一一个花时间来研究它到底是如何实现的、以及为什么它是一个好的想法的人。与简单的数学相似，最初的STL规则和原理的概括也是难以置信的。
考虑第一个实现：在调用find(vi.begin(),vi.end(),7)中，迭代子vi.begin()和vi.end()会相应地成first为last，在find()内部有些东西指向int（整型）、int*。在这样的实现中，*成为了指针，++成为了指针增加操作符，!=成为了指针比较操作符。也就是说，find()的实现是明显的、理想的。特别地，我们没有使用函数调用来访问那些作为运算法则的有效参数的操作符（例如*和!=），因为它们依赖于模板参数。在这种情况中，模板与"泛型"的大多数机制从根本上都是不同的，它依赖于当前编程语言中的间接函数调用（类似虚拟函数）。如果有一个好的优化程序（optimizer），vector<int>::iterator可以成为一个把*和++作为内建函数（inline function）的、没有资源花费（overhead）的类。这种优化程序现在很少，它通过捕捉无保证的假设（如下所示）来进行类改善类型检查。
| int* p = find(vi.begin(),vi.end(),7); // 迭代子类型不能是 int* |
那么为什么我们不省去所有的"迭代子材料"和使用指针呢？其中一个原因是vector<int>::iterator可能已经成为了一个提供了范围检查访问的类。我们看看find()的其它调用：
| list<double>::iterator q= find(vd.begin(),vd.end(),3.14); if (q != vd.end()) { // 我们找到了3.14 // … } else { // vi 中没有3.14 // … } |
此处list<double>::iterator不会成为double*。实际上，在最普通的链表实现方式中，应该是Link*类型的，其中是链表节点类型的，例如：
| template<class T> struct Link { T value; Link* suc; Link* pre; }; |
这意味着，*的意思是p->value（返回值字段），++的意思是p->suc（使指针指向下一个链接），!=指针比较的意思是（比较Link*s）。同样，这种实现也是明显的、理想的。但是，它与我们前面看到的vector<int>::iterator完全不同了。
我们使用了模板组合（combination）和重载解决方案为find()的单一 源代码 定义和使用来挑选根本不同的、也是理想的代码。请注意，这儿不存在运行时分派（dispatch）、没有虚拟函数调用。实际上，它只有琐碎的内联函数和指针的基本操作（例如*和++）的调用。在速度和代码大小方面，我们都到取得了很大的成功。
为什么没有把"序列"或"容器"作为基本的概念，而使用了"一对迭代子"呢？部分原因在于"一对迭代子"只不过比"容器"的概念更普通。例如，给定迭代子，我们可以只对容器的前一半进行排序：sort(vi.begin(), vi.begin()+vi.size()/2)。另一个原因是STL遵循了 C ++的设计原则，我们必须一律地提供转换（transition）路径、支持内建的和用户定义类型。如果某个人把数据保存在普通的数组中会怎么样呢？我们仍然可以使用STL算法。例如：
| char buf[max]; // … 填充buf … int* p = find(buf,buf+max,7); if (p != buf+max) { // 我们找到了 7 // … } else { // buf 中没有 7 // … } |
此处，find()中的*、++和!=都是指针操作符！与C++本身不同，STL与一些旧的概念（例如C数组）是兼容的。我们始终提供转换路径，平等地对待用户定义类型和内建类型（如数组）。
STL像ISO C++标准库所采用的容器和算法框架一样，包含一打容器（例如vector、list和 map ）和数据结构（例如数组），它们可以被当作序列使用。此外，还有大约60种算法（例如find、sort、accumulate和merge）。你可以查阅资料看到更详细的信息。
STL的优雅和性能的关键在于--与C++本身类似--它是基于直接的 内存 和计算硬件模型的。STL的序列的概念基本上是把内存作为一组对象序列的硬件视点。STL的基本语法直接映射到硬件指令，允许算法最佳地实现。接下来，模板的编译时解析和他们支持的完美内联成为了把STL高级表达式高效率地映射到硬件层的关键因素。
1.2 函数对象
我将介绍STL使用的一些基本的技术，它会让你了解：在普通C++机制上建立的STL是如何提供空前的灵活性和性能的。迄今为止，我们所描述的STL框架组件都有些严格。每种算法都严格地采用标准指定的方法来准确地实现某种功能。例如，我们需要查找一个与自己指定的值相等的元素。实际上，查找一个带有某些（自己指定的）属性的元素，例如小于某个给定的值、匹配某个并非简单相等的值（例如，匹配大小写无关的字符串或者在允许很小差别的情况下，匹配双精度数值），是一项很普通的事务。
下面的例子不是查找值7，我们将查找某些符合条件的值（也就是小于7的值）：
| vector<int>::iterator p = find_if(v.begin(),v.end(),Less_than<int>(7)); if (p != vi.end()) { // 我们找到了值小于7 的元素 // … } else { // vi 没有值小于 7 的元素 // … } |
Less_than<int>(7)是什么东西呢？它是一个函数对象，它是某个类的对象，该类带有 应用 程序操作符（( )），被定义成执行某个函数：
| template<class T> struct Less_than { T value; Less_than(const T& v) :value(v) { } bool operator()(const T& v) const { return v<value; } }; |
例如：
| Less_than<double> f(3.14); // Less_than 保存了双精度值 3.14 bool b1 = f(3); // b1 为真（3<3.14 是真的） bool b2 = f(4); // b2 为假（4<3.14 是假的） |
从2004年的情况来看，在D&E中没有提到函数对象是很奇怪的。我们应该使用一个章节来讲述它们。甚至于用户自定义的应用程序操作符（( )）的使用情况也没有提到，尽管它已经存在很长时间，并且很卓著。例如，它是几个最初的允许重载的操作符之一（在=之后），它还用于模仿Fortran下标（subscript notation）。
我们可以编写一个find()版本，它使用了函数对象，而不是简单的!=来检测是否可以找到某个元素。它的名字是find_if()：
| template<class In, class Pred> In find_if(In first, In last, Pred pred) { while (first!=last && !pred(*first)) ++first; return first; } |
我们简单地用!pred(*first)代替了*first!=val。函数模板find_if()会接受任何能够把元素值作为参数调用的对象。特别地，我们可以把普通的函数作为它的第三个参数来调用find_if()：
| bool less_than_7(int a) { return 7<a; } vector<int>::iterator p = find_if(v.begin(),v.end(),less_than_7); |
但是，这个例子显示了，与函数相比我们为什么更喜欢函数对象：我们可以使用一个（或多个）参数来初始化函数对象，同时函数对象可以保持这些信息供以后使用。函数对象可以保持任何状态。这样就可以形成更 通用 、更优良的代码。如果我们需要，我们以后可以检查它的状态。例如：
| template<class T> struct Accumulator { // 保持 n 个值的总和 T value; int count; Accumulator() :value(), count(0) { } Accumulator(const T& v) :value(v), count(0) { } void operator()(const T& v) { ++count; value+=v; } }; |
我们可以把Accumulator对象传递给一个重复调用它的算法。其部分结果保持在对象中。例如：
| int main() { vector<double> v; double d; while (cin>>d) v.push_back(d); Accumulator<double> ad; ad = for_each(v.begin(),v.end(), ad); cout << "sum==" << ad.value << ", mean==" << ad.value/ad.count << '\n'; } |
标准类库算法for_each简单地把它的第三个参数应用在自己序列中的每个元素上，并把这个参数作为返回值。另一种使用函数对象的方法比较"杂乱"--就是使用全局变量来保持value和count。
有趣的是，简单的函数对象比功能相同的函数的性能更好。其原因在于它们趋向于按值（by value）传递，因此它们更易于内联（inline）。当我们传递那些执行很简单操作（例如用于排序的比较条件）的对象或函数的时候，这一点是非常重要的。特别地，当对简单类型（例如整型或双精度型）的数组进行排序的时候，函数对象的内联就是STL（C++标准类库）的sort()在多方面超越了传统的qsort()原因。
函数对象是用于更高级构造的一种C++机制。它并非高级理念的最好表达方式，但是它在用于普通目的的语言环境中，显示出令人惊讶的表现能力和固有的高性能。作为表现能力的一个例子，Jaakko J?rvi演示了如何提供和使用一个Lambda类，使它的真正意义合法化：
| Lambda x; List<int>::iterator p = find_if(lst.begin(),lst.end(),x<=7); |
如果你希望 <= 能够工作，那么不用建立一个通用类库，而是为Lambda和<=添加大约十余行代码定义。如果使用上面例子中的Less_than，那么我们可以简单地添加：
| class Lambda {}; template<class T> Less_than<T> operator<=(Lambda,const T& v) { return Less_than<T>(v); } |
因此，find_if调用中的x<=7参数变成了operator<=(Lambda,const int&)调用，它会生成一个Less_than<int>对象，它就是这一部分中第一个例子所使用的对象。它们之间的差别仅仅是--我们实现了更简单和直观的语法。这是C++表现能力的一个很好的例子，也是类库的接口如何比其实现更加简单的例子。自然地，与辛苦地编写一个循环来查找值小于7的元素相比，它是没有运行时开销的。
1.3 STL的影响
STL对C++的思想的影响是极大的。在STL之前，我一般列举C++支持的三种基本的编程样式（"范例"）：
－面向过程编程
－数据抽象
－面向对象编程
我认为模板是对数据抽象的支持。在试用了STL一段时间之后，我提出第四种样式：
－泛型编程
以使用模板为基础的技术，以及从功能性编程中获取大量灵感的技术与传统的数据抽象有本质的不同。人们只是认为类型、对象和资源不同。新的C++类库是使用模板技术编写的，才获得了静态类型安全和高效率。模板技术对于嵌入式系统编程和高性能数学运算也是很关键的，在这些环境中，资源的管理和正确性是关键。在这些领域中STL并非总是理想的。例如，它没有直接地支持线性代数，而且在紧凑的实时系统中（在这种环境下一般会禁止自由地使用存储）也很难使用它。但是，STL证明了在模板的帮助下可以实现什么样的功能，并提出了一些有效的技术示例。例如，利用迭代子（和 分配器 ）把逻辑 内存 访问与实际内存访问分离开来，对于很多高性能数字运算就是很关键的；使用小型的、简单的内联、对象对于嵌入式系统编程中最佳地使用硬件也是很关键的。这类技术有一些记载在标准委员会关于性能的技术报告中了。这是对当前过度地使用过分依赖于类层次和虚拟函数的"面向对象"技术的这种趋势的一种大范围的反击--也是一种有建设意义的替代方案。
很明显，STL并不完美。相对来说没有完美的东西。但是，它开辟了新天地，而且它拥有的影响力甚至于超过了巨大的C++群体。使用C++时，当人们试图推动STL所倡导的技术来超越STL技术的时候，它们讨论"模板元数据编程"。我们中有些人也会考虑STL迭代子的限制（使用generator和range是不是更好？），以及C++如何更好地支持这些使用（概念、初始化器）。
上一页 1 2