《Effective STL》

haoji

器宏。条款13给了一个你可能要关闭的特殊环境的例子，但你也可能因为其他原因而要那么做。比如，引用计数只对频繁拷贝的字符串有
帮助，而有些程序不经常拷贝字符串，所以没有那个开销。
● string对象的大小可能从1到至少7倍char*指针的大小。
● 新字符串值的建立可能需要0、1或2次动态分配。
● string对象可能是或可能不共享字符串的大小和容量信息。
● string可能是或可能不支持每对象配置器。
● 不同实现对于最小化字符缓冲区的配置器有不同策略。
现在，不要误解我。我认为string是标准库中的最重要的组件之一，而且我鼓励你尽可能经常地使用它。例如条款13，专注于你为什么应该用string
来取代动态分配的字符数组。同时，如果你要有效使用STL，你需要小心string实现的多样性，特别是如果你正在写必须在不同STL平台上运行的代
码并且你面临严格的性能需求。
而且，string好像很简单。谁会想到它的实现可以如此有趣？

haoji

Center of STL Study
——最优秀的STL学习网站
条款16: 如何将vector和string的数据传给遗留的API
因为C++语言已经在1998年标准化，C++的中坚分子在努力推动程序员从数组转到vector时就没什么顾虑了。
同样明显的情况也发生于尝试使开发者从char*指针迁移到string对象的过程中。有很好的理由来做这些转变，
包括可以消除常见的编程错误（参见条款13），而且有机会获得STL算法的全部强大能力（比如参见条款
31）。
但是，障碍还是有的，最常见的一个就是已经存在的遗留的C风格API接受的是数组和char*指针，而不是
vector和string对象。这样的API函数还将会存在很长时间，如果我们要有效使用STL的话，就必须和它们和平
共处。
幸运的是，这很容易。如果你有一个vector对象v，而你需要得到一个指向v中数据的指针，以使得它可以被当
作一个数组，只要使用&v[0]就可以了。对于string对象s，相应的咒语是简单的s.c_str()。但是继续读下去。如
广告中难懂的条文时常指出的，必然会有几个限制。
给定一个
vector<int> v;
表达式v[0]生产一个指向vector中第一个元素的引用，所以，&v[0]是指向那个首元素的指针。vector中的元素
被C++标准限定为存储在连续内存中，就像是一个数组，所以，如果我们想要传递v给这样的C风格的API：
void doSomething(const int* pInts, size_t numInts);
我们可以这么做：
doSomething(&v[0], v.size());
也许吧。可能吧。唯一的问题就是，如果v是空的。如果这样的话，v.size()是0，而&v[0]试图产生一个指向根
本就不存在的东西的指针。这不是件好事。其结果未定义。一个较安全的方法是这样：
if (!v.empty()) {

haoji

doSomething(&v[0], v.size());
}
如果你在一个不好的环境中，你可能会碰到一些半吊子的人物，他们会告诉你说可以用v.begin()代替&v[0]，
因为（这些讨厌的家伙将会告诉你）begin返回指向vector内部的迭代器，而对于vector，其迭代器实际上是指
针。那经常是正确的，但正如条款50所说，并不总是如此，你不该依赖于此。begin的返回类型是iterator，而
不是一个指针，当你需要一个指向vector内部数据的指针时绝不该使用begin。如果你基于某些原因决定键入v.
begin()，就应该键入&*v.begin()，因为这将会产生和&v[0]相同的指针，这样可以让你有更多的打字机会，而
且让其他要弄懂你代码得人感觉到更晦涩。坦白地说，如果你正在和告诉你使用v.begin()代替&v[0]的人打交
道的话，你该重新考虑一下你的社交圈了。（译注：在VC6中，如果用v.begin()代替&v[0]，编译器不会说什
么，但在VC7和g++中这么做的话，就会引发一个编译错误）
类似从vector上获取指向内部数据的指针的方法，对string不是可靠的，因为（1）string中的数据并没有保证被
存储在独立的一块连续内存中，（2）string的内部表示形式并没承诺以一个null字符结束。这解释了string的成
员函数c_str存在的原因，它返回一个按C风格设计的指针，指向string的值。因此我们可以这样传递一个string
对象s给这个函数，
void doSomething(const char *pString);
像这样：
doSomething(s.c_str());
即使是字符串的长度为0，它都能工作。在那种情况下，c_str将返回一个指向null字符的指针。即使字符串内
部自己内含null时，它同样能工作。但是，如果真的这样，doSomething很可能将第一个内含的null解释为字符
串结束。string对象不在意是否容纳了结束符，但基于char*的C风格API在意。
再看一下doSomething的声明：
void doSomething(const int* pints, size_t numInts);
void doSomething(const char *pString);
在两种形式下，指针都被传递为指向const的指针。vector和string的数据只能传给只读取而不修改它的API。这
到目前为止都是最安全的事情。对于string，这也是唯一可做的，因为没有承诺说c_str产生的指针指在string数
据的内部表示形式上；它可以返回一个指针指向数据的一个不可修改的拷贝，这个拷贝满足C风格API对格式
的要求。（如果这个恐吓令你毛骨悚然的话，还请放心吧，因为它也许不成立。我没听说目前哪个库的实现

