STL模板实现机制

《STL模板实现机制》由会员分享，可在线阅读，更多相关《STL模板实现机制（10页珍藏版）》请在装配图网上搜索。

1、C+之父Bjarne谈C+中的STL模板在1994年，我主要关心的是如何使ISO C+标准尽可能地好-同时在它所包含的特性和规范的质量两个方面-并获得多 数人的同意。即使人们不接受某种规范，也不会影响它（规范）的良好性。ISO标准没有强制力，因此有些人认为自己 不值得浪费时间来适应它，除非（群体）社团的压力能够使他们确信该规范的价值。对于一个实现者来说，适应环境是 很重要的额外工作，因此适应环境是一个有意识的决定，并且需要分配一些资源，而这些资源本来可以在其它地方使用。 某些晦涩的语言特性很难在某些编译器中实现。我们可以实现或者购买类库，而且领先的、可靠的实现者（implemented 也有机

2、会用自己的富于想像力的专利特性来锁定用户。因此，我认为要点是：让委员会成员和他们所代表的组织确信 该标准的文档是他们所期望看到的最好的文档。在做了很多工作之后，该委员会获得了成功。1997年10月，在Morristown（New Jersey，USA）会议上，技术 成员的最终投票结果是43-0。在获知这个结果以后，我们进行了庆祝活动！在1998年，ISO成员国以空前的22-0的 投票结果批准了这个标准。为了获取大家的一致同意，委员会做了大量的技术工作，也使用了一些外交策略：在那个时 候，我喜欢说政治问题无法解决；我们必须找到引发该问题的技术问题并解决它。我无法想象仅仅通过投票，因为少 数服从多

3、数才简单解决的问题，同时，由于政治上的讨价还价的问题也危害了我们最好的技术判断-而这个问题（模 板的分开编译）仍然在恶化，需要寻找一个更好的技术方案。在最后投票之前的一年里，委员会的工作是：1. 细节、细节和更多的细节。2. STL3. 模板的分开编译第一个问题非常明显：国际标准必须用大量的篇幅来关注细节信息；实际上，实现（implement）与已有标准的兼 容性是标准的关键目标，同时还是实现之间的工具和应用程序能够迁移的基础。标准是一个712页的文档（加上索引等 内容），它是采用高度技术化的和正式的方式编写的，因此为了理解真正的含义需要很多的细节信息。像以前一样，我 在新语言规范上附加了新版

4、的C+编程语言”，以提供更有帮助意义和面向用户的语言描述。STL 的出现第二个问题，STL （标准模板类库”，它是ISO C+标准类库的容器和算法框架）成为标准的一部分是一个主要的 创新，并且它成为了新的用以思考已经出现的编程技术的出发点。STL基本上革命性地脱离了我们原来思考容器和容器 使用问题的方式。在 Simula 早期，容器（例如列表）曾经是困扰人的：如果，并且只有当某个对象已经（显式或隐式 地）衍生自那些包含编译器所需链接信息的特定的Link或Object 类的时候，它才能被放到容器中。这种容器基本上是 引用Link的容器。这暗示着基本的类型（例如int和double）不能直接地放入

5、容器中，数组类型（它直接支持基本的类 型）必定跟其它的容器不同。此外，如果我们希望把真正的简单类对象（例如complex和Point）放入容器中，那么它 们在时间和空间上就无法达到理想效果。它同时还暗示着这种容器不是静态类型安全的。例如，Circle可以被加入列表 中，但是当它被提取出来的时候，我们只知道它是一个Object,需要使用一个转换（显式类型转换）来恢复其静态类型。Simula 容器和数组关于内建和用户定义类型（只有后来的一些可以放入容器）、关于容器和数组（只有数组能够保 存基本的类型；数组不能保存用户定义类型，只能保存用户定义类型的指针）都有一些奇怪的条款Smalltalk使用了相

6、 同的方法，也有相同的问题，后来的一些语言（例如Java和C#）也是这样的。由于它有明显的效用，而且很多设计者 现在都熟悉它，所以很多C+类库也遵循这种模型。但是，我却发现它是无规律的和低效率的（在时间和空间上），使 用它开发真正通用的类库是不可以接受的。这就是我在1985年没有为C+提供适当的标准类库（这个失误）的根本原 因。当我编写D&E的时候，我知道了一种容器和容器使用的新方法，它是由Alex Stepanov开发的。Alex当时在HP 实验室工作，之前在Bell实验室工作了多年，在那儿他接近了Andrew Koenig，我也在那儿与他讨论过类库设计和模板 机制。他鼓励我进一步研究某些模

