《Effective STL》

haoji

端。如果我们忘记调用releaseMutexFor，我们将不会释放互斥量。
而且，这种基于Lock的方法在有异常的情况下是稳健的。C++保证如果抛出了异常，局部对象就会被销毁，
所以即使当我们正在使用Lock对象时有异常抛出，Lock也将释放它的互斥量。如果我们依赖手工调用
getMutexFor和releaseMutexFor，那么在调用getMutexFor之后releaseMutexFor之前如果有异常抛出，我们将不会
释放互斥量。
异常和资源管理是重要的，但是它们不是本条款的主题。本条款是关于STL里的线程安全。当涉及到线程安
全和STL容器时，你可以确定库实现允许在一个容器上的多读取者和不同容器上的多写入者。你不能希望库
消除对手工并行控制的需要，而且你完全不能依赖于任何线程支持。

haoji

Center of STL Study
——最优秀的STL学习网站
vector和string
所有的STL容器都很有用，但如果你像大多数C++程序员，你会发现你自己接触vector和string比它们的同胞更
经常。那是可以预料到的。vector和string被设计为代替大部分数组的应用，而数组很有用，它们被包含于从
COBOL到Java的每个商业上成功的编程语言。
本章的条款从多个角度覆盖了vector和string。我们从一个为什么值得从数组转换过来的讨论开始，然后看看
改进vector和string性能的方法，确定string的实现中重要的变种，检验怎么传递vector和string数据到只知道C的
API，学习怎么除去过剩的内存分配。我们用一个有教育意义的不同寻常的东西，vector<bool>，这个不能使
用的小vector的考察来作结尾。
本章的每一个条款都会帮你掌握这两个STL中最重要的容器，优化它们的应用。当我们完成的时候，你会知
道怎么让它们更好地为你服务。

haoji

条款13：尽量使用vector和string来代替动态分配的数组
这一刻，你决定使用new来进行动态分配，你需要肩负下列职责：
1. 你必须确保有的人以后会delete这个分配。如果后面没有delete，你的new就会产生一个资源泄漏。
2. 你必须确保使用了delete的正确形式。对于分配一个单独的对象，必须使用“delete”。对于分配一个
数组，必须使用“delete []”。如果使用了delete的错误形式，结果会未定义。在一些平台上，程序在
运行期会当掉。另一方面，它会默默地走向错误，有时候会造成资源泄漏，一些内存也随之而去。
3. 你必须确保只delete一次。如果一个分配被删除了不止一次，结果也会未定义。
职责真多，而且我不能理解为什么如果可以省心你却还要负责。感谢vector和string，用了它们就可以不像以
前那么麻烦了。
无论何时，你发现你自己准备动态分配一个数组（也就是，企图写“new T[...]”），你应该首先考虑使用一
个vector或一个string。（一般来说，当T是一个字符类型的时候使用string，否则使用vector，但我们在本条款
的后面将遇到的情况中，vector<char>可能是一个合理的设计选择。）vector和string消除了上面的负担，因为
它们管理自己的内存。当元素添加到那些容器中时它们的内存会增长，而且当一个vector或string销毁时，它
的析构函数会自动销毁容器中的元素，回收存放那些元素的内存。
另外，vector和string是羽翼丰满的序列容器，所以它们让你支配可以作用于这样的容器的整个STL算法军火
库。虽然数组也可以用于STL算法，但没有提供像begin、end和size这样的成员函数，也没有内嵌像iterator、
reverse_iterator或value_type那样的typedef。而且char*指针当然不能和提供了专用成员函数的string竞争。STL用
的越多，越会歧视内建的数组。
如果你关心你必须继续支持的遗留代码，它们都是基于数组的，放松点，无论如何都应该使用vector和
string。条款16演示了把vector和string中的数据传给需要array的API有多简单，所以整合遗留代码一般都没有问
题。
坦白地说，我想到了一个（也是唯一一个）用vector或string代替动态分配数组会出现的问题，而且它只关系
到string。很多string实现在后台使用了引用计数（参见条款15），一个消除了不必要的内存分配和字符拷贝的
策略，而且在很多应用中可以提高性能。事实上，一般认为通过引用计数优化字符串很重要，所以C++标准
委员会特别设法保证了那是一个合法的实现。
唉，一个程序员的优化就是其他人的抱怨，而且如果你在多线程环境中使用了引用计数的字符串，你可能发
现避免分配和拷贝所节省下的时间都花费在后台并发控制上了。（细节请参考Sutter的文章《Optimizations
That Aren't (In a Multithreaded World)》[20]。）如果你在多线程环境中使用引用计数字符串，就应该注意线程
安全性支持所带来的的性能下降问题。

