STL高效编程(-) STL的容器

STL有很多概念，迭代器，高效的算法，函数对象，但是对于大多数的开发者而言，STL最突出的地方还是容器(Container)，容器远远比数组强大和灵活。

容器可以动态增长，独立管理内存，提供对容器元素的高效的灵活的访问，等等。STL容器是有效的封装最常见的数据结构和算法，在我看来，STL容器就是代表着c++的数据结构，从数组，链表，栈，队列，表，哈希表。每一个容器代表着一种数据结构。

概括一下，STL的容器可以分为以下几个大类:

一：序列容器，　有vector, list, deque, string.

二 : 关联容器,     有set, multiset, map, mulmap, hash_set, hash_map, hash_multiset, hash_multimap

                                 带有下划线的是非标准的，如果是VC8.0的话，在stdext名字空间里。

三: 其他的杂项： stack, queue, valarray, bitset

由此可见，STL为我们提供了那么多的容器，如果想要有效的使用它们，你真的需要弄明白每个容器是干什么的。最好你能知道他们的一些实现原理，陆续的我还会写一些STL容器实现的文章。容器的实现往往决定着你如何更好的使用容器。下面简单讲一下STL各个容器的实现:

1. vector: 内部实现是数组，一段连续的内存。

2. list， 内部实现是双链表

3. deque 内部实现是内存块的链表。

4. string： 连续的内存

5. set，map： 红黑树(平衡二叉树的一种)

6. hash_map, hash_set 用哈希表(散列表)来实现。

7. stack: 用vector或者是deque来实现

8. queue,用deque实现

本文仅当时抛砖引玉，大致讲一下选择容器的一些原则。

1. 你需要“可以在容器的任意位置插入一个新元素”的能力吗？如果是，你需要序列容器，关联容器做不到。

2. 你关心元素在容器中的顺序吗？如果不，散列容器就是可行的选择。否则，你要避免使用散列容器。

3. 必须使用标准C++中的容器吗？如果是，就可以除去散列容器、slist和rope。

4. 你需要哪一类迭代器？如果必须是随机访问迭代器，在技术上你就只能限于vector、deque和string，但

你也可能会考虑rope.

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

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

7. 查找速度很重要吗？如果是，你就应该看看散列容器，排序的vector和

标准的关联容器——仅供参考。

● 你介意如果容器的底层使用了引用计数吗？如果是，你就得避开string，因为很多string的实现是用引

用计数。于是你得重新审核你的string，你可以考虑使用vector<char>。

● 你需要插入和删除的事务性语义吗？也就是说，你需要有可靠地回退插入和删除的能力吗？如果是，

你就需要使用基于节点的容器。如果你需要多元素插入的事务性语义，你就应该选择list，因为list是唯一

提供多元素插入事务性语义的标准容器。事务性语义对于有兴趣写异常安全代码的程序员来说非常重要。

（事务性语义也可以在连续内存容器上实现，但会有一个性能开销，而且代码不那么直观。要了解这方

面的知识，请参考Sutter的《Exceptional C++》。

● 你要把迭代器、指针和引用的失效次数减到最少吗？如果是，你就应该使用基于节点的容器，因为在

这些容器上进行插入和删除不会使迭代器、指针和引用失效（除非它们指向你删除的元素）。一般来

说，在连续内存容器上插入和删除会使所有指向容器的迭代器、指针和引用失效。

● 你需要具有有以下特性的序列容器吗：1）可以使用随机访问迭代器；2）只要没有删除而且插入只发

生在容器结尾，指针和引用的数据就不会失效？  这个一个非常特殊的情况，但如果你遇到这种情况，

deque就是你梦想的容器。（有趣的是，当插入只在容器结尾时，deque的迭代器也可能会失效，deque

是唯一一个“在迭代器失效时不会使它的指针和引用失效”的标准STL容器。为什么呢？这是由实现所决定的，

STL高效编程(二)- 注意容器的不同特点，小心容器无关的代码

STL是建立在泛型之上的。数组泛型为容器，以对象类型为参数。函数泛型成算法，以迭代器类型为参数。指针泛型为迭代器，参数化了所指向的对象的类型。

这只是个开始。独立的容器类型泛化为序列或关联容器，而且类似的容器拥有类似的功能。标准的以连续内存为实现的容器都提供随机访问迭代器，标准的基 于节点的容器都提供双向迭代器。序列容器支持push_front或push_back，但关联容器不支持。关联容器提供对数时间复杂度的 lower_bound、upper_bound和equal_range成员函数，但序列容器却没有。

明白容器的不同特性，对STL编程很重要，因此，写容器无关的代码是很危险的。尽管STL提供了很多一致的接口和迭代器类型。

最热心的“容器无关代码”的鼓吹者很快发现，写既要和序列容器又要和关联容器一起工作的代码并没有什么意义。很多成员函数只存在于其中一类容器中， 比如，只有序列容器支持push_front或push_back，只有关联容器支持count和lower_bound，等等。在不同种类中，甚至连一 些如insert和erase这样简单的操作在名称和语义上也是天差地别的。举个例子，当你把一个对象插入一个序列容器中，它保留在你放置的位置。但如果 你把一个对象插入到一个关联容器中，容器会按照的排列顺序把这个对象移到它应该在的位置。举另一个例子，在一个序列容器上用一个迭代器作为参数调用 erase，会返回一个新迭代器，但在关联容器上什么都不返回。

