《Effective STL》 - [美] Scott Meyers

Z-Library: 《中文版Effective STL:50条有效使用STL的经验 (技术经典著作大系)》

引言

你已经熟悉STL了。你知道怎样创建容器、怎样遍历容器中的内容，知道怎样添加和删除元素，以及如何使用常见的算法，比如find和sort。但是你并不满意。你总是感到自己还不能充分地利用STL。本该很简单的任务却并不简单；本该很直接的操作却要么泄漏资源，要么结果不对；本该更有效的过程却需要更多的时间或内存，超出了你的预期。是的，你已经知道如何使用STL了，但是你并不能确定自己是否在有效地使用它。

本书中的信息将会使你成为一位更优秀的STL程序员；它会使你成为一位高效率、高产出的程序员；它还会使你成为一位快乐的程序员。使用STL很令人开心，但是有效地使用它则令人更开心，这种开心来源于它会使你有更多的时间离开键盘，因为你可能不相信自己会节省这么多时间。即便是对STL粗略浏览一遍，也能发现这是一个非常酷的库，但你可能想象不到实际上它还要酷得多（无论是深度还是广度）。本书的一个主要目标是向你展示这个库是多么令人惊奇，因为在我从事程序设计近三十年来，我从来没看到过可以与STL相媲美的代码库。可能你也没见过。

定义、使用和扩展STL

STL之所以存在扩展，其中一个原因是，STL的设计目的就是为了便于扩展。但在本书中，我将把焦点放在如何使用STL上，而不是如何向其中添加新的部件。比如，你会发现，我将很少讲述如何编写自己的算法，对于如何编写新的容器和迭代器也没有给出任何建议。我相信，在考虑增强STL的能力之前，首先重要的是掌握STL已经提供了什么，而这正是本书的焦点所在。

术语，术语，术语

vector、string、deque 和 list 被称为标准序列容器。标准关联容器是 set、multiset、map 和 multimap。

注

根据迭代器所支持的操作，可以把迭代器分为五类。简单来说，输入迭代器（input iterator）是只读迭代器，在每个被遍历到的位置上只能被读取一次。输出迭代器（output iterator）是只写迭代器，在每个被遍历到的位置上只能被写入一次。输入和输出迭代器的模型分别是建立在针对输入和输出流（例如文件）的读写操作的基础上的。所以不难理解，输入和输出迭代器最常见的表现形式是istream_iterator和ostream_iterator。

前向迭代器 （forward iterator）兼具输入和输出迭代器的能力，但是它可以对同一个位置重复进行读和写。前向迭代器不支持operator--，所以它只能向前移动。所有的标准STL容器都支持比前向迭代器功能更强大的迭代器，但是，你在第25条中可以看到，散列容器的一种设计会产生前向迭代器。单向链表容器（见第50条）也提供了前向迭代器。

双向迭代器 （bidirectional iterator）很像前向迭代器，只是它们向后移动和向前移动同样容易。标准关联容器都提供了双向迭代器。list也是如此。

随机访问迭代器 （random access iterator）有双向迭代器的所有功能，而且，它还提供了“迭代器算术”，即向前或向后跳跃一步的能力。vector、string和deque都提供了随机访问迭代器。指向数组内部的指针对于数组来说也是随机访问迭代器。

所有重载了函数调用操作符（即operator()）的类都是一个函数子类（functor class）。从这些类创建的对象被称为函数对象（function object）或函数子（functor）。在STL中，大多数使用函数对象的地方同样也可以使用实际的函数，所以我经常使用“函数对象”（function object）这个术语既表示C++函数，也表示真正的函数对象。

函数bind1st和bind2nd被称为绑定器（binder）。

第1章 容器

第1条：慎重选择容器类型。

注

• 标准STL序列容器 ：vector、string、deque和list。

• 标准STL关联容器 ：set、multiset、map和multimap。

• 非标准序列容器slist和rope 。slist是一个单向链表，rope本质上是一“重型”string。（“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给了你多种选择。在STL以外，你还有更多的选择。在选择一个容器之前，请仔细考虑所有的选择。存在“默认的容器”吗？我可不这样认为。

第2条：不要试图编写独立于容器类型的代码。

即便是最热心地倡导独立于容器类型的代码的人也很快会意识到，试图编写对序列容器和关联容器都适用的代码几乎是毫无意义的。很多成员函数仅当其容器为某一种类型时才存在，例如，只有序列容器才支持push_front或push_back，只有关联容器才支持count和lower_bound，等等。即使是insert和erase这样的基本操作，也会随容器类型的不同而表现出不同的原型和语义。

面对现实吧：这么做不值得。不同的容器是不同的，它们有非常明显的优缺点。

它们并不是被设计来交换使用的，你无法掩盖这一点。如果你试图这样做，你只是在碰运气，而这种运气却是碰不到的。

第3条：确保容器中的对象副本正确而高效。

容器中保存了对象，但并不是你提供给容器的那些对象。而当从容器中取出一个对象时，你所取出的也并不是容器中所保存的那份。当向容器中加入对象时（通过如insert或push_back之类的操作），存入容器的是你所指定的对象的副本。当（通过如front或back之类的操作）从容器中取出一个对象时，你所得到的是容器中所保存的对象的副本。进去的是副本，出来的也是副本（copy in，copy out）。这就是STL的工作方式。

当然，在存在继承关系的情况下，复制动作会导致剥离（slicing）。也就是说，如果你创建了一个存放基类对象的容器，却向其中插入派生类的对象，那么在派生类对象（通过基类的复制构造函数）被复制进容器时，它所特有的部分（即派生类中的信息）将会丢失。“剥离”问题意味着向基类对象的容器中插入派生类对象几乎总是错误的。如果你希望插入后的对象仍然表现得像派生类对象一样，例如调用派生类的虚函数等，那么这种期望是错误的。

使复制动作高效、正确，并防止剥离问题发生的一个简单办法是使容器包含指针而不是对象。也就是说，使用Widget* 的容器，而不是Widget的容器。复制指针的速度非常快，并且总是会按你期望的方式进行（它复制构成指针的每一位），而且当它被复制时不会有任何剥离现象发生。不幸的是，指针的容器也有其自身的一些令人头疼的、与STL相关的问题。你可以参考第7条和第33条。如果你想避开这些使人头疼的问题，同时又想避免效率、正确性和剥离这些问题，你可能会发现智能指针（smart pointer）是一个诱人的选择。要想了解更多关于这种选择的知识，请参阅第7条。

提示

与数组相比，STL容器要聪明得多。你让它创建多少对象，它就（通过复制）创建多少对象，不会多，也不会少。你让它创建时它才创建，只有当你让它使用默认构造函数时它才会使用。没错，STL容器是在创建副本；确实是这样的，你需要明白这一点。但是，跟数组相比，它们仍是迈出了一大步。这是一个不可忽略的事实