haoji

要知道你正在使用的string实现是否是引用计数的，通常最简单的方式是参考库的文档。因为通常认为引用计
数是一种优化，制作商一般把它作为一个特性来吹捧。另一种方法是看库的string实现的源代码。我一般不推
荐尝试从库源代码中得到东西，但有时候这是唯一能找出你想知道的东西的方法。如果你选择了这个方法，
就要记住string是一个basic_string<char>的typedef（而wstring是basic_string<wchar_t>的typedef），所以你真正需
要看的是basic_string模板。最容易检查的地方是可能的类构造函数。看看它是否在某处增加了引用计数。如
果是，string就是引用计数的。如果不是，要么就是string不是引用计数，要么就是你看错了代码。呵呵。
如果你用到的string实现是引用计数的，而你想在已经确定string的引用计数支持是一个性能问题的多线程环境
中运行，你至少有三个合理的选择，而且没有一个放弃了STL。第一，看看你的库实现是否可以关闭引用计
数，通常是通过改变预处理变量的值。当然那是不可移植的，但使工作变得可能，值得研究。第二，寻找或
开发一个不使用引用计数的string实现（或部分实现）替代品。第三，考虑使用vector<char>来代替string，
vector实现不允许使用引用计数，所以隐藏的多线程性能问题不会出现了。当然，如果你选择了
vector<char>，你就放弃了string的专用成员函数，但大部分功能仍然可以通过STL算法得到，所以你从一种语
法切换到另一种不会失去很多功能。
所有的结果都是简单的。如果你在使用动态分配数组，你可能比需要的做更多的工作。要减轻你的负担，就
使用vector或string来代替。

haoji

Center of STL Study
——最优秀的STL学习网站
条款14：使用reserve来避免不必要的重新分配
关于STL容器，最神奇的事情之一是只要不超过它们的最大大小，它们就可以自动增长到足以容纳你放进去
的数据。（要知道这个最大值，只要调用名叫max_size的成员函数。）对于vector和string，只要需要更多空
间，就以realloc等价的思想来增长。这个类似于realloc的操作有四个部分：
1. 分配新的内存块，它有容器目前容量的几倍。在大部分实现中，vector和string的容量每次以2为因数增
长。也就是说，当容器必须扩展时，它们的容量每次翻倍。
2. 把所有元素从容器的旧内存拷贝到它的新内存。
3. 销毁旧内存中的对象。
4. 回收旧内存。
给了所有的分配，回收，拷贝和析构，你就应该知道那些步骤都很昂贵。当然，你不会想要比必须的更为频
繁地执行它们。如果这没有给你打击，那么也许当你想到每次这些步骤发生时，所有指向vector或string中的
迭代器、指针和引用都会失效时，它会给你打击的。这意味着简单地把一个元素插入vector或string的动作也
可能因为需要更新其他使用了指向vector或string中的迭代器、指针或引用的数据结构而膨胀。
reserve成员函数允许你最小化必须进行的重新分配的次数，因而可以避免真分配的开销和迭代器/指针/引用
失效。但在我解释reserve为什么可以那么做之前，让我简要介绍有时候令人困惑的四个相关成员函数。在标
准容器中，只有vector和string提供了所有这些函数。
● size()告诉你容器中有多少元素。它没有告诉你容器为它容纳的元素分配了多少内存。
● capacity()告诉你容器在它已经分配的内存中可以容纳多少元素。那是容器在那块内存中总共可以容纳
多少元素，而不是还可以容纳多少元素。如果你想知道一个vector或string中有多少没有被占用的内
存，你必须从capacity()中减去size()。如果size和capacity返回同样的值，容器中就没有剩余空间了，而
下一次插入（通过insert或push_back等）会引发上面的重新分配步骤。
● resize(Container::size_type n)强制把容器改为容纳n个元素。调用resize之后，size将会返回n。如果n小于
当前大小，容器尾部的元素会被销毁。如果n大于当前大小，新默认构造的元素会添加到容器尾部。
如果n大于当前容量，在元素加入之前会发生重新分配。
● reserve(Container::size_type n)强制容器把它的容量改为至少n，提供的n不小于当前大小。这一般强迫
进行一次重新分配，因为容量需要增加。（如果n小于当前容量，vector忽略它，这个调用什么都不
做，string可能把它的容量减少为size()和n中大的数，但string的大小没有改变。在我的经验中，使用
reserve来从一个string中修整多余容量一般不如使用“交换技巧”，那是条款17的主题。）[1]

