《Effective STL》

haoji

条款5：尽量使用区间成员函数代替它们的单元素兄弟 24
条款14：使用reserve来避免不必要的重新分配 66
条款15：小心string实现的多样性 68
条款23：考虑用有序vector代替关联容器 100
条款24：当关乎效率时应该在map:perator[]和map-insert之间仔细选择106
条款25：熟悉非标准散列容器 111
条款29：需要一个一个字符输入时考虑使用istreambuf_iterator 126
条款31：了解你的排序选择 133
条款44：尽量用成员函数代替同名的算法 190
条款46：考虑使用函数对象代替函数作算法的参数 201
《Effective STL》的方针
构成本书50个条款的方针是基于世界上最有经验的STL程序员的见解和建议。这些方针总结了你应该总是做的——或总
是避免做的——以发挥标准模板库的最大功效。同时，它们只是方针。在一些条件下，违反它们是有意义的。例如，条
款7的标题告诉你在容器销毁前应该删除容器内new得的指针，但那个条款的正文说明只适用于当容器销毁时被那些指针
指向的对象也得跟随而去的情况。情况经常如此，但不永远为真。类似的，条款35的标题恳求你使用STL算法进行简单
的忽略大小写字符串比较，但条款的正文指出在一些情况里，你最好使用不仅在STL之外，而且甚至不是标准C++一部
分的一个函数！
只有你足够了解你正写的软件，它运行的环境，以及建立它的场景，才能确定违反我提出的方针是否合理。多数时候，
不是，而且伴随每个条款的讨论解释了为什么。在一些情况里，它是。对指南奴隶般的盲从是不对的，但骑士般的漠视
也不对。在一个人冒险之前，你应该保证你有一个好原因。

haoji

Center of STL Study
——最优秀的STL学习网站
容器
没错，STL有迭代器、算法和函数对象，但对于大多数C++程序员，容器是最突出的。它们比数组更强大更
灵活，可以动态增长（也常是缩减），可以管理属于它们自己的内存，可以跟踪它们拥有的对象数目，可以
限制它们支持操作的算法复杂度等等。它们的普及是很容易理解的。它们比竞争对手更好，不管竞争对手是
来自其他库或你自己写的容器类型。STL容器不只是好，而是相当好。
本章关注的是可以适用于所有STL容器的指导方针。后面的章节则专注于特殊的容器类型。把这个专题放在
这里还因为让你知道在选择适当的容器时应该面对的约束；避免产生为一个容器类型写的代码也可以用于其
它容器类型的错觉；容器里对象拷贝操作的重要性；当指针或auto_ptr存放在容器中时出现的难点；删除的
输入和输出；你可以或不可以使用自定义分配器；达到最高效率的技巧和考虑在多线程环境下容器的使用。
有很多需要覆盖的领域，但没关系。这些条款会把它分解为小块，按照这种方式，你差不多现在就能发现几
个可以应用于你的代码的主意。

haoji

Center of STL Study
——最优秀的STL学习网站
条款1：仔细选择你的容器
你知道C++中有很多你可以支配的容器，但是你意识到有多少吗？要确定你没有忽略你的选项，这里有一个
快速回顾。
● 标准STL序列容器：vector、string、deque和list。
● 标准STL关联容器：set、multiset、map和multimap。
● 非标准序列容器slist和rope。slist是一个单向链表，rope本质上是一个重型字符串。（“绳子
（rope）”是重型的“线（string）”。明白了吗？）你可以找到一个关于这些非标准（但常见的）容
器的概览在条款50。
● 非标准关联容器hash_set、hash_multiset、hash_map和hash_multimap。我在条款25检验了这些可以广泛
获得的基于散列表的容器和标准关联容器的不同点。
● vector<char>可以作为string的替代品。条款13描述了这个替代品可能会有意义的情况。
● vector作为标准关联容器的替代品。就像条款23所说的，有时候vector可以在时间和空间上都表现得比
标准关联容器好。
● 几种标准非STL容器，包括数组、bitset、valarray、stack、queue和priority_queue。因为它们是非STL容
器，所以在本书中关于它们我说得很少，虽然条款16提到了数组比STL容器更有优势的一种情况，而
条款18揭示了为什么bitset可能比vector<bool>要好。值得注意的是，数组可以和STL算法配合，因为指
针可以当作数组的迭代器使用。
这是所有的选项，而且可以考虑的范围和可以在它们之间的选择一样丰富。不走运的是，STL的大多数讨论
只限于容器世界的一个很窄的视野，忽略了很多关于选择适当容器的问题。就连标准都介入了这个行动，提
供了以下的在vector、deque和list之间作选择的指导方案：
vector、list和deque提供给程序员不同的复杂度，因此应该这么用：vector是一种可以默认使用
的序列类型，当很频繁地对序列中部进行插入和删除时应该用list，当大部分插入和删除发生
在序列的头或尾时可以选择deque这种数据结构。
如果你主要关心的是算法复杂度，我想这个方案是有理由的建议，但需要关心更多东西。
现在，我们要检查一些可以补充算法复杂度的重要的容器相关问题，但首先我需要介绍一种STL容器的分类
方法，它被讨论的次数并不像它应该的那样多。那是连续内存容器和基于节点的容器的区别。
连续内存容器（也叫做基于数组的容器）在一个或多个（动态分配）的内存块中保存它们的元素。如果一个

