目录
Content
Chapter_1
Chapter_2
Chapter_3
Chapter_4
Chapter_5
Chapter_6
Chapter_7
Chapter_8
Chapter_1
导读
你已经熟悉了STL。你知道怎么建立容器，迭代它们的内容，添加删除元素和应用常见算法，比如find和sort。但你并不
满足，你不能摆脱STL所提供的超过它们能带来的好处的感觉。应该简单的任务并非那样。应该直截了当的操作确有资
源泄漏或错误行为。应该高效的过程却需要比你希望给它们的更多的时间和内存。是的，你知道怎么使用STL，但你不
确定你在有效地使用它。
我为你写了这本书。
在《Effective STL》中，我解释了怎样结合STL组件来在库的设计得到最大的好处。这样的信息允许你对简单、直接的问
题开发简单、直接的解决方案，也帮你对更复杂的问题设计优雅的方法。我描述了常见的STL使用错误，而且向你演示
怎么避开它们。那帮助你躲开闪资源漏、不可移植的代码和未定义的行为。我讨论了优化代码的方法，所以你能使STL
表现得像它应该的那样快速、光滑。
本书里的信息将使你成为一个更好的STL程序员，它将让你成为一个更高产的程序员。而且它将让你成为一个更愉快的
程序员，使用STL很有趣，但是有效地使用它更为有趣，这种有趣是它们必须把你拽离键盘，因为你不能相信你争拥有
的好时光。即使对STL的匆匆一瞥也能发现它是一个非常酷的库，但这份酷比你可能想象的更宽更深。我在本书的一个
主要目标是传达给你这个库有多神奇，因为在我编程的差不多30年里，我从未见过任何像STL的东西。你或许也没有。
定义、使用和扩展STL
没有“STL”的官方定义，而且当人们使用这个术语时，不同的人表示的是不同的东西。在本书中，“STL”的意思是
与迭代器合作的C++标准库的一部分。那包括标准容器（包括string），iostream库的一部分，函数对象和算法。它不包
括标准容器适配器（stack、queue和priority_queue）以及bitset和valarray容器，因为它们缺乏迭代器支持。它也不包括数
组。真的，数组以指针的形式支持迭代器，但数组是C++语言的一部分，并非库。
技术上，我的STL的定义排除了标准C++库的扩展，特别是散列容器，单链表，rope和多种非标准函数对象。虽然如
此，一个有效的STL程序员需要知道这样的扩展，因此我在合适的地方提到了它们。的确，条款25致力于非标准散列容
器的概述。它们现在不在STL里，但类似它们的东西几乎肯定将要进入标准C++库的下一个版本，而在窥见未来是有价
值的。
存在STL扩展的原因之一是STL是被设计为可扩展的库。不过，在本书里，我关注于使用STL，而不是给它添加新的组
件。例如，如果你发现，我没有说多少关于写你自己的算法的东西，而且我根本没有在写新容器和迭代器上提供指导。
我相信在你着手增加它的能力之前，掌握STL已经提供的东西很重要，所以那是我在《Effective STL》里关注的。当你决
定建立你自己STLesque组件时，你将在像Josuttis的《The C++ Standard Library》[3]和Austern的《Generic Programming and
the STL》[4]这样的书里找到建议。我确实在这本书里讨论的STL扩展的一个方面是写你自己的函数对象。你不可能在不
知道怎么写自己的函数对象的情况下有效地使用STL，所以我为这个主题投入了整整一章（第6章）。
引用
先前段落中对Josuttis和Austern的书的引用演示了我怎么处理书目引用的。通常，我试图提及引用的足够信息以便已经熟
悉它的人能够鉴别出来。例如，如果你已经知道这些作者的书，就不必转向参考书目那里查明[3]和[4]提及的你已经知
道的书。当然，如果你不熟悉一个出版物，参考书目（从第225页开始）会给你全面的引用。
我经常引用三个一般没有使用引用编号的东西。第一个是C++国际标准[5]，我通常把它简称为“标准”。其他两个是
我早先关于C++的书，《Effective C++》[1]和《More Effective C++》[2]。
STL和标准
我经常提及C++标准，因为《Effective STL》专注于可移植的，与标准一致的C++。理论上，我在这本书里演示的一切都
可以用于每个C++实现。实际上，那不是真的。编译器的缺陷和STL实现凑合成防止一些有效的代码编译或表现出它们
应该有的行为。那是很常见的情况，我描述了这些问题，而且解释了你应该怎么变通地解决他们。
有时候，最容易的变通办法是使用另一个STL实现。附录B给一个这种情况的例子。实际上，STL用得越多，编译器和库
实现的区别就越重要。程序员在设法让合法的代码编译时遇到困难，他们通常责备他们的编译器，但对于STL，编译器
可能是好的，而STL实现是不良的。为了强调你得依赖编译器和库实现的事实，我使用你的STL平台。一个STL平台是一
个特定编译器和一个标准模板库特定实现的组合。在本书里，如果我提及一个编译器问题，你能确信我意思是编译器有
问题。但是，如果我说你的STL平台有问题，你应该理解为“可能是编译器缺陷，可能是库缺陷，或许都有”。
我一般提及你的“编译器们”——复数。那是我长期相信你通过确保代码可以在多于一个的编译器上工作的方法来改进
你的代码质量（特别是移植性）的产物。此外，使用多个编译器一般可以简化拆解由STL的使用不当造成的错误信息难
题。（条款49致力于解码此类消息的方法。）
关于与标准一致的代码，我强调的另一个方面是你应该避免构造未定义行为。这样的构造可能在运行期做任何事情。不
幸的是，这意味着它们可能正好做了你想要的，而那会导致一种错误的安全感。太多程序员以为未定义行为总会导致一
个明显的问题，例如，一个分段错误或其他灾难性的错误。未定义行为的结果实际上更为狡猾，例如，破坏极少引用的
数据。它们也可以通过程序运行。我发现一个未定义行为的好定义是“为我工作，为你工作，在开发和QA期间工作，
但在你最重要的用户面前爆炸了”。避免未定义行为很重要，所以我指出了它会出现的通常情况。你应该训练你自己警
惕这样的情况。
引用计数
讨论STL而没有提及引用计数是几乎不可能的。正如你将在条款7和33看见的，基于指针的容器的设计几乎总要导致引用
计数。另外， 很多string实现内部是引用计数的，而且，正如条款15解释的，这可能是一个你不能忽视的实现细节。在
本书里，我认为你已经熟悉引用的基础。如果你不是，大多数中级和高级C++教材都覆盖了这个主题。例如，在
《More Effective C++》里，相关材料是在条款28和29。如果你不知道引用计数是什么而且你不喜欢学习，不要担心。你
也可以读完本书，虽然这里那里可能有一些句子不像它们应该的那么有意义。
string和wstring
我关于string说的任何东西都可以相等地应用到给它的宽字符兄弟，wstring。类似地，任何时候我提及string和char或char*
之间的关系，对于wstring和wchar_t或wchar_t*之间的关序也是正确的。换句话说，只是因为我在本书里不明确地提及宽
字符字符串，不要以为STL不能支持它们。它也像基于char的字符串一样支持它们。它必须。string和wstring都是同一个
模板的实例化，basic_string。
术语，术语，术语
这不是STL的入门书，所以我认为你知道基本的东西。仍然，下面的术语十分重要，我感到需要强迫复习它们：
● vector、string、deque和list被称为标准序列容器。标准关联容器被是set、multiset、map和multimap。
● 迭代器被分成五个种类，基于它们支持的操作。简要地说，输入迭代器是每个迭代位置只能被读一次的只读迭
代器。输出迭代器是每个迭代位置只能被写一次的只写迭代器。输入和输出迭代器被塑造为读和写输入和输出
流（例如，文件）。因此并不奇怪输入和输出迭代器最通常的表现分别是istream_iterator和ostream_iterator。
前向迭代器有输入和输出迭代器的能力，但是它们可以反复读或写一个位置。它们不支持operator--，所以它们
可以高效地向前移动任意次数。所有标准STL容器都支持比前向迭代器更强大的迭代器，但是，正如你可以在条
款25看到的，散列容器的一种设计可以产生前向迭代器。单链表容器（在条款50提到）也提供前向迭代器。
双向迭代器就像前向迭代器，除了它们的后退可以像前进一样容易。标准关联容器都提供双向迭代器。list也
有。
随机访问迭代器可以做双向迭代器做的一切事情，但它们也提供“迭代器算术”，即，有一步向前或向后跳的
能力。vector、string和deque都提供随机访问迭代器。指进数组的指针可以作为数组的随机访问迭代器。
● 重载了函数调用操作符（即，operator()）的任何类叫做仿函数类。从这样的类建立的对象称为函数对象或仿函
数。STL中大部分可以使用函数对象的地方也都可以用真函数，所以我经常使用术语“函数对象”来表示C++函
数和真的函数对象。
● 函数bind1st和bind2nd称为绑定器。
STL的一个革命性方面是它的复杂度保证。这些保证约束了任何STL操作允许表现的工作量。这极好，因为它可以帮你
确定同一问题不同方法的相对效率，不论你使用的是什么STL平台。不幸的是，如果你不了解计算机科学的行话，在复
杂度保证后面的专有名词可能会把你弄糊涂。这里有一个关于我在本书里使用的复杂度术语的快速入门。每个都引用了
它作为n的函数做一件事情要多久，n是容器或区间的元素数目。
● 以常数时间执行的操作的性能不受n的改变而影响，例如，向list中插入一个元素是一个常数时间操作。不管list有
一个还是一百万个元素，插入都花费同样数量的时间。
不要太照字面理解占用“常数时间”。 它不意味着做某些事情所花费时间的数量是字面上的常数，它只表明不
被n影响。例如，两个STL平台可能花费非常不同数量的时间执行相同的“常数时间”操作。如果一个库比另一
个有更复杂的实现，或如果一个编译器执行了充分的更积极优化的时候，这就会发生。
常数时间复杂度的一个变体是分摊常数时间。以分摊常数时间运行的操作通常是常数时间的操作，但偶尔它们
花的时间也取决于n。分摊常数时间操作通常以常数时间运行。
● 当n变大时，以对数时间运行的操作需要更多的时间运行，但它需要的时间以与n的对数成正比的比率增长。例
如，在一百万个项上的一次操作预计花费大约在一百个项上三倍的时间，因为log n3 = 3 log n。在关联容器上的
大多数搜寻操作（例如，set::find）是对数时间操作。
● 以线性时间运行的操作需要的时间以与n成正比的比率增长。标准算法count以线性时间运行，因为它必须查看给
定区间中的每个元素。如果区间的大小扩大了三倍，它也必须做三倍的工作，而且我们期望它大约花费三倍时
间来完成。
通常，常数时间操作运行得比要求对数时间的快，而对数时间操作运行得比线性的快。当n变得足够大时，这总是真
的，但对于n相对小的值，有时候更差理论复杂度的操作可能或胜过更好理论复杂度的操作。如果你想对知道更多STL
复杂度保证的东西，转向Josuttis的《The C++ Standard Library》[3]。
术语的最后一个要注意的东西是，记住map或multimap里的每个元素都有两个组件。我一般叫第一个组件键，叫第二个
组件值。以
map m;
为例，string是键，double是值。
代码例子
这本书充满了例子代码，当我引入每个例子时我都作了解释。不过仍然值得提前知道一些事情。
你可以从上面map的例子看到我通常忽略#include，而且忽视STL组件在namespace std里的事实。当定义map m，我可以
这么写，
#include