C++之父Bjarne谈C++中的STL模板
副标题#e#
在1994年，我主要体贴的是如何使ISO C++尺度尽大概地好–同时在它所包括的特性和类型的质量两个方面–并得到大都人的同意。纵然人们不接管某种类型，也不会影响它（类型）的精采性。ISO尺度没有强制力，因此有些人认为本身不值得挥霍时间来适应它，除非（群体）社团的压力可以或许使他们确信该类型的代价。对付一个实现者来说，适应情况是很重要的特别事情，因此适应情况是一个有意识的抉择，而且需要分派一些资源，而这些资源原来可以在其它处所利用。某些艰涩的语言特性很难在某些编译器中实现。我们可以实现可能购置类库，并且领先的、靠得住的实现者（implementer）也有时机用本身的富于想像力的专利特性来"锁定"用户。因此，我认为要点是：让委员会成员和他们所代表的组织确信该尺度的文档是他们所期望看到的最好的文档。
在做了许多事情之后，该委员会得到了乐成。1997年10月，在Morristown（New Jersey，USA）集会会议上，技能成员的最终投票功效是43-0。在获知这个功效今后，我们举办了庆祝勾当！在1998年，ISO成员国以空前的22-0的投票功效核准了这个尺度。为了获取各人的一致同意，委员会做了大量的技能事情，也利用了一些交际计策：在谁人时候，我喜欢说"政治问题无法办理；我们必需找到激发该问题的技能问题并办理它"。我无法想象仅仅通过投票，因为少数听从大都才简朴"办理"的问题，同时，由于"政治上的讨价还价"的问题也危害了我们最好的技能判定–而这个问题（模板的分隔编译）仍然在"恶化"，需要寻找一个更好的技能方案。
在最后投票之前的一年里，委员会的事情是：
1. 细节、细节和更多的细节。
2. STL
3. 模板的分隔编译
#p#副标题#e#
第一个问题很是明明：国际尺度必需用大量的篇幅来存眷细节信息；实际上，实现（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了！
#p#分页标题#e#
在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++，那么我就有须要对它的想法和语言利用方法作一些简朴的先容。
#p#分页标题#e#
我们来思量一个问题：把工具存储在容器中，并编写算法来操纵这些工具。我们凭据直接、独立和观念的殽杂表示方法来思量这个问题。自然地，我们但愿可以或许在多种容器（譬喻列表、向量、映射）中存储多种范例（譬喻整型、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*
#p#分页标题#e#
那么为什么我们不省去所有的"迭代子质料"和利用指针呢？个中一个原因是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)是什么对象呢？它是一个函数工具，它是某个类的工具，该类带有应用措施操纵符（( )），被界说成执行某个函数：
#p#分页标题#e#
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一段时间之后，我提出第四种样式：
－泛型编程
#p#分页标题#e#
以利用模板为基本的技能，以及从成果性编程中获取大量灵感的技能与传统的数据抽象有本质的差异。人们只是认为范例、工具和资源差异。新的C++类库是利用模板技能编写的，才得到了静态范例安详和高效率。模板技能对付嵌入式系统编程和高机能数学运算也是很要害的，在这些情况中，资源的打点和正确性是要害。在这些规模中STL并非老是抱负的。譬喻，它没有直接地支持线性代数，并且在紧凑的及时系统中（在这种情况下一般会克制自由地利用存储）也很难利用它。可是，STL证明白在模板的辅佐下可以实现什么样的成果，并提出了一些有效的技能示例。譬喻，操作迭代子（和分派器）把逻辑内存会见与实际内存会见分分开来，对付许多高机能数字运算就是很要害的；利用小型的、简朴的内联、工具对付嵌入式系统编程中最佳地利用硬件也是很要害的。这类技能有一些记实在尺度委员会关于机能的技能陈诉中了。这是对当前太过地利用过度依赖于类条理和虚拟函数的"面向工具"技能的这种趋势的一种大范畴的还击–也是一种有建树意义的替代方案。
很明明，STL并不完美。相对来说没有完美的对象。可是，它开发了新天地，并且它拥有的影响力甚至于高出了庞大的C++群体。利用C++时，当人们试图敦促STL所建议的技能来逾越STL技能的时候，它们接头"模板元数据编程"。我们中有些人也会思量STL迭代子的限制（利用generator和range是不是更好？），以及C++如何更好地支持这些利用（观念、初始化器）。