haoji

新元素被查入或者已存元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空
间或者填充原来被删除的元素所占的空间。这种移动影响了效率（参见条款5和14）和异常安全（就像我们将
会看到的）。标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。
基于节点的容器在每个内存块（动态分配）中只保存一个元素。容器元素的插入或删除只影响指向节点的指
针，而不是节点自己的内容。所以当有东西插入或删除时，元素值不需要移动。表现为链表的容器——比如
list和slist——是基于节点的，所有的标准关联容器也是（它们的典型实现是平衡树）。非标准的散列容器使
用不同的基于节点的实现，就像我们将会在条款25中看到的。
利用这个不恰当的术语，我们已经准备好描述一些大多数关于在容器间选择的问题。在这个讨论中，我略过
考虑非STL类容器（比如，数组、bitset等），因为毕竟这是本关于STL的书。
● 你需要“可以在容器的任意位置插入一个新元素”的能力吗？如果是，你需要序列容器，关联容器做
不到。
● 你关心元素在容器中的顺序吗？如果不，散列容器就是可行的选择。否则，你要避免使用散列容器。
● 必须使用标准C++中的容器吗？如果是，就可以除去散列容器、slist和rope。
● 你需要哪一类迭代器？如果必须是随机访问迭代器，在技术上你就只能限于vector、deque和string，但
你也可能会考虑rope（关于rope的更多信息在条款50）。如果需要双向迭代器，你就用不了slist（参见
条款50）和散列容器的一般实现（参见条款25）。
● 当插入或者删除数据时，是否非常在意容器内现有元素的移动？如果是，你就必须放弃连续内存容器
（参见条款5）。
● 容器中的数据的内存布局需要兼容C吗？如果是，你就只能用vector（参见条款16）。
● 查找速度很重要吗？如果是，你就应该看看散列容器（参见条款25），排序的vector（参见条款23）和
标准的关联容器——大概是这个顺序。
● 你介意如果容器的底层使用了引用计数吗？如果是，你就得避开string，因为很多string的实现是用引
用计数（参见条款13）。你也不能用rope，因为权威的rope实现是基于引用计数的（参见条款50）。
于是你得重新审核你的string，你可以考虑使用vector<char>。
● 你需要插入和删除的事务性语义吗？也就是说，你需要有可靠地回退插入和删除的能力吗？如果是，
你就需要使用基于节点的容器。如果你需要多元素插入（比如，以范围的方式——参见条款5）的事
务性语义，你就应该选择list，因为list是唯一提供多元素插入事务性语义的标准容器。事务性语义对
于有兴趣写异常安全代码的程序员来说非常重要。（事务性语义也可以在连续内存容器上实现，但会
有一个性能开销，而且代码不那么直观。要了解这方面的知识，请参考Sutter的《Exceptional C++》的
条款17[8]。）
● 你要把迭代器、指针和引用的失效次数减到最少吗？如果是，你就应该使用基于节点的容器，因为在
这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。一般来
说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。
● 你需要具有有以下特性的序列容器吗：1）可以使用随机访问迭代器；2）只要没有删除而且插入只发

haoji

