本书对C++ STL进行了全面而深入的阐述。STL(标准模板库)是在惠普实验室中开发的,已纳入ANSI/ISO C++标准。其中的代码采用模板类及模板函数的方式,可以极大地提高编程效率。本书由P.J. Plauger等四位对C++ STL的实现有着卓越贡献的大师撰写,详细讨论了C++ STL的各个部分。全书分为16章,其中的13章通过背景知识、功能描述、头文件代码、测试程序和习题,分别讲述了C++ STL中的13个头文件,其他章节介绍了STL中广泛涉及的三个主题--迭代器、算法和容器。本书附录列出了接口和术语表,最后列出了参考文献。
本书适合对C++有一定了解的程序员及高等院校师生阅读。
序 言\r\n第0章 简介\r\n背景知识\r\n功能描述\r\n使用STL\r\n实现STL\r\n测试STL\r\n习题\r\n第1章 迭代器\r\n背景知识\r\n功能描述\r\n使用迭代器\r\n习题\r\n第2章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第3章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第4章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第5章 算法\r\n背景知识\r\n功能描述\r\n使用算法\r\n习题\r\n第6章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第7章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第8章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试 \r\n习题\r\n第9章 容器\r\n背景知识\r\n功能描述\r\n使用容器\r\n习题\r\n第10章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第11章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第12章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题\r\n第13章 \r\n背景知识\r\n功能描述\r\n使用\r\n实现\r\n测试\r\n习题 \r\n第14章 \r\n背景知识 \r\n功能描述 \r\n使用 \r\n实现 \r\n测试 \r\n习题 \r\n第15章 \r\n背景知识 \r\n功能描述 \r\n使用 \r\n实现 \r\n测试 \r\n习题 \r\n第16章 \r\n背景知识 \r\n功能描述 \r\n使用 \r\n实现 \r\n测试 \r\n习题 \r\n附录A 接口 \r\n附录B 术语 \r\n参考文献
标准模板库( Standard Template Library, 简称 STL)是 ANSI/ISO C++语言的库的一个主要组成部分. 它最初是惠普实验室( Hewlett-Packard Labs)的产物, 开发者为Alexander Stepanov及Meng Lee(参见 S&L95), 主要基于早期的. 由 Stepanov和 David R Musser两人完成的工作. (参见 M&S87. M&S89及 M&S94. 这里所有的引用都列于附录C中. )你将会发现在这个库中包含着对于C++中的模板( template)的各种使用, 其中大部分的使用都值得炫耀, 并且具有良好的连贯性. 确实, STL已经开始有意义地改变了许多程序员编写C++代码的方式.
本书展示了怎样使用STL中提供的模板类(template classe)及模板函数(template function), 一如C++标准中所要求的一样(参见条款20及23~26). 我们在此将STL视为标准C++中所定义的庞大的库中一个相对独立的子集. C++中库的设计与ANSI/ISO标准C(ANS89与ISO90)中的库设计一脉相承. 因此, 也可以将本书视为P. J. Plauger先前的两本书, 《The Standard C Library》(Pla92)与《The Draft Standard C++ Library》(Pla95)的一个后续版本. 几乎所有 C++程序员感兴趣的有关库的内容都可以在这三本书找到.
C+十标准
1998年, C++标准正式通过, 并且将在接下来的一段时间中保持一种稳定的状态①. 它既是ANSI标准, 也是ISO标准, 也就是说, 它既是美国的国家标准, 也是一种全球通用的标准. 作为标准化进程的一部分, 整个标准C++语言及库第一次完整地描述在一起. 一个相对较晚加入这个标准化进程的事件是在C++标准的草案中接纳STL为C++标准的一部分. 现在, 标准C++的编译器及库的各种实现也不过刚刚出现. 也就是说, 即使是很有经验的C++程序员也将发现本书中有许多东西是全新的.
同样, 在1994年6月被标准化委员会接纳为C++标准草案的一部分之前, 对 STL的早期描述(至少早于 S&L95)仅限于一个相对狭窄的范围内. 在被接纳的过程中, STL本身又被重新组织并且在几个重要的环节做了修改. 现在, 在标准C++中的STL已经不再是由惠普实验室开发出来的那套软件开发包, 同时它与那些由不同的代理提供的强化版本也不同. 这也就是说, 即使是那些有着早期的STL使用经验的程序员也可以从本书中获得新的知识. 你将会在本书中发现对STL的完整描述, 一如在C++标准中指定的那样.
本书中还将至少告诉你一种实现STL的方法. 书中提供了大概6000行经过测试. 证明可行的代码, 同时这些代码也被证实可以移植到许多C++编译器上. 实际上, 这些代码在本质上和 Microsoft Visual C++. IBM Visual Age或其他厂商所提供的 C++编译器中的 STL代码几乎是相同的. 我们仅仅是在排版及符号表达方面做了小小的改动, 以使得这些代码在书中更具有可读性, 同时将它们用来作为教学示例也比较方便.
作为对C++库的扩展, 书中提供的这些代码可以工作于任何其他C++库上面(参见附录A). 然而, 当与一个完全符合C++标准的库一起工作时, 它表现得尤为出色. 我们尽可能地去除了那些不具有可移植性或不可能被广泛利用的代码. 那些过分依赖于C++语言中最近才加入的特性的代码, 如模板的部分特化(template partial specialization)等, 有可能在一些编译器上导致问题的产生. 你也可以在那些商业化的STL版本中发现对于这些特殊情况的各种不同的折衷处理.
无论如何, 你都可以通过使用本书中提供的代码, 获得一些对于如何使用由模板构成的库的宝贵经验, 而使用模板库也己经开始成为C++世界中的一个重要标准. 同样重要的是, 我们相信看完一个实际的STL实现将有助于你更好地理解和应用它.
这就引入了本书的另一个目的. 除了给出STL的标准, 以及实现它的可行代码之外, 本书还可以作为一本如何使用该库的教程. 你将发现在本书中存在着一些有用的背景信息, 告诉你STL是如何演变成现在的这个版本的, 使用它意味着什么, 以及如何使用它. 为此并不需要阅读和理解我们所提供的所有代码. 哪怕是对于本书的粗略学习, 也能给你带来不少有益的收获. 不需要是老手才能从本书中获益, 那些偶尔才显得比较老练的程序员将会发现这里所提供的信息简直就是无价之宝.
本书的目的不是教你如何写C++代码. 我们假定你已经了解了足够多的C++知识, 已经可以看懂简单的C++代码. 虽然在本书中出现的代码并不是那么简单, 但不要怕, 我们会解释其间所使用的各种技巧.
扩展STL
本书的最终目的就是告诉程序员如何设计及实现对 STL的扩展. STL集合了大量的算法. 数据结构以及编程技巧. 然而, 它并没有提供程序员可能需要的全部特性. 相比而言, 它只是提供了那些核心的. 被广为使用的特性, 并且描述了这些核心代码的编写规则.
当你掌握了这些规则后, 就可以往STL中添加自己的算法, 并且让它与已有的数据结构一同正常地工作. 你也可以添加自己的数据结构, 使之与已有的算法协同工作. 通过将本书中提供的STL代码作为例子来使用, 你将很快学会如何以最少的新增代码来处理新的问题, 并且发现这些新增的代码可以在以后的项目中重用. 这也就是设计库的最终原因.
本书的结构
本书的结构看起来更像是STL代码本身的结构. C++标准中列出了大量的头文件, 但只有其中的 13个头文件中定义了STL中所有的模板. 这13个头文件的每一个在本书中都有对应的一章. 其他的章节则全面地介绍了STL, 并讨论了STL中三个涉及较为广泛的主题--迭代器(iterator). 算法(algorithm)和容器(xontainer). 这些头文件中的大部分都有着适量的相关内容, 因此也就引起了一些相关的讨论. 有关它们的相关章节必然会导致讨论范围的扩大.
每一个章节都以相同的模式讲述了一个头文件. 一开始是一个简短的背景介绍小节, 接着就是有关这个头文件内容的功能性描述, 然后是对于如何更好地使用该头文件中提供的特性所给出的一些建议. 再接着给出了组成头文件的C++代码, 并伴随有代码是如何工作的有关注释. 我们还为每一个头文件给出了一个小小的测试程序, 给出至少一个粗略的例子演示每一个定义的模板是如何使用的.
在每一章的最后给出了一些习题. 如果本书是作为某个大学课程的课本的话, 这些习题可以当作家庭作业来完成. 大部分习题都是简单的练习, 例如使用库, 或是代码重写等. 它们能够使人理解实现中的某些重点, 或是展示了实现中的一些合理变更. 那些较难的习题都标注出来了, 它们可作为一个更大范围的项目的基础. 那些自学本书的人可以将这些习题作为一种锻炼, 以激发更多的思考.