Effective STL(item1 - item22)

条款1：仔细选择你的容器

标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。

基于节点的容器是list和slist以及所有关联容器。

●     你需要“可以在容器的任意位置插入一个新元素”的能力吗？如果是，你需要序列容器，关联容器做

不到。

●     你关心元素在容器中的顺序吗？如果不，散列容器就是可行的选择。否则，你要避免使用散列容器。

●     必须使用标准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）只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效？这个一个非常特殊的情况，但如果你遇到这种情况，

deque就是你梦想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque

是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。）

条款2：小心对“容器无关代码”的幻想

不同的容器是不同的，而且它们的优点和缺点有重大不同。

它们并不被设计成可互换的，而且你做不了什么包装的工作。

既然有了要一次次的改变容器类型的必然性，你可以用这个常用的方法让改变得以简化：使用封装，封装，

再封装。其中一种最简单的方法是通过自由地对容器和迭代器类型使用typedef。

要限制如果用一个容器类型替换了另一个容器可能需要修改的代码，就需要在类中隐藏那个容器，而且要通

过类的接口限制容器特殊信息可见性的数量。比如，如果你需要建立一个客户列表，请不要直接用list。取而

代之的是，建立一个CustomerList类，把list隐藏在它的private区域。你写不出容器无关性代码，但他们可能可以。

条款3：使容器里对象的拷贝操作轻量而正确

拷贝对象是STL的方式。

一个使拷贝更高效、正确而且对分割问题免疫的简单的方式是建立指针的容器而不是对象的容器。

我们需要知道STL容器使用了拷贝，但是别忘了一个事实：比起数组它们仍然是一个进步。

条款4：用empty来代替检查size()是否为0

你应该首选empty的构造，而且理由很简单：对于所有的标准容器，empty是一个常数时间的操作，但对于一

些list实现，size花费线性时间。

条款5：尽量使用区间成员函数代替它们的单元素兄弟

太多的STL程序员过度使用copy，所以我重复一遍我的建议：几乎所有目标区间被插入迭代器指定的copy的使用都可以

用调用的区间成员函数的来代替。

●     一般来说使用区间成员函数可以输入更少的代码。

●     区间成员函数会导致代码更清晰更直接了当。

我们有一个：效率。当处理标准序列容器时，应用单元素成员函数比完成同样目的

的区间成员函数需要更多地内存分配，更频繁地拷贝对象，而且/或者造成多余操作。

●     区间构造。所有标准容器都提供这种形式的构造函数： 

container::container(InputIterator begin,               // 区间的起点

                        InputIterator end);     // 区间的终点

●     区间插入。所有标准序列容器都提供这种形式的insert： 

void container::insert(iterator position,               // 区间插入的位置

                        InputIterator begin,    // 插入区间的起点

                        InputIterator end);     // 插入区间的终点

关联容器使用它们的比较函数来决定元素要放在哪里，所以它们了省略position参数。

void container::insert(lnputIterator begin, InputIterator end); 

●     区间删除。每个标准容器都提供了一个区间形式的erase，但是序列和关联容器的返回类型不同。序列容器提供

了这个： 

iterator container::erase(iterator begin, iterator end); 

而关联容器提供这个：

void container::erase(iterator begin, iterator end); 

●     区间赋值。就像我在这个条款的一开始提到的，所有标准列容器都提供了区间形式的assign： 

void container::assign(InputIterator begin, InputIterator end);

所以现在我们明白了，尽量使用区间成员函数来代替单元素兄弟的三个可靠的论点。区间成员函数更容易写，它们更清

楚地表达你的意图，而且它们提供了更高的性能。那是很难打败的三驾马车。

条款6：警惕C++最令人恼怒的解析

假设你有一个int的文件，你想要把那些int拷贝到一个list中。这看起来像是一个合理的方式：

ifstream dataFile("ints.dat");

list<int> data(istream_iterator<int>(dataFile), // 警告！这完成的并不

                istream_iterator<int>());               // 是像你想象的那样

用括号包围一个

实参的声明是不合法的，但用括号包围一个函数调用的观点是合法的，所以通过增加一对括号，我们强迫编译器以我们的方式看事情：

list<int> data((istream_iterator<int>(dataFile)),       // 注意在list构造函数

                        istream_iterator<int>());       // 的第一个实参左右的

                                                // 新括号

一个更好的解决办法是在数据声明中从时髦地使用匿名istream_iterator对象后退一步，仅仅给那些迭代器名

字。以下代码到哪里都能工作：

ifstream dataFile("ints.dat");