第4条：调用empty而不是检查size()是否为0。

对任一容器c，下面的代码 if(c.size()== 0) 本质上与 if (c.empty()) 是等价的。既然如此，你或许会疑惑为什么要偏向于某一种形式，尤其是考虑到empty通常被实现为内联函数（inline function），并且它所做的仅仅是返回size是否为0。

你应该使用empty形式，理由很简单：empty对所有的标准容器都是常数时间操作，而对一些list实现，size耗费线性时间。

提示

不管发生了什么，调用empty而不是检查size==0是否成立总是没错的。所以，如果你想知道容器中是否含有零个元素，请调用empty。

第5条：区间成员函数优先于与之对应的单元素成员函数。

设计该小测验的第二个目的是为了揭示为什么区间成员函数（range member function）优先于与之对应的单元素成员函数。区间成员函数是指这样的一类成员函数，它们像STL算法一样，使用两个迭代器参数来确定该成员操作所执行的区间。如果不使用区间成员函数来解决本条款开篇时提出的问题，你就得写一个显式的循环。

太多的STL程序员滥用了copy，所以我刚才给出的建议值得再重复一下：通过利用插入迭代器的方式来限定目标区间的copy调用，几乎都应该被替换为对区间成员函数的调用。

注

现在回到assign的例子。我们已经给出了使用区间成员函数而不是其相应的单元素成员函数的原因：

• 通过使用区间成员函数，通常可以少写一些代码。

• 使用区间成员函数通常会得到意图清晰和更加直接的代码。

效率分析

第一种影响是不必要的函数调用。把numValues个元素逐个插入到v中导致了对insert的numValues次调用。而使用区间形式的insert，则只做了一次函数调用，节省了numValues－1次。当然，使用内联（inlining）可能会避免这样的影响，但是，实际中不见得会使用内联。只有一点是肯定的：使用区间形式的insert，肯定不会有这样的影响。

内联无法避免第二种影响，即把v中已有的元素频繁地移动到插入后它们所处的位置。每次调用insert把新元素插入到v中时，插入点后的每个元素都要向后移动一个位置，以便为新元素腾出空间。所以，位置p的元素必须被移动到位置p＋l，等等。在我们的例子中，我们向v的前端插入numValues个元素，这意味着v中插入点之后的每个元素都要向后移动numValues个位置。每次调用insert时，每个元素需向后移动一个位置，所以每个元素将移动numValues次。如果插入前v中有n个元素，就会有n* numValues次移动。在这个例子中，v中存储的是int类型，每次移动最终可能会归为调用memmove，可是如果v中存储的是Widget这样的用户自定义类型，则每次移动会导致调用该类型的赋值操作符或复制构造函数。（大多数情况下会调用赋值操作符，但每次vector中的最后一个元素被移动时，将会调用该元素的复制构造函数。）所以在通常情况下，把numValues个元素逐个插入到含有n个元素的vector<Widget>的前端将会有n* numValues次函数调用的代价：(n－1)* numValues次调用Widget的赋值操作符和numValues次调用Widget的复制构造函数。即使这些调用是内联的，你仍然需要把v中的元素移动numValues次。

与此不同的是，C++标准要求区间insert函数把现有容器中的元素直接移动到它们最终的位置上，即只需付出每个元素移动一次的代价。总的代价包括n次移动、numValues次调用该容器中元素类型的复制构造函数，以及调用该类型的赋值操作符。同每次插入一个元素的策略相比较，区间insert减少了n* (numValues－1)次移动。细算下来，这意味着如果numValues是100，那么区间形式的insert比重复调用单元素形式的insert减少了99％的移动。

在讲述单元素形式的成员函数和与其对应的区间成员函数相比较所存在的第三个效率问题之前，我需要做一个小小的更正。我在前面的段落中所写的是对的，的确是对的，但并不总是对的。区间insert函数仅当能确定两个迭代器之间的距离而不会失去它们的位置时，才可以一次就把元素移动到其最终位置上。这几乎总是可能的，因为所有的前向迭代器都提供了这样的功能，而前向迭代器几乎无处不在。标准容器的所有迭代器都提供了前向迭代器的功能。非标准散列容器的迭代器也是如此（见第25条）。指针作为数组的迭代器也提供了这一功能。实际上，不提供这一功能的标准迭代器仅有输入和输出迭代器。所以，我所说的是正确的，除非传入区间形式insert的是输入迭代器（如istream_iterator，见第6条）。仅在这样的情况下，区间insert也必须把元素一步步移动到其最终位置上，因而它的优势就丧失了。（对于输出迭代器不会产生这个问题，因为输出迭代器不能用来标明一个区间。）

不明智地使用重复的单元素插入操作而不是一次区间插入操作，这样所带来的最后一个性能问题跟内存分配有关，尽管它同时还伴有讨厌的复制问题。在第14条将会指出，如果试图把一个元素插入到vector中，而它的内存已满，那么vector将分配具有更大容量（capacity）的新内存，把它的元素从旧内存复制到新内存中，销毁旧内存中的元素，并释放旧内存。然后它把要插入的元素加入进来。第14条还解释了多数vector实现每次在内存耗尽时，会把容量加倍，因此，插入numValues个新元素最多可导致log<sub>2</sub>numValues次新的内存分配。第14条指出，表现出这种行为的vector实现是存在的，因此，把1000个元素逐个插入可能会导致10次新的内存分配（包括低效的元素复制）。与之对应（而且，到现在为止也可以预见），使用区间插入的方法，在开始插入前可以知道自己需要多少新内存（假定给它的是前向迭代器），所以不必多次重新分配vector的内存。可以想见，这一节省是很可观的。

提示

现在你明白了，优先选择区间成员函数而不是其对应的单元素成员函数有三条充分的理由：区间成员函数写起来更容易，更能清楚地表达你的意图，而且它们表现出了更高的效率。这是很难被打败的三驾马车。

第6条：当心C++编译器最烦人的分析机制。

注

list<int> data(istream iterator<int>(dataFile), istream_iterator<int>()); //小心!结果不会是你所想象的那样

请你注意了。这声明了一个函数data，其返回值是list<int>。这个data函数有两个参数：

• 第一个参数的名称是dataFile。它的类型是istream_iterator<int>。dataFile两边的括号是多余的，会被忽略。

• 第二个参数没有名称。它的类型是指向不带参数的函数的指针，该函数返回一个istream_iterator<int>。

这令人吃惊，对吧？但它却与C++中的一条普遍规律相符，即尽可能地解释为函数声明。

注

所有这些都很有意思（通过它自己的歪曲的方式），但这并不能帮助我们做自己想做的事情。我们想用文件的内容初始化list<int>对象。现在我们已经知道必须绕过某一种分析机制，剩下的事情就简单了。把形式参数的声明用括号括起来是非法的，但给函数参数加上括号却是合法的，所以通过增加一对括号，我们强迫编译器按我们的方式来工作：