生在容器结尾，指针和引用的数据就不会失效？这个一个非常特殊的情况，但如果你遇到这种情况，
deque就是你梦想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque
是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。）
这些问题几乎不是事情的完结。比如，它们没有关注不同的容器类型使用不同的内存配置策略（条款10和14
讨论了这些策略的一些方面）。但是，它们已经足够是你信服了，除非你对元素顺序、标准的一致性、迭代
器能力、内存布局和C的兼容性、查找速度、因为引用计数造成的行为不规则、事务性语义的轻松实现和迭
代器失效的条件没兴趣，你得在容器操作的算法复杂度上花更多的考虑时间。当然这样的复杂度是重要的，
但这离整个故事很远。
当面对容器时，STL给了你很多选项。如果你的视线超越了STL的范围，那就会有更多的选项。在选择一个容
器前，要保证考虑了所有你的选项。一个“默认容器”？我不这么认为。

haoji

Center of STL Study
——最优秀的STL学习网站
条款2：小心对“容器无关代码”的幻想
STL是建立在泛化之上的。数组泛化为容器，参数化了所包含的对象的类型。函数泛化为算法，参数化了所
用的迭代器的类型。指针泛化为迭代器，参数化了所指向的对象的类型。
这只是个开始。独立的容器类型泛化为序列或关联容器，而且类似的容器拥有类似的功能。标准的内存相邻
容器（参见条款1）都提供随机访问迭代器，标准的基于节点的容器（再参见条款1）都提供双向迭代器。序
列容器支持push_front或push_back，但关联容器不支持。关联容器提供对数时间复杂度的lower_bound、
upper_bound和equal_range成员函数，但序列容器却没有。
随着泛化的继续，你会自然而然地想加入这个运动。这种做法值得赞扬，而且当你写你自己的容器、迭代器
和算法时，你会自然而然地推行它。唉，很多程序员试图把它推行到不同的样式。他们试图在他们的软件中
泛化容器的不同，而不是针对容器的特殊性编程，以至于他们可以用，可以说，现在是一个vector，但以后
仍然可以用比如deque或者list等东西来代替——都可以在不用改变代码的情况下来使用。也就是说，他们努
力去写“容器无关代码”。这种可能是出于善意的泛化，却几乎总会造成麻烦。
最热心的“容器无关代码”的鼓吹者很快发现，写既要和序列容器又要和关联容器一起工作的代码并没有什
么意义。很多成员函数只存在于其中一类容器中，比如，只有序列容器支持push_front或push_back，只有关
联容器支持count和lower_bound，等等。在不同种类中，甚至连一些如insert和erase这样简单的操作在名称和
语义上也是天差地别的。举个例子，当你把一个对象插入一个序列容器中，它保留在你放置的位置。但如果
你把一个对象插入到一个关联容器中，容器会按照的排列顺序把这个对象移到它应该在的位置。举另一个例
子，在一个序列容器上用一个迭代器作为参数调用erase，会返回一个新迭代器，但在关联容器上什么都不返
回。（条款9给了一个例子来演示这点对你所写的代码的影响。）
假设，然后，你希望写一段可以用在所有常用的序列容器上——vector, deque和list——的代码。很显然，你必
须使用它们能力的交集来编写，这意味着不能使用reserve或capacity（参见条款14），因为deque和list不支持它
们。由于list的存在意味着你得放弃operator[]，而且你必须受限于双向迭代器的性能。这意味着你不能使用需
要随机访问迭代器的算法，包括sort，stable_sort，partial_sort和nth_element（参见条款31）。
另一方面，你渴望支持vector的规则，不使用push_front和pop_front，而且用vector和deque都会使splice和成员
函数方式的sort失败。在上面约束的联合下，后者意味着你不能在你的“泛化的序列容器”上调用任何一种
sort。
这是显而易见的。如果你冒犯里其中任何一条限制，你的代码会在至少一个你想要使用的容器配合时发生编

haoji