istream_iterator<int> dataBegin(dataFile);

istream_iterator<int> dataEnd;

list<int> data(dataBegin, dataEnd);

条款7：当使用new得指针的容器时，记得在销毁容器前delete那些指针
我们需要记住的所有事情就是STL容器很智能，但它们没有智能到知道是否应该删除它们所包含的指针。当你要删除指针的容器时要避免资源泄漏，你必须用智能引用计数指针对象（比如Boost的shared_ptr）来代替指针，或者你必须在容器销毁前手动删除容器中的每个指针。

条款8：永不建立auto_ptr的容器

拷贝一个auto_ptr将改变它的值

条款9：在删除选项中仔细选择

如果我们观察在本条款中提到的所有东西，我们得出下列结论：

●     去除一个容器中有特定值的所有对象： 

如果容器是vector、string或deque，使用erase-remove惯用法。

如果容器是list，使用list::remove。

如果容器是标准关联容器，使用它的erase成员函数。

●     去除一个容器中满足一个特定判定式的所有对象： 

如果容器是vector、string或deque，使用erase-remove_if惯用法。

如果容器是list，使用list::remove_if。

如果容器是标准关联容器，使用remove_copy_if和swap，或写一个循环来遍历容器元素，当你把迭代

器传给erase时记得后置递增它。

●     在循环内做某些事情（除了删除对象之外）： 

如果容器是标准序列容器，写一个循环来遍历容器元素，每当调用erase时记得都用它的返回值更新你

的迭代器。

如果容器是标准关联容器，写一个循环来遍历容器元素，当你把迭代器传给erase时记得后置递增它。

条款10：注意分配器的协定和约束

因此，如果你想要写自定义分配器，让我们总结你需要记得的事情。

●     把你的分配器做成一个模板，带有模板参数T，代表你要分配内存的对象类型。

●     提供pointer和reference的typedef，但是总是让pointer是T*，reference是T&。

●     决不要给你的分配器每对象状态。通常，分配器不能有非静态的数据成员。

●     记得应该传给分配器的allocate成员函数需要分配的对象个数而不是字节数。也应该记得这些函数返回

T*指针（通过pointer typedef），即使还没有T对象被构造。

●     一定要提供标准容器依赖的内嵌rebind模板。

条款11：理解自定义分配器的正确用法

分配器在许多情况里有用。只要你遵循相同类型的所有分配器都一定等价的限制条

件，你将毫不费力地使用自定义分配器来控制一般内存管理策略，群集关系和使用共享内存以及其他特殊的堆。

条款12：对STL容器线程安全性的期待现实一些

当涉及到线程安全和STL容器时，你可以确定库实现允许在一个容器上的多读取者和不同容器上的多写入者。你不能希望库消除对手工并行控制的需要，而且你完全不能依赖于任何线程支持。

条款13：尽量使用vector和string来代替动态分配的数组

如果你用到的string实现是引用计数的，而你现在已经确定string的引用计数支持是一个性能问题的多线程环境中运行，你至少有三个合理的选择，而且没有一个放弃了STL。第一，看看你的库实现是否可以关闭引用计数，通常是通过改变预处理变量的值。当然那是不可移植的，但使工作变得可能，值得研究。第二，寻找或开发一个不使用引用计数的string实现（或部分实现）替代品。第三，考虑使用vector<char>来代替string，vector实现不允许使用引用计数，所以隐藏的多线程性能问题不会出现了。当然，如果你选择了vector<char>，你就放弃了string的专用成员函数，但大部分功能仍然可以通过STL算法得到，所以你从一种语法切换到另一种不会失去很多功能。

所有的结果都是简单的。如果你在使用动态分配数组，你可能比需要的做更多的工作。要减轻你的负担，就使用vector或string来代替。

条款14：使用reserve来避免不必要的重新分配

回到本条款的主旨，通常有两情况使用reserve来避免不必要的重新分配。第一个可用的情况是当你确切或者

大约知道有多少元素将最后出现在容器中。那样的话，就像上面的vector代码，你只是提前reserve适当数量的

空间。第二种情况是保留你可能需要的最大的空间，然后，一旦你添加完全部数据，修整掉任何多余的容

量。这里要加上一个注意点：调用reserve不改变容器中对象的个数。

条款15：小心string实现的多样性

● 字符串值可能是或可能不是引用计数的。默认情况下，很多实现的确是用了引用计数，但它们通常提供了关闭的方法，一般是通过预处理

器宏。条款13给了一个你可能要关闭的特殊环境的例子，但你也可能因为其他原因而要那么做。比如，引用计数只对频繁拷贝的字符串有

