标签（空格分隔）： STL
运用STL，可以充分利用该库的设计，让我为简单而直接的问题设计出简单而直接的解决方案，也能帮助你为更复杂的问题设计出优雅的解决方案。我将指出一些常见的STL错误用法，并指出该如何避免这样的错误。这能帮助你避免产生资源泄漏、写出不能移植的代码，以及出现不确定的行为。我还将讨论如何对你的代码进行优化，从而可以让STL执行得更快、更流畅，就像你所期待的那样。
STL并没有一个官方的正式定义，不同的人使用这个词的时候，它有不同的含义。在本书中，STL表示C++标准库中与迭代器一起工作的那部分，其中包括标准容器（包含string）、iostream库的一部分，函数对象和各种算法。它排除了标准容器配接器（stack、queue和priority_queue）以及容器bitset和valarray，因为它们缺少对迭代器的支持。数组也不包括在其中。不错，数组支持指针形式的迭代器，但数组是C++语言的一部分。而不是STL库的一部分。
第一章 容器
没错，STL中有迭代器（iterator）、算法（algorithm）和 函数对象（function object）,但是 对于大多数C++程序员来说，最值得注意的还是容器。容器比数组功能更强大、更灵活。它们可以动态增长（和缩减），可以自己管理内存，可以记住自己包含了多少对象。它们限定了自己所支持的操作的复杂性。
问题1：如何进行动态增长（和缩减）
A 如何就我所面临的具体制约条件选择适当的容器类型；
B 对于容器中的对象，复制操作的重要性；
C 当指针或auto_ptr被存放在容器中时会有什么样的困难；
D 删除操作的细节；
E 用定制的分配只能做什么以及不能做什么；
F 使程序获得最高效率的窍门；
G 在多线程环境中使用容器时的一些考虑；
标准STL序列容器： vector、string、deque 和 list。
标准STL关联容器： set、multiset、map 和 multimap。
非标准序列容器： slist 和 rope。slist是一个单向链表，rope本质上是一 "重型" string 。
非标准关联容器： hash_set、hash_multiset、hash_map 和
hash_multimap。在第25条中，我们分析了这些基于散列表的、标准关联容器的变体（它们通常是广泛可用的）。
vector<char> 作为 string 的替代。在一些情况下，这种替代是有意义的。
vector作为标准关联容器的替代。正如第23条所阐明的，有时vector在运行时间和空间上都要优于标准关联容器。
几种标准的非STL容器，包括数组、bitset、valarray、stack、queue和priority_queue。因为它们不是STL容器，后面解释了为什么bitset比vector<bool>要好。值得记住的是，数组也可以被用于STL算法，因为指针可以被用作数组的迭代器。
C++标准就 "如何在vector、deque 和 list 中做出选择" 提供了如下建议：
vector、list和deque为程序员提供了不同的复杂性，vector是默认应使用的序列类型；当需要频繁地在序列中间做插入和删除操作时，应使用list；当大多数插入和删除操作发生在序列的头部和尾部时，deque是应考虑的数据结构。
对STL容器的一种分类方法，该方法没有得到应有的重视。这就是对连续内存容器和基于节点的容器的区分。
连续内存容器（或称为基于数组的容器，array-based container）把它的元素存放在一块或多块（动态分配的）内存中，每块内存中存有多个元素。当有新元素插入或已有的元素被删除时，同一内存块中的其他元素要向前或向后移动，以便为新元素让出空间，或者填充被删除元素所留下的空隙。这种移动影响到效率和异常安全性。标准的连续内存容器有vector、string和deque。非标准的rope也是一个连续内存容器。
基于节点的容器在每一个（动态分配的）内存块中只存放一个元素。容器中元素的插入或删除只影响到指向节点的指针，而不影响节点本身的内容，所以，当有插入或删除操作时，元素的值不需要移动。表示链表的容器，如List 和 slist，是基于节点的；所以标准的关联容器也是如此（通常的实现方式是平衡树）。非标准的散列容器使用不同的基于节点的实现）
你是否需要在容器的任意位置插入新元素？ 如果需要，就选择序列容器；关联容器时不行的。
你是否关心容器中的元素是排序的？ 如果不关心，则散列容器是 一个可行的选择方案；否则，你要避免散列容器。
对插入和删除操作，你需要事务语义吗？也就是说，在插入和删除操作失败时，你需要回滚的能力吗？如果需要，你就要使用基于节点的容器。如果对多个元素的插入操作（即针对一个区间的形式）需要事务语义，则你需要选择list，因为在标准容器中，只有list对多个元素的插入操作提供了事务语义。对那些希望编写异常安全代码的程序员，事务语义显得尤为重要。（使用连续内存容器也可以获得事务语义，但是要付出性能上的代价，而且代价也显得不那么直接了当。
确保容器中的对象副本正确而高效
容器中保存了对象，但并不是你提供给容器的那些对象。而当从容器中取出一个对象时，你所取出的也并不是容器中所保存的那份。当向容器中加入对象时（通过insert或Push_back之类的操作），存入容器的是你所指定的对象的副本。当（通过如front或back之类的操作）从容器中取出一个对象时，你所得到的是容器中所保存的对象的副本。进去的是副本，出来的也是副本。这就是STL的工作方式。
一旦一个对象被保存到容器中，它经常会进一步被复制。当对vector、string或deque进行元素的插入或删除操作时，现有元素的位置通常会被移动（复制）。如果你使用下列任何操作--排序算法，next_permutation 或 previous_permutation，remove，unique或类似的操作，rotate或reverse，等等. 那么对象将会被移动。没错，复制对象是STL的工作方式。
复制动作是通过一个对象的复制成员函数就可以很方便地复制该对象，特别是对象的赋值构造函数（copy constructor）和复制赋值操作符（copy assignment operator）。内置类型（built-in type）（如整型、指针类型等）的实现总是简单地按位赋值。如果你向容器中填充对象，而对象的复制操作又很费时，那么向容器中填充对象这一简单的操作将会成为程序的性能"瓶颈"。放入容器中的对象越多，而且，如果这些对象的“副本”有特殊的含义，那么把它们放入容器时将不可避免地会产生错误。
当然，在存在继承关系的情况下，复制动作会导致剥离（slicing）.也就是说，如果你创建了一个存放基类对象的容器，却向其中插入派生类的对象，那么在派生类对象（通过基类的复制构造函数）被复制进容器时，它所特有的部分（即派生类中的信息）将会丢失：
vector<Widget> vw;
class SpecialWidget: public Widget{...}; //SpecialWidget 继承于上面的Widget
SpecialWidget sw;
vw.push_back(sw); // sw作为基类对象呗复制进vw中，它的派生类特有部分在复制时被丢掉了
“剥离” 问题意味着向基类对象的容器中插入派生类对象几乎总是错误的。如果你希望插入后的对象仍然表现得像派生类对象一样，例如调用派生类的虚函数等，那么这种期望是错误的。（关于剥离问题的更多知识，请参见Effective C++的第22条。关于STL中剥离问题的另一个例子）
使复制动作高效、正确，并防止剥离问题发生的一个简单办法是使容器包含指针而不是对象。也就是说，使用Widget*的容器，而不是Widget的容器。复制指针的速度非常快，并且总是会按你期望的方式进行（它复制构成指针的每一位），而且当它被复制时不会有任何剥离现象发生。如果你想避开这些使人头疼的问题，同时又想避免效率、正确性和剥离这些问题，你可能会发现智能指针（small pointer）是一个诱人的选择。
STL做了很多副本，但它总的设计思想是为了避免不必要的复制。事实上，它总体的设计目标是为了避免创建不必要的对象。把它跟C和C++仅有的内置容器（即数组）的行为做比较：
Widget w[maxNumWidgets]; //创建了有maxNumWidgets个Widget的数组，//每个对象都使用默认构造函数来创建
如果用STL，则我们可以使用vector，当需要的时候它会增长；
我们也可以创建一个空的vector，它包含足够的空间来容纳 maxNumWidgets个Widget对象，但并没有创建任何一个Widget对象：
vector<Widget> vw;
vw.reserver(maxNumWidgets);
调用empty而不是检查size() 是否为0.
对于任一容器c，代码：if(c.size() == 0)...本质上与if(c.empty())... 是等价的。既然如此，还是应该使用empty()，理由是：empty对所有的标准容器都是常数时间操作，而对一些list实现，size耗费线性时间。到底是什么使list这么讨厌呢？为什么它不也提供常数时间的size呢？答案在于list所独有的链接（splice）操作。考虑如下代码：
list<int> list1;
list<int> list2;
...
list1.splice(list1.end(),list2,find(list2.begin(),list2.end(),5),find(list2.rbegin(),list2.rend(),10).base());
// 把list2中从第一个含5的节点到最后一个含10的所有节点移动到list1的末尾。
链接后的list1中有多少个元素？很明显，链接后的list1中的元素个数是它链接前的元素个数加上链接过来的元素个数。但有多少个元素被链接过来了呢？应该与 find(list2.begin(),list2.end(),5),find(list2.rbegin(),list2.rend(),10).base() 所定义的区间中的元素个数一样多。究竟有多少个，如果不遍历该区间是无法知道的。通常，list或splice——必须做出让步。其中的一个可以成为常数时间操作，但不可能二者都是。
不同的链表实现通过不同的方式解决这一冲突，具体方式取决于作者选择把size还是splice实现得最为高效。如果你使用的list实现恰好是把splice的常数时间操作放在第一位，那么你使用empty而不是size会更好些，因为empty操作总是花费常数时间。即使现在你使用的list实现不是这种方式，将来你也可能会发现自己在使用这样的实现。比如，你可能把自己的代码移植到不同的平台上，不管发生了什么，调用empty而不是检查size==0是否成立总是没错的。所以，如果你想知道容器中是否含有零个元素，请调用empty。
区间成员函数优先于与之对应的单元素成员函数。
给定v1和v2两个矢量（vector）,使v1的内容和v2的后半部分相同的最简单操作是什么？
不必为了当v2含有奇数个元素时"一半"的定义而煞费苦心。只要做到合理即可。
v1.assign(v2.begin() + v2.size()/2, v2.end());
assign这么一个使用及其方便，却为许多程序员所忽略的成员函数。对所有的标准序列容器(vector,string,deque 和list)，它都存在。当你需要完全替换一个容器的内容时，你应该想到赋值（assignment）如果你想把一个容器复制到相同类型的另一个容器，那么operator=是可选择的赋值函数，但正如该例子所揭示的那样，当你想给容器一组全新的值时，你可以使用assign，而operator=则不能满足你的要求。
这里同时也揭示了为什么区间成员函数（range member function）优先于与之对应的单元素成员函数。区间成员函数是指这样的一类成员函数，它们像STL算法一样，使用两个迭代器参数来确定该成员操作所执行的区间。如果不使用区间成员函数来解决问题，就得写一个显式的循环，或许像这样：
vector<Widget>v1, v2;
v1.clear(); //clear 和 erase 的区别
for(vector<Widget>::conset_iterator ci = v2.begin() + v2.size()/2; ci != v2.end(); ++ci)
v1.push_back(*ci);
这样写显式的循环，其实比调用assign多做了很多工作。这样的循环在一定程度上影响了效率，后面会接着讨论这个问题。避免循环的一种方法是遵从第43条的建议，使用一个算法：
v1.clear();
copy(v2.begin() + v2.size()/2, v2.end(), back_inserter(v1));
同调用assign相比，所做的工作还是多了些。而且，尽管上面的代码中没有循环，但copy中肯定有。结果是，影响效率的因素仍然存在。几乎所有通过利用插入迭代器的方式（即利用inserter、back_inserter 或 front_inserter）来限定目标区间的copy调用，其实都可以（也应该）被替换为堆区间成员函数的调用。比如，在这里，对copy的调用可以被替换为利用区间的Insert版本：
v1.insert(v1.end(), v2.begin() + v2.size()/2, v2.end());
同调用copy相比，敲键盘的工作稍少了些，但它更加直截了当地说明了所发生的事情：数据被插入到V1中。对copy的调用也说明了这一点，但没有这么直接，而是把重点放在了不合适的地方。对这里所发生的事情，有意义的不是元素被复制，而是有新的数据被插入到了v1中。Insert成员函数很清晰地表明了这一点，使用copy则把这一点掩盖了。太多的STL程序员滥用了copy，所以我刚才给出的建议值得再重复一下：通过利用插入迭代器的方式来限定目标区间的copy 调用，几乎都应该被替换为对区间成员函数的调用。
太多的STL程序员滥用了copy，所以我刚才给出的建议值得再重复一下：通过利用插入迭代器的方式来限定目标区间的copy调用，几乎都应该被替换为对区间成员函数的调用。
现在回到assign的例子。我们已经给出了使用区间成员函数而不是其相应的单元素成员函数的原因：
- 通过使用区间成员函数，通常可以少写一些代码。
- 使用区间成员函数通常会得到意图清晰和更加直接的代码。
对于标准的序列容器，我们又一个标准：效率。当处理标准序列容器时，为了取得同样的效果，使用单元素的成员函数比使用区间成员函数需要更多地调用内存分配子，更频繁地复制对象，而且 / 或者做冗余的操作。
比如，假定你要把一个int数组复制到一个vector的前端。（首先，数据可能来自数组而不是vector，因为数据来自遗留的C代码。关于STL容器和C API混合使用时导致的问题。使用vector的区间insert函数，非常简单：
// 假定numValues 在别处定义
int data[numValues];
vector<int> v;
...
v.insert(v.begin(),data,data+numValues); //把整数插入到v的前端
而通过显式地循环调用insert，或多或少可能像这样：
请注意，我们必须记得把insert的返回值记下来供下次进入循环时使用。如果在每次插入操作后不更新insertLoc，我们会遇到两个问题。首先，第一次迭代后的所有循环迭代都将导致不可预料的行为（undefined behavior），因为每次调用insert都会使insertLoc无效。其次，即使insertLoc仍然有效，插入总是发生在vector的最前面（即在v.begin()处），结果这组整数被以相反的顺序复制到v当中。
如果遵从第43条，把循环替换为对copy的调用，我们得到如下代码：
当copy模板被实例化之后，基于copy的代码和使用循环的代码几乎是相同的，所以，为了分析效率。我们将注意力集中在显式循环上，但要记住，对于使用copy的代码，下列分析同样有效。分析显式循环将更易于理解“哪些地方影响了效率”。对，右多个地方影响了效率，使用单元素版本的insert总共在三个方面影响了效率，而如果使用区间版本的insert，则这三种影响都不复存在。
第一种影响是不必要的函数调用。把numValues个元素逐个插入到v中导致了对insert的numValues次调用。而使用区间形式的insert，则只做了一次函数调用，当然，使用内联（inlining）可能会避免这样的影响，但是，实际中不见得会使用内联。只要一点是肯定的：使用区间形式的insert，肯定不会有这样的影响。
内联无法避免第二种影响，即把v中已有的元素频繁地移动到插入后它们所处的位置。每次调用insert把新元素插入到v中时，插入点后的每个元素都要向后移动一个位置，以便为新元素腾出空间。所以，位置p的元素必须被移动到位置p+1，等等。在我们的例子中，我们向v的前端插入numValues个元素，这意味着v中插入点之后的每个元素都要向后移动numValues个位置。每次调用insert时，每个元素需向后移动一个位置，所以每个元素将移动numValues次。如果插入前v中有n个元素，就会有nnumValues次移动。在这个例子中，v中存储的是int类型，每次移动最终可能会归为调用memmove，可是如果v中存储的是Widget这样的用户自定义类型，则每次一定会导致调用该类型的赋值操作符或复制构造函数。（大多数情况下会调用赋值操作符，但每次vector中的最后一个元素被移动时，将会调用该元素的复制构造函数。）所以在通常情况下，把numValues个元素逐个插入到含有n个元素的vector<Widget>的前端将会有nnumValues次函数调用的代价：(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个新元素最多可导致log2numValues次新的内存分配。
第14条指出，表现出这种行为的vector实现是存在的，因此，把1000个元素逐个插入可能会导致10次新的内存分配（包括低效的元素复制）。与之对应（而且，到现在为止也可以预见），使用区间插入的方法，在开始插入前可以知道自己需要多少新内存（假定给它的是前向迭代器），所以不必多次重新分配vector的内存。可以想见，这一节省是很客观的。
刚才所做的分析是针对vector的，但该论证过程对string同样有效。对于deque，论证过程与之类似，但deque管理内存的方式与vector和string都不同。但是，关于把元素不必要地移动很多次的论断依然是成立的。
在标准的序列容器中，现在只剩下list，对此使用区间形式而不是单元素形式的insert也有其效率上的优势。关于重复函数调用的论断当然继续生效，由于链表工作的方式，对list中某些节点的next和prev指针的重复的，多余的赋值操作。
每当有元素加入到链表中时，含有这一元素的节点必须设定它的next和prev指针，当然新节点前面的节点（我们称之为B，代表“前面”）必须设置自己的next指针，而新节点后面的节点则必须设定自己的prev指针：
当通过调用list的单元素insert把一系列节点逐个加入进来时，除了最后一个新节点，其余所有的节点都要把其next指针赋值两次：一次指向A，另一次指向在它之后插入的节点。每次有新节点再A前面插入时，A会把其prev指针指向新指针。如果A前面插入了numValues个指针，对所插入的节点的next指针会有numValues-1次多余的赋值，对A的prev指针也会有numValues-1次赋值。总共就会有2*（numValues-1）次不必要的指针赋值。
而避免这一代价的答案是使用区间形式的Insert。因为这一函数知道最终将插入多少节点，可以避免不必要的指针赋值，而只使用一次赋值将每个指针设为插入后的值。
下面了解哪些成员函数支持区间，在下面的函数原型中，参数类型iterator按字母意义理解为容器的迭代器类型，即container:: iterator。另一方面，参数类型 InputIterator表示任何类型的输入迭代器都是可接受的。
区间创建：所有的标准容器都提供了如下形式的构造函数：
当传给这种构造函数的迭代器是istream_iterator或者istreambuf_iterator时（见第29条），你可能会遇到C++最烦人的分析机制，它使编译器把这条语句解释为函数声明，而不是定义新的容器对象。第6条将向你解释这一分析的细节，包括你如何避免这一问题。
区间插入：所有的标准序列容器都提供了如下形式的insert：
关联容器利用比较函数来决定元素该插入何处，它们提供了一个省去position参数的函数原型：
在寻找区间形式的insert来代替单元素版本时，不要忘了一些单元素的变体使用了不同的函数名称，从而把自己给掩盖了。比如，push_front和push_back都向同其中插入单一元素，尽管它们不叫insert。当你看到使用push_front或push_back的循环调用，或者front_inserter或back_inserter被作为参数传递给copy函数时，你会发现在这里区间形式的insert可能是更好的选择。
区间删除。所有的标准容器都提供了区间形式的删除（erase）操作，但对于序列和关联容器，其返回值有所不同。
为何会有这样的区别呢，据说使用关联容器版本的erase返回一个迭代器（指向被删除元素之后的元素）将导致不可接受的性能负担。包括我在内的很多人都对这种说法表示怀疑，可是C++标准毕竟是C++标准。
本条款中关于insert 的效率分析对erase也类似。对vector和string的论断中，有一条对erase不适用，那就是内存的反复分配。这是因为vector和string的内存会自动增长以容纳新元素，但当元素数目减少时内存却不会自动减少。（第17条将指出怎样减少vector或string所占用的多余内存）
区间赋值。正如我在本条款开头所指出的，所有的标准容器都提供了区间形式的assign：
第六条：当心C++编译器最烦人的分析机制。
假设你有一个存有整数(int)的文件，你想把这些整数复制到一个list中。下面是很合理的一种做法：
这种做法的思路是，把一对istream_iterator传入到list的区间构造函数中（见第5条），从而把文件中的整数复制到list中。这段代码可以通过编译，但是在运行时，它什么也不会做。它不会从文件中读取任何数据，它不会创建list。这是因为第二条语句并没有声明一个list，也没有调用构造函数。
【这里是当做声明了一个函数，参数为 istream_iterator<int>】
下面从最基本的说起，下面这行代码声明了一个带double参数并返回int的函数：
int f(double d);
下面这行也一样，参数d两边的括号是多余的，会被忽略：
int f(double (d)); //同上；d两边的括号被忽略
下面这行声明了同样的函数，只是它省略了参数名称：
int f(double);
这三种形式的声明你应当很熟悉，尽管以前你可能不知道可以给参数名加上圆括号。
现在再看三个函数声明。第一个声明了一个函数g，它的参数是一个指向不带任何参数的函数的指针，该函数返回double值：
clipboard10.png
有另外一种方式可表明同样的意思。唯一的区别是，pf用非指针的形式来声明（这种形式在C和C++中都有效）：
clipboard11.png
跟通常一样，参数名称可以省略，因此下面是g的第三种声明，其中参数名pf被省略了：
clipboard12.png
请注意围绕参数名的括号（int f(double (d)); //同上；d两边的括号被忽略）
与独立的括号的区别。围绕参数名的括号被忽略，而独立的括号则表明参数列表的存在；它们说明存在一个函数指针参数。
在熟悉了对f和g的声明后，我们开始研究本条款开始时提出的问题。它是这样的：
clipboard13.png
请你注意了。这声明了一个函数data，其返回值是list<int>。这个data函数有两个参数：
- 第一个参数的名称是dataFile。它的类型是istream_iterator<int>。dataFile两边的括号是多余的，会被忽略。
- 第二个参数没有名称。它的类型是指向不带参数的函数的指针，该函数返回一个istream_iterator<int>。
这一切都与C++中的一条普通规律相符，即尽可能地解释为函数声明。曾经多少次见到过下面这种错误？
clipboard14.png
它没有声明名为w 的Widget，而是声明了一个名为w的函数，该函数不带任何参数，并返回一个Widget。学会识别这一类言不达意是称为C++程序员的必经之路。
所有这些都很有意思（通过它自己的歪曲的方式），但这并不能帮助我们做自己想做的事情。我们想用文件的内容初始化list<int> 对象。现在我们已经知道必须绕过某一种分析机制，剩下的事情就简单了。把形式参数的声明用括号括起来是非法的，但给函数参数加上括号却是合法的，所以通过增加一对括号，我们强迫编译器按我们的方式来工作：
clipboard15.png
这是声明data的正确方式，在使用istream_iterator和区间构造函数时（同样，见第5条）,注意到这一点是有益的。
不幸的是，并不是所有的编译器都知道这一点。几乎有一半测试的编译器中，拒绝接受data的上述声明方式，除非它被错误地用不带括号的形式来声明。更好地方式是在对data的声明中避免使用匿名的istream_iterator对象（尽管使用匿名对象是一种趋势），而是给这些迭代器一个名称。下面的代码应该总是可以工作的：
clipboard16.png
使用命名的迭代器对象与通常的STL程序风格相违背，但你或许觉得为了使代码对所有编译器都没有二义性，并且使维护代码的人理解起来更容易，这一代价是值得的。
Copy 函数
所谓变易算法就是一组能够修改容器元素数据的模板函数，可进行序列数据的复制，变换等。其中copy就是其中一个元素复制算法copy。该算法主要用于容器之间元素的拷贝，即将迭代器区间[first, last] 的元素复制到由复制目标result给定的区间[result, result+(last-first)]中。函数原型为：
template<class InputIterator, class OutputIterator>
OutputIterator copy(
InputIterator _First,
InputIterator _Last,
OutputIterator _DestBeg
);
参数：
_First, _Last 指出被复制的元素的区间范围[_First, _Last].
_DestBeg 指出复制到的目标区间起始位置
返回值：
返回一个迭代器，指出已被复制元素区间的最后一个位置
程序示例：
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main ()
{
int myints[] = {10, 20, 30, 40, 50, 60, 70};
vector<int> myvector;
vector<int>::iterator it;
myvector.resize(7); // 为容器myvector分配空间
//copy用法一：
//将数组myints中的七个元素复制到myvector容器中
copy ( myints, myints+7, myvector.begin() );
cout << "myvector contains: ";
for ( it = myvector.begin(); it != myvector.end(); ++it )
{
cout << " " << *it;
}
cout << endl;
//copy用法二:
//将数组myints中的元素向左移动一位
copy(myints + 1, myints + 7, myints);
cout << "myints contains: ";
for ( size_t i = 0; i < 7; ++i )
{
cout << " " << myints[i];
}
cout << endl;
return 0;
}
从上例中我们看出copy算法可以很简单地将一个容器里面的元素复制至另一个目标容器中，上例中代码特别要注意一点就是myvector.resize(7);这行代码，在这里一定要先为vector分配空间，否则程序会崩，这是初学者经常犯的一个错误。
其实copy函数最大的威力是结合标准输入输出迭代器的时候，我们通过下面这个示例就可以看出它的威力了。
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <string>
using namespace std;
int main ()
{
typedef vector<int> IntVector;
typedef istream_iterator<int> IstreamItr;
typedef ostream_iterator<int> OstreamItr;
typedef back_insert_iterator< IntVector > BackInsItr;
IntVector myvector;
// 从标准输入设备读入整数
// 直到输入的是非整型数据为止 请输入整数序列，按任意非数字键并回车结束输入
cout << "Please input element：" << endl;
copy(IstreamItr(cin), IstreamItr(), BackInsItr(myvector));
//输出容器里的所有元素，元素之间用空格隔开
cout << "Output : " << endl;
copy(myvector.begin(), myvector.end(), OstreamItr(cout, " "));
cout << endl;
return 0;
}
对于 vector 的clear() 和erase() 的区别
vector :: erase(): 从指定容器删除指定位置的元素或某段范围内的元素
vector :: erase() 方法有两种重载形式
如下：
iterator erase(iterator _Where);
iterator erase(iterator _First, iterator _Last); // 但是这里不会删除掉_Last 所对应的数据
如果是删除指定位置的元素时，返回值是一个迭代器，指向删除元素下一个元素；如果是删除某范围内的元素时：返回值也表示一个迭代器，指向最后一个删除元素的下一个元素；如何一个容器里有多个相同的元素，要怎么删除呢？
for(Iter = v1.begin(); Iter != v1.end(); Iter++)
{
if(*Iter == 10)
{
Iter = v1.erase(Iter);//Iter为删除元素的下一个元素的迭代器
//即第一次这段语句后Iter 会是20，大家可以通过debug调试出来查看下数值
}
if(Iter == v1.end()) //要控制迭代器不能超过整个容器
{
break;
}
}
但是这里就算调用了erase 其实好像也只是将后面的数移位覆盖了前面的数，但是整个size还是没有改变。
而对于vector，clear() 并没有真正释放内存（这是为优化效率所做的事），clear实际所做的是为vector中所保存的所有对象调用析构函数（如果有的话），然后初始化size这些东西，让你觉得把所有的对象清除了。但是总的来讲vector并没有出现内存泄漏。在《effective STL》中的“条款17" 已经指出了：
当vector、string大量插入数据后，即使删除了大量数据（或者全部都删除，即clear）并没有改变容器的容量（capacity），所以仍然会占用着内存。为了避免这种情况，我们应该想办法改变容器的容量使之尽可能小的符合当前数据所需（shrink to fit）
《Effective STL》给出的解决方案是：
vector<type> v;
//.... 这里添加许多元素给v
//.... 这里删除v中的许多元素
vector<type>(v).swap(v);
//此时v的容量已经尽可能的符合其当前包含的元素数量
//对于string则可能像下面这样
string(s).swap(s);
即先创建一个临时拷贝与原先的vector一致，值得注意的是，此时的拷贝 其容量是尽可能小的符合所需数据的。紧接着该拷贝与原先的vector v 进行交换。好了此时，执行交换后，临时变量会被销毁，内存得到释放。此时的v即为原先的临时拷贝，而交换后的临时拷贝则为容量非常大的vector（不过已经被销毁）
为了证明这一点，我写了一个程序，如下：
#include <iostream>
#include <vector>
using namespace std;
vector <string> v;
char ch;
int main ()
{
for(int i=0; i<1000000; i++)
v.push_back("abcdefghijklmn");
cin >> ch;
// 此时检查内存情况 占用54M
v.clear();
cin >> ch;
// 此时再次检查， 仍然占用54M
cout << "Vector 的 容量为" << v.capacity() << endl;
// 此时容量为 1048576
vector<string>(v).swap(v);
cout << "Vector 的 容量为" << v.capacity() << endl;
// 此时容量为0
cin >> ch;
// 检查内存，释放了 10M+ 即为数据内存
return 0;
}
在创建一个vector后，vector的实际容量一般会比所给数据要大，这样做应该是避免过多的重新分配内存的吧。
当然，上面这种方法虽然释放了内存，但是同时也增加了拷贝数据的时间消耗。不过一般需要重新调整容量的情况都是 vector 本身元素较少的情况，所以，时间消耗可以忽略不计。
再回过来看vector内存释放机制
vector 中的内建有内存管理，当vector离开它的生存期的时候，它的析构函数会把vector 中的元素销毁，并释放它们所占用的空间，所以用 vector 一般不用显式释放 ——不过，如果你 vector 中存放的是指针，那么当 vector 销毁时，那些指针指向的对象不会被销毁，那些内存不会被释放。 其实这也是一种比较常见的内存泄漏。
vector的工作原理是系统预先分配一块capacity大小的空间，当插入的数据超过这个空间的时候，这块空间会以某种方式扩展，但是你删除数据的时候，它却不会缩小。vector为了防止大量分配连续内存的开销，保持一块默认的尺寸，clear只是清数据了，为清内存，因为vector的capacity容量未变化，系统维护一个的默认值。
有什么方法可以释放掉vector中占用的全部内存呢？
标准的解决方法如下
template<class T>
void ClearVector(vector<T>& vt)
{
vector<T> vtTemp;
vtTemp.swap(vt);
}
----------------------------------------
举例1：
vector<int> vec(100);
cout<< vec.capacity()<<endl;
vector<int>().swap(vec);
cout<< vec.capacity()<<endl;
-----------------------------------------
利用vector释放指针：
#include<vector>
using namespace std;
vector<void*> v;
每次new之后调用v.push_back()该指针，
在程序退出时或其它你认为适当的时候，执行如下代码：
//这里就是通过一轮循环，然后将每一个节点的指针给销毁了，再调用clear()函数。
for (vector<void *>::iterator it = g_vPtrManager.begin(); it != g_vPtrManager.end(); it ++)
{
if (NULL != *it)
{
delete *it;
*it = NULL;
}
}
v.clear();
// remark: 若你的程序是多线程的，注意以下线程安全问题，必要时加个临界区控制一下。
总结：
vector与deque不同，其内存占用空间只会增长，不会减小。比如你首先分配了10,000个字节，然后erase掉后面9,999个，则虽然有效元素只有一个，但是内存占用仍为10,000个。所有空间在vector析构时回收。empty()是用来检测容器是否为空的，clear()可以清空所有元素。但是即使clear()，所占用的内存空间依然如故。如果你需要空间动态缩小，可以考虑使用deque。如果非要用vector，这里有一个方法：
vector<int>().swap(nums); //nums.swap(vector<int>());
vector<int>().swap(nums)；
{
std::vector<int> tmp = nums;
nums.swap(tmp);
}
// 加一对大括号是可以让tmp退出{}的时候自动析构。
// swap技法就是通过交换函数swap()，使得vector离开其自身的作用域，从而强制释放vector所占的内存空间。
assign的设计
assign的函数的好处，应该很好理解就是在不能使用赋值符“=”的情况下，可以将一个容器中的部分元素通过迭代器传递赋值到另一个容器中，但是在assign的使用过///程中，有一点需要特别注意，就是调用assign（）函数的容器必须有足够的空间来容纳复制过来的元素。
函数原型：
void assign(const_iterator first, const_iterator last);
void assign(size_type n, const T&x = T());
功能：
将区间(first,last)的元素赋值到当前的vector容器中，或者赋n个值为x的元素到vector容器中，这个容器会清除掉vector容器中以前的内容。
#include <vector>
#include <iostream>
int main( )
{
using namespace std;
vector<int> v1, v2, v3;
vector<int>::iterator iter;
v1.push_back(10); v1.push_back(20); v1.push_back(30); v1.push_back(40); v1.push_back(50); v2.push_back(1); v2.push_back(2);
v2.assign(v1.begin(), v1.end());
cout << "v2 = ";
for (iter = v2.begin(); iter != v2.end(); iter++)
cout << *iter << " ";
cout << endl;
v3.assign(7, 3) ;
cout << "v3 = ";
for (iter = v3.begin(); iter != v3.end(); iter++)
cout << *iter << " ";
cout << endl;
return 0;
}
说到安全问题，我还想问，vector是不是线程安全的？http://book.51cto.com/art/201305/394132.htm
标准 C++的世界相当狭小和古旧。在这个纯净的世界中，所有的可执行程序都是静态链接的。不存在内存映像文件或共享内存。没有窗口系统，没有网络，没有数据库，也没有其他进程。考虑到这一点，当你得知 C++标准对线程只字未提时，你不应该感到惊讶。于是，你对STL的线程安全性的第一个期望应该是，它会因不同实现而异。
当然，多线程程序是很普遍的，所以多数STL提供商会尽量使自己的实现可在多线程环境下工作。然而，即使他们在这一方面做得不错，多数负担仍然在你的肩膀上。理解为什么会这样是很重要的。STL提供商对解决多线程问题只能做很有限的工作。
在STL容器中支持多线程的标准（这是多数提供商们所希望的）已经为SGI所确定，并在它们的STL Web站点上发布。概括来说，它指出，对一个 STL实现你最多只能期望：
多个线程读是安全的。多个线程可以同时读同一个容器的内容，并且保证是正确的。自然地，在读的过程中，不能对容器有任何写入操作。
多个线程对不同的容器做写入操作是安全的。多个线程可以同时对不同的容器做写入操作。
就这些。我必须指明，这是你所能期待的，而不是你所能依赖的。有些实现提供了这些保证，有些则没有。
写多线程的代码并不容易，许多程序员希望 STL的实现能提供完全的线程安全性。如果是这样的话，程序员可以不必再考虑自己做同步控制。这无疑是很方便的，但要做到这一点将会很困难。考虑当一个库试图实现完全的容器线程安全性时可能采取的方式：
对容器成员函数的每次调用，都锁住容器直到调用结束。
在容器所返回的每个迭代器的生存期结束前，都锁住容器（比如通过 begin 或 end 调用）。
对于作用于容器的每个算法，都锁住该容器，直到算法结束。
（实际上这样做没有意义。因为，算法无法知道它们所操作的容器。尽管如此，在这里我们仍要讨论这一选择。因为即使这是可能的，我们也会发现这种做法仍不能实现线程安全性，这对于我们的讨论是有益的）。
现在考虑下面的代码。它在一个vector<int>中查找值为5的第一个元素，如果找到了，就把该元素置为0.
vector<int> v;
...
vector<int>:: iterator first5(find(v.begin(),v.end(),5)); // 第 1 行
if (first5 != v.end()){ //第 2行
*first5 =0; //第 3行
}
在一个多线程环境中，可能在第一行刚刚完成后，另一个不同的线程会更改 v中的数据。如果这种更改真的发生了，那么第2行对 first5 和 v.end是否相等的检查将会变得没有
意义，因为v的值将会与在第一行结束时不同。事实上，这一检查会产生不确定的行为，因为另外一个线程可能会夹在第1行和第2行中间，使 first5 变得无效，这第二个线程或许会执行一个插入操作使得vector 重新分配它的内存。类似地，第 3行对*first5的赋值也是不安全的，因为另一个线程可能在第 2行和第 3行之间执行，该线程可能会使 first5无效，例如可能会删除它所指向的元素（或者至少是曾经指向过的元素）。
要做到线程安全， v必须从第 1行到第 3行始终保持在锁住状态，很难想象一个 STL实现能自动推断出这一点。考虑到同步原语（例如信号量、互斥体等）通常会有较高的开销，这就更难想象，一个 STL实现如何既能够做到这一点，同时又不会对那些在第 1行和第 3行之间本来就不会有另外线程来访问 v的程序（假设程序就是这样设计的）造成显著的效率影响。
这样的考虑说明了为什么你不能指望任何 STL 实现来解决你的线程难题。相反，在这种情况下，必须手工做同步控制。在这个例子中，或许可以这样做：
vector<int> v;
...
getMutexFor(v);
vector<int>::iterator first5(find(v.begin(), v.end(), 5));
if (first5 != v.end()){
*first5 = 0;
}
releaseMutexFor(v);
更为面向对象的方案是创建一个Lock类，它在构造函数中获得一个互斥体，在析构函数中释放它，从而尽可能地减少 getMutexFor 调用没有相对应的 releaseMutexFox调用的可能性。这样的类（实际上是一个类模板）看起来大概像下面这样：
template<typename Container> //一个为容器获取和释放互斥体的模板
class Lock{
public:
Lock( const Container& container): c(container){
getMutexFox(c); // 在构造函数中获取互斥体
}
~Lock(){
releaseMutexFor(c); // 在析构函数中释放它
}
private:
const Container& c;
};
使用类（如 Lock）来管理资源的生存期的思想通常被称为 "获得资源时即初始化"，你可以在任何一本全面介绍C++的书中找到这种思想。
vector<int> v;
{ Lock<vector<int> > lock(v); //获取互斥体
vector<int>::iterator first5(find(v.begin(), v.end(), 5)); if (first5 != v.end()) { *first5 = 0; }
} //代码块结束，自动释放互斥体
因为 Lock对象在其析构函数中释放容器的互斥体，所以很重要的一点是，当互斥体应该被释放时，Lock就要被析构。为了做到这一点，我们创建了一个新的代码块（block），在其中定义了Lock，当不再需要互斥体时就结束该代码块。看起来好像是我们把“调用releaseMutexFor”这一任务换成了“结束代码块”，事实上这种说法是不确切的。如果我们忘了为Lock创建新的代码块，则互斥体仍然会被释放，只不过会晚一些——当控制到达包含 Lock的代码块末尾时。而如果我们忘记了调用releaseMutexFor，那么我们永远也不会释放互斥体。
而且，基于 Lock的方案在有异常发生时也是强壮的。C++保证，如果有异常被抛出，局部对象会被析构，所以，即便在我们使用 Lock对象的过程中有异常抛出， Lock仍会释放它所拥有的互斥体。
如果我们依赖于手工调用 getMutexFor和releaseMutexFor，那么，当在调用 getMutexFor之后而在调用 releaseMutexFor之前有异常被抛出时，我们将永远也无法释放互斥体。
异常和资源管理虽然很重要，但它们不是本条款的主题。本条款是讲述STL中的线程安全性的。当涉及STL容器和线程安全性时，你可以指望一个STL库允许多个线程同时读一个容器，以及多个线程对不同的容器做写入操作。你不能指望 STL库会把你从手工同步控制中解脱出来，而且你不能依赖于任何线程支持。
已经证实存在一个漏洞。如果该异常根本没有被捕获到，那么程序将终止。在这种情况下，局部对象（如 lock）可能还没有让它们的析构函数被调用到。有些编译器会调用它们，有些编译器不会。这两种情况都是有效的。
网友评论