容器在C++中的详细说明(vector)

矫情吗；* 2022-06-09 03:28 158阅读 0赞

**第1章 容器**

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

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

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

非标准序列容器slist和rope。slist是一个单向链表，rope本质上是一“重型”string。

非标准的关联容器hash\_set、hase\_multiset、hash\_map和hash\_multimap。

vector<char>作为string的替代。(见第13条)

vector作为标准关联容器的替代。(见第23条)

几种标准的非STL容器，包括数组、bitset、valarray、stack、queue和priority\_queue。

你是否关心容器中的元素是如何排序的？如果不关心，选择哈希容器.

容器中数据的布局是否需要和C兼容？如果需要兼容，就只能选择vector。(见第16条)

元素的查找速度是否是关键的考虑因素？如果是，就要考虑哈希容器、排序的vector和标准关联容器－或许这就是优先顺序。

对插入和删除操作，你需要事务语义吗？如果是，只能选择list。因为在标准容器中，只有list对多个元素的插入操作提供了事务语义。

deque是唯一的、迭代器可能会变为无效（插入操作仅在容器末尾发生时，deque的迭代器可能会变为无效）而指向数据的指针和引用依然有效的标准STL容器。

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

如果你想编写对大多数的容器都适用的代码，你只能使用它们的功能的交集。不同的容器是不同的，它们有非常明显的优缺点。它们并不是被设计用来交换使用的。

你无法编写独立于容器的代码，但是，它们（指客户代码）可能可以。

**第3条：确保容器中的对象拷贝正确而高效。**

copy in,copy out，是STL的工作方式，它总的设计思想是为了避免不必要的拷贝。使拷贝动作高效并且防止剥离问题发生的一个简单办法是使容器包含指针而不是对象。

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

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

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

区间成员函数写起来更容易，更能清楚地表达你的意图，而且它们表现出了更高的效率。

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

把形参加括号是合法的，把整个形参的声明（包括数据类型和形参名字）用括号括起来是非法的。

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

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

**第8条：切勿创建包含auto\_ptr的容器对象。**

拷贝一个auto\_ptr意味着改变它的值。例如对一个包含auto\_ptr的vector调用sort排序，结果是vector的几个元素被置为NULL而相应的元素被删除了。

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

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

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

SeqContainer<int>c;

c.erase(remove(c.begin(),c.end(),1963),c.end());

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

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

要删除容器中满足特定条件的所有对象：

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

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

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

AssocCOntainer<int> c;

...

AssocContainer<int> goodValues;

remove\_copy\_if(c.begin(), c.end(), inserter(goodValues,goodValues.end()),badValue);

c.swap(goodValues);

或