list<int> data((istream iterator<int>(dataFile)), istream_iterator<int>()); //注意list构造函数的第一参数两边的括号

注

更好的方式是在对data的声明中避免使用匿名的istream_iterator对象（尽管使用匿名对象是一种趋势），而是给这些迭代器一个名称。下面的代码应该总是可以工作的：

ifstream dataFile("ints.dat");
istream_iterator<int> dataBegin(dataFile);
istream_iterator<int> dataEnd;
list<int> data(dataBegin, dataEnd);

提示

使用命名的迭代器对象与通常的STL程序风格相违背，但你或许觉得为了使代码对所有编译器都没有二义性，并且使维护代码的人理解起来更容易，这一代价是值得的。

第7条：如果容器中包含了通过new操作创建的指针，切记在容器对象析构前将指针delete掉。

STL中的容器相当“聪明”。它们提供了迭代器，以便进行向后和向前的遍历（通过begin、end、rbegin等）；它们告诉你所包含的元素类型（通过它们的value_type类型定义）；在插入和删除的过程中，它们自己进行必要的内存管理；它们报告自己有多少对象，最多能容纳多少对象（分别通过size和max_size）；当然，当它们自身被析构时，它们自动析构所包含的每个对象。

有了这么“聪明”的容器，许多程序员不再考虑自己做善后清理工作。更糟的是，他们认为，容器会考虑为他们做这些事情。很多情况下，他们是对的。但当容器包含的是通过new的方式而分配的指针时，他们这么想就不正确了。没错，指针容器在自己被析构时会析构所包含的每个元素，但指针的“析构函数”不做任何事情！它当然也不会调用delete。

提示

• 永远都不要错误地认为：你可以通过创建auto_ptr的容器使指针被自动删除。这个想法很可怕，也很危险。我将在第8条中解释为什么你应该避免这样做。

• 你所要记住的是：STL容器很智能，但没有智能到知道是否该删除自己所包含的指针的程度。当你使用指针的容器，而其中的指针应该被删除时，为了避免资源泄漏，你必须或者用引用计数形式的智能指针对象（比如Boost的shared_ptr）代替指针，或者当容器被析构时手工删除其中的每个指针。

• 最后，可能你会想到，既然像DeleteObject这样的结构能使指针容器（其中的指针指向有效的对象）避免资源泄漏更加容易，那么，创建一个类似的DeleteArray结构，对于元素为指向数组的指针的容器，使它们避免资源泄漏也应该是可能的。这当然是可能的，但是否可取则是另一回事。第13条解释了为什么动态分配的数组几乎总是不如vector和string对象。所以在坐下来写DeleteArray前，先看看第13条。或许你会发现你永远也不会用到DeleteArray结构。

第8条：切勿创建包含auto_ptr的容器对象。

现在我先说它的一个缺点。理解这一缺点不需要auto_ptr的知识，甚至不需要容器的知识：COAP是不可移植的。它怎么可以移植呢？C++标准都禁止它，好的STL平台已经做到了这一点。有理由相信，随着时间的推进，现在没有在这一点上支持标准的STL平台将会变得更加符合标准，那时，使用COAP的代码将变得比现在更加不可移植。如果你看重可移植性（你应该这样），就应该放弃COAP，因为它们不能通过可移植性测试。

或许你对可移植性不太关心。如果是这样，那我就告诉你复制auto_ptr意味着什么，这会很特别——有些人会说很古怪。当你复制一个auto_ptr时，它所指向的对象的所有权被移交到拷入的auto_ptr上，而它自身被置为NULL。你理解得对，复制一个auto_ptr意味着改变它的值。

提示

如果你的目标是包含智能指针的容器，这并不意味着你要倒霉。包含智能指针的容器是没有问题的，第50条中会指出你能找到在STL容器中工作得很好的智能指针。问题的根源只是在于auto_ptr不是这样的智能指针。它根本就不是！

第9条：慎重选择删除元素的方法。

注

如果你有一个连续内存的容器（vector、deque或string——见第1条），那么最好的办法是使用erase-remove习惯用法（见第32条）：

c.erase(remove(c.begin(), c.end(), 1963), c.end()); //当c是vector、string或deque时，erase-remove习惯用法是删除特定值的元素的最好办法

对list，这一办法同样适用。但正如第44条所指出的，list的成员函数remove更加有效：

c.remove(1963); //当c是list时，remove成员函数//是删除特定值的元素的最好办法。

当c是标准关联容器（例如set、multiset、map或multimap）时，使用任何名为remove的操作都是完全错误的。这样的容器没有名为remove的成员函数，使用remove算法可能会覆盖容器的值（见第32条），同时可能会破坏容器。（细节请参考第22条，那里解释了为什么试图对map和multimap使用remove不能编译，而试图对set和multiset使用remove时可能编译通不过。）

对于关联容器，解决问题的正确方法是调用erase：

c.erase(1963); //当c是标准关联容器时，erase成员函数是删除特定值元素的最好办法。

这样做不仅是正确的，而且是高效的，只需要对数时间开销。（对序列容器的基于remove的技术需要线性时间。）而且，关联容器的erase成员函数还有另外一个优点，即它是基于等价（equivalence）而不是相等（equality）的，这一区别的重要性将在第19条中解释。

现在给我们带来麻烦的是vector、string和deque。我们不能再使用erase-remove习惯用法了，因为没办法使erase或remove向日志文件中写信息。而且我们不能使用刚才为关联容器设计的循环，因为对vector、string和deque，它会导致不确定的行为！记住，对这类容器，调用erase不仅会使指向被删除元素的迭代器无效，也会使被删除元素之后的所有迭代器都无效。在我们的例子中，这包括i之后的所有迭代器。采用i++、++i或你所能想象得出的其他形式都无济于事，因为它们都会导致迭代器无效。

提示

要删除容器中有特定值的所有对象：

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

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

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

• 要删除容器中满足特定判别式（条件）的所有对象：

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

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

  3. 如果容器是一个标准关联容器，则使用remove_copy_if和swap，或者写一个循环来遍历容器中的元素，记住当把迭代器传给erase时，要对它进行后缀递增。

• 要在循环内部做某些（除了删除对象之外的）操作：

  1. 如果容器是一个标准序列容器，则写一个循环来遍历容器中的元素，记住每次调用erase时，要用它的返回值更新迭代器。

  2. 如果容器是一个标准关联容器，则写一个循环来遍历容器中的元素，记住当把迭代器传给erase时，要对迭代器做后缀递增。

第10条：了解分配子（allocator）的约定和限制。

提示

乌拉！我们对分配子特性的研究终于结束了。现在让我们总结一下如果你希望编写自定义的分配子，都需要记住哪些内容：

• 你的分配子是一个模板，模板参数T代表你为它分配内存的对象的类型。

• 提供类型定义pointer和reference，但是始终让pointer为T* ，reference为T&。