译错误。可见这种代码有多阴险。
这里的罪魁祸首是不同的序列容器所对应的不同的迭代器、指针和引用的失效规则。要写能正确地和vector,
deque和list配合的代码，你必须假设任何使那些容器的迭代器，指针或引用失效的操作符真的在你用的容器
上起作用了。因此，你必须假设每次调用insert都使所有东西失效了，因为deque::insert会使所有迭代器失效，
而且因为缺少capacity，vector::insert也必须假设使所有指针和引用失效。（条款1解释了deque是唯一一个在迭
代器失效的情况下指针和引用仍然有效的东西）类似的理由可以推出一个结论，所有对erase的调用必须假设
使所有东西失效。
想要知道更多？你不能把容器里的数据传递给C风格的界面，因为只有vector支持这么做（参见条款16）。你
不能用bool作为保存的对象来实例化你的容器，因为——正如条款18所阐述的——vector 并非总表现为一个
vector，实际上它并没有真正保存bool值。你不能期望享受到list的常数时间复杂度的插入和删除，因为vector
和deque的插入和删除操作是线性时间复杂度的。
当这些都说到做到了，你只剩下一个“泛化的序列容器”，你不能调用reserve、capacity、operator[]、
push_front、pop_front、splice或任何需要随机访问迭代器的算法；调用insert和erase会有线性时间复杂度而且
会使所有迭代器、指针和引用失效；而且不能兼容C风格的界面，不能存储bool。难道这真的是你想要在你
的程序里用的那种容器？我想不是吧。
如果你控制住了你的野心，决定愿意放弃对list的支持，你仍然放弃了reserve、capacity、push_front和
pop_front；你仍然必须假设所有对insert和erase的调用有线性时间复杂度而且会使所有东西失效；你仍然不能
兼容C风格的布局；而且你仍然不能储存bool。
如果你放弃了序列容器，把代码改为只能和不同的关联容器配合，这情况并没有什么改善。要同时兼容set和
map几乎是不可能的，因为set保存单个对象，而map保存对象对。甚至要同时兼容set和multiset（或map和
multimap）也是很难的。set/map的insert成员函数只返回一个值，和他们的multi兄弟的返回类型不同，而且你
必须避免对一个保存在容器中的值的拷贝份数作出任何假设。对于map和multimap，你必须避免使用operator
[]，因为这个成员函数只存在于map中。
面对事实吧：这根本没有必要。不同的容器是不同的，而且它们的优点和缺点有重大不同。它们并不被设计
成可互换的，而且你做不了什么包装的工作。如果你想试试看，你只不过是在考验命运，但命运并不想被考
验。
接着，当天黑以后你认识到你决定使用的容器，嗯，不是最理想的，而且你需要使用一个不同的容器类型。
你现在知道当你改变容器类型的时候，不光要修正编译器诊断出来的问题，而且要检查所有使用容器的代
码，根据新容器的性能特征和迭代器，指针和引用的失效规则来看看那些需要修改。如果你从vector切换到
其他东西，你也需要确认你不再依靠vector的C兼容的内存布局；如果你是切换到一个vector，你需要保证你
不用它来保存bool。

haoji

既然有了要一次次的改变容器类型的必然性，你可以用这个常用的方法让改变得以简化：使用封装，封装，
再封装。其中一种最简单的方法是通过自由地对容器和迭代器类型使用typedef。因此，不要这么写:
class Widget {...};
vector<Widget> vw;
Widget bestWidget;
... // 给bestWidget一个值
vector<Widget>::iterator i = // 寻找和bestWidget相等的Widget
find(vw.begin(), vw.end(), bestWidget);
要这么写：
class Widget { ... };
typedef vector<Widget> WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw;
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget);
这是改变容器类型变得容易得多，如果问题的改变是简单的加上用户的allocator时特别方便。（一个不影响
对迭代器/指针/参考的失效规则的改变）
class Widget { ... };
template<typename T> // 关于为什么这里需要一个template
SpecialAllocator { ... }; // 请参见条款10
typedef vector<Widget, SpecialAllocator<Widget> > WidgetContainer;
typedef WidgetContainer::iterator WCIterator;
WidgetContainer cw; // 仍然能用
Widget bestWidget;
...
WCIterator i = find(cw.begin(), cw.end(), bestWidget); // 仍然能用
如果typedef带来的代码封装作用对你来说没有任何意义的话，你仍然会称赞它们可以节省许多工作。比如，
你有一个如下类型的对象

haoji

