泛型编程与STL (2009 年度畅销榜NO.292 )

许多程序员可能并不知道，C++不仅是一个面向对象程序语言， 它还适用于泛型编程(generic programming)。这项技术可以大大增强你的能力，协助你写出高效率并可重复运用的软件组件(software components)。
本书由知名的C++专家Matthew H．Austern执笔，引导你进入泛型编程思维模型，并将你带往此一模型的最重要成品：C++ Standard Template Library(STL)。本书揭示STL的奥秘，告诉你STL不仅仅是一组方便运用的容器类(container classes)。对于泛型组件和可交互作用的组件而言，STL是一个具备扩充能力的框架(framework)、
《泛型编程与STL》阐述了泛型编程的中心思想：concepts、modeling、refinement，并为你展示这些思想如何导出STL的基础概念：iterators、containers、function objects。循此路线，你可以把STL想像为一个由concepts(而非明确之functions或classes)组成的程序库：、你将学习其正式结构并因此获得其潜在威力所带来的完整优势。本书使你能够：
●以你自己的“可移植组件”及“可交互作用之泛型组件”扩充STL；
●产生一些算法，让它们和它们所处理之型别(types)及数据结构彻底划清界线；
●撰写更精致、更高效、更有效力的代码，可跨平台重复使用。

译序（侯捷）
前言

第一篇 泛型编程导入
第1章 STL巡礼
1.1 一个简单的例子
1.2 总结

第2章 算法与区间
2.1 线性查找(Linear Search)
2.2 Concepts和Modeling
2.3 Iterators(迭代器,泛型指针)
2.4 Refinement(精炼,强化)
2.5 总结

第3章 再论Iterators(迭代器or泛型指针)
3.1 Iterator Traits(迭代器特征)与Associated Types(相关型别)
3.2 定义新组件(New Components)
3.3 总结

第4章 Function Objects(函数对象)
4.1 将线性查找一般化
4.2 Function Object Concepts(函数对象概念)
4.3 Function Object Adapters(函数对象配接器)
4.4 预定义的Function Objects
4.5 总结

第5章 Containers(容器)
5.1 一个简单的Containers
5.2 Containers Concepts
5.3 大小可变的Containers Concepts
5.4 总结

第二篇 参考手册：STL Concepts
第6章 基本概念
6.1 Assignable
6.2 Default Comparable
6.3 Equality Comparable
6.4 可序性(Ordering)

第7章 Iterators(迭代器or泛型指针)
7.1 Trivial Iterator
7.2 Input Iterator
7.3 Output Iterator
7.4 Forward Iterator
7.5 Bidirectional Iterator
7.6 Random Access Iterator

第8章 Function Objects(函数对象)
8.1 基本的Function Objects
8.2 Adaptable Function Objects
8.3 Predicates
8.4 特化的Concept

第9章 Containers(容器)
9.1 General Container Concepts
9.2 Sequence(序列: 循序式容器)
9.3 Associative Containers(关联式容器)
9.4 Allocator(空间配置器)

第三篇 参考手册: 算法与类
第10章 基本组件
10.1 Pair
10.2 Iterator基本要素
10.3 allocator
10.4 内存管理基本要素
10.5 临时缓冲区

第11章 [不改变操作对象之内容]的算法
11.1 线性查找
11.2 子序列匹配
11.3 计算元素个数
11.4 for_each
11.5 比较两个Ranges
11.6 最大值与最小值

第12章 [会改变操作对象之内容]的算法
12.1 拷贝某个区间
12.2 互换元素
12.3 transform
12.4 替换元素
12.5 充填整个区间
12.6 移除元素
12.7 排列算法
12.8 分割
12.9 随机重排与抽样
12.10 一般化之数值算法

第13章 排序和查找
13.1 对某个区间排序
13.2 sorted ranges上的操作行为
13.3 堆的相关操作

第14章 Iterator Classess(迭代器类)
14.1 Insert Iterators
14.2 Stream Iterators
14.3 reverse_iterator
14.4 raw_storage_iterator

第15章 Function Object Classes(函数对象类)
15.1 Function Object Base Classes
15.2 算术运算
15.3 大小比较
15.4 逻辑运算
15.5 证同与投射
15.6 特殊的Function Objects
15.7 Member Function Adapters
15.8 其他的Adapters

第16章 Container Classes(容器类)
16.1 序列(Sequences)
16.2 Associative Containers(关联式容器)
16.3 Container Adapters

附录A 可移植性与标准化
A.1 语言上的变动
A.2 程序库的变动
A.3 命名及包装

参考书目
索引