haoji

使用了这个自由权的。）
对于vector，有更多一点点灵活性。如果你将v传给一个修改其元素的C风格API的话，典型情况都是没问题，
但被调用的函数绝不能试图改变vector中元素的个数。比如，它绝不能试图在vector还未使用的容量上“创
建”新的元素。如果这么干了，v的内部状态将会变得不一致，因为它再也不知道自己的正确大小了。v.size()
将会得到一个不正确的结果。并且，如果被调用的函数试图在一个大小和容量（参见条款14）相等的vector上
追加数据的话，真的会发生灾难性事件。我甚至根本就不愿去想象它。实在太可怕了。
你注意到我在前面的“典型情况都是没问题”那句话用的是“典型地”一词吗？你当然注意到了。有些
vector对其数据有些额外的限制，而如果你把一个vector传递给需要修改vector数据的API，你一定要确保这些
额外限制继续被满足。举个例子，条款23解释了有序vector经常可以作为关联容器的替代品，但对这些vector
而言，保持顺序非常重要。如果你将一个有序vector传给一个可能修改其数据的API函数，你需要重视vector
在调用返回后不再保持顺序的情况。
如果你想用C风格API返回的元素初始化一个vector，你可以利用vector和数组潜在的内存分布兼容性将存储
vecotr的元素的空间传给API函数：
// C API：此函数需要一个指向数组的指针，数组最多有arraySize个double
// 而且会对数组写入数据。它返回写入的double数，不会大于arraySize
size_t fillArray(double *pArray, size_t arraySize);
vector<double> vd(maxNumDoubles); // 建立一个vector，
// 它的大小是maxNumDoubles
vd.resize(fillArray(&vd[0], vd.size())); // 让fillArray把数据
// 写入vd，然后调整vd的大小
// 为fillArray写入的元素个数
这个技巧只能工作于vector，因为只有vector承诺了与数组具有相同的潜在内存分布。但是，如果你想用来自
C风格API的数据初始化string对象，也很简单。只要让API将数据放入一个vector<char>，然后从vector中将数
据拷到string：
// C API：此函数需要一个指向数组的指针，数组最多有arraySize个char
// 而且会对数组写入数据。它返回写入的char数，不会大于arraySize
size_t fillString(char *pArray, size_t arraySize);
vector<char> vc(maxNumChars); // 建立一个vector，
// 它的大小是maxNumChars
size_t charsWritten = fillString(&vc[0], vc.size()); // 让fillString把数据写入vc
string s(vc.begin(), vc.begin()+charsWritten); // 从vc通过范围构造函数

haoji

// 拷贝数据到s（参见条款5）
事实上，让C风格API把数据放入一个vector，然后拷到你实际想要的STL容器中的主意总是有效的：
size_t fillArray(double *pArray, size_t arraySize); // 同上
vector<double> vd(maxNumDoubles); // 一样同上
vd.resize(fillArray(&vd[0], vd.size()));
deque<double> d(vd.begin(), vd.end()); // 拷贝数据到deque
list<double> l(vd.begin(), vd.end()); // 拷贝数据到list
set<double> s(vd.begin(), vd.end()); // 拷贝数据到set
此外，这也提示了vector和string以外的STL容器如何将它们的数据传给C风格API。只要将容器的每个数据拷
到vector，然后将它们传给API：
void doSomething(const int* pints, size_t numInts); // C API (同上)
set<int> intSet; // 保存要传递给API数据的set
...
vector<int> v(intSet.begin(), intSet.end()); // 拷贝set数据到vector
if (!v.empty()) doSomething(&v[0], v.size()); // 传递数据到API
你也可以将数据拷进一个数组，然后将数组传给C风格的API，但你为什么想这样做？除非你在编译期就知道
容器的大小，否则你不得不分配动态数组，而条款13解释了为什么你应该总是使用vector来取代动态分配的数
组。