7、板机制的泛化和效率，但是很幸运的是，他却没有说服我让模板更类似Ada泛型。如 果他成功了，他就无法设计和实现STL 了！在1993年末，Alex在泛型编程技术方面显示了他最近十年的长期研究的进展，这种技术是基于严格的数学基础的、 目标是成为最通用和最高效的编程技术。他是一个容器和算法的框架。他首先联系了Andrew，Andrew花几天时间研 究这种技术之后，就把它展示给我了。我的第一反映是很迷惑。我发现STL的容器和容器使用方式是多余的，甚至于是 丑陋的。与很多通晓面向对象编程的程序员一样，我认为自己知道容器的样子与STL代码的样子有怎样的不同。但是， 在我建立工具列表（我认为这个列表对于容器

8、来说是很重要的）的几年里，令我惊讶的是，我发现STL除了一个条件之 外，符合其它所有的条件。那个缺少的条件是使用通用基类为所有的衍生类（例如所有的对象或容器）提供服务（例如 永续性）。但是，我不认为这种服务对容器的概念有本质的意义。它让我花了几周时间才感觉到STL比较舒适。在那以后，我担心把一个全新样式的类库介绍给C+群体已经太晚 了。让标准委员会在标准进行过程中这么迟的时候接受新的和革命性的东西的成功几率是非常小的（的确是这样的）。 即使出现最好的情况，标准也会被延迟一年-而C+群体急切需要该标准。同时，委员会本质上是一个保守的团体，而 STL 是革命性的。因此成功的机会是很渺茫的，但是我还

9、是在它上面进行着辛勤的工作。毕竟，由于C+没有足够大的、足够好的标 准库，我的感觉非常糟糕。Andrew Koenig尽了最大的努力来鼓励我，并且Alex Stepanov用他知道的最好的东西来游 说Andy和我。幸运的是，Alex不太了解在委员会中使某种东西成为主流的难度，因此他不太沮丧，并且继续研究技术 方面，继续为Andrew和我讲授。我开始给其他人解释STL背后的想法。1993年10月，在加利福尼亚的San Jose举行的标准委员会会议上，我们邀请了 Alex进行晚间演讲。它叫做C+ 编程的科学，它处理了规则类型的大多数原则-连接构造、赋值和等同。我还介绍了转发迭代子的原则。我没有提起

10、任 何容器的问题，只提到一个算法：查找。这次演讲是活跃的下层社会的大胆创新，而其巨大的乐趣使委员会的态度从 现在让我们作些主要的事情变成了等等，让我们瞧一瞧。这正是我们需要的暂停时间！在后来的四个月中，我们进行试验、争论、游说、讲授、编程和重新设计，这样Alex 才能在1994年三月加利福尼亚的San Diego委员会会议上提供STL的完整说明。1994年末在HP 个会议上，Alex 提出了 C+类库实现，我们在很多细节上达成了一致，但是STL的大小成为了主要的障碍。最后，在Alex的催促下， 我拿起笔，逐字地删除，大约删掉了三分之二的内容。对于每一个工具，我都必须向 Alex 和其他类库专家

11、非常简短地 解释为什么它不能被删掉、为什么它使大多数C+程序员受益。这是个可怕的过程。Alex后来声明说这让他心痛。但是， 这样的删减造就了现在知名的STL，并让它1994年10月在加拿大Waterloo的会议上成为ISO C+标准的一部分-而 原始的和完全的STL都没有达到这个目标。对简化STL的必要修改也把标准延迟了一年以上。回想起来，我认为当时 我们做的事情造成的伤害比预料的要小一些。在对采用STL的可能性的讨论中，我记得一件事情：Beman Dawes冷静地声明自己认为STL对于普通程序员来 说过于复杂了，但是作为试验，他自己实现了 10%，从此他不再认为STL超过了标准的难度。Bem

12、an是委员会中很少 编写应用程序的人。不幸的是，委员会趋向于由建立编译器、类库和工具的人员所控制。在STL方面我信任Alex Stepanov。在STL之前，他花了十年以上的时间，用一些无用的语言（例如Scheme和 Ada）来研究基本的想法和技术。但是，Alex第一个坚持要求其他人一起参与。David Musser和Alex在泛型编程方面 一起工作了约二十年，Meng Lee与他一起在HP工作，帮助他编写最初的STL。Alex和Andrew Koenig之间的电子邮 件讨论也有帮助作用。除了苛刻的试验之外，我的贡献很小。我建议与内存相关的所有信息都集中到一个对象中-就形 成了分配器（allo