这不是一本讨论面向对象编程(object-oriented programming)的书。 你或许会觉得奇怪。毕竟，你可能在书店的C++分类区看到这本书，也可能听过别人把面向对象与C++当同一件事来讲，但是这并非C++语言的唯一用途。基本上C++支持多种不同的设计思维模型(paradigms)，其中最新也最鲜为人知的一项就是泛型编程(generic programming)。 正如许多新的观念一样，泛型编程实际上已有很长一段历史了。早期的泛型编程研究论文大约在25年前就已经出现；第一个实验性质的泛型程序库并非以C++写成，而是以Ada[MS89a，MS89b]和Scheme[KMS88]完成。由于泛型算法太新，所以还没有相关教科书。 第一个走出研究圈的样例显得格外重要，它就是STL：C++ Standard Template Library。STL是由Alexander Stepanov(他后来成为Hewlett-Packard实验室的一员)和Meng Lee共同发展，于1994年被纳入C++标准程序库的一部分。可免费取得之[HPSTL实现品][SL95]也于这一年发行，它是展示STL强大威力的范本。 当Standard Template Library开始成为C++标准规格的一部分，C++族群立刻意识到这是一个高品质而且高效率的容器类程序库(container classes library)。要在一堆物品中找出熟悉的东西是最容易的了，而每一位C++程序员都熟悉容器类。每个具相当水准的程序也都需要某种管理对象的方法，甚至每位C++程序员都曾实现过strings、vectors或lists。 C++早期就已经有容器类程序库的存在。这个语言加入template classes(亦即[可参数化的型别])之后，第一个用途一事实上也是引入template的主要原因一就是将容器类参数化。很多厂商包括Borland、Microsoft、Rogue Wave与IBM，都有自己的程序库，其中包括Array，或其对等物。 容器类的观念是如此根深蒂固，以致于STL给人的初步印象似乎不比其他容器类程序库多了些什么这种印象使大家疏忽了STL的独特性。 STL是一种高效、泛型、可交互操作的软件组件；巨大，而且可以扩充。它包含计算机科学中的许多基本算法和数据结构，而且它把算法和数据结构完全分离开来，互不耦合。STL不只是一个容器类程序库，更精确地说它是一个泛型算法(generic algorithms)库；容器的存在使这些算法有东西可以操作。 你可以在程序中使用现有的STL算法，正如你使用现有的容器一样。举例来说，当你想要使用C标准库中的qsort函数，你也可以使用泛型的STL sort(而且sort更简单、更弹性、更安全，也更有效率)。很多书籍，包括David Musser与Atul Saini合著的STL Tutorial and Reference Guide[MS96]，以及Mark Nelson的C++ Programmer's Guide to the Standard Template Library[Nel95]，都有说明如何以这种方式使用STL。 这实际上是非常有用的。重复运用代码总比重新撰写代码来得好，现在你可以在你的程序中重复运用既有的STL算法。然而这还只是以某个角度来使用STL而已。STL的设计具有扩充性；也就是说你可以自行撰写一些组件，与STL组件交互作用，就像不同的STL组件之间可以交互作用一样。有效地运用STL，意味着对它进行扩充。 如何阅读本书 本书把Standard Template Library当作抽象概念库(1ibraryOfabstractconcepts)来描述。本书定义出STL基本的各个concepts与抽象性质，并指出所谓[某个型别模塑出某个concept]是什么意思， [以某个concept的接口写成一个算法]又是什么意思。本书讨论STL涵盖的各个类和算法，并阐明如何撰写属于你自己并相容于STL的类和算法。此外本书还包含一份所有STL concepts、classes、算法的完整参考手册。 每个人都应该阅读第一篇，这一部分介绍STL与泛型编程的主要概念。说明如何使用以及撰写一个泛型算法，并解释[算法之所以为泛型]的意义。所谓泛型(Genericity)，具有[在多种数据型别上皆可操作]的含意。 探究泛型算法，自然而然便导出了concepts、modeling与refinement的核心观念，这些观念之于泛型编程，就像多型与继承之于面向对象编程，同样地基础，同样地重要。泛型算法作用于一维区间上，导出STL的数个基本概念：iterators、containers、function Objects。 第一篇同时也介绍了本书通用的符号及排版习惯：术语modeling和refinement、ranges的非对称标示法，以及concept名称的特殊字体。 STL定义了很多concepts。某些concepts只因技术上的细节而互不相同。第一篇是个概论，概略讨论STL concepts的全貌。第二篇是详细的参考手册，包含每个STL concept的严格定义。你可能不会想要遍读第二篇：当你需要参考某个concept时才到第二篇查询，应该是更好的做法。(每当需要撰写符合某个STL concept的新型别时，你都应该参考第二篇。) 第三篇同样是参考手册，提供STL预定义的算法和类的说明。这一部分仰赖第二篇的[concept定义]甚多。STL所有的算法和几乎所有的具象型别都是templates，每个template的参数都能以某种concept的model加以描述。第三篇的定义可以和第二篇对应的章节交互参考。 理想状况下，本书到达第三篇就可以结束了。不幸的是现实需求使我必须写出更多章节：一份有关可移植性议题的附录。STL问世之初并没有可移植性问题，因为只有一份实现品存在。这种情况已不复存在。一旦某种语言或程序库有一个以上的实现品存在，任何关心可移植性的人都必须知道每个实现品之间的差异。 你仍然可以从anonymous FTP站台butler.hpl.hp.com下载早期的HP实现品，但此作品已无人维护。Silicon Graphics Computer Systems (SGl) 有一份较新的免费作品，可以从http://www.sgx.com/Technology/STL下载。至于SGI STL在不同编译器上的移植版本，可以从http://www.metabyte.com/～fbp/stl取得。此外这个世界还存在有其他商业化STL实现品。 如果你正在撰写真正的程序，光了解函数库的设计理论是不够的；你还必须知道不同的STL实现品以及不同的C++编译器之间的差别。这些不怎么吸引人但却必要的细节，构成了附录A的主题。