• 千万别让你的分配子拥有随对象而不同的状态（per-object state）。通常，分配子不应该有非静态的数据成员。

• 记住，传给分配子的allocate成员函数的是那些要求内存的对象的个数，而不是所需的字节数。同时要记住，这些函数返回T* 指针（通过pointer类型定义），即使尚未有T对象被构造出来。

• 一定要提供嵌套的rebind模板，因为标准容器依赖该模板。

第11条：理解自定义分配子的合理用法。

提示

正如这些例子所显示的，分配子在许多场合下都非常有用。只要你遵守了同一类型的分配子必须是等价的这一限制要求，那么，当你使用自定义的分配子来控制通用的内存管理策略的时候，或者在聚集成员关系的时候，或者在使用共享内存和其他特殊堆的时候，就不会陷入麻烦。

第12条：切勿对STL容器的线程安全性有不切实际的依赖。

因为Lock对象在其析构函数中释放容器的互斥体，所以很重要的一点是，当互斥体应该被释放时Lock就要被析构。为了做到这一点，我们创建了一个新的代码块（block），在其中定义了Lock，当不再需要互斥体时就结束该代码块。看起来好像是我们把“调用releaseMutexFor”这一任务换成了“结束代码块”，事实上这种说法是不确切的。如果我们忘了为Lock创建新的代码块，则互斥体仍然会被释放，只不过会晚一些——当控制到达包含Lock的代码块末尾时。而如果我们忘记了调用releaseMutexFor，那么我们永远也不会释放互斥体。

而且，基于Lock的方案在有异常发生时也是强壮的。C++保证，如果有异常被抛出，局部对象会被析构，所以，即便在我们使用Lock对象的过程中有异常抛出，Lock仍会释放它所拥有的互斥体（已经证实存在一个漏洞。如果根本没有捕获异常，那么程序将终止。在这种情况下，局部对象（如lock）可能还没有调用它们的析构函数。有些编译器会这样，有些编译器不会这样，这两种情况都是有效的） 。如果我们依赖于手工调用getMutexFor和releaseMutexFor，那么，当在调用getMutexFor之后而在调用releaseMutexFor之前有异常被抛出时，我们将永远也无法释放互斥体。

提示

异常和资源管理虽然很重要，但它们不是本条款的主题。本条款是讲述STL中的线程安全性的。当涉及STL容器和线程安全性时，你可以指望一个STL库允许多个线程同时读一个容器，以及多个线程对不同的容器做写入操作。你不能指望STL库会把你从手工同步控制中解脱出来，而且你不能依赖于任何线程支持。

第2章　vector和string

第13条：vector和string优先于动态分配的数组。

每次当你发现自己要动态地分配一个数组时（例如想写"new T[...]"时），你都应该考虑用vector和string来代替。（一般情况下，当T是字符类型时用string，否则用vector。不过在本条款中，我们还会见到一种特殊的情形，在这种情形下，vector<char>可能是一种更为合理的选择。）vector和string消除了上述的负担，因为它们自己管理内存。当元素被加入到容器中时，它们的内存会增长；而当vector或string被析构时，它们的析构函数会自动析构容器中的元素并释放包含这些元素的内存。

提示

总结起来很简单，如果你正在动态地分配数组，那么你可能要做更多的工作。为了减轻自己的负担，请使用vector或string。

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

注

reserve成员函数能使你把重新分配的次数减少到最低限度，从而避免了重新分配和指针／迭代器／引用失效带来的开销。但是，在解释reserve怎样做到这一点之前，我将简单概括一下4个相互关联，但有时会被混淆的成员函数。在标准容器中，只有vector和string提供了所有这4个函数。

• size()告诉你该容器中有多少个元素。它不会告诉你该容器为自己所包含的元素分配了多少内存。

• capacity()告诉你该容器利用已经分配的内存可以容纳多少个元素。这是容器所能容纳的元素总数，而不是它还能容纳多少个元素。如果你想知道一个vector有多少未被使用的内存，你就得从capacity()中减去size()。如果size和capacity返回同样的值，就说明容器中不再有剩余空间了，因此下一个插入操作（通过insert或push_back等）将导致上面所讲过的重新分配过程。

• resize(Container::size_type n)强迫容器改变到包含n个元素的状态。在调用resize之后，size将返回n。如果n比当前的大小（size）要小，则容器尾部的元素将会被析构。如果n比当前的大小要大，则通过默认构造函数创建的新元素将被添加到容器的末尾。如果n比当前的容量要大，那么在添加元素之前，将先重新分配内存。

• reserve(Container::size_type n)强迫容器把它的容量变为至少是n，前提是n不小于当前的大小。这通常会导致重新分配，因为容量需要增加。（如果n比当前的容量小，则vector忽略该调用，什么也不做；而string则可能把自己的容量减为size()和n中的最大值，但是string的大小肯定保持不变。以我的经验，使用reserve从string中除去多余的容量通常不如使用“swap技巧”。“swap技巧”是第17条的主题。）

提示

回到本条款的要点上。通常有两种方式来使用reserve以避免不必要的重新分配。第一种方式是，若能确切知道或大致预计容器中最终会有多少元素，则此时可使用reserve。在这种情况下，就像上面代码中的vector一样，你可以简单地预留适当大小的空间。第二种方式是，先预留足够大的空间（根据你的需要而定），然后，当把所有数据都加入以后，再去除多余的容量。要去除多余部分并不困难，但在这里我不想指出如何做，因为这其中有一个诀窍。要想学习这个诀窍，请参阅第17条。

第15条：注意string实现的多样性。

注

很明显，string的实现比乍看上去有更多的自由度；同样明显的是，不同的实现以不同的方式利用了这种设计上的灵活性。这些区别总结如下：

• string的值可能会被引用计数，也可能不会。很多实现在默认情况下会使用引用计数，但它们通常提供了关闭默认选择的方法，往往是通过预处理宏来做到这一点。第13条给出了你想将其关闭的一种特殊情况，但其他的原因也可能会让你这样做。比如，只有当字符串被频繁复制时，引用计数才有用，而有些应用并不经常复制内存，这就不值得使用引用计数了。

• string对象大小的范围可以是一个char* 指针的大小的1倍到7倍。

• 创建一个新的字符串值可能需要零次、一次或两次动态分配内存。

• string对象可能共享，也可能不共享其大小和容量信息。

• string可能支持，也可能不支持针对单个对象的分配子。

• 不同的实现对字符内存的最小分配单位有不同的策略。

提示

请不要误解我的意思。我认为string是标准库中最重要的部分之一，我鼓励你多使用它。比如，第13条就是讲述为什么你应该使用string来代替动态分配的字符数组。同时，如果你想有效地使用STL，那么，你需要知道string实现的多样性，尤其是当你编写的代码必须要在不同的STL平台上运行而你又面临着严格的性能要求的时候。而且，string看起来是这么简单，而谁又能想到它的实现会这么有趣呢？