13、cator）。我还草拟了 Alex想法的初始需求表，建立表格记录STL算法和类对它们的模板参数的要求。 这些需求表实际上表明这种语言的表达能力不足-这种需求应该成为代码的一部分。1.1 STL 的理念那么什么是STL呢？到目前为止，它作为标准C+的一部分已经快十年了，因此你的确应该知道它，但是如果你 不熟悉现代的C+，那么我就有必要对它的想法和语言使用方式作一些简单的介绍。我们来考虑一个问题：把对象存储在容器中，并编写算法来操作这些对象。我们按照直接、独立和概念的混合表现 方式来考虑这个问题。自然地，我们希望能够在多种容器（例如列表、向量、映射）中存储多种类型（例如整型Point、 Shape

14、）的对象，并在容器中的对象上应用大量的算法（例如排序、检索、积聚）。此外，我们希望使用的这些对象、 容器和算法都是静态类型安全的、尽可能地快速、尽可能地简洁、不冗长、易于阅读。同时实现这些目标并不容易。实 际上，为了解决这个难题，我差不多花费了十年还是没有找到成功的方法。STL解决方案是以带元素类型的参数化容器以及与容器完全分离的算法为基础的。容器的每种类型都提供一种迭代 子（iterator）类型，只使用这些迭代子就可以实现对容器中所有元素的访问。通过这种方式，我们可以编写算法来使用 迭代子而不用知道提供迭代子的容器的信息。每种迭代子类型与其它类型都是完全独立的，除非要为必要的操作（例如 *