haoji

这个简介明确表示了只要有元素需要插入而且容器的容量不足时就会发生重新分配（包括它们维护的原始内
存分配和回收，对象的拷贝和析构和迭代器、指针和引用的失效）。所以，避免重新分配的关键是使用
reserve尽快把容器的容量设置为足够大，最好在容器被构造之后立刻进行。
例如，假定你想建立一个容纳1-1000值的vector<int>。没有使用reserve，你可以像这样来做：
vector<int> v;
for (int i = 1; i <= 1000; ++i) v.push_back(i);
在大多数STL实现中，这段代码在循环过程中将会导致2到10次重新分配。（10这个数没什么奇怪的。记住
vector在重新分配发生时一般把容量翻倍，而1000约等于210。）
把代码改为使用reserve，我们得到这个：
vector<int> v;
v.reserve(1000);
for (int i = 1; i <= 1000; ++i) v.push_back(i);
这在循环中不会发生重新分配。
在大小和容量之间的关系让我们可以预言什么时候插入将引起vector或string执行重新分配，而且，可以预言
什么时候插入会使指向容器中的迭代器、指针和引用失效。例如，给出这段代码，
string s;
...
if (s.size() < s.capacity()) {
s.push_back('x');
}
push_back的调用不会使指向这个string中的迭代器、指针或引用失效，因为string的容量保证大于它的大小。
如果不是执行push_back，代码在string的任意位置进行一个insert，我们仍然可以保证在插入期间没有发生重
新分配，但是，与伴随string插入时迭代器失效的一般规则一致，所有从插入位置到string结尾的迭代器/指针/
引用将失效。
回到本条款的主旨，通常有两情况使用reserve来避免不必要的重新分配。第一个可用的情况是当你确切或者
大约知道有多少元素将最后出现在容器中。那样的话，就像上面的vector代码，你只是提前reserve适当数量的

haoji

空间。第二种情况是保留你可能需要的最大的空间，然后，一旦你添加完全部数据，修整掉任何多余的容
量。修整部分不难，但是我将不这里显示它，因为对它有一个技巧。要学习这个技巧，请转向条款17。
[1] 根据勘误表，这里要加上一个注意点：调用reserve不改变容器中对象的个数。

haoji

Center of STL Study
——最优秀的STL学习网站
条款15：小心string实现的多样性
Bjarne Stroustrup曾经用奇特的标题写一篇文章，《Sixteen Ways to Stack a Cat》[27]。事实表明实现string几乎有和那一样多的方法。当然，作为有经
验而且老于世故的软件工程师，我们应该忽视“实现细节”，但是如果爱因斯坦是对的，上帝存在于细节里，现实要求我们有时皈依宗教。即使当
细节不重要的时候，对它们有一些了解使我们能够确信它们不重要。
例如，一个string对象的大小是多少？换句话说，sizeof(string)返回什么值？如果你正密切注意内存消耗，这可能是一个重要的问题，或你正想用一
个string对象代替一个原始的char*指针。
关于sizeof(string)的消息是“有趣”，如果你担心空间问题，这几乎肯定是你不想听到的。string和char*指针一样大的实现很常见，也很容易找到
string是char*7倍大小的string实现。为什么会有差别？为了理解这一点，我们必须知道string可能存什么数据和它可能决定保存在哪里。
实际上每个string实现都容纳了下面的信息：
● 字符串的大小，也就是它包含的字符的数目。
● 容纳字符串字符的内存容量。（字符串大小和容量之间差别的回顾，参见条款14。）
● 这个字符串的值，也就是，构成这个字符串的字符。
另外，一个string可能容纳
● 它的配置器的拷贝。对于为什么这个域是可选的解释，转向条款10并阅读关于这个古怪的管理分配器的规则。
依赖引用计数的string实现也包含了
● 这个值的引用计数。
不同的string实现以不同的方式把这些信息放在一起。为了证明我的意思，我将让你看四种不同的string实现使用的数据结构。并不是要特别选择这
些实现，它们都来自于常用的STL实现，而正好是我检查的前四个库的string实现。
在实现A中，每个string对象包含一个它配置器的拷贝，字符串的大小，它的容量，和一个指向包含引用计数（“RefCnt”）和字符串值的动态分配
的缓冲区的指针。在这实现中，一个使用默认配置器的字符串对象是指针大小的四倍。对于一个自定义的配置器，string对象会随配置器对象的增
大而变大：
实现B的string对象和指针一样大，因为在结构体中只包含一个指针。再次，这里假设使用默认配置器。正如实现A，如果使用自定义配置器，这个
string对象的大小会增加大约配置器对象的大小。在这个实现中，使用默认配置器不占用空间，这归功于这里用了一个在实现A中没有的使用优化。