第16条：了解如何把vector和string数据传给旧的API。

注

对于

vector<int> v;

表达式v[0]给出了一个引用，它是该矢量中的第一个元素，所以&v[0]是指向第一个元素的指针。C++标准要求vector中的元素存储在连续的内存中，就像数组一样。所以，如果我们希望把v传给一个如下所示的C API：

void doSomething(const int* plnts, size t numInts):

那我们可以这样做：

doSomething(&v[0], v.size());

这样或许能行。可能不会出错。唯一麻烦的地方在于，v可能是空的。如果是这样，那么v.size()会是零，&v[0]则试图产生一个指针，而该指针指向的东西并不存在。这可不好。这样的结果是不确定的。安全一点的方式是：

if (!v.empty()) {
  doSomething(&v[0], v.size())
};

在一个错误的环境中，你可能会遇到一些可疑的人，他们告诉你用v.begin()来代替&v[0]，因为（这些讨厌的人会告诉你）begin返回vector的迭代器，而对于vector来说，迭代器实际上就是指针。通常这是正确的，但正如第50条所指出的那样，事实并不总是这样的，你不应该依赖于这一点。begin的返回值是一个迭代器，不是指针；当你需要一个指向vector中的数据的指针时，你永远不应该使用begin。如果为了某种原因你决定用v.begin()，那么请使用&* v.begin()，因为这和&v[0]产生同样的指针，只是你要敲入更多的字符，而且别人想理解你的代码会更加困难。坦率地讲，如果你周围的人都告诉你使用v.begin()而不是&v[0]，那么，你应该重新考虑你周围的环境是否合适了。

这种得到容器中数据指针的方式对于vector是适用的，但对于string却是不可靠的。因为：（1）string中的数据不一定存储在连续的内存中；（2）string的内部表示不一定是以空字符结尾的。这也正说明了为什么在string中存在成员函数c_str。c_str函数返回一个指向字符串的值的指针，而且该指针可用于C。因此，我们可以把一个字符串s传给下面的函数：

void doSomething(const char* pString);

doSomething(s.c_str());

即使字符串的长度是零，这样做也是可以的。在这种情况下，c_str会返回一个指向空字符的指针。对字符串内部有空字符的情况也是可以的。但是，在这种情况下，doSomething会把内部的第一个空字符当作结尾的空字符。string对象中包含空字符没关系，但是对基于char* 的C API则不行。

第17条：使用“swap技巧”除去多余的容量。

注

按下面的做法，你可以从contestants矢量中除去多余的容量：

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

表达式vector<Contestant>(contestants)创建一个临时的矢量，它是contestants的副本：这是由vector的复制构造函数来完成的。然而，vector的复制构造函数只为所复制的元素分配所需要的内存，所以这个临时矢量没有多余的容量。然后我们把临时矢量中的数据和contestants中的数据做swap操作，在这之后，contestants具有了被去除之后的容量，即原先临时变量的容量，而临时变量的容量则变成了原先contestants臃肿的容量。到这时（在语句结尾），临时矢量被析构，从而释放了先前为contestants所占据的内存。乌拉！shrink-to-fit。

注

作为题外话，swap技巧的一种变化形式可以用来清除一个容器，并使其容量变为该实现下的最小值。只要与一个用默认构造函数创建的vector或string做交换（swap）就可以了：

vector<Contestant> v;
string s; //使用v和s
vector<Contestant>().swap(v); //清除v并把它的容量变为最小
string().swap(s); //清除s并把它的容量变为最小

提示

关于swap技巧，或者关于一般性的swap，我最后再说一句。在做swap的时候，不仅两个容器的内容被交换，同时它们的迭代器、指针和引用也将被交换（string除外）。在swap发生后，原先指向某容器中元素的迭代器、指针和引用依然有效，并指向同样的元素——但是，这些元素已经在另一个容器中了。

第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没有用非常规的方式对operator&做重载。）所以，如果vector<bool>是一个容器，那么下面这段代码必须可以被编译：

vector<bool>; //用vector<bool>::operator[]返回的
bool *pb = &v[0]; //变量的地址初始化一个bool*变量

但是它不能编译。不能编译的原因是，vector<bool>是一个假的容器，它并不真的储存bool，相反，为了节省空间，它储存的是bool的紧凑表示。在一个典型的实现中，储存在“vector”中的每个“bool”仅占一个二进制位，一个8位的字节可容纳8个“bool”。在内部，vector<bool>使用了与位域（bitfield）一样的思想，来表示它所存储的那些bool；实际上它只是假装存储了这些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中所含元素类型的指针。我不是已经提到过vector<bool>中并没有存储bool吗？）

第二种可以替代vector<bool>的选择是bitset。bitset不是STL容器，但它是标准C++库的一部分。与STL容器不同的是，它的大小（即元素的个数）在编译时就确定了，所以它不支持插入和删除元素。而且，因为它不是一个STL容器，所以它不支持迭代器。但是，与vector<bool>一样，它使用了一种紧凑表示，只为所包含的每个值提供一位空间。它提供了vector<bool>特有的flip成员函数，以及其他一些特有的、对位的集合有意义的成员函数。如果你不需要迭代器和动态地改变大小，那么你可能会发现bitset很适合你的需要。

现在我来介绍那个失败了的雄心勃勃的试验，正是这个试验把并非容器的vector<bool>留在了STL中。先前我曾经提到，代理对象在C++软件开发中经常会很有用。C++标准委员会的人很清楚这一点，所以他们决定开发vector<bool>，以演示STL如何支持“通过代理来存取其元素的容器”。他们说，C++标准中有了这个例子，于是，人们在实现自己的基于代理的容器时就有了一个现成的参考。

提示

然而，他们却发现，要创建一个基于代理的容器，同时又要求它满足STL容器的所有要求是不可能的。由于种种原因，他们失败了的尝试被遗留在标准中。人们可能会猜测为什么vector<bool>留了下来，但实际上，这无关紧要。重要的是：vector<bool>不完全满足STL容器的要求；你最好不要使用它；你可以用deque<bool>和bitset来替代它，这两个数据结构几乎能做vector<bool>所能做的一切事情。

第3章　关联容器

就像电影《绿野仙踪》中的多色马一样，关联容器是一些不同颜色的动物。没错，它们和序列容器有很多相同的特性，但在很多方面也有本质的不同。比如，它们会自动排序；它们按照等价（equivalence）而不是相等（equality）的标准来对待自己的内容；set和map不允许有重复的项目；map和multimap通常忽略它们所包含的每个对象中的一半。没错，关联容器是容器，但如果你能允许我把vector和string比作堪萨斯州的话，那么我们肯定不会还在堪萨斯州了。

第19条：理解相等（equality）和等价（equivalence）的区别。