15、和+）提供了相同语义（semantics）。我们可以用图形来说明。我们来看一个很恰当的例子，它在不同的容器中查找不同类型的元素。首先，下面是两个容器：vector vi; / 整型向量 list vd; /双精度型列表目前存在一些向量和列表概念的标准类库，它们是作为模板实现的。假如你已经用相应的元素类型值恰当地初始化 过它们，那么在vi中查找第一个值为7的元素和在vd中查找第一个值为3.14的元素的语法如下:vector:iterator p = find(vi.begin(),vi.end(),7);list:iterator q = find(vd.begin(),vd.end(),3.1

16、4);其基本的想法是，你能够把任何容器的(所有)元素都作为一个元素序列(sequence)。容器知道第一个元素在 哪儿,最后一个元素在哪儿。我们把指向一个元素的对象称为迭代子。接着我们就可以使用一对迭代子(begin()和end() 来表示容器中的元素，其中begin()指向第一个元素，end()指向最后一个元素前面。end()迭代子指向最后一个元素后面，而不是指向最后一个元素，这就使空序列不会成为一种特殊情况。你能对迭代子做什么样的操作？你可以得到迭代子指向的元素的值(像指针一样使用*)，可以使迭代子指向下一个 元素(像指针一样使用+)，可以比较两个迭代子，看它们是否指向同一个元素(使用=或

17、!=)。令人惊讶的是，这已 经足以实现find()(查找功能)了：templatevclass 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

18、()返回的时候,它的值要么指向值为val的第一个元素，要么指向最后一个元素后面(end()。 于是我们可以编写下面的代码：vector:iterator p = find(vi.begin(),vi.end(),7);if (p != vi.end() /我们找到了 7/ .else / vi中没有7/ .这是非常非常简单的。它简单得像数学书的前面几页，速度也很快。但是，我知道自己不是唯一一个花时间来研究 它到底是如何实现的、以及为什么它是一个好的想法的人。与简单的数学相似，最初的 STL 规则和原理的概括也是难以 置信的。考虑第一个实现：在调用find(vi.begin(),vi.end()

19、,7)中，迭代子vi.begin()和vi.end()会相应地成first为last， 在find()内部有些东西指向int(整型)、int*。在这样的实现中，*成为了指针，+成为了指针增加操作符，！= 成为了指针比较操作符。也就是说，find()的实现是明显的、理想的。特别地，我们没有使用函数调用来访 问那些作为运算法则的有效参数的操作符(例如*和!=)，因为它们依赖于模板参数。在这种情况中，模板 与泛型的大多数机制从根本上都是不同的，它依赖于当前编程语言中的间接函数调用(类似虚拟函数)。 如果有一个好的优化程序(optimizer), vector:iterator可以成为一个把*和+作为

20、内建函数(inline function)的、没有资源花费(overhead)的类。这种优化程序现在很少，它通过捕捉无保证的假设(如 下所示)来进行类改善类型检查。int* p = find(vi.begin(),vi.end(),7); / 迭代子类型不能是 int*那么为什么我们不省去所有的迭代子材料和使用指针呢？其中一个原因是vector:iterator可能 已经成为了一个提供了范围检查访问的类。我们看看find()的其它调用：list:iterator q= find(vd.begin(),vd.end(),3.14);if (q != vd.end() /我们找到了 3.14els

21、e / vi中没有3.14此处list:iterator不会成为double*。实际上，在最普通的链表实现方式中，应该是Link*类 型的，其中是链表节点类型的，例如：template struct Link T value;Link* suc;Link* pre;；这意味着，*的意思是p-value （返回值字段），+的意思是p-suc （使指针指向下一个链接），！= 指针比较的意思是（比较Link*s）。同样，这种实现也是明显的、理想的。但是，它与我们前面看到的 vector:iterator 完全不同了。我们使用了模板组合（combination）和重载解决方案为find（）的单一源代码

22、定义和使用来挑选根本不 同的、也是理想的代码。请注意，这儿不存在运行时分派（dispatch）、没有虚拟函数调用。实际上，它 只有琐碎的内联函数和指针的基本操作（例如*和+）的调用。在速度和代码大小方面，我们都到取得了很 大的成功。为什么没有把序列或容器作为基本的概念，而使用了一对迭代子呢？部分原因在于一对迭代子 只不过比容器的概念更普通。例如，给定迭代子，我们可以只对容器的前一半进行排序：sort（vi.begin（）, vi.begin（）+vi.size（）/2）。另一个原因是STL遵循了 C+的设计原则，我们必须一律地提供转换（transition） 路径、支持内建的和用户定义类型。如

23、果某个人把数据保存在普通的数组中会怎么样呢？我们仍然可以使 用 STL 算法。例如：char bufmax;填充bufint* p = find（buf,buf+max,7）;if （p != buf+max） /我们找到了 7else / buf中没有7此处，find（）中的*、+和!=都是指针操作符！与C+本身不同，STL与一些旧的概念（例如C数组） 是兼容的。我们始终提供转换路径，平等地对待用户定义类型和内建类型（如数组）。STL像ISO C+标准库所采用的容器和算法框架一样，包含一打容器（例如vector、list和map）和 数据结构（例如数组），它们可以被当作序列使用。此外，还有大

24、约60 种算法（例如 find、 sort、 accumulate 和merge）。你可以查阅资料看到更详细的信息。STL的优雅和性能的关键在于-与C+本身类似-它是基于直接的内存和计算硬件模型的oSTL的序列 的概念基本上是把内存作为一组对象序列的硬件视点。STL的基本语法直接映射到硬件指令，允许算法最 佳地实现。接下来，模板的编译时解析和他们支持的完美内联成为了把STL高级表达式高效率地映射到硬 件层的关键因素。1.2 函数对象我将介绍STL使用的一些基本的技术，它会让你了解：在普通C+机制上建立的STL是如何提供空前的灵活性和 性能的。迄今为止，我们所描述的STL框架组件都有些严格。每种

25、算法都严格地采用标准指定的方法来准确地实现某种 功能。例如，我们需要查找一个与自己指定的值相等的元素。实际上，查找一个带有某些(自己指定的)属性的元素， 例如小于某个给定的值、匹配某个并非简单相等的值(例如，匹配大小写无关的字符串或者在允许很小差别的情况下， 匹配双精度数值)，是一项很普通的事务。下面的例子不是查找值7，我们将查找某些符合条件的值(也就是小于7 的值)：vector:iterator p = find_if(v.begin(),v.end() ,L ess_than(7);if (p != vi.end() /我们找到了值小于7的元素/ .else / vi没有值小于7的元素/

26、 .Less_than(7)是什么东西呢？它是一个函数对象，它是某个类的对象，该类带有应用程序操作符()，被定 义成执行某个函数：templatevclass T struct Less_than T value;Less_than(const T& v) :value(v) bool operator()(const T& v) const return vvvalue; ;例如：Less_than f(3.14); / Less_than 保存了双精度值 3.14bool b1 = f(3); / bl 为真(33.14 是真的)bool b2 = f(4); / b2 为假(4In fi

27、nd_if(In first, In last, Pred pred)while (first!=last & !pred(*first) +first;return first;我们简单地用!pred(*firstH弋替了*first!=val。函数模板find_if()会接受任何能够把元素值作为参数调用的对象。特别 地，我们可以把普通的函数作为它的第三个参数来调用find_if()：bool less_than_7(int a)return 7a;vector:iterator p = findf(v.begin(),v.end(),less_than_7);但是，这个例子显示了，与函数相

28、比我们为什么更喜欢函数对象：我们可以使用一个(或多个)参数来初始化函数 对象，同时函数对象可以保持这些信息供以后使用。函数对象可以保持任何状态。这样就可以形成更通用、更优良的弋 码。如果我们需要，我们以后可以检查它的状态。例如：templatevclass T struct Accumulator / 保持 n 个值的总和T value;int count;Accumulator。:value(), count(O) Accumulator(const T& v) :value(v), count(0) void operator()(const T& v) +count; value+=v;

29、 ;我们可以把Accumulator对象传递给一个重复调用它的算法。其部分结果保持在对象中。例如：int main()vector v;double d;while (cind) v.push_back(d);Accumulator ad;ad = for_each(v.begin(),v.end(), ad);cout sum= ad.value , mean= ad.value/ad.count n;标准类库算法 for_each 简单地把它的第三个参数应用在自己序列中的每个元素上，并把这个参数作为返回值。另一 种使用函数对象的方法比较杂乱就是使用全局变量来保持value和count。有趣

30、的是，简单的函数对象比功能相同的函数的性能更好。其原因在于它们趋向于按值(by value)传递，因此它 们更易于内联(inline)。当我们传递那些执行很简单操作(例如用于排序的比较条件)的对象或函数的时候，这一点是 非常重要的。特别地，当对简单类型(例如整型或双精度型)的数组进行排序的时候，函数对象的内联就是STL (C+ 标准类库)的sort()在多方面超越了传统的qsort()原因。函数对象是用于更高级构造的一种C+机制。它并非高级理念的最好表达方式，但是它在用于普通目的的语言环境中， 显示出令人惊讶的表现能力和固有的高性能。作为表现能力的一个例子，Jaakko J?rvi演示了如何提

31、供和使用一个 Lambda 类，使它的真正意义合法化：Lambda x;List:iterator p = findf(lst.begin(),lst.end(),x=7);如果你希望 =能够工作，那么不用建立一个通用类库，而是为Lambda和 Less_thanoperator=(Lambda,const T& v)return Less_than(v);因此，find_if 调用中的 x=7 参数变成了 operator=(Lambda,const int&)调用，它会生成一个 Less_than对象， 它就是这一部分中第一个例子所使用的对象。它们之间的差别仅仅是-我们实现了更简单和直观的

32、语法。这是C+表现 能力的一个很好的例子，也是类库的接口如何比其实现更加简单的例子。自然地，与辛苦地编写一个循环来查找值小于 7 的元素相比，它是没有运行时开销的。1.3 STL的影响STL对C+的思想的影响是极大的。在STL之前，我一般列举C+支持的三种基本的编程样式(范例)：面向过程编程数据抽象面向对象编程我认为模板是对数据抽象的支持。在试用了 STL 一段时间之后，我提出第四种样式：泛型编程以使用模板为基础的技术，以及从功能性编程中获取大量灵感的技术与传统的数据抽象有本质的不同。人们只是认 为类型、对象和资源不同。新的C+类库是使用模板技术编写的，才获得了静态类型安全和高效率。模板技术对

33、于嵌入 式系统编程和高性能数学运算也是很关键的，在这些环境中，资源的管理和正确性是关键。在这些领域中STL并非总是 理想的。例如，它没有直接地支持线性代数，而且在紧凑的实时系统中(在这种环境下一般会禁止自由地使用存储)也 很难使用它。但是，STL证明了在模板的帮助下可以实现什么样的功能，并提出了一些有效的技术示例。例如，利用迭 代子(和分配器)把逻辑内存访问与实际内存访问分离开来，对于很多高性能数字运算就是很关键的；使用小型的、简 单的内联、对象对于嵌入式系统编程中最佳地使用硬件也是很关键的。这类技术有一些记载在标准委员会关于性能的技 术报告中了。这是对当前过度地使用过分依赖于类层次和虚拟函数的面向对象技术的这种趋势的一种大范围的反击- 也是一种有建设意义的替代方案。很明显，STL并不完美。相对来说没有完美的东西。但是，它开辟了新天地，而且它拥有的影响力甚至于超过了巨 大的C+群体。使用C+时，当人们试图推动STL所倡导的技术来超越STL技术的时候，它们讨论模板元数据编程。 我们中有些人也会考虑STL迭代子的限制（使用generator和range是不是更好？），以及C+如何更好地支持这些使 用（概念、初始化器）。