帮助，而有些程序不经常拷贝字符串，所以没有那个开销。

● string对象的大小可能从1到至少7倍char*指针的大小。

● 新字符串值的建立可能需要0、1或2次动态分配。

● string对象可能是或可能不共享字符串的大小和容量信息。

● string可能是或可能不支持每对象配置器。

● 不同实现对于最小化字符缓冲区的配置器有不同策略。

条款16: 如何将vector和string的数据传给遗留的API

vector v;

void doSomething(const int* pints, size_t numInts);

if (!v.empty()) doSomething(&v[0], v.size()); // 传递数据到API

string s;

void doSomething(const char *pString);

doSomething(s.c_str());

条款17：使用“交换技巧”来修整过剩容量

class Contestant {...};

vector<Contestant> contestants;

vector<Contestant>(contestants).swap(contestants);

同样的技巧可以应用于string：

string s;

... // 使s变大，然后删除所有它的字符

string(s).swap(s); // 在s上进行“收缩到合适”

另外，交换技巧的变体可以用于清除容器和减少它的容量到你的实现提供的最小值。你可以简单地和一个默

认构造的临时vector或string做个交换：

vector<Contestant> v;

string s;

... // 使用v和s

vector<Contestant>().swap(v); // 清除v而且最小化它的容量

string().swap(s); // 清除s而且最小化它的容量

条款18：避免使用vector<bool>

因为vector<bool>是一个伪容器，并不保存真正的bool，而是打包bool以节省空间。在一个典

型的实现中，每个保存在“vector”中的“bool”占用一个单独的比特，而一个8比特的字节将容纳8

个“bool”。在内部，vector<bool>使用了与位域（bitfield）等价的思想来表示它假装容纳的bool。

条款19：了解相等和等价的区别

总之，通过只使用一个比较函数并使用等价作为两个值“相等”的意义的仲裁者，标准关联容器避开了很多

会由允许两个比较函数而引发的困难。一开始行为可能看起来有些奇怪（特别是当你发现成员和非成员find

可能返回不同结果），但最后，它避免了会由在标准关联容器中混用相等和等价造成的混乱。

条款20：为指针的关联容器指定比较类型

无论何时你建立一个指针的标准关联容器，你必须记住容器会以指针的值排序。这基本上不是你想要的，所以你几乎

总是需要建立自己的仿函数类作为比较类型。

struct DereferenceLess {

template <typename PtrType>

bool operator()(PtrType pT1, // 参数是值传递的，

PtrType pT2) const // 因为我们希望它们

{ // 是（或行为像）指针

return *pT1 < *pT2;

}

};

本条款是关于指针的关联容器，但它也可以应用于表现为指针的对象的容器，例如，智能

指针和迭代器。如果你有一个智能指针或迭代器的关联容器，那也得为它指定比较类型。幸运的是，指针的

这个解决方案也可以用于类似指针的对象。正如DereferenceLess适合作为T*的关联容器的比较类型一样，它也

可以作为T对象的迭代器和智能指针容器的比较类型。

条款21: 永远让比较函数对相等的值返回false

因为相等不是等价

条款22：避免原地修改set和multiset的键

本条款的动机很容易理解。正如所有标准关联容器，set和multiset保持它们的元素有序，这些容器的正确行为

依赖于它们保持有序。 如果你改了关联容器里的一个元素的值（例如，把10变为1000），新值可能不在正确

的位置，而且那将破坏容器的有序性。

你将原谅我以这种方法放它，但要记得关键的事情是对于set和multiset，如果你进行任何容器元素的原地修

改，你有责任确保容器保持有序。

条款23：考虑用有序vector代替关联容器

在有序vector中存储数据很有可能比在标准关联容器中保存相同的数据消耗更少的内存；当页面错误

值得重视的时候，在有序vector中通过二分法查找可能比在一个标准关联容器中查找更快。

阶段性操作：

1. 建立。通过插入很多元素建立一个新的数据结构。在这个阶段，几乎所有的操作都是插入和删除。几

乎没有或根本没有查找。

2. 查找。在数据结构中查找指定的信息片。在这个阶段，几乎所有的操作都是查找。几乎没有或根本没

有插入和删除。

3. 重组。修改数据结构的内容，也许通过删除所有现有数据和在原地插入新数据。从动作上说，这个阶

段等价于阶段1。一旦这个阶段完成，应用程序返回阶段2。

如果你的程序不是按照阶段的方式操作数据结构，那么使用有序vector代替标准关联容器几乎可以确定是在

浪费时间。