STL模板实现机制.doc

C+之父Bjarne谈C+中的STL模板在1994年，我主要关心的是如何使ISO C+标准尽可能地好-同时在它所包含的特性和规范的质量两个方面-并获得多数人的同意。即使人们不接受某种规范，也不会影响它（规范）的良好性。ISO标准没有强制力，因此有些人认为自己不值得浪费时间来适应它，除非（群体）社团的压力能够使他们确信该规范的价值。对于一个实现者来说，适应环境是很重要的额外工作，因此适应环境是一个有意识的决定，并且需要分配一些资源，而这些资源本来可以在其它地方使用。某些晦涩的语言特性很难在某些编译器中实现。我们可以实现或者购买类库，而且领先的、可靠的实现者（implementer）也有机会用自己的富于想像力的专利特性来锁定用户。因此，我认为要点是：让委员会成员和他们所代表的组织确信该标准的文档是他们所期望看到的最好的文档。在做了很多工作之后，该委员会获得了成功。1997年10月，在Morristown（New Jersey，USA）会议上，技术成员的最终投票结果是43-0。在获知这个结果以后，我们进行了庆祝活动！在1998年，ISO成员国以空前的22-0的投票结果批准了这个标准。为了获取大家的一致同意，委员会做了大量的技术工作，也使用了一些外交策略：在那个时候，我喜欢说政治问题无法解决；我们必须找到引发该问题的技术问题并解决它。我无法想象仅仅通过投票，因为少数服从多数才简单解决的问题，同时，由于政治上的讨价还价的问题也危害了我们最好的技术判断-而这个问题（模板的分开编译）仍然在恶化，需要寻找一个更好的技术方案。在最后投票之前的一年里，委员会的工作是：1. 细节、细节和更多的细节。2. STL3. 模板的分开编译第一个问题非常明显：国际标准必须用大量的篇幅来关注细节信息；实际上，实现（implement）与已有标准的兼容性是标准的关键目标，同时还是实现之间的工具和应用程序能够迁移的基础。标准是一个712页的文档（加上索引等内容），它是采用高度技术化的和正式的方式编写的，因此为了理解真正的含义需要很多的细节信息。像以前一样，我在新语言规范上附加了新版的C+编程语言，以提供更有帮助意义和面向用户的语言描述。STL的出现第二个问题，STL（标准模板类库，它是ISO C+标准类库的容器和算法框架）成为标准的一部分是一个主要的创新，并且它成为了新的用以思考已经出现的编程技术的出发点。STL基本上革命性地脱离了我们原来思考容器和容器使用问题的方式。在Simula早期，容器（例如列表）曾经是困扰人的：如果，并且只有当某个对象已经（显式或隐式地）衍生自那些包含编译器所需链接信息的特定的Link或Object类的时候，它才能被放到容器中。这种容器基本上是引用Link的容器。这暗示着基本的类型（例如int和double）不能直接地放入容器中，数组类型（它直接支持基本的类型）必定跟其它的容器不同。此外，如果我们希望把真正的简单类对象（例如complex和Point）放入容器中，那么它们在时间和空间上就无法达到理想效果。它同时还暗示着这种容器不是静态类型安全的。例如，Circle可以被加入列表中，但是当它被提取出来的时候，我们只知道它是一个Object，需要使用一个转换（显式类型转换）来恢复其静态类型。 Simula容器和数组关于内建和用户定义类型（只有后来的一些可以放入容器）、关于容器和数组（只有数组能够保存基本的类型；数组不能保存用户定义类型，只能保存用户定义类型的指针）都有一些奇怪的条款。Smalltalk使用了相同的方法，也有相同的问题，后来的一些语言（例如Java和C#）也是这样的。由于它有明显的效用，而且很多设计者现在都熟悉它，所以很多C+类库也遵循这种模型。但是，我却发现它是无规律的和低效率的（在时间和空间上），使用它开发真正通用的类库是不可以接受的。这就是我在1985年没有为C+提供适当的标准类库（这个失误）的根本原因。 当我编写D&E的时候，我知道了一种容器和容器使用的新方法，它是由Alex Stepanov开发的。Alex当时在HP实验室工作，之前在Bell实验室工作了多年，在那儿他接近了Andrew Koenig，我也在那儿与他讨论过类库设计和模板机制。他鼓励我进一步研究某些模板机制的泛化和效率，但是很幸运的是，他却没有说服我让模板更类似Ada泛型。如果他成功了，他就无法设计和实现STL了！在1993年末，Alex在泛型编程技术方面显示了他最近十年的长期研究的进展，这种技术是基于严格的数学基础的、目标是成为最通用和最高效的编程技术。他是一个容器和算法的框架。他首先联系了Andrew，Andrew花几天时间研究这种技术之后，就把它展示给我了。我的第一反映是很迷惑。我发现STL的容器和容器使用方式是多余的，甚至于是丑陋的。与很多通晓面向对象编程的程序员一样，我认为自己知道容器的样子与STL代码的样子有怎样的不同。但是，在我建立工具列表（我认为这个列表对于容器来说是很重要的）的几年里，令我惊讶的是，我发现STL除了一个条件之外，符合其它所有的条件。那个缺少的条件是使用通用基类为所有的衍生类（例如所有的对象或容器）提供服务（例如永续性）。但是，我不认为这种服务对容器的概念有本质的意义。 它让我花了几周时间才感觉到STL比较舒适。在那以后，我担心把一个全新样式的类库介绍给C+群体已经太晚了。让标准委员会在标准进行过程中这么迟的时候接受新的和革命性的东西的成功几率是非常小的（的确是这样的）。即使出现最好的情况，标准也会被延迟一年-而C+群体急切需要该标准。同时，委员会本质上是一个保守的团体，而STL是革命性的。因此成功的机会是很渺茫的，但是我还是在它上面进行着辛勤的工作。毕竟，由于C+没有足够大的、足够好的标准库，我的感觉非常糟糕。Andrew Koenig尽了最大的努力来鼓励我，并且Alex Stepanov用他知道的最好的东西来游说Andy和我。幸运的是，Alex不太了解在委员会中使某种东西成为主流的难度，因此他不太沮丧，并且继续研究技术方面，继续为Andrew和我讲授。我开始给其他人解释STL背后的想法。1993年10月，在加利福尼亚的San Jose举行的标准委员会会议上，我们邀请了Alex进行晚间演讲。它叫做C+编程的科学，它处理了规则类型的大多数原则-连接构造、赋值和等同。我还介绍了转发迭代子的原则。我没有提起任何容器的问题，只提到一个算法：查找。这次演讲是活跃的下层社会的大胆创新，而其巨大的乐趣使委员会的态度从现在让我们作些主要的事情变成了等等，让我们瞧一瞧。这正是我们需要的暂停时间！在后来的四个月中，我们进行试验、争论、游说、讲授、编程和重新设计，这样Alex才能在1994年三月加利福尼亚的San Diego委员会会议上提供STL的完整说明。1994年末在HP一个会议上，Alex提出了C+类库实现，我们在很多细节上达成了一致，但是STL的大小成为了主要的障碍。最后，在Alex的催促下，我拿起笔，逐字地删除，大约删掉了三分之二的内容。对于每一个工具，我都必须向Alex和其他类库专家非常简短地解释为什么它不能被删掉、为什么它使大多数C+程序员受益。这是个可怕的过程。Alex后来声明说这让他心痛。但是，这样的删减造就了现在知名的STL，并让它1994年10月在加拿大Waterloo的会议上成为ISO C+标准的一部分-而原始的和完全的STL都没有达到这个目标。对简化STL的必要修改也把标准延迟了一年以上。回想起来，我认为当时我们做的事情造成的伤害比预料的要小一些。在对采用STL的可能性的讨论中，我记得一件事情：Beman Dawes冷静地声明自己认为STL对于普通程序员来说过于复杂了，但是作为试验，他自己实现了10，从此他不再认为STL超过了标准的难度。Beman是委员会中很少编写应用程序的人。不幸的是，委员会趋向于由建立编译器、类库和工具的人员所控制。 在STL方面我信任Alex Stepanov。在STL之前，他花了十年以上的时间，用一些无用的语言（例如Scheme和Ada）来研究基本的想法和技术。但是，Alex第一个坚持要求其他人一起参与。David Musser和Alex在泛型编程方面一起工作了约二十年，Meng Lee与他一起在HP工作，帮助他编写最初的STL。Alex和Andrew Koenig之间的电子邮件讨论也有帮助作用。除了苛刻的试验之外，我的贡献很小。我建议与内存相关的所有信息都集中到一个对象中-就形成了分配器（allocator）。我还草拟了Alex想法的初始需求表，建立表格记录STL算法和类对它们的模板参数的要求。这些需求表实际上表明这种语言的表达能力不足-这种需求应该成为代码的一部分。1.1 STL的理念那么什么是STL呢？到目前为止，它作为标准C+的一部分已经快十年了，因此你的确应该知道它，但是如果你不熟悉现代的C+，那么我就有必要对它的想法和语言使用方式作一些简单的介绍。我们来考虑一个问题：把对象存储在容器中，并编写算法来操作这些对象。我们按照直接、独立和概念的混合表现方式来考虑这个问题。自然地，我们希望能够在多种容器（例如列表、向量、映射）中存储多种类型（例如整型、Point、Shape）的对象，并在容器中的对象上应用大量的算法（例如排序、检索、积聚）。此外，我们希望使用的这些对象、容器和算法都是静态类型安全的、尽可能地快速、尽可能地简洁、不冗长、易于阅读。同时实现这些目标并不容易。实际上，为了解决这个难题，我差不多花费了十年还是没有找到成功的方法。STL解决方案是以带元素类型的参数化容器以及与容器完全分离的算法为基础的。容器的每种类型都提供一种迭代子（iterator）类型，只使用这些迭代子就可以实现对容器中所有元素的访问。通过这种方式，我们可以编写算法来使用迭代子而不用知道提供迭代子的容器的信息。每种迭代子类型与其它类型都是完全独立的，除非要为必要的操作（例如*和+）提供了相同语义（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.14); 其基本的想法是，你能够把任何容器的（所有）元素都作为一个元素序列（sequence）。容器知道第一个元素在哪儿，最后一个元素在哪儿。我们把指向一个元素的对象称为迭代子。接着我们就可以使用一对迭代子（begin()和end()）来表示容器中的元素，其中begin()指向第一个元素，end()指向最后一个元素前面。end()迭代子指向最后一个元素后面，而不是指向最后一个元素，这就使空序列不会成为一种特殊情况。你能对迭代子做什么样的操作？你可以得到迭代子指向的元素的值（像指针一样使用*），可以使迭代子指向下一个元素（像指针一样使用+），可以比较两个迭代子，看它们是否指向同一个元素（使用=或!=）。令人惊讶的是，这已经足以实现find()（查找功能）了：template 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: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:iterator可以成为一个把*和+作为内建函数（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.14 / else / 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()的单一源代码定义和使用来挑选根本不同的、也是理想的代码。请注意，这儿不存在运行时分派（dispatch）、没有虚拟函数调用。实际上，它只有琐碎的内联函数和指针的基本操作（例如*和+）的调用。在速度和代码大小方面，我们都到取得了很大的成功。为什么没有把序列或容器作为基本的概念，而使用了一对迭代子呢？部分原因在于一对迭代子只不过比容器的概念更普通。例如，给定迭代子，我们可以只对容器的前一半进行排序：sort(vi.begin(), vi.begin()+vi.size()/2)。另一个原因是STL遵循了C+的设计原则，我们必须一律地提供转换（transition）路径、支持内建的和用户定义类型。如果某个人把数据保存在普通的数组中会怎么样呢？我们仍然可以使用STL算法。例如：char bufmax; / 填充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:iterator p = find_if(v.begin(),v.end(),Less_than(7); if (p != vi.end() / 我们找到了值小于7 的元素/ else / vi 没有值小于 7 的元素/ Less_than(7)是什么东西呢？它是一个函数对象，它是某个类的对象，该类带有应用程序操作符（( )），被定义成执行某个函数：template struct Less_than T value; Less_than(const T& v) :value(v) bool operator()(const T& v) const return vvalue; ; 例如：Less_than f(3.14); / Less_than 保存了双精度值 3.14 bool b1 = f(3); / b1 为真（33.14 是真的）bool b2 = f(4); / b2 为假（43.14 是假的） 从2004年的情况来看，在D&E中没有提到函数对象是很奇怪的。我们应该使用一个章节来讲述它们。甚至于用户自定义的应用程序操作符（( )）的使用情况也没有提到，尽管它已经存在很长时间，并且很卓著。例如，它是几个最初的允许重载的操作符之一（在=之后），它还用于模仿Fortran下标（subscript notation）。我们可以编写一个find()版本，它使用了函数对象，而不是简单的!=来检测是否可以找到某个元素。它的名字是find_if()：template 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 7a; vector:iterator p = find_if(v.begin(),v.end(),less_than_7); 但是，这个例子显示了，与函数相比我们为什么更喜欢函数对象：我们可以使用一个（或多个）参数来初始化函数对象，同时函数对象可以保持这些信息供以后使用。函数对象可以保持任何状态。这样就可以形成更通用、更优良的代码。如果我们需要，我们以后可以检查它的状态。例如：template 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 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。有趣的是，简单的函数对象比功能相同的函数的性能更好。其原因在于它们趋向于按值（by value）传递，因此它们更易于内联（inline）。当我们传递那些执行很简单操作（例如用于排序的比较条件）的对象或函数的时候，这一点是非常重要的。特别地，当对简单类型（例如整型或双精度型）的数组进行排序的时候，函数对象的内联就是STL（C+标准类库）的sort()在多方面超越了传统的qsort()原因。函数对象是用于更高级构造的一种C+机制。它并非高级理念的最好表达方式，但是它在用于普通目的的语言环境中，显示出令人惊讶的表现能力和固有的高性能。作为表现能力的一个例子，Jaakko J?rvi演示了如何提供和使用一个Lambda类，使它的真正意义合法化：Lambda x; List:iterator p = find_if(lst.begin(),lst.end(),x=7); 如果你希望 = 能够工作，那么不用建立一个通用类库，而是为Lambda和=添加大约十余行代码定义