haoji

Center of STL Study
——最优秀的STL学习网站
条款17：使用“交换技巧”来修整过剩容量
假设你正在为TV游戏秀《Give Me Lots Of Money — Now!》写支持软件，而且你要跟踪可能的竞争者，你把
它们保存在一个vector中：
class Contestant {...};
vector<Contestant> contestants;
当这个秀需要一个新的竞争者时，它将被申请者淹没，你的vector很快获得很多元素。但是秀的制作人只要
预期的游戏者，一个相对少数符合条件的候选人移到vector前端（可能通过partial_sort或partition——参见条款
31），如果不是候选人的就从vector删除（典型的通过调用erase的区间形式——参见条款5）。这很好地减少
了vector的大小，但没有减少它的容量。如果你的vector有时候容纳了10万个的可能的候选人，它的容量会继
续保持在至少100,000，即使后来它只容纳10个。
要避免你的vector持有它不再需要的内存，你需要有一种方法来把它从曾经最大的容量减少到它现在需要的
容量。这样减少容量的方法常常被称为“收缩到合适（shrink to fit）”。收缩到合适很容易实现，但代码
——我该怎么说？——比直觉的要少。让我演示给你看，然后我会解释它是怎么工作的。
这是你怎么修整你的竞争者vector过剩容量的方法：
vector<Contestant>(contestants).swap(contestants);
表达式vector<Contestant>(contestants)建立一个临时vector，它是contestants的一份拷贝：vector的拷贝构造函数
做了这个工作。但是，vector的拷贝构造函数只分配拷贝的元素需要的内存，所以这个临时vector没有多余的
容量。然后我们让临时vector和contestants交换数据，这时我们完成了，contestants只有临时变量的修整过的容
量，而这个临时变量则持有了曾经在contestants中的发胀的容量。在这里（这个语句结尾），临时vector被销
毁，因此释放了以前contestants使用的内存。瞧！收缩到合适。
同样的技巧可以应用于string：
string s;
... // 使s变大，然后删除所有

haoji

// 它的字符
string(s).swap(s); // 在s上进行“收缩到合适”
现在，语言警察要求我告诉你并没有保证这个技术会真的消除多余的空间。如果vector和string想要的话，实
现可以自由地给予它们过剩的空间，而且有时候它们想要。比如，它们可能必须有一个最小容量限制，或者
它们可能强制vector或string的容量是2的整数次方。（在我的经历中，这样不规则的string实现比vector实现更
常见。例子参见条款15。）这近似于“收缩到合适”，然而，并不是真的意味着“使容量尽可能小”，它意
味着“使容量和这个实现可以尽量给容器的当前大小一样小”。但是，只要没有切换不同的STL实现，这是
你能做的最好的方法。所以当你想对vector和string进行“收缩到合适”时，就考虑“交换技巧”。
另外，交换技巧的变体可以用于清除容器和减少它的容量到你的实现提供的最小值。你可以简单地和一个默
认构造的临时vector或string做个交换：
vector<Contestant> v;
string s;
... // 使用v和s
vector<Contestant>().swap(v); // 清除v而且最小化它的容量
string().swap(s); // 清除s而且最小化它的容量

haoji

Center of STL Study
——最优秀的STL学习网站
条款18：避免使用vector<bool>
做为一个STL容器，vector<bool>确实只有两个问题。第一，它不是一个STL容器。第二，它并不容纳bool。
除此以外，就没有什么要反对的了。
一个东西不能成为STL容器只因为会有人会说它是。一个东西要成为STL容器就必须满足所有在C++标准23.1
节中列出的容器必要条件。在这些要求中有这样一条：如果c是一个T类型对象的容器，且c支持operator[]，
那么以下代码必须能够编译：
T *p = &c[0]; // 无论operator[]返回什么，
// 都可以用这个地址初始化一个T*
换句话说，如果你使用operator[]来得到Container<T>中的一个T对象，你可以通过取它的地址而获得指向那
个对象的指针。（假设T没有倔强地重载一些操作符。）然而如果vector<bool>是一个容器，这段代码必须能
够编译：
vector<bool> v;
bool *pb = &v[0]; // 用vector<bool>:perator[]返回的
// 东西的地址初始化一个bool*
但它不能编译。因为vector<bool>是一个伪容器，并不保存真正的bool，而是打包bool以节省空间。在一个典
型的实现中，每个保存在“vector”中的“bool”占用一个单独的比特，而一个8比特的字节将容纳8
个“bool”。在内部，vector<bool>使用了与位域（bitfield）等价的思想来表示它假装容纳的bool。
正如bool，位域也只表现为两种可能的值，但真的bool和化装成bool的位域之间有一个重要的不同：你可以创
建指向真的bool的指针，但却禁止有指向单个比特的指针。
引用单个比特也是禁止的，这为vector<bool>接口的设计摆出了难题。因为vector<T>:perator[]的返回值应该
是T&。如果vector<bool>真正容纳bool，这不成问题，但因为它没有，vector<bool>:perator[]需要返回指向
一个比特的引用，而并不存在这样的东西。
为了解决这个难题，vector<boo>:perator[]返回一个对象，其行为类似于比特的引用，也称为代理对象。
（如果仅使用STL，你并不需要明白什么是代理对象，但它是一项值得了解的C++技术。关于代理对象的信