for(AssocContainer<int>::iterator i = c.begin();i!=c.end();/\* do nothing \*/)\{

if(badValue(\*i)) c.erase(i++);

else ++i;

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

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

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

**第10条：了解分配子(allocator)的约定和限制。**

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

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

对一个STL实现你最多只能期望：

多个线程读是安全的。

多个线程对不同的容器写入操作是安全的。

你不能期望STL库会把你从手工同步控制中解脱出来，而且你不能依赖于任何线程支持。

**第2章vector和string**

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

如果用new，意味着你要确保后面进行了delete。

如果你所使用的string是以引用计数来实现的，而你又运行在多线程环境中，并认为string的引用计数实现会影响效率，那么你至少有三种可行的选择，而且，没有一种选择是舍弃STL。首先，检查你的库实现，看看是否可以禁用引用计数，通常是通过改变某个预处理变量的值。其次，寻找或开发一个不使用引用计数的string实现。第三，考虑使用vector<char>而不是string。vector的实现不允许使用引用计数，所以不会发生隐藏的多线程性能问题。

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

通常有两种方式来使用reserve以避免不必要的重新分配。第一种方式是，若能确切知道或大致预计容器中最终会有多少个元素，则此时可使用reserve。第二种方式是，先预留足够大的空间，然后，当把所有的数据都加入后，再去除多余的容量。

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

如果你想有效的使用STL，那么你需要知道string实现的多样性，尤其是当你编写的代码必须要在不同的STL平台上运行而你又面临着严格的性能要求的时候。

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

如果你有个vector v，而你需要得到一个只想v中的数据的指针，从而可把数据作为数组来对才，那么只需要使用＆v［0］就可以了，也可以用＆＊v.begin（），但是不好理解。对于string s，随应的形式是s.c\_str()。

如果想用来自C API的数据来初始化一个vector，那么你可以利用vector和数组的内存布局兼容性，先把数据写入到vector中，然后把数据拷贝到期望最终写入的STL容器中。

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

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

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

同样的技巧对string也实用：

string s；

...

string(s).swap(s);

**第18条：避免使用vector<bool>。**

作为STL容器，vector<bool>只有两点不对。首先，它不是一个STL容器；其次，它并不存储bool。除此以外，一切正常。因此最好不要使用它，你可以用deque<bool>和bitset替代。vector<bool>来自一个雄心勃勃的试验，代理对象在C＋＋软件开发中经常会很有用。C＋＋标准委员会的人很清楚这一点，所以他们决定开发vector<bool>，以演示STL如果支持 “通过代理对象来存取其元素的的容器”。他们说，C＋＋标准中有了这个例子，于是，人们在实现自己的基于代理的容器时就有了一个参考。然而他们却发现，要创建一个基于代理的容器，同时又要求它满足STL容器的所有要求是不可能的。由于种种原因，他们失败了的尝试被遗留在标准中。

**第3章 关联容器**

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

标准关联容器总是保持排列顺序的，所以每个容器必须有一个比较函数（默认为less）。等价的定义正是通过该比较函数而确定的。相等一定等价，等价不一定相等。

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

每当你创建包含指针的关联容器时，容器将会按照指针的值（就是内存地址）进行排序，绝大多数情况下，这不是你所希望的。

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

现在我给你演示一个很酷的现象。创建一个set，用less\_equal作为它的比较类型，然后把10插入到该集合中：

set<int, less\_equal<int> > s; //s用"<="来排序

s.insert(10);

对于第二个insert，集合会检查下面的表达式是否为真：

!(10a<= 10b) && !(10b <= 10a);//检查10a和10b是否等价，结果是!(true)&& !(true) 为false

结果集合中有两个10！

从技术上讲，用于对关联容器排序的比较函数必须为他们所比较的对象定义个“严格的弱序化”（strictweak ordering）。

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

如果你不关心可移植性，而你想改变set或multiset中元素的值，并且你的STL实现（有的STL实现中，比如set<T>::iterator的operator\*总是返回const T&，就不能修改了）允许你这么做，则请继续做下去。只是注意不要改变元素中的键部分，即元素中能够影响容器有序性的部分。

如果你重视可移植性，就要确保set和multiset中的元素不能被修改。至少不能未经过强制类型转换（转换到一个引用类型const\_cast<T&>）就修改。

如果你想以一种总是可行而且安全的方式来许该set、multiset、map和multimap中的元素，则可以分5个简单步骤来进行：

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

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

3.修改该拷贝，使它具有你期望的值。

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

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

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

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

很多应用程序使用其数据结构的方式并不这么混乱。他们使用其数据结构的过程可以明显地分为三个阶段，总结如下：

1.设置阶段。创建一个新的数据结构，并插入大量元素。在这个阶段，几乎所有的操作都是插入和删除操作。很少或几乎没有查找操作。

2.查找操作。查询该数据结构以找到特定的信息。在这个阶段，几乎所有的操作都是查找操作，很少或几乎没有插入和删除操作。

3.重组阶段。改变该数据结构的内容，或许是删除所有的当前数据，再插入新的数据。在行为上，这个阶段与第1阶段类似。当这个阶段结束以后，应用程序又回到第2阶段。

**第24条：当效率至关重要时，请在map::operator\[\]与map::insert之间谨慎作出选择。**

假定我们有一个Widget类，它支持默认构造函数，并根据一个double值来构造和赋值：

class Widget\{

public:

Widget();

Widget(double weight);

Widget& operator=(double weight);

...

map的operator\[\]函数与众不同。它与vector、deque和string的operator\[\]函数无关，与用于数组的内置operator\[\]也没有关系。相反，map::operator\[\]的实际目的是为了提供“添加和更新”(add orupdate)的功能。也就是说，对于下面的例子：

map<int, Widget> m;

m\[1\] = 1.50;

语句m\[1\] = 1.50相当于

typedef map<int, Widget> IntWidgetMap;

pair<INtWidgetMap::iterator, bool> result =m.insert(IntWidgetMap::value\_type(1.Widget()));//用键值1和默认构造的值创建一个新的map条目

result.first->second = 1.50;//调用赋值构造函数

我们最好把对operator\[\]的调用换成对insert的直接调用：

m.insert(IntWidgetMap::value\_type(1,1.50));

这里的效果和前面的代码相同，只是它通常会节省三个函数调用：一个用于创建默认构造的临时Widget对象，一个用于析构该临时对象，另一个是调用Widget的赋值操作符。

请看一下做更新操作时我们的选择：

m\[k\] = v; //使用operator\[\]把k的值更新为v

m.insert(IntWidgetMap::value\_type(k,v)).first->second= v; //使用insert把k的值更新为v

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

如果要更新一个已有的映射表元素，选择operator\[\]；如果要添加一个新的元素，选择insert。

**第25条：熟悉非标准的哈希容器。**

标准C++库没有任何哈希容器，每个人认为这是一个遗憾，但是C++标准委员会认为，把它们加入到标准中所需的工作会拖延标准完成的时间。已经有决定要在标准的下一个版本中包含哈希容器。

**第4章 迭代器**

**第26条：iterator优先于const\_iterator、reverse\_iterator以及const\_reverse\_iterator。**

减少混用不同类型的迭代器的机会，尽量用iterator代替const\_iterator。从const正确性的角度来看，仅仅为了避免一些可能存在的STL实现缺陷而放弃使用const\_iteraor显得有欠公允。但考虑到在容器类的某些成员函数中指定使用iterator的现状，得出iterator较之const\_iterator更为实用的结论也就不足为奇了。更何况，从实践的角度来看，并不总是值得卷入const\_iterator的麻烦中。

**第27条：使用distance和advance将容器的const\_iterator转换成iterator。**

下面的代码试图把一个const\_iterator强制转换为iterator：

typedef deque<int> IntDeque; //类型定义，简化代码

typedef IntDeque::iterator Iter;

typedeef IntDeque:;const\_iterator ConstIter;

ConstIter ci; //ci是一个const\_iterator

...

Iter i(ci); //编译错误！从const\_iterator到iterator没有隐式转换途径

Iter i(const\_cast<Iter>(ci)); //仍然是编译错误！不能将const\_iterator强制转换为iterator

包含显式类型转换的代码不能通过编译的原因在于，对于这些容器类型，iterator和const\_iterator是完全不同的类，他们之间的关系甚至比string和complex<double>之间的关系还要远。

下面是这种方案的本质。

typedef deque<int> IntDeque; //类型定义，简化代码

typedef IntDeque::iterator Iter;

typedeef IntDeque:;const\_iterator ConstIter;

IntDeque d;

ConstIter ci; //ci是一个const\_iterator

... //使ci指向d

Iter i(d.begin());//使i指向d的起始位置

advance(i,distance<ConstIter>(i,ci));//移动i，使它指向ci所指的位置

这中方法看上去非常简单和直接，也很令人吃惊。为了得到一个与const\_iterator指向同一位置的iterator，首先创建一个新的iterator，将它指向容器的起始位置，然后取得const\_iterator距离容器起始位置的偏移量，并将iterator向前移动相同的偏移量即可。这项技术的效率取决于你所使用的迭代起，对于随机迭代器，它是常数时间的操作；对于双向迭代器，以及某些哈希容器，它是线性时间的操作。

**第28条：正确理解由reverse\_iterator的base()成员函数所产生的iterator的用法。**

如果要在一个reverse\_iterator ri指定的位置上插入元素，则只需在ri.base()位置处插入元素即可。对于插入操作而言，ri和ri.base()是等价的，ri.base()是真正与ri对应的iterator。

如果要在一个reverse\_iterator ri指定的位置上删除一个元素，则需要在ri.base()前一个位置上执行删除操作。对于删除操作而言，ri和ri.base()是不等价的。

我们还是有必要来看一看执行这样一个删除操作的实际代码，其中暗藏着惊奇之处：

vector<int> v;

... //同上，插入1到5

vector<int>::reverse\_iterator ri =find(v.rbegin(),v.rend(),3);//使ri指向3

v.erase(--ri.base()); //试图删除ri.base()前面的元素，对于vector，往往编译通不过

对于vector和string，这段代码也许能工作，但对于vector和string的许多实现，它无法通过编译。这是因为在这样的实现中，iterator(和vconst\_iterator)是以内置指针的方式实现的，所以ri.base()的结果是一个指针。C和C＋＋都规定了从函数返回的指针不应该被修改，所以所以编译不能通过。

既然不能对base()的结果做递减操作，那么只要先递增reverse\_iterator，然后再调用base()函数即可！

...

v.erase((++ri).base()); //删除ri所指的元素，这下编译没问题了！

**第29条：对于逐个字符的输入请考虑使用istreambuf\_iterator。**

假如你想把一个文本文件的内容拷贝到一个string对象中，以下的代码看上去是一种合理的解决方案：

ifstream inputFile("interestingData.txt");

inputFIle.unsetf(ios::skipws);//istream\_iterator使用operator>>函数来完成实际的读操作，而默认情况下operator>>函数会跳过空白字符

string fileData((istream\_iterator<char> (inputFIle)),istream\_iterator<char>());

然而，你可能会发现整个拷贝过程远不及你希望的那般快。istream\_iterator内部使用的operator>>实际上执行了格式化的输入，但如果你只是想从输入流中读出下一个字符的话，它就显得有点多余了。

有一种更为有效的途径，那就是使用STL中最为神秘的法宝之一：istreambuf\_iterator。istreambuf\_iterator<char>对象使用方法与istream\_iterator<char>大致相同，但是istreambuf\_iterator<char>直接从流的缓冲区读取下一个字符。（更为特殊的是，istreambuf\_iterator<char>对象从一个输入流istream s中读取下一个字符的操作是通过s.rdbuf()->sgetc()来完成的。）

ifstream inputFile("interestingData.txt");

stringfileData((istreambuf\_iterator<char>(inputFile)),istreambuf\_iterator<char>());

这次我们用不着清楚输入流的skipws标志，因为istreambuf\_iterator不会跳过任何字符。

同样的，对于非格式化的逐个字符输出过程，你也应该考虑使用ostreambuf\_iterator。

**第5章 算法**

**第30条：确保目标区间足够大。**

当程序员希望向容器中添加新的对象，这里有一个例子：

int transmogrify(int x); //该函数根据x生成一个新的值

vector<int> values;

vector<int> results;

transform(values.begin(),values.end(),back\_inserter(results),transmogrify);

back\_inserter返回的迭代起将使得push\_back被调用，所以back\_inserter可适用于所有提供了push\_back方法的容器。同理，front\_inserter仅适用于那些提供了push\_front成员函数的容器（如deque和list）。

当是使用reserver提高一个序列插入操作的效率的时候，切记reserve只是增加了容器的容量，而容器的大小并未改变。当一个算法需要向vector或者string中加入新的元素，即使已经调用了reserve，你也必须使用插入型的迭代器。如下代码给出了一种错误的方式：

vector<int> values;

vector<int> results;

...

results.reserve(results.size() + values.size());

transform(values.begin(), values.end(), results.end(),transmogrify);//变换的结果会写入到尚未初始化的内存，结果将是不确定的

在以上代码中transform欣然接受了在results尾部未初始化的内存中进行复制操作的任务。由于赋值操作重视在两个对象之间而不是在一个对象与一个未初始化的内存块之间进行，所以一般情况下，这段代码在运行时会失败。

假设希望transform覆盖results容器中已有的元素，那么就需要确保results中已有的元素至少和values中的元素一样多。否则，就必须使用resize来保证这一点。

vector<int> values;

vector<int> results;

...

if(results.size() < values.size())\{

results.resize(values.size());

transform(values.begin(),values.end(),results.begin(),transmogrify);

或者，也可以先清空results，然后按通常的方式使用一个插入型迭代起：

...

results.clear();

results.reserve(values.size());

transform(values.begin(),values.end(),back\_inserter(results),transmogrify);

**第31条：了解各种与排序有关的选择。**

sort(stable\_sort)、partial\_sort和nth\_element算法都要求随即访问迭代器，所以这些算法只能被应用于vector、string、deque和数组。partion（stable\_partion）只要求双向迭代器就能完成工作。对于标准关联容器中的元素进行排序并没有实际意义，因为它们总是使用比较函数来维护内部元素的有效性。list是唯一需要排序却无法使用这些排序算法的容器，为此，list特别提供了sort成员函数（有趣的是，list::sort执行的是稳定排序）。如果希望希望一个list进行完全排序，可以用sort成员函数；但是，如果需要对list使用partial\_sort或者nth\_element算法的话，你就只能通过间接途径来完成了。一种间接做法是，将list中的元素拷贝到一个提供随即访问迭代器的容器中，然后对该容器执行你所期望的算法；另一种简介做法是，先创建一个list::iterator的容器，再对该容器执行相应的算法，然后通过其中的迭代器访问list的元素；第三中方法是利用一个包含迭代器的有序容器的信息，通过反复地调用splice成员函数，将list中的元素调整到期望的目标位置。可以看到，你会有很多中选择。

**第32条：如果确实需要删除元素，则需要在remove这一类算法之后调用erase。**

1 2 3 99 5 99 7 8 9 99

调用remove(v.begin(),v.end(),99)；后变成

1 2 3 5 7 8 9 8 9 99

remove无法从迭代器推知对应的容器类型，所以就无法调用容器的成员函数erase，因此就无法真正删除元素。其他两个算法remove\_if和unique也类似。不过list::remove和list::unique会真正删除元素（比用erase-remove和erase-unique更为高效），这是STL中一个不一致的地方。

**第33条：对包含指针的容器使用remove这一类算法时要特别小心。**

无论你如何处理那些存放动态分配的指针的容器，你总是可以这样来进行：或者调用remove类算法之前先手工删除指针并将它们置为空，或者通过引用计数的智能指针(如boost::shared\_ptr)，或者你自己发明的其他某项技术。

下面的代码利用第一种方式：

void delAndNullifyUncertified(Widget\*& pWidget)

if(!pWidget->isCertified())

delete pWidget;

pWidget = 0;

for\_each(v.begin(),v.end(),delAndNullifyUndertified);

v.erase(vemove(v.begin(),v.end(),static\_cast<Widget\*>(0)),v.end());

下面的的代码使用第二中方式：

template<typename T> //RSCP = "ReferenceCounting Smart Pointer"

class RCSP\{...\};

tpedef RCSP<Widget> RCSPW;

vector<RCSPW> v;

...

v.push\_back(RCSPW(new Widget));

...

v.erase(remove\_if(v.begin(),v.end(),not1(mem\_fun(&Widget::isCertified))),v.end());

**第34条：了解哪些算法要求使用排序的区间作为参数。**

下面的代码要求排序的区间：

binary\_search lower\_bound

upper\_bound equal\_range

set\_union set\_intersection

set\_difference set\_symmetric\_difference

merge inplace\_merge

includes

下面的算法并不一定需要排序的区间：

unique unique\_copy

**第35条：通过mismatch或lexicographical\_compare实现简单的忽略大小写的字符串比较。**

用mistatch实现：

//此函数判断两个字母是否相同，而忽略它们的大小写

int ciCharCompare(char c1, char c2)

int lc1 =tolower(static\_cast<unsigned\_char>(c1));

int lc2 =tolower(static\_cast<unsigned\_char>(c2));

if(lc1 < lc2)return -1;

if(lc1 > lc2)return 1;

return 0;

/\*此函数保证传递给ciStringCompareImpl的s1比s2短，如果s1和s2相同，返回0；如果s1比s2短，返回\-1；如果s1比s2长，返回1。\*/

int ciStringCompare(const string& s1, conststring& s2)

if(s1.size() <=s2.size()) return ciStringCompareImpl(s1, s2);

else return –ciStringCompareImpl(s2, s1);

//如果s1和s2相同，返回0；如果s1比s2短，返回\-1；如果s1和s2都是在非结尾处发生不匹配，有开始不匹配的那个字符决定。

int ciStringCompareImpl(const string &s1, conststring &c2)

typedefpair<string::const\_iterator,string::const\_iterator> PSCI;

PSCI p =mismatch(s1.begin(),s1.end(),s2.begin(),not2(ptr\_fun(ciCharCompare)));

if(p.first ==s1.end())\{

if(p.second ==s2.end()) return 0;

else return -1;

returnciCharCompair(\*p.first, \*p.second);

用lexicographical\_compare实现：

bool ciCharLess(char c1, char c2)

return tolower(static\_cast<unsigned char>(c1)) <tolower(static\_cast<unsigned char>(c2));

bool ciStringCompare(const string &s1,const string&s2)

return lexicographical\_compare(s1.begin(), s1.end(),s2.begin(), s2.end(), ciCharLess);

**第36条：理解copy\_if算法的正确实现。**

STL中没有copy\_if的算法，下面是一个实现，但是不够完美：

template<typename INputIterator,typenameOUtputIterator,tpename Predicate>

OutputIterator copy\_if(INputIterator begin,INputIteratorend,OutputIterator destBegin,Predicate p)

return remove\_copy\_if(begin,end,destBegin, not1(0));

copy\_if(widgets.begin(), widgets.end(),ostream\_iterator<Widget>(cerr, "\\n"),isDefective);//编译错误

因为not1不能被直接应用到一个函数指针上（见41条），函数指针必须先用ptr\_fun进行转换。为了调用copy\_if的这个实现，你传入的不仅是一个函数对象，而且还应该是一个可配接（adaptable）的函数对象。虽然这很容易做到，但是要想成为STL算法，它不能给客户这样的负担。

下面是copy\_if的正确实现：

template<typename INputIterator,typenameOUtputIterator,typename Predicate>

OutputIterator copy\_if(INputIterator begin,INputIteratorend,OutputIterator destBegin,Predicate p)

while(begin != end)\{

if(p(\*begin)) \*destBegin++ = \*begin;

\++begin;

return destBegin;

第37条：使用accumulate或者for\_each进行区间统计。

确保accumulate的返回类西和初始值类型相同。for\_each返回的是一个函数对象。accumulate不允许副作用而for\_each允许。（这是一个深层次的问题，也是一个涉及STL核心的问题，待解）

**第6章 函数子、函数子类、函数及其他**

**第38条：遵循按值传递的原则来设计函数子类。**

在STL中，函数对象在函数之间来回传递的时候也是像函数指针那样按值传递的。因此，你的函数对象必须尽可能的小，否则拷贝的开销会很大；其次，函数对象必须是单态的，也就是说，它们不得使用虚函数。这是因为，如果参数的类型是基类类型，而实参是派生类对象，那么在传递过程中会产生剥离问题（slicingproblem）：在对象拷贝过程中，派生部分可能会被去掉，而仅保留了基类部分（见第3条）。

试图禁止多态的函数子同样也是不实际的。所以必须找到一种两全其美的办法，既允许函数对象可以很大并且／或保留多态性，又可以与STL所采用的按值传递函数子的习惯保持一致。这个办法就是：将所需要的数据和虚函数从函数子中分离出来，放到一个新的类中，然后在函数子中设一个指针，指向这个新类。

**第39条：确保判别式是“纯函数”。**

一个判别式（predicate）是一个返回值为bool类型的函数。一个纯函数（purefunction）是指返回值仅仅依赖于其参数的函数。

因为接受函数子的STL算法可能会先创建函数子对象的拷贝，然后使用这个拷贝，因此这一特性的直接反映就是判别式函数必须是纯函数。

template<typename FwdIterator,typename Predicata>

FwdIterator remove\_if(FwdIterator begin, FwdIterator end,Predicate p)

begin = find\_if(begin, end, p);//可能是p的拷贝

if(begin == end return begin;

else\{

FwdIterator next = begin;

return remove\_copy\_if(++next, end, begin, p);//可能是p的另一个拷贝

**第40条：若一个类是函数子，则应使它可配接。**

4个标准的函数配接器(not1、not2、bind1st和bind2nd）都要求一些特殊的类型定义。提供了这些必要的类型定义（argument\_type、first\_argument\_type、second\_argument\_type以及result\_type）的函数对象被称为可配接的（adaptable）函数对象，反之，如果函数对象缺少这些类型定义，则称为不可配接的。可配接的函数对象能够与其他STL组件更为默契地协同工作。不过不同种类的函数子类所需要提供的类型定义也不尽相同，除非你要编写自定义的配接器，否则你并不需要知道有关这些类型定义的细节。这是因为，提供这些类型定义最简便的办法是让函数子从特定的基类继承，或者更准确的说，如果函数子类的operator()只有一个形参，那么它应该从std::unary\_function模板的一个实例继承；如果函数子类的operator()有两个形参，那么它应该从std::binary\_function继承。

对于unary\_function，你必须指定函数子类operator()所带的参数的类型，以及返回类型；对于binary\_function，你必须指定三个类型：operator()的第一个和第二个参数的类型，以及operator()的返回类型。以下是两个例子：

template<typename T>

class MeetsThreshold: publicstd::unary\_function<Widget, bool> \{

private:

const T threshold;

public:

MeetsThreshold(const T& threshold);

bool operator()(const Widget&) const;

...

\};

struct WidgetNameCompare:

public std::binary\_function<Widget, Widget, bool> \{

bool operator() (const Widget& lhs, const Widget&rhs) const;

\};

你可能已经注意到MeetsThreshold是一个类，而WidgetNameCompare是一个结构。这是因为MeetsThreshold包含了状态信息（数据成员threshold），而类是封装状态信息的一种逻辑方式；与此相反，WidgetNameCompare并不包含状态信息，因而不需要任何私有成员。如果一个函数子的所有成员都是公有的，那么通常会将其声明为结构而不是类。究竟是选择结构还是类来定义函数子纯属个人编码风格，但是如果你正在改进自己的编码风格，并希望自己的风格更加专业一点的话，你就应该注意到，STL中所有无状态的函数子类（如less<T>、plus<T>等）一般都定义成结构。

我们在看一下WidgetNameCompare：

struct WidgetNameCompare:

public std::binary\_function<Widget, Widget, bool> \{

bool operator() (const Widget& lhs, const Widget&rhs) const;

\};

虽然operator()的参数类型都是constWidget&，但我们传递给binary\_function的类型却是Widget。一般情况下，传递给unary\_function或binary\_function的非指针类型需要去掉const和引用（&）部分（不要问其中的原因，如果你有兴趣，可以访问boost.org，卡可能看他们在调用特性(traits)和函数对象配接器方面的工作）。

如果operator()带有指针参数，规则又有不同了。下面是WidgetNameCOmpare函数子的另一个版本，所不同的是，这次以Widget\*指针作为参数：

struct PtrWidgetNameCompare:

public std::binary\_function<const Widget\*, constWidget\*, bool> \{

bool operator() (const Widget\* lhs, const Widget\* rhs)const;

\};

**第41条：理解ptr\_fun、mem\_fun和mem\_fun\_ref的来由。**

如果有一个函数f和一个对象x，现在希望在x上调用f，而我们在x的成员函数之外，那么为了执行这个调用，C＋＋提供了三种不同的语法：

f(x); //语法\#1：f是一个非成员函数

x.f(); //语法\#2：f是一个成员函数，并且x是一个对象或一个对象引用

p->f(); //语法\#3：f是成员函数，并且p是一个指向对象x的指针

现在假设有个可用于测试Widget对象的函数：

void test(Widget& w);

另有一个存放Widget对象的容器：

vector<Widget> vw;

为了测试vw中的每一个Widget对象，自然可以用如下的方式来调用for\_each：

for\_each(vw.begin(), vw.end(), test); //调用\#1 (可以通过编译)

但是，加入test是Widget的成员函数，即Widget支持自测：

class Widget\{

public:

...

void test();

....

\};

那么在理想情况下，应该也可以用for\_each在vw中的每个对象上调用Widget::test成员函数：

for\_each(vw.begin(), vw.end(), &Widget::test);//调用\#2（不能通过编译）

实际上，如果真的很理想的话，那么对于一个存放Widget\*指针的容器，应该也可以通过for\_each来调用Widget::test：

list<Widget\*> lpw;

for\_each(lpw.begin(), lpw.end(), &Widget::test);//调用\#3（也不能通过编译）

这是因为STL中一种和普遍的惯例：函数或函数对象在被调用的时候，总是使用非成员函数的语法形式（即\#1）。

现在mem\_fun和mem\_fun\_ref之所以必须存在已经很清楚了－－它们被用来调整（一般是\#2和\#3）成员函数，使之能够通过语法\#1被调用。mem\_fun、mem\_fun\_ref的做法其实很简单，只要看一看其中任意一个函数的声明就清楚了。它们是真正的函数模板，针对它们所配接的成员函数的圆形的不同，有几种变化形式。我们来看其中一个声明，以便了解它是如何工作的：

template<typename R, typename C> //该mem\_fun声明针对不带参数的非const成员函数，C是类，R是所指向的成员函数的返回类型

mem\_fun\_t<R,C>

mem\_fun(R(C::\*pmf) ());

mem\_fun带一个指向某个成员函数的指针参数pmf，并且返回一个mem\_fun\_t类型的对象。mem\_fun\_t是一个函数子类，它拥有该成员函数的指针，并提供了operator()函数，在operator()中调用了通过参数传递进来的对象上的该成员函数。例如，请看下面一段代码：

list<Widget\*> lpw;

...

for\_each(lpw.begin(),lpw.end(),mem\_fun(&Widget::test));//现在可以通过编译了

for\_each接受到一个类型为mem\_fun\_t的对象，该对象中保存了一个指向Widget::test的指针。对于lpw中的每一个Widget\*指针，for\_each将会使用语法\#1来调用mem\_fun\_t对象，然后，该对象立即用语法\#3调用Widget\*指针的Widget::test()。

（ptr\_fun是多余的吗？）mem\_fun是针对成员函数的配接器，mem\_fun\_ref是针对对象容器的配接器。

**第42条：确保less<T>与operator<具有相同的含义。**

operator<不仅仅是less的默认实现方式，它也是程序员期望less所做的事情。让less不调用operator<而去坐别的事情，这会无端地违背程序员的意愿，这与“少”带给人惊奇的原则（theprinciple of least astonishment）完全背道而驰。这是很不好的，你应该尽量避免这样做。

如果你希望以一种特殊的方式来排序对象，那么最好创建一个特殊的函数子类，它的名字不能是less。

**第7章 在程序中使用STL**

**第43条：算法调用优于手写的循环。**

有三个理由：

效率：算法通常比程序员自己写的循环效率更高。

STL实现者可以针对具体的容器对算法进行优化；几乎所有的STL算法都使用了复杂的计算机科学算法，有些科学算法非常复杂，并非一般的C＋＋程序员所能够到达。

正确性：自己写的循环比使用算法容易出错。

比如迭代器可能会在插入元素后失效。

可维护性：使用算法的代码通常比手写循环的代码更加简介明了。

算法的名称表明了它的功能，而for、while和do却不能，每一位专业的C＋＋程序员都应该知道每一个算法所做的事情，看到一个算法就可以知道这段代码的功能，而对于循环只能继续往下看具体的代码才能懂代码的意图。

**第44条：容器的成员函数优先于同名的算法。**

第一：成员函数往往速度快；第二，成员函数通常与容器（特别是关联容器）结合得更紧密（相等和等价的差别，比如对于关联容器，count只能使用相等测试）。

**第45条：正确区分count、find、binary\_search、lower\_bound、upper\_bound和equal\_range。**

<table> 
 <tbody> 
 <tr> 
 <td> 想知道什么 </td> 
 <td colspan="2"> 使用算法 </td> 
 <td colspan="2"> 使用成员函数 </td> 
 </tr> 
 <tr> 
 <td> 对未排序的区间 </td> 
 <td> 对排序的区间 </td> 
 <td> 对set或map </td> 
 <td> 对multiset或multimap </td> 
 </tr> 
 <tr> 
 <td> 特定的值存在吗 </td> 
 <td> find </td> 
 <td> binary_search </td> 
 <td> count </td> 
 <td> find </td> 
 </tr> 
 <tr> 
 <td> 特定的值存在吗？如果有，第一个在哪里 </td> 
 <td> find </td> 
 <td> equal_range </td> 
 <td> find </td> 
 <td> find或lower_bound </td> 
 </tr> 
 <tr> 
 <td> 第一个不超过特定值的对象在哪里 </td> 
 <td> find_if </td> 
 <td> lower_bound </td> 
 <td> lower_bound </td> 
 <td> lower_bound </td> 
 </tr> 
 <tr> 
 <td> 第一个超过某个特定值的对象在哪里 </td> 
 <td> find_if </td> 
 <td> upper_bound </td> 
 <td> upper_bound </td> 
 <td> upper_bound </td> 
 </tr> 
 <tr> 
 <td> 具有特定值的对象有多少个 </td> 
 <td> count </td> 
 <td> equal_range&nbsp; (然后distance) </td> 
 <td> count </td> 
 <td> count </td> 
 </tr> 
 <tr> 
 <td> 具有特定值的对象都在哪里 </td> 
 <td> find(反复调用) </td> 
 <td> equal_range </td> 
 <td> equal_range </td> 
 <td> equal_range </td> 
 </tr> 
 </tbody> 
</table>

**第46条：考虑使用函数对象而不是函数指针作为STL算法的参数。**

函数指针抑制了内联机制，而函数对象可以被编译器优化为内联。

另一个理由是，这样做有助于避免一些微妙的、语言本身的缺陷。在偶然的情况下，有些看似合理的代码会被编译器以一些合法但又含糊不清的理由而拒绝。例如，当一个函数模板的实例化名称并不完全等同于一个函数的名称时，就可能会出现这样的问题。下面是一个例子：

template<typename FPType>

FPType average(FPType val1, FPType val2)//返回两个浮点的平均值

return (val1 + val2) / 2;

template<typename InputIter1,typename InputIter2>

void writeAverages(InputIter1 begin1, INputIter1 end1,InputIter2 begin2,ostream& s) //将两个序列的值按顺序对应取平均，然后写到一个流中

transform(begin1, end1, begin2,

ostream\_iterator<typenameiterator\_trais<InputIterl>::value\_type(s,"\\n")>,

average<typenameiterator\_traits<InputIterl>::value\_type>//错误？

);

许多编译器接受这段代码，但是Ｃ＋＋标准却不认同这样的代码。原因在于，理论上存在另一个名为average的函数模板，它也只带一个类型参数。如果这样的话，表达式average<typenameiterator\_traits<InputIterl>::value\_type>就会有二义性，因为编译器无法分辨到底应该实例化哪一个模板。换成函数对象就可以了。

**第47条：避免产生“直写型”（write-only）的代码。**

代码被阅读的次数远远大于它被编写的次数。

**第48条：总是包含（\#include）正确的头文件。**

几乎所有的标准STL容器都被声明在与之同名的头文件中。

除了４个STL算法外，其他所有的算法都被声明在<algorithm>中，这4个算法是accumulate、inner\_product、adjacent\_difference和partial\_sum，它们都被声明在头文件<numeric>中。

特殊类型的迭代器，包括istream\_iterator和istreambuf\_iterator（见第29条），被声明在<iterator>中。

标准的函数子（比如less<T>）和函数子配接器（比如not1、bind2nd）被声明在头文件<functional>中。

**第49条：学会分析与STL相关的编译器诊断信息。**

用文本替换（例如用string替换掉basic\_string<char,structstd::char\_traits<char>,class std::allocator<char> >）。

**第50条：熟悉STL相关的Web站点。**

SGI STL站点：http://www.sig.com/tech/stl/

STLport站点：http://stlport.org

BOost站点：[http://boost.org][http_boost.org]

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

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

**非标准序列容器** slist和rope。slist是一个单向链表，rope本质上是一个重型字符串。（rope是一个重型string）

**非标准关联容器** hash\_set、hash\_multiset、hash\_map和hash\_multimap。

**vector<char>可以作为string的替代品。**

**vector作为标准关联容器的替代品。** 有时候vector可以在时间和空间上都表现得比标准关联容器好。

几种 **标准非STL容器** ，包括数组、bitset、valarray、stack、queue和priority\_queue。

这是所有的选项，而且可以考虑的范围和可以在它们之间的选择一样丰富。不过，STL的大多数讨论只限于容器世界的一个很窄的视野，忽略了很多关于选择适当容器的问题。就连标准都介入了这个行动，提供了以下的在vector、deque和list之间作选择的指导方案：

vector、list和deque提供给程序员不同的复杂度，因此应该这么用：vector是一种可以默认使用的序列类型，当很频繁地对序列中部进行插入和删除时应该用list，当大部分插入和删除发生在序列的头或尾时可以选择deque这种数据结构。

如果主要关心的是算法复杂度，这个方案是有理由的建议，但需要关心更多东西。我们检查一些可以补充算法复杂度的重要的容器相关问题，但首先需要介绍一种STL容器的分类方法，是连续内存容器和基于节点的容器的区别。

**连续内存容器** （也叫做 **基于数组的容器** ）在一个或多个（动态分配）的内存块中保存它们的元素。如果一个新元素被插入或者已存元素被删除，其他在同一个内存块的元素就必须向上或者向下移动来为新元素提供空间或者填充原来被删除的元素所占的空间。这种移动影响了效率和异常安全。标准的连续内存容器是vector、string和deque。非标准的rope也是连续内存容器。

**基于节点的容器** 在每个内存块（动态分配）中只保存一个元素。容器元素的插入或删除只影响指向节点的指针，而不是节点自己的内容。所以当有东西插入或删除时，元素值不需要移动。表现为链表的容器——比如list和slist——是基于节点的，所有的标准关联容器也是（它们的典型实现是平衡树）。非标准的hash容器使用不同的基于节点的实现。

**如果需要可以在容器的任意位置插入一个新元素** ，则要使用序列容器，关联容器做不到。

**如果不需要关心元素在容器中的顺序** ，hash容器就是可行的选择。否则，避免使用hash容器。

**如果必须使用标准C++中的容器** ，就可以除去hash容器、slist和rope。

**需要哪一类迭代器** ？如果必须是随机访问迭代器，在技术上就只能限于vector、deque和string，但也可能会考虑rope。如果需要双向迭代器，就用不了slist和hash容器的一般实现。

**当插入或者删除数据时，是否非常在意容器内现有元素的移动？** 如果是，就必须放弃连续内存容器。

**容器中的数据的内存布局需要兼容C吗？** 如果是，就只能用vector。

**查找速度很重要吗？** 如果是，就应该看看hash容器，排序的vector和标准的关联容器。

**介意如果容器的底层使用了引用计数吗？** 如果是，就得避开string，因为很多string的实现是用引用计数。也不能用rope，因为权威的rope实现是基于引用计数的。

**需要插入和删除的事务性（transactional）语义吗？** 也就是说，需要有可靠地回退（roll back）插入和删除的能力吗？如果是，就需要使用基于节点的容器。如果需要多元素插入（比如，以范围的方式）的事务性语义，就应该选择list，因为list是唯一提供多元素插入事务性语义的标准容器。事务性语义对于写异常安全代码来说非常重要。（事务性语义也可以在连续内存容器上实现，但会有一个性能开销，而且代码不那么直观。

**要把迭代器、指针和引用的失效次数减到最少吗？** 如果是，就应该使用基于节点的容器，因为在这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。一般来说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。

**需要具有有以下特性的序列容器吗：1）可以使用随机访问迭代器；2）只要没有删除而且插入只发生在容器结尾，指针和引用的数据就不会失效？** 这个一个非常特殊的情况，但如果遇到这种情况，deque就是理想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。）

一. 种类：

*  **标准STL序列容器**：vector、string、deque和list。
 *  **标准STL关联容器**：set、multiset、map和multimap。
 *  **非标准序列容器**slist和rope。slist是一个单向链表，rope本质上是一个重型字符串
 *  **非标准关联容器**hash\_set、hash\_multiset、hash\_map和hash\_multimap。
 *  几种**标准非STL容器**，包括数组、bitset、valarray、stack、queue和priority\_queue

值得注意的是，数组可以和STL算法配合，因为指针可以当作数组的迭代器使用。

二.删除元素

如果想删除东西，记住 remove 算法后，要加上 erase

所谓删除算法，最终还是要调用成员函数去删除某个元素，但是因为 remove 并不知道它现在作用于哪个容器，所以 remove 算法不可能真的删除一个元素

1.Vector

vector < int > v; 
v.reserve( 10 ); 
 for ( int i = 1 ; i <= 10 ; \++ i) \{ 
v.push\_back(i); 
\} 
cout << v.size(); // 10 
 v\[ 3 \] = v\[ 5 \] = v\[ 9 \] = 99 ; 
remove(v.begin(), v.end(), 99 ); 
 // v.erase(remove(v.begin(),v.end(),99),v.end()); 
 cout << v.size(); // 10！

2. list

list<int> listTest;

listTest.remove(99);// 这个成员函数将真的删除元素，并且要比 erase+remove 高效

remove 和 remove\_if 之间的十分相似。但 unique 行为也像 remove 。它用来从一个区间删除东西（邻近的重复值）而不用访问持有区间元素的容器。如果你真的要从容器中删除元素，你也必须成对调用 unique 和 erase ， unique 在 list 中也类似于 remove 。正像 list::remove 真的删除东西（而且比 erase-remove 惯用法高效得多）。 list::unique 也真的删除邻近的重复值（也比 erase-unique 高效）。

三 迭代器失效：

一个网友提的问题：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][] Code 
void main() 
\{ 
vector <string> vcs; 
vcs.push\_back( "this is A"); 
vector <string> ::iterator it=vcs.begin(); 
int i=9; 
for(;it!=vcs.end();\++it) 
\{ 
cout < <"caplity of vector is : "<<vcs.size()<<endl; 
 
cout < <"\--->"<<\*it <<endl; //去掉此句会有一个超过vector 
//大小的循环，高手能解释一下为什么? 
if(i==9) 
\{ 
vcs.push\_back( "this is BBBBB"); 
cout < <"vcs.push!"<<endl; 
\} 
i=8; 
\} 
\} 
典型的迭代器失效![dot.gif][].

vector：  
1.当插入（push\_back）一个元素后，end操作返回的迭代器肯定失效。  
2.当插入(push\_back)一个元素后，capacity返回值与没有插入元素之前相比有改变，则需要重新加载整个容器，此时first和end操作返回的迭代器都会失效。  
3.当进行删除操作（erase，pop\_back）后，指向删除点的迭代器全部失效；指向删除点后面的元素的迭代器也将全部失效。

\#include<queue>

deque迭代器的失效情况：  
1.在deque容器首部或者尾部插入元素不会使得任何迭代器失效。  
2.在其首部或尾部删除元素则只会使指向被删除元素的迭代器失效。  
3.在deque容器的任何其他位置的插入和删除操作将使指向该容器元素的所有迭代器失效。

List/set/map

1. 删除时，指向该删除节点的迭代器失效

list < int > intList; 
list < int > ::iterator it = intList.begin(); 
 while (it != intList.end()) 
\{ 
it = intList.erase(it); 
…… 
\}

四.选择时机<转>--总结各种容器特点

(1) vector  
内部数据结构：数组。  
随机访问每个元素，所需要的时间为常量。  
在末尾增加或删除元素所需时间与元素数目无关，在中间或开头增加或删除元素所需时间随元素数目呈线性变化。  
可动态增加或减少元素，内存管理自动完成，但程序员可以使用reserve()成员函数来管理内存。  
vector的迭代器在内存重新分配时将失效（它所指向的元素在该操作的前后不再相同）。当把超过capacity()-size()个元素插入vector中时，内存会重新分配，所有的迭代器都将失效；否则，指向当前元素以后的任何元素的迭代器都将失效。当删除元素时，指向被删除元素以后的任何 元素的迭代器都将失效。  
  
(2)deque  
内部数据结构：数组。  
随机访问每个元素，所需要的时间为常量。  
在开头和末尾增加元素所需时间与元素数目无关，在中间增加或删除元素所需时间随元素数目呈线性变化。  
可动态增加或减少元素，内存管理自动完成，不提供用于内存管理的成员函数。  
增加任何元素都将使deque的迭代器失效。在deque的中间删除元素将使迭代器失效。在deque的头或尾删除元素时，只有指向该元素的迭代器失效。  
  
(3)list  
内部数据结构：双向环状链表。  
不能随机访问一个元素。  
可双向遍历。  
在开头、末尾和中间任何地方增加或删除元素所需时间都为常量。  
可动态增加或减少元素，内存管理自动完成。  
增加任何元素都不会使迭代器失效。删除元素时，除了指向当前被删除元素的迭代器外，其它迭代器都不会失效。  
  
(4)slist  
内部数据结构：单向链表。  
不可双向遍历，只能从前到后地遍历。  
其它的特性同list相似。  
  
(5)stack  
适配器，它可以将任意类型的序列容器转换为一个堆栈，一般使用deque作为支持的序列容器。  
元素只能后进先出（LIFO）。  
不能遍历整个stack。  
  
(6)queue  
适配器，它可以将任意类型的序列容器转换为一个队列，一般使用deque作为支持的序列容器。  
元素只能先进先出（FIFO）。  
不能遍历整个queue。  
  
(7)priority\_queue  
适配器，它可以将任意类型的序列容器转换为一个优先级队列，一般使用vector作为底层存储方式。  
只能访问第一个元素，不能遍历整个priority\_queue。  
第一个元素始终是优先级最高的一个元素。  
  
(8)set  
键和值相等。  
键唯一。  
元素默认按升序排列。  
如果迭代器所指向的元素被删除，则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。  
  
(9)multiset  
键可以不唯一。  
其它特点与set相同。  
  
(10)hash\_set  
与set相比较，它里面的元素不一定是经过排序的，而是按照所用的hash函数分派的，它能提供更快的搜索速度（当然跟hash函数有关）。  
其它特点与set相同。  
  
(11)hash\_multiset  
键可以不唯一。  
其它特点与hash\_set相同。  
  
(12)map  
键唯一。  
元素默认按键的升序排列。  
如果迭代器所指向的元素被删除，则该迭代器失效。其它任何增加、删除元素的操作都不会使迭代器失效。  
  
(13)multimap  
键可以不唯一。  
其它特点与map相同。  
  
(14)hash\_map  
与map相比较，它里面的元素不一定是按键值排序的，而是按照所用的hash函数分派的，它能提供更快的搜索速度（当然也跟hash函数有关）。  
其它特点与map相同。  
  
(15)hash\_multimap  
键可以不唯一。  
其它特点与hash\_map相同。

deque 即双端队列。

（deque，全名double-ended queue）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，其限定插入和删除操作在表的两端进行。 　　双端队列是限定插入和删除操作在表的两端进行的线性表。这两端分别称做端点1和端点2。也可像 栈一样，可以用一个铁道转轨网络来比喻双端队列。在实际使用中，还可以有输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队 列）和输入受限的双端队列（即一个端点允许插入和删除，另一个端点只允许删除的双端队列）。而如果限定双端队列从某个端点插入的元素只能从该端点删除，则 该双端队列就蜕变为两个栈底相邻的栈了。 　　尽管双端队列看起来似乎比栈和队列更灵活，但实际上在应用程序中远不及栈和队列有用。

你也可以用std::copy来实现。  
std::copy( vec.begin(), vec.end(), p );  
p\[vec.size()\] = 0;

vector中大批量元素拷贝到本地磁盘。。用怎么的方法最快？  
自己只能想到循环拷贝。。各位兄弟姐妹有没有什么更好的方法

比如我建立一个结构体。。将此结构体的内容放在vector <T> vec变量中； 
当存放到10000个时。。我就想把这10000组数据移动到本地磁盘。怎么做才能更快些？ 
网友回复:vector内存放的元素内存是连续的，所以可以直接取第一个要保存数据的指针，然后向后10000个结构体大小的数据进行保存。 
保存后再用vector的erase来删除，记得要用区间的版本 vector <T>::erase(beg, end) 
网友回复:写了个例子。。。。。

\#include <iostream> 
\#include <vector> 
using namespace std;

//放入VECTOR并要保存的VECTOR中的结构体  
typedef struct TAG\_T1  
\{  
int i;  
\}TAG\_T1;

int main() 
\{ 
//赋值 
TAG\_T1 x1;x1.i = 1; 
TAG\_T1 x2; x2.i = 2; 
TAG\_T1 x3; x3.i = 3; 
vector <TAG\_T1> v; 
v.push\_back(x1); 
v.push\_back(x2); 
v.push\_back(x3);

//取首个元素指针  
TAG\_T1 \*pFirst = (TAG\_T1\*)&(\*v.begin());

//按内存顺序遍历三个元素 
cout < < (pFirst 0)->i < < endl; 
cout < < (pFirst 1)->i < < endl; 
cout < < (pFirst 2)->i < < endl;

//区间删除  
v.erase(v.begin(), v.begin() 3);  
return 0;  
\}  
网友回复:其中TAG\_T1 \*pFirst = (TAG\_T1\*)&(\*v.begin()); 中的v.begin()，可以按成其它迭代器即可  
本篇文章来源于 [www.itzhe.cn][] IT者网站 原文链接：[http://www.itzhe.cn/news/20080729/188050.html][http_www.itzhe.cn_news_20080729_188050.html]

废话不多说，直接上代码：

template< typename T> 
size\_t copy(std::vector<T> const& src, T\* dest, size\_t N) \{ 
size\_t count = std::min(N, src.size()); 
std::copy(src.begin(), src.begin()+count, dest); 
return count; 
\}

使用范例：

constint MAX\_SIZE = 10; 
double dArr\[MAX\_SIZE\]; 
vector< double> dVec(MAX\_SIZE, 1); 
copy(dVec, dArr, MAX\_SIZE); 
copy(dArr, dArr+MAX\_SIZE, ostream\_iterator< double>(cout, *" "*));

参考：

[http://stackoverflow.com/questions/633549/how-to-copy-the-contents-of-stdvector-to-c-style-static-array-][http_stackoverflow.com_questions_633549_how-to-copy-the-contents-of-stdvector-to-c-style-static-array-] [safely][http_stackoverflow.com_questions_633549_how-to-copy-the-contents-of-stdvector-to-c-style-static-array-]

**vector在C++中的详细说明**

vector是C++标准模板库中的部分内容，它是一个多功能的，能够操作多种数据结构和算法的模板类和函数库。vector之所以被认为是一个容器，是因为它能够像容器一样存放各种类型的对象，简单地说，vector是一个能够存放任意类型的动态数组，能够增加和压缩数据。

为了可以使用vector，必须在你的头文件中包含下面的代码：

\#include<vector>

vector属于std命名域的，因此需要通过命名限定，如下完成你的代码：

using std::vector;

vector<int>vInts;

或者连在一起，使用全名：

std::vector<int>vInts;

建议使用全局的命名域方式：usingnamespace std;

函数

表述

c.assign(beg,end)c.assign(n,elem)

将\[beg; end)区间中的数据赋值给c。将n个elem的拷贝赋值给c。

c.at(idx)

传回索引idx所指的数据，如果idx越界，抛出out\_of\_range。

c.back()

传回最后一个数据，不检查这个数据是否存在。

c.begin()

传回迭代器中的第一个数据地址。

c.capacity()

返回容器中数据个数。

c.clear()

移除容器中所有数据。

c.empty()

判断容器是否为空。

c.end()

指向迭代器中末端元素的下一个，指向一个不存在元素。

c.erase(pos)

c.erase(beg,end)

删除pos位置的数据，传回下一个数据的位置。

删除\[beg,end)区间的数据，传回下一个数据的位置。

c.front()

传回第一个数据。

get\_allocator

使用构造函数返回一个拷贝。

c.insert(pos,elem)

c.insert(pos,n,elem)

c.insert(pos,beg,end)

在pos位置插入一个elem拷贝，传回新数据位置。在pos位置插入n个elem数据。无返回值。在pos位置插入在\[beg,end)区间的数据。无返回值。

c.max\_size()

返回容器中最大数据的数量。

c.pop\_back()

删除最后一个数据。

c.push\_back(elem)

在尾部加入一个数据。

c.rbegin()

传回一个逆向队列的第一个数据。

c.rend()

传回一个逆向队列的最后一个数据的下一个位置。

c.resize(num)

重新指定队列的长度。

c.reserve()

保留适当的容量。

c.size()

返回容器中实际数据的个数。

c1.swap(c2)

swap(c1,c2)

将c1和c2元素互换。同上操作。

vector<Elem>

cvector<Elem>c1(c2)

vector <Elem>c(n)

ector <Elem>c(n, elem)

vector <Elem>c(beg,end)

c.~ vector<Elem>()

创建一个空的vector。复制一个vector。创建一个vector，含有n个数据，数据均已缺省构造产生。创建一个含有n个elem拷贝的vector。创建一个以\[beg;end)区间的vector。销毁所有数据，释放内存。

operator\[\]

返回容器中指定位置的一个引用。

创建一个vector

vector容器提供了多种创建方法，下面介绍几种常用的。

创建一个Widget类型的空的vector对象：

vector<Widget>vWidgets;

创建一个包含500个Widget类型数据的vector：

vector<Widget>vWidgets(500);

创建一个包含500个Widget类型数据的vector，并且都初始化为0：

vector<Widget>vWidgets(500, Widget(0));

创建一个Widget的拷贝：

vector<Widget>vWidgetsFromAnother(vWidgets);

向vector添加一个数据

vector添加数据的缺省方法是push\_back()。push\_back()函数表示将数据添加到vector的尾部，并按需要来分配内存。例如：向vector<Widget>中添加10个数据，需要如下编写代码：

for(int i=0;i<10; i++) \{

vWidgets.push\_back(Widget(i));

获取vector中制定位置的数据

vector里面的数据是动态分配的，使用push\_back()的一系列分配空间常常决定于文件或一些数据源。如果想知道vector存放了多少数据，可以使用empty()。获取vector的大小，可以使用size()。例如，如果想获取一个vectorv的大小，但不知道它是否为空，或者已经包含了数据，如果为空想设置为\-1，你可以使用下面的代码实现：

int nSize =v.empty() ? -1 : static\_cast<int>(v.size());

访问vector中的数据

使用两种方法来访问vector。

1、vector::at()

2、vector::operator\[\]

operator\[\]主要是为了与C语言进行兼容。它可以像C语言数组一样操作。但at()是我们的首选，因为at()进行了边界检查，如果访问超过了vector的范围，将抛出一个例外。由于operator\[\]容易造成一些错误，所有我们很少用它，下面进行验证一下：

分析下面的代码：

vector<int>v;

v.reserve(10);

for(int i=0;i<7; i++) \{

v.push\_back(i);

try \{int iVal1 =v\[7\];

// not boundschecked - will not throw

int iVal2 =v.at(7);

// bounds checked -will throw if out of range

\} catch(constexception& e) \{

cout <<e.what();

删除vector中的数据

vector能够非常容易地添加数据，也能很方便地取出数据，同样vector提供了erase()，pop\_back()，clear()来删除数据，当删除数据时，应该知道要删除尾部的数据，或者是删除所有数据，还是个别的数据。

Remove\_if()算法如果要使用remove\_if()，需要在头文件中包含如下代码：：

\#include<algorithm>

Remove\_if()有三个参数：

1、iterator \_First：指向第一个数据的迭代指针。

2、iterator \_Last：指向最后一个数据的迭代指针。

3、predicate \_Pred：一个可以对迭代操作的条件函数。

条件函数

条件函数是一个按照用户定义的条件返回是或否的结果，是最基本的函数指针，或是一个函数对象。这个函数对象需要支持所有的函数调用操作，重载operator()()操作。remove\_if()是通过unary\_function继承下来的，允许传递数据作为条件。

例如，假如想从一个vector<CString>中删除匹配的数据，如果字串中包含了一个值，从这个值开始，从这个值结束。首先应该建立一个数据结构来包含这些数据，类似代码如下：

\#include<functional>

enum findmodes \{

FM\_INVALID = 0,

FM\_IS,

FM\_STARTSWITH,

FM\_ENDSWITH,

FM\_CONTAINS

\};

typedef structtagFindStr \{

UINT iMode;

CString szMatchStr;

\} FindStr;

typedef FindStr\*LPFINDSTR;

然后处理条件判断：

class FindMatchingString: public std::unary\_function<CString, bool> \{

public:

FindMatchingString(constLPFINDSTR lpFS) :

m\_lpFS(lpFS) \{

booloperator()(CString& szStringToCompare) const \{

bool retVal =false;

switch(m\_lpFS->iMode) \{

case FM\_IS: \{

retVal =(szStringToCompare == m\_lpFDD->szMatchStr);

break;

case FM\_STARTSWITH:\{

retVal =(szStringToCompare.Left(m\_lpFDD->szMatchStr.GetLength())

==m\_lpFDD->szWindowTitle);

break;

case FM\_ENDSWITH: \{

retVal =(szStringToCompare.Right(m\_lpFDD->szMatchStr.GetLength())

==m\_lpFDD->szMatchStr);

break;

case FM\_CONTAINS: \{

retVal =(szStringToCompare.Find(m\_lpFDD->szMatchStr) != -1);

break;

return retVal;

private:

LPFINDSTR m\_lpFS;

\};

通过这个操作你可以从vector中有效地删除数据：

FindStr fs;

fs.iMode =FM\_CONTAINS;

fs.szMatchStr =szRemove;

vs.erase(std::remove\_if(vs.begin(),vs.end(), FindMatchingString(&fs)), vs.end());

Remove(),remove\_if()等所有的移出操作都是建立在一个迭代范围上的，不能操作容器中的数据。所以在使用remove\_if()，实际上操作的时容器里数据的上面的。

看到remove\_if()实际上是根据条件对迭代地址进行了修改，在数据的后面存在一些残余的数据，那些需要删除的数据。剩下的数据的位置可能不是原来的数据，但他们是不知道的。

调用erase()来删除那些残余的数据。注意上面例子中通过erase()删除remove\_if()的结果和vs.enc()范围的数据。

例子：

//--------------------------------------------------------------------------- 
 
\#include <vcl.h> 
\#pragma hdrstop 
 
\#include "Unit1.h" 
//--------------------------------------------------------------------------- 
\#pragma package(smart\_init) 
\#pragma resource "\*.dfm" 
TForm1 \*Form1; 
 
\#include <vector> 
\#include <assert.h> 
 
using namespace std; 
 
struct STResult 
\{ 
double Time; 
double Xp; 
double Yp; 
int id; 
\}; 
 
//--------------------------------------------------------------------------- 
\_\_fastcall TForm1::TForm1(TComponent\* Owner) 
: TForm(Owner) 
\{ 
\} 
 
vector <STResult> ResultVector; 
 
void \_\_fastcall test() 
\{ 
//test 
//vector <STResult> ResultVector; 
STResult stritem; 
stritem.Time = .1; 
stritem.Xp = .1; 
stritem.Yp = .1; 
stritem.id = 1; 
 
ResultVector.push\_back( stritem ); 
 
\} 
//--------------------------------------------------------------------------- 
void \_\_fastcall TForm1::Button1Click(TObject \*Sender) 
\{ 
test(); 
assert(ResultVector\[0\].id == 1); 
\} 
//---------------------------------------------------------------------------

C++ Vector用法深入剖析

[C++][C]编程语言中有一种叫做Vector的应用方法，它的作用在实际编程中是非常重要的。在这里我们将会为大家详细介绍一下C++ Vector的相关应用技巧及基本内容，希望能给大家带来一些帮助。

(1)vector< 类型 > 标识符 ;

(2)vector< 类型 > 标识符(最大容量) ；

(3)vector< 类型 > 标识符（最大容量，初始所有值）；

(4) int i\[4\] = \{12,3,4,5\};

1. vector**<**类型**>** vi(i , i+2); //得到i索引值为3以后的值；

(5)vector< vector<int> > //vi 定义2维的容器；记得一定要有空格，不然会报错

2. vector**<****int****>** line

3. // 在使用的时候一定要首先将vi个行进行初始化;

4. for(int i = 0 ; i **<****10** ; i ++)

5. \{

6. vector.push\_back(line);

7. \}

8. /// 个人认为使用vector定义二维数组很好，  
因为是长度可以不预先确定。很好。

(6)C++ Vector排序

9. vector**<****int****>** vi ;

10. vi.push\_back(1);

11. vi.push\_back(3);

12. vi.push\_back(0);

13. sort(vi.begin() , vi.end()); /// /小到大

14. reverse(vi.begin(),vi.end()) /// 从大道小

(7)顺序访问

15. vector **<****int****>** vi ;

16. for( int i = 0 ; i **<****10** ; i ++)

17. \{

18. vector.push\_back(i);

19. \}

20. for(int i = 0 ; i **<****10** ; i ++) /// 第一种调用方法

21. \{

22. cout **<<vector**\[i\] **<<**" " ;

23. \}

24. for(vector**<int>**::iterator it = vi.begin() ;

25. it !=vi.end() ; it++) ///第二种调用方法

26. \{

27. cout **<<** \*it **<<** " " ;

28. \}

(8)寻找

29. vector **<****int****>** vi ;

30. for( int i = 0 ; i **<****10** ; i ++)

31. \{

32. vector.push\_back(i);

33. \}

34. vector **<****int****>**::interator it = find(vi.begin() , vi.end,3) ;

35. cout **<<** \*it **<<****endl** ; ///返回容器内找到值的位置。

(9)使用数组对C++ Vector进行初始化

36. int i\[10\] =\{1,2,3,4,5,6,7,78,8\} ;

37. ///第一种

38. vector**<int>** vi(i+1,i+3); ///从第2个元素到第三个元素

39. for(vector **<int>**::interator it = vi.begin() ;

40. it != vi.end() ; it++)

41. \{

42. cout **<<** \*it **<<**" " ;

43. \}

(10) 结构体类型

44. struct temp

45. \{

46. public :

47. string str ;

48. public :

49. int id ;

50. \}tmp

51. int main()

52. \{

53. vector **<temp>** t ;

54. temp w1 ;

55. w1.str = "Hellowor" ;

56. w1.id = 1 ;

57. t.push\_back(t1);

58. cout **<<****w1.str****<<** "," **<<w1.id****<<endl** ;

59. return 0 ;

60. \}

[http_boost.org]: http://boost.org
[ContractedBlock.gif]: http://www.cnblogs.com/Images/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220609/b7413465e72f4cc8a52cd77e4e77f4b9.png
[dot.gif]: /images/20220609/5eee0322707341d59f1b914dac817e3e.png
[www.itzhe.cn]: http://www.itzhe.cn/
[http_www.itzhe.cn_news_20080729_188050.html]: http://www.itzhe.cn/news/20080729/188050.html
[http_stackoverflow.com_questions_633549_how-to-copy-the-contents-of-stdvector-to-c-style-static-array-]: http://stackoverflow.com/questions/633549/how-to-copy-the-contents-of-stdvector-to-c-style-static-array-safely
[C]: http://developer.51cto.com/art/200709/56340.htm