map<string,
vectorWidget>::iterator,
CIStringCompare> // CIStringCompare是“忽略大小写的字符串比较”
// 参见条款19
而且你要用const_iterator遍历这个map，你真的想不止一次地写下
map<string, vectorWidget>::iterator, CIStringCompare>::const_iterator
？当你使用STL一段时间以后，你会认识到typedef是你的好朋友。
typedef只是其它类型的同义字，所以它提供的的封装是纯的词法（译注：不像#define是在预编译阶段替换
的）。typedef并不能阻止用户使用（或依赖）任何他们不应该用的（或依赖的）。如果你不想暴露出用户对
你所决定使用的容器的类型，你需要更大的火力，那就是class。
要限制如果用一个容器类型替换了另一个容器可能需要修改的代码，就需要在类中隐藏那个容器，而且要通
过类的接口限制容器特殊信息可见性的数量。比如，如果你需要建立一个客户列表，请不要直接用list。取而
代之的是，建立一个CustomerList类，把list隐藏在它的private区域：
class CustomerList {
private:
typedef list<Customer> CustomerContainer;
typedef CustomerContainer::iterator CCIterator;
CustomerContainer customers;
public: // 通过这个接口
... // 限制list特殊信息的可见性
};
一开始，这样做可能有些无聊。毕竟一个customer list是一个list，对吗？哦，可能是。稍后你可能发现从列表
的中部插入和删除客户并不像你想象的那么频繁，但你真的需要快速确定客户列表顶部的20%——一个为
nth_element算法量身定做的任务（参见条款31）。但nth_element需要随机访问迭代器，不能兼容list。在这种
情况下，你的客户“list”可能更应该用vector或deque来实现。
当你决定作这种更改的时候，你仍然必须检查每个CustomerList的成员函数和每个友元，看看他们受影响的程
度（根据性能和迭代器/指针/引用失效的情况等等），但如果你做好了对CustomerList地实现细节做好封装的
话，那对CustomerList的客户的影响将会很小。你写不出容器无关性代码，但他们可能可以。

haoji

Center of STL Study
——最优秀的STL学习网站
条款3：使容器里对象的拷贝操作轻量而正确
容器容纳了对象，但不是你给它们的那个对象。此外，当你从容器中获取一个对象时，你所得到的对象不是
容器里的那个对象。取而代之的是，当你向容器中添加一个对象（比如通过insert或push_back等），进入容
器的是你指定的对象的拷贝。拷进去，拷出来。这就是STL的方式。
一旦一个对象进入一个容器，以后对它的拷贝并不少见。如果你从vector、string或deque中插入或删除了什
么，现有的容器元素会移动（拷贝）（参见条款5和14）。如果你使用了任何排序算法（参见条款31）：
next_permutation或者previous_permutation；remove、unique或它们的同类（参见条款32）；rotate或reverse等，
对象会移动（拷贝）。是的，拷贝对象是STL的方式。
你可能会对所有这些拷贝是怎么完成的感兴趣。这很简单，一个对象通过使用它的拷贝成员函数来拷贝，特
别是它的拷贝构造函数和它的拷贝赋值操作符（很好的名字，不是吗？）。对于用户自定义类，比如
Widget，这些函数传统上是这么声明的：
class Widget {
public:
...
Widget(const Widget&); // 拷贝构造函数
Widget& operator=(const Widget&); // 拷贝赋值操作符
...
};
如果你自己没有声明这些函数，你的编译器始终会为你声明它们。拷贝内建类型（比如int、指针等）也始终
是通过简单地拷贝他们的内在比特来完成的。（有关拷贝构造函数和赋值操作符的详细情况，请参考任何C+
+的介绍性书籍。在《Effective C++》中，条款11和27专注于这些函数的行为。）
因为会发生所有这些拷贝，本条款的动机现在就很清楚了。如果你用一个拷贝过程很昂贵对象填充一个容
器，那么一个简单的操作——把对象放进容器也会被证明为是一个性能瓶颈。容器中移动越多的东西，你就
会在拷贝上浪费越多的内存和时钟周期。此外，如果你有一个非传统意义的“拷贝”的对象，把这样的对象
放进容器总是会导致不幸。（会导致的不幸之一的例子请看条款8。）
当然由于继承的存在，拷贝会导致分割。那就是说，如果你以基类对象建立一个容器，而你试图插入派生类