haoji

息，参考《More Effective C++》的条款30，还有Gamma等人的《设计模式》[6]中的“Proxy”章节。）深入
本质来看，vector<bool>看起来像这样：
template <typename Allocator>
vector<bool, Allocator> {
public:
class reference {...}; // 用于产生引用独立比特的代理类
reference operator[](size_type n); // operator[]返回一个代理
...
}
现在，这段代码不能编译的原因就很明显了：
vector<bool> v;
bool *pb = &v[0]; // 错误！右边的表达式是
// vector<bool>::reference*类型，
// 不是bool*
因为它不能编译，所以vector<bool>不满足STL容器的必要条件。是的，vector<bool>是在标准中，是的，它
几乎满足了所有STL容器的必要条件，但是几乎还不够好。你写的有关STL容器的模板越多，会越深刻地认识
到这一点。那天会来的。我保证，当你会写出一个模板，它只在取容器元素的地址时会产生一个指向包含类
型的指针时才能工作，到那时，你将突然明白容器和几乎是容器之间的区别。
也许你想知道为什么vector<bool>存在于标准中，而它并不是一个容器。答案是与一个失败的高贵实验有
关，但让我们推迟一下那个讨论，我有一个更紧迫的问题。如果vector<bool>应避免，因为它不是一个容
器，那当我需要一个vector<bool>时应该用什么？
标准库提供了两个替代品，它们能满足几乎所有需要。第一个是deque<bool>。deque提供了几乎所有vector所
提供的（唯一值得注意的是reserve和capacity），而deque<bool>是一个STL容器，它保存真正的bool值。当
然，deque内部内存不是连续的。所以不能传递deque<bool>中的数据给一个希望得到bool数组的C API[1]（参
见条款16），但你也不能让vector<bool>做这一点，因为没有可移植的取得vector<bool>中数据的方法。（条
款16中用于vector的技术不能在vector<bool>上通过编译，因为它们依赖于能够取得指向容器中包含的元素类
型的指针。我提到过vector<bool>中不保存bool值吧？）
第二个vector<bool>的替代品是bitset。bitset不是一个STL容器，但它是C++标准库的一部分。与STL容器不
同，它的大小（元素数量）在编译期固定，因此它不支持插入和删除元素。此外，因为它不是一个STL容
器，它也不支持iterator。但就像vector<bool>，它使用一个压缩的表示法，使得它包含的每个值只占用一比

haoji

特。它提供vector<bool>特有的flip成员函数，还有一系列其他操作位集（collection of bits）所特有的成员函
数。如果不在乎没有迭代器和动态改变大小，你也许会发现bitset正合你意。
现在我们来讨论那个失败的高贵实验，它遗留下的残渣就是STL非容器的vector<bool>。我前面提到代理对象
在C++软件开发中十分有用。C++标准委员会的成员当然也明白，他们决定开发vector<bool>做为说明STL可
以支持包含通过代理访问元素的容器的演示。它们的理由很从分，有了这个例子在标准中，开发者将有一个
现成的参考来实现自己的基于代理的容器。
唉，他们发现的是不可能创建满足所有STL容器的需要的基于代理的容器。但因为某种原因，他们没有尝试
在标准中再开发一个。你可以去推测为什么保留vector<bool>，但现实地说，这没关系。重要的是：
vector<bool>不满足STL容器的必要条件，你最好不要使用它；而deque<bool>和bitset是基本能满足你对
vector<bool>提供的性能的需要的替代数据结构。
[1] 这可能是C99 API，因为bool只在这个版本的C语言中才加入。