haoji

B的string指向的对象包含字符串的大小、容量和引用计数，以及容纳字符串值的动态分配缓冲区的指针。对象也包含在多线程系统中与并发控制有
关的一些附加数据。这样数据在我们考虑之外，所以我只是把数据结构的那部分标记为“其他”：
“其他”的框比其它框大，因为我按比例画框。如果一个框大小是另一个的两倍，大的框使用的字节数是小的两倍，在实现B中，用于并发控制的
数据是一个指针大小的6倍。
实现C的string对象总是等于指针的大小，但是这个指针指向一个包含所有与string相关的东西的动态分配缓冲器：它的大小、容量、引用计数和
值。没有每物体配置器（per-object allocator）的支持。缓冲区也容纳一些关于值可共享性的数据，我们在这里不考虑这个主题，所以我标记
为“X”。（如果你首先对为什么一个引用计数值可能不可共享感兴趣，参考《More Effective C++》的条款29。）
实现D的string对象是一个指针大小的七倍（仍然假设使用了默认配置器）。这个实现没有使用引用计数，但每个string包含了一个足以表现最多15个
字符的字符串值的内部缓冲区。因此小的字符串可以被整个保存在string对象中，一个有时被称为“小字符串优化”的特性。当一个string的容量超
过15时，缓冲器的第一部分被用作指向动态分配内存的一个指针，而字符串的值存放在那块内存中：

haoji

这些图不仅证明了我能读源代码并能画漂亮的照片，而且它们也让你可以推断出在这样的语句中建立string，
string s("Perse"); // 我们的狗叫做“Persephone”，但我们
// 一般只叫她“Perse”。访问她的网站
// http://www.aristeia.com/Persephone/
在实现D下将会没有动态分配，在实现A和C下一次，而在实现B下两次（一次是string对象指向的对象，一次是那个对象指向的字符缓冲区）。如果
你关心动态分配和回收内存的次数，或如果你关心经常伴随这样分配的内存开销，你可能想要避开实现B。另一方面， 实现B的数据结构包括了对
多线程系统并发控制的特殊支持的事实意味着它比实现A或C更能满足你的需要，尽管动态分配次数较多。（实现D不需要对多线程的特殊支持，
因为它不使用引用计数。条款13讲了更多线程和引用计数字符串之间的关系。更多关于你可能希望的STL容器中的线程支持方面的信息，参考条款
12。）
在基于引用计数的设计中，字符串对象之外的每个东西都可以被多个字符串共享（如果它们有相同的值），所以我们可以从图中观察到的其他东西
是实现A比B或C提供更少的共享性。特别是，实现B和C能共享一个字符串的大小和容量，因此潜在地减少了每物体分摊的的储存数据的开销。有
趣的是，实现C不能支持每对象配置器的事实意味着它是唯一可以共享配置器的实现：所有字符串必须使用同一个！（再次，管理分配器规则的细
节在条款10。）实现D在字符串对象间没有共享数据。
你不能完全从图中推断出的字符串行为的一个有趣方面是关于小字符串的内存管理策略。有些实现拒绝为小于一个适当字符数分配内存，实现A、
C和D就是这样。再看看这条语句：
string s("Perse"); // s是一个大小为5的字符串
实现A有32个字符的最小分配大小，所以虽然在所有实现下s的大小是5，在实现A下它的容量是31。（第32个字符大概被保留作尾部的null，因此可
以容易地实现c_str成员函数。）实现C也有一个最小量，但它是16，而且没有为尾部null保留空间。所以在实现C下，s的容量是16。实现D的最小缓
冲区大小也是16，包括尾部null的空间。当然，在这里区别出实现D是因为容量小于16的字符串使用的内存包含在本身字符串对象中。实现B没有最
小分配，在实现B下，s的容量是7。（为什么不是6或5。我不知道。我没有那么细致地读那些源代码，抱歉。）
如果你预计会有许多短字符串和两者中任何一个（1）你的释放环境内存非常小或（2）你关心引用的地点而且想要把字符串聚集在尽量少的页面
中，我觉得对于最小分配的各种各样的实现策略可能对你很重要。
很显然，string实现的自由度比乍看之下多得多，也很显然，不同的实现以不同的方式从它们的设计灵活性中得到好处。让我们总结一下：
● 字符串值可能是或可能不是引用计数的。默认情况下，很多实现的确是用了引用计数，但它们通常提供了关闭的方法，一般是通过预处理