在实际操作中，相等的概念是基于operator==的。如果表达式“x==y”返回真，则x和y的值相等，否则就不相等。这很直接明了，但是你脑子里应该记住，x和y有相等的值并不一定意味着它们的所有数据成员都有相等的值。比如，我们可能有一个Widget类，它在内部记录着自己最近一次被访问的时间：

class Widget {
public:
private:
  TimeStamp lastAccessed;

而我们可能有一个针对Widget的operator==，它忽略了这个域：

bool operator==(const Widget& lhs, const Widget& rhs) {
  //忽略了lastAccessed域的代码
}

在这种情况下，两个Widget即使有不同的lastAccessed域，它们也可以有相等的值。

等价关系是以“在已排序的区间中对象值的相对顺序”为基础的。如果你从每个标准关联容器（即set、multiset、map和multimap，排列顺序也是这些容器的一部分）的排列顺序来考虑等价关系，那么这将是非常有意义的。对于两个对象x和y，如果按照关联容器c的排列顺序，每个都不在另一个的前面，那么称这两个对象按照c的排列顺序有等价的值。这听起来很复杂，但其实不然。举例来说，考虑set<Widget>s。如果两个Widget w1和w2，在s的排列顺序中哪个也不在另一个的前面，那么，w1和w2对于s而言有等价的值。set<Widget>的默认比较函数是less<Widget>，而在默认情况下less<Widget>只是简单地调用了针对Widget的operator<，所以，如果下面的表达式结果为真，则w1和w2对于operator<有等价的值：

!(w1 < w2); //w1<w2 不为真
&& //而且
!(w2 < w1); //w2<w1 不为真

这里的含义是：如果两个值中的任何一个（按照一定的排序准则）都不在另一个的前面，那么这两个值（按照这一准则）就是等价的。

注

在一般情形下，一个关联容器的比较函数并不是operator<，甚至也不是less，它是用户定义的判别式（predicate）。（要想了解有关判别式的更多信息，请参见第39条。）每个标准关联容器都通过key_comp成员函数使排序判别式可被外部使用，所以，如果下面的表达式为true，则按照关联容器c的排序准则，两个对象x和y有等价的值：

!c.key_comp()(x,y)&& !c.key_comp()(y, x) //在c的排列顺序中，x在y之前1不为真，y在x之前也不为真

表达式!c.key_comp()(x,y)看起来很讨厌，但一旦你理解了c.key_comp返回一个函数（或者一个函数对象），它就不显得那么讨厌了。!c.key_comp()(x,y)仅仅是调用key_comp返回的函数（或函数对象），并以x和y作为传入参数。然后它把结果取反。只有当x按照c的排列顺序在y之前时，c.key_comp()(x,y)才返回真，所以，只有当x按照c的排列顺序不在y之前时，!c.key_comp()(x,y)才为真。

注

有了CIStringCompare，很容易就能建立一个不区分大小写的set<string>：

set<string, CiStringCompare> ciss; //ciss=“不区分大小写的字符串集”

如果我们把字符串“Persephone”和“persephone”插入到该集合中，则只有第一个字符串会被插入，因为第二个和第一个等价：

ciss.insert("Persephone"); //一个新元素被插入到集合中
ciss.insert("persephone"); //没有新元素被插入到集合中

如果我们用set的find成员函数来查找字符串“persephone”，则该查找会成功:

if (ciss.find("persephone") != ciss.end())...//该检查将成功

但如果我们使用非成员的6nd算法，则查找将失败:

if (find(ciss.begin(), ciss.end(), "persephone") != ciss.end())...//该检查将失败

这是因为“persephone”与“Persephone”等价（按照比较函数子CIStringCompare），但并不相等（因为string("persephone")!=string("Persephone")）。该例子从一个方面解释了为什么你应该遵循第44条中的建议，优先选用成员函数（像set::find）而不是与之对应的非成员函数（像find）。

标准关联容器总是保持排列顺序的，所以每个容器必须有一个比较函数（默认为less）来决定保持怎样的顺序。等价的定义正是通过该比较函数而确定的，因此，标准关联容器的使用者要为所使用的每个容器指定一个比较函数（用来决定如何排序）。如果该关联容器使用相等来决定两个对象是否有相同的值，那么每个关联容器除了用于排序的比较函数外，还需要另一个比较函数来决定两个值是否相等。（默认情况下，该比较函数应该是equal_to，但有趣的是，equal_to从来没有被用作STL的默认比较函数。当STL中需要相等判断时，一般的惯例是直接调用operator==。比如，非成员函数find算法就是这么做的。）

有趣的是，一旦你离开了排序的关联容器的领域，情况就发生了变化，相等与等价的问题可以被——也已经被——重新看待。对于非标准的（但使用很普遍的）基于散列表的关联容器，有两种常见的设计。一种是基于相等的，而另一种则是基于等价的。我鼓励你转过去读一读第25条，以便更多地了解这些容器和它们所采用的设计策略

提示

总之，使用单一的比较函数，并把等价关系作为判定两个元素是否“相同”的依据，使得标准关联容器避免了一大堆“若使用两个比较函数将带来的问题”。乍一看，它们的行为可能有些古怪（尤其是当你意识到成员的和非成员的find会返回不同的结果的时候），但从长远来看，这样做避免了在标准关联容器中混合使用相等和等价将会带来的混乱。

第20条：为包含指针的关联容器指定比较类型。

如果你想让string* 指针在集合中按字符串的值排序，那么你不能使用默认的比较函数子类(functor class)less<string* >。你必须自己编写比较函数子类，该类的对象以string* 指针为参数，并按照它们所指向的string的值进行排序。

这里的问题是，set模板的三个参数每个都是一个类型。不幸的是，stringPtrLess不是一个类型，它是一个函数。这就是为什么试图用stringPtrLess作为set的比较函数无法通过编译的原因。set不需要一个函数，它需要的是一个类型，并在内部用它创建一个函数。

哦，还有一件事情。本条款是关于包含指针的关联容器的，但它同样也适用于其他一些容器，这些容器中包含的对象与指针的行为相似，比如智能指针和迭代器。如果你有一个包含智能指针或迭代器的容器，那么你也要考虑为它指定一个比较类型。幸运的是，对指针的解决方案同样也适用于那些类似指针的对象。就像DereferenceLess适合作为包含T* 的关联容器的比较类型一样，对于容器中包含了指向T对象的迭代器或智能指针的情形，DereferenceLess也同样可用作比较类型。

第21条：总是让比较函数在等值情况下返回false。

很简单，结果是false。也就是说，该集合的结论是10A 和10B 不等价，从而不相同，因此，10B 将会被插入到容器中10A 的旁边。从技术角度来看，这会导致不确定的行为，但更普遍的后果是，会导致集合中有10的两份副本，这意味着它不再是一个集合！通过使用less_equal作为我们的比较类型，我们破坏了set容器！而且，任何一个比较函数，如果它对相等的值返回true，则都会导致同样的结果。相等的值按照定义却是不等价的。很酷，是不是？

为了避免跌入这个陷阱，你只要记住，比较函数的返回值表明的是按照该函数定义的排列顺序，一个值是否在另一个之前。相等的值从来不会有前后顺序关系，所以，对于相等的值，比较函数应当始终返回false。

提示

从技术上来说，用于对关联容器排序的比较函数必须为它们所比较的对象定义一个“严格的弱序化”（strict weak ordering）。（对于传递给像sort这类算法（见第31条）的比较函数也有同样的限制。）即，任何一个定义了“严格的弱序化”的函数必须对相同值的两个副本返回false。

第22条：切勿直接修改set或multiset中的键。

这是因为，对于一个map<K,V>或multimap<K,V>类型的对象，其中的元素类型是pair<const K,V>。因为键的类型是const K，所以它不能被修改。（喔，如果利用const_cast，你或许可以修改它，后面我们将会看到。不管你是否相信，有时你可能希望这样做。

但请注意，本条款的标题中并没有提到map或multimap。这是有原因的。正如上面的例子所演示的，直接修改键的值对map或multimap是行不通的（除非使用强制类型转换），但对set和multiset是可能的。对于set<T>或multiset<T>类型的对象，容器中元素的类型是T，而不是const T。因此，只要你愿意，你随时可以改变set或multiset中的元素，而无须任何强制类型转换。（实际上，事情并不是这么简单，但我们稍后再讨论这一点。没理由太着急。我们先爬行一段，然后再在碎玻璃上爬行。）

因为我们在这里所做的是修改雇员中与集合的排序方式无关的部分（雇员记录中不属于键的部分），所以这段代码不会破坏该集合。因此它是合法的。但使它合法就意味着set/multiset的元素不能为const。这解释了它们为什么不是const的原因。

因为set或multiset中的值不是const，所以，对这些值进行修改的代码可以通过编译。本条款的目的是提醒你，如果你改变了set或multiset中的元素，请记住，一定不要改变键部分（key part）——元素的这部分信息会影响容器的排序性。如果改变了这部分内容，那么你可能会破坏该容器，再使用该容器将导致不确定的结果，而错误的责任在于你。另一方面，这项限制只适用于被包含对象的键部分。对于被包含元素的其他部分，则完全是开放的；尽管修改吧！

因为标准的模棱两可，以及由此产生的不同理解，所以，试图修改set或multiset中元素的代码将是不可移植的。

注

啊哈，强制类型转换。我们已经看到，改变set或multiset中元素的非键部分是合理的，所以我觉得有必要向你演示一下如何做到这一点。也就是说，怎样正确地修改元素的非键部分，并且是可移植的做法。这并不难，但是需要一个常常被许多程序员所忽略的技巧：你必须首先强制转换到一个引用类型。作为一个例子，再来看看setTitle调用，我们已经知道在有些实现下它不能通过编译：

EmplDSet::iteratori=se.find(selectedlD);
if (i != se.end()) {
  i->setTitle("Corporate Deity"); //有些STL实现将认为这一行不合法，因为*i为const
}

为了使它能够编译和正确执行，我们必须把* i的常量性质（constness）转换掉。下面是正确的做法：

if (i != se.end()) {
  const_cast<Employee&>(*i).setTitle("Corporate Deity"); //转换掉*i的const性质
}

它将取得i所指的对象，并告诉编译器把类型转换的结果当作一个指向（非const的）Employee的引用，然后对该引用调用setTitle。我暂时不解释为什么这样做是可以的，而是先来解释为什么另一种方式不能像人们所期望的那样工作。

很多人写出这样的代码：

if (i != se.end()) {
  static_cast<Employee>(*i).setTitle("Corporate Deity"); //把*i转换成Employee
}

它与下面的方式是等价的：

if (i != se.end()) {
  ((Employee)(*i)).setTitle("Corporate Deity"); //同上。只是使用了C方式的类型转换
}

这两种方式都能通过编译。因为它们是等价的，所以它们出错的原因也相同。在运行时，它们不会修改* i！在这两种情况下，类型转换的结果是一个临时的匿名对象，它是* i的一个副本，setTitle被作用在这个临时对象上，而不是* i上！* i没有改变，因为setTitle从来没有被作用于该对象，相反，它是在该对象的副本上被调用的。这两种语法形式都等价于：

if (i != se.end()){
  Employee tempCopy(*i); //把*i复制到tempCopy
  tempCopy.setTitle("Corporate Deity"); //修改tempCopy
}

现在，强制转换到引用的重要性应该很清楚了。通过强制转换到引用类型，我们避免了创建新的对象。这样，类型转换的结果将会指向已有的对象，即i所指的那个对象。当setTitle被作用在该引用所指的对象上时，我们是在对* i调用setTitle，而这正是我们所期望的。

我刚才所说的对于set和multiset没有任何问题，但对于map和multimap，情况就有些复杂了。前面提到过，map<K,V>或multimap<K,V>包含的是pair<const K,V>类型的元素。这里的const意味着pair的第一个部分被定义成const，而这又意味着如果试图把它的const属性强制转换掉，则结果将可能会改变键部分。理论上，一个STL实现可以把这样的值写在一个只读的内存区域中（比如一个虚拟内存页面，一旦被写入后，将由一个系统调用进行写保护），这时若试图修改它，则最好的结果将是没有效果。我从来没有听说过有这样的STL实现，但如果你坚持要遵从C++标准所制定的规则，那就永远都不要试图修改在map或multimap中作为键的对象。

你肯定已经听说过强制类型转换是危险的，我希望本书能使这一点更加清楚。我也相信，只要你能避免使用它，你就不应该使用。执行一次强制类型转换就意味着临时关掉了类型系统的安全性，而我们刚才讨论过的隐患指出了当你放弃安全网的时候将会发生什么事情。

注

大多数强制类型转换都可以避免，包括我们刚刚考虑过的那个转换。如果你想以一种总是可行而且安全的方式来修改set、multiset、map和multimap中的元素，则可以分5个简单步骤来进行：

1. 找到你想修改的容器的元素。如果你不能肯定最好的做法，第45条介绍了如何执行一次恰当的搜索来找到特定的元素。

2. 为将要被修改的元素做一份副本。在map或multimap的情况下，请记住，不要把该副本的第一个部分声明为const。毕竟，你想要改变它。

3. 修改该副本，使它具有你期望它在容器中的值。

4. 把该元素从容器中删除，通常是通过调用erase来进行的（见第9条）。

5. 把新的值插入到容器中。如果按照容器的排列顺序，新元素的位置可能与被删除元素的位置相同或紧邻，则使用“提示”（hint）形式的insert，以便把插入的效率从对数时间提高到常数时间。把你从第1步得来的迭代器作为提示信息。

下面是同样的Employee例子，这次是用安全的、可移植的方式来编写的:

EmplDSet se; //如前，se是按照ID号排序的雇员集合//如前，selectedID是存储有特定
Employee selectedlD; //ID号的Employee变量
EmplDSet::iterator i = se.find(selectedlD); //第1步:找到待修改的元素

if (i != se.end()) {
  Employee e(*i); //第2步:复制该元素
  e.setTitle("Corporate Deity"); //第3步:修改副本//第4步:删除该元素:
  se.erase(i++); //递增迭代器以保持它的有效性(见第9条1/第5步:插入新元素:提示它的位置
  se.insert(i, e); //和原来的相同
}

提示

你要原谅我这么做，但关键是要记住，对set和multiset，如果你直接对容器中的元素做了修改，那么你要保证该容器仍然是排序的。

第23条：考虑用排序的vector替代关联容器。

标准关联容器通常被实现为平衡的二叉查找树。二叉查找树这种数据结构对插入、删除和查找的混合操作做了优化，也就是说，它所适合的那些应用程序先做一些插入操作，然后做查找，然后可能又插入一些元素，或许接着删掉一些，随后又做一些查找，然后是更多的插入和删除，更多的查找，等等。这一系列事件的主要特征是插入、删除和查找混在一起。总的说来，没办法预测出针对这棵树的下一个操作是什么。

先考虑大小的问题。假定我们需要一个容器来存储Widget对象，因为查找速度对我们很重要，所以我们考虑使用一个Widget的关联容器或一个排序的vector<Widget>。如果选择了关联容器，则我们几乎肯定在使用平衡二叉树。这样的树是由树节点构成的，每个节点不仅包含了一个Widget，而且还包含了几个指针：一个指针指向该节点的左儿子，一个指针指向该节点的右儿子，（通常）还有一个指针指向它的父节点。这意味着在一个关联容器中存储一个Widget所伴随的空间开销至少是3个指针。

相反，如果我们把Widget存储在vector中，则不会有任何额外开销；我们只是简单地存储一个Widget。当然，vector本身也有开销，在vector的末尾可能会有空闲的（预留的）空间（见第14条），但平均到每个vector，这些开销通常是微不足道的（通常是3个机器字，即3个指针或者2个指针加1个int），而且如果有必要，结尾的空闲空间可以用“swap技巧”去除（见第17条）。即便多余的空间没有被去除掉，它对下面的分析也没有影响，因为在做查找时这块内存根本就不会被引用到。

假定我们的数据结构足够大，它们被分割后将跨越多个内存页面，但vector将比关联容器需要更少的页面。这是因为vector不需要针对每个Widget付出额外的开销，而关联容器针对每个Widget需要3个指针。为了看清楚为什么这很重要，假定在你所使用的系统中，Widget的大小是12个字节，指针的大小是4字节，而一个内存页面可以容纳4096（4K）个字节。忽略对每个容器的开销，如果使用vector，则你在一个页面上可以存储341个Widget，而如果使用关联容器，则你最多只能存储170个。这样，跟使用vector相比，使用关联容器占用了大约两倍的内存。如果你的操作系统使用了虚拟内存，则很容易看出这将会导致更多的页面错误，从而当数据量很大的时候，系统会显著变慢。

提示

总结：在排序的vector中存储数据可能比在标准关联容器中存储同样的数据要耗费更少的内存，而考虑到页面错误的因素，通过二分搜索法来查找一个排序的vector可能比查找一个标准关联容器要更快一些。

当然，对于排序的vector，最不利的地方在于它必须保持有序！当一个新的元素被插入时，新元素之后的所有元素都必须向后移动一个元素的位置。听起来这很费事，实际上也确实如此，尤其是当vector必须重新分配自己的内存时（见第14条），因为这时通常需要复制vector中的所有元素。与此类似，如果一个元素被从vector中删除了，则在它之后的所有元素也都要向前移动。插入和删除操作对于vector来说是昂贵的，但对于关联容器却是廉价的。这就是为什么只有当你知道“对数据结构的使用方式是：查找操作几乎从不跟插入和删除操作混在一起”时，再考虑使用排序的vector而不是关联容器才是合理的。

为了用vector来模仿map或multimap，你必须要省去const，因为当你对这个vector进行排序时，它的元素的值将通过赋值操作被移动，这意味着pair的两个部分都必须是可以被赋值的。所以，当使用vector来模仿map<K,V>时，存储在vector中的数据必须是pair<K,V>，而不是pair<const K,V>。

第24条：当效率至关重要时，请在mapinsert之间谨慎做出选择。

map的operator[]函数与众不同。它与vector、deque和string的operator[]函数无关，与用于数组的内置operator[]也没有关系。相反，map::operator[]的设计目的是为了提供“添加和更新”（add or update）的功能。也就是说，对于map<K, V> m;，表达式 m[k]= v; 检查键k是否已经在map中了。如果没有，它就被加入，并以v作为相应的值。如果k已经在映射表中了，则与之关联的值被更新为v。

现在应该明白为什么这种方式会降低性能了。我们先默认构造了一个Widget，然后立刻赋给它新的值。如果“直接使用我们所需要的值构造一个Widget”比“先默认构造一个Widget再赋值”效率更高，那么，我们最好把对operator[]的使用（包括与之相伴的构造和赋值）换成对insert的直接调用：m.insert(IntWidgetMap::value type(1, 1.50)); 这里的最终效果和前面的代码相同，只是它通常会节省3个函数调用：一个用于创建默认构造的临时Widget对象，一个用于析构该临时对象，另一个是调用Widget的赋值操作符。这些函数调用的代价越高，使用mapoperator[]节省的开销就越大。

当我们做更新操作时，即，当一个等价的键（见第19条）已经在映射表中时，形势恰好反过来了。为了看清楚为什么会这样，请看一下做更新操作时我们的选择：

m[k] = v; //使用operator[]把k的值更新为v
m.insert(IntWidgetMap::value type(k, v)).first->second = v; //使用insert把k的值更新为V

仅仅从语法形式本身来考虑，或许已经会促使你选择operator[]了，但现在我们要讲的是效率问题，所以我们将忽略这个因素。

insert调用需要一个IntWidgetMap::value_type类型的参数（即pair<int,Widget>），所以当我们调用insert时，我们必须构造和析构一个该类型的对象。这要付出一个pair构造函数和一个pair析构函数的代价。而这又会导致对Widget的构造和析构动作，因为pair<int,Widget>本身又包含了一个Widget对象。而operator[]不使用pair对象，所以它不会构造和析构任何pair或Widget。

对效率的考虑使我们得出结论：当向映射表中添加元素时，要优先选用insert，而不是operator[]；而从效率和美学的观点考虑，结论是：当更新已经在映射表中的元素的值时，要优先选择operator[]。

提示

当效率至关重要时，你应该在mapinsert之间仔细做出选择。如果要更新一个已有的映射表元素，则应该优先选择operator[]；但如果要添加一个新的元素，那么最好还是选择insert