假设, 你希望写一段可以用在所有常用的序列容器上——vector, deque和list——的代码。很显然，你必须使用它们接口的交集来编写，这意味着不能使用reserve或capacity，因为deque和 list不支持它们。由于list的存在意味着你得放弃operator[]，而且你必须受限于双向迭代器的性能。这意味着你不能使用需要随机访问迭代器 的算法，包括sort，stable_sort，partial_sort和nth_element

另一方面，你渴望支持vector的规则，不使用push_front和pop_front，而且用vector和deque都会使splice和成员函数方式的sort失败。在上面约束的联合下，后者意味着你不能在你的“泛化的序列容器”上调用任何一种sort。

这是显而易见的。如果你冒犯里其中任何一条限制，你的代码会在至少一个你想要使用的容器配合时发生编译错误。可见这种代码有多阴险。

这里的罪魁祸首是不同的序列容器所对应的不同的迭代器、指针和引用的失效规则。要写能正确地和vector, deque和list配合的代码，你必须假设任何使那些容器的迭代器，指针或引用失效的操作符真的在你用的容器上起作用了。因此，你必须假设每次调用 insert都使所有东西失效了，因为deque::insert会使所有迭代器失效，而且因为缺少capacity，vector::insert也必 须假设使所有指针和引用失效。（条款1 解释了deque是唯一一个在迭代器失效的情况下指针和引用仍然有效的东西）类似的理由可以推出一个结论，所有对erase的调用必须假设使所有东西失效。

STL高效编程(三)-使容器元素的拷贝正确和高效

首先，你必须要明白的是，容器容纳着许多对象，但不是你传给它的那些原始对象，而是对象的拷贝。

此外，当你从容器中获取一个对象时，得到的不是容器里的那个对象，而是对象的拷贝。同样的，当你向容器中添加一个对象时（通过insert或push_back），添加到容器的是你给的对象的拷贝 。 copy进去，copy出来,这就是STL的方式。所以，STL要求对象必须是可拷贝的。对象被存到容器里之后，对它的拷贝并不少见。如果你从 vector、string或deque中插入或删除了元素，现有元素会移动（拷贝）。如果你使用了任何排序算法，一般的排序算法都要求交换，交换是需要 拷贝的，这种例子很多。

你可能会对所有这些拷贝是怎么完成的感兴趣。这很简单，一个对象通过使用它的拷贝成员函数来拷贝，特别是它的拷贝构造函数和它的拷贝赋值构造函数。这就是传说中的BIG 3. 对于用户自定义类，比如Widget，这些函数传统上是这么声明的：

class Widget { 

public: 

	...      

 Widget();       

Widget(const Widget&);		// 拷贝构造函数      

Widget& operator=(const Widget&);	// 拷贝赋值操作符

 	... 

};

      

如果你自己没有声明这些函数，你的编译器会在需要的时候为你生成它们。拷贝内建类型（比如int、指针等）也始终是通过简单地拷贝他们的二进制 bit值来完成的。（有关拷贝构造函数和赋值操作符的详细情况，请参考任何C++的介绍性书籍。我想你推荐c++ programming和inside c++ project model.这两本书讲的很透彻）。

如果你用一个拷贝操作很昂贵的对象填充一个容器，那么一个简单的操作——把对象放进容器也会被证明为是一个性能瓶颈。容器中移动越多的东西，你就会在拷贝上浪费越多的内存和CPU时钟周期。此外，如果你定义了的有问题拷贝构造函数，这也会直接影响到容器。

当然由于继承的存在，拷贝会导致切割片（slicing）。那就是说，如果你以基类对象建立一个容器，而你试图插入派生类对象，那么当对象（通过基类的拷贝构造函数）拷入容器的时候对象的派生部分会被删除。

vector<Widget> vw; 

class SpecialWidget:	// SpecialWidget从上面的Widget派生

public Widget {...};

SpecialWidget sw; 

vw.push_back(sw);		// sw被当作基类对象拷入vw， 当拷贝时它的子类部分丢失了      

切片问题暗示了把一个派生类对象插入基类对象的容器几乎总是错的。如果你希望结果对象表现为派生类对象，比如，调用派生类的虚函数等，总是错的。（关于slicing问题更多的背景知识，请参考《Effective C++》条款22。）

一个使拷贝更高效、正确而且避免分割问题的简单的方式是建立指针的容器而不是对象的容器。也就是说，不是建立一个Widget的容器，建立一个 Widget*的容器。拷贝指针很快，而且不会有额外的开销（仅仅是简单的的二进制值的拷贝），而且当指针拷贝时不会产生slicing的问题。美中不足 的是，指针的容器有带来了另外一个令人头疼的问题，你需要自己手动来删除这些指针。如果你不想手动来删除指针，在权衡效率、正确性和slicing这些因 素时，智能指针会是一个不错的解决方案。

如果所有这些使STL的拷贝机制听起来很疯狂，就请重新想想。是，STL进行了大量拷贝，但它一般设计时，会尽量避免不必要的对象拷贝，实际上，它的实现也尽量避免不必要的对象拷贝。和C和C++内建容器的行为做个对比，下面的数组：

即使我们一般只使用其中的一些或者我们立刻使用从某个地方获取（比如，一个文件）的值覆盖每个默认构造的值，这也得构造maxNumWidgets个Widget对象。使用STL来代替数组，你可以使用一个可以在需要的时候增长的vector：

我们也可以建立一个可以足够包含maxNumWidgets个Widget的空vector，但没有构造Widget：

vector<Widget> vw;

vw.reserve(maxNumWidgets);

和数组对比，STL容器更灵活。它们只建立（通过拷贝）你需要的个数的对象，而且它们只在你指定的时候做。是的，我们需要知道STL容器使用了拷贝，但是别忘了一个事实：相比数组来说它们仍然是一个进步。