STL常用容器.docx

STL常用容器
STL是C/C++开发中一个非常重要的模板，而其中定义的各种容器也是非常方便我们 大家使用。下面，我们就浅谈某些常用的容器。这里我们不涉及容器的基本操作之类，只 是要讨论一下各个容器其各自的特点。STL中的常用容器包括：顺序性容器(vector, deque、list)、关联容器(map、set) 容器适配器(queue、stac)。1、顺序性容器 (1) vector
vector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具 有连续的存储空间，所以在插入和删除操作方面，效率比较慢。vector有多个构造函数， 默认的构造函数是构造一个初始长度为0的内存空间，旦分配的内存空间是以2的倍数动 态增长的，即内存空间增长是按照20, 21, 22, 23.....增长的,在push_back的过程中，若 发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2 倍，再将原先空间中的元素复制到新的空间中，性能消耗比较大，尤其是当元素是非内部 数据时(非内部数据往往构造及拷贝构造函数相当复杂)。vector的另一个常见的问题就是 clear操作。clear函数只是把vector的size清为零，但vector中的元素在内存中并没 有消除，所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露，现在 经常用的方法是swap函数来进行解决：vector V;
V. push_back(l); V. push_back(2);V. push_back(l); V. push_back(2); vector 0. swap(V); 或者 V. swap (vector 0);
利用swap函数，和临时对象交换，使V对象的内存为临时对象的内存，而临时对象 的内存为V对象的内存。交换以后，临时对象消失，释放内存。(2) deque
deque和vector类似,支持快速随机访问。二者最大的区别在于,vector只能在末 端插入数据，而deque支持双端插入数据。deque的内存空间分布是小片的连续，小片间 用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新 分配空间后，原有的元素是不需要拷贝的。(3) list
list是一个双向链表，因此它的内存空间是可以不连续的，通过指针来进行数据的访 问，这使list的随机存储变得非常低效，因此list没有提供口操作符的重载。但list 可以很好地支持任意地方的插入和删除，只需移动相应的指针即可。
(4)在实际使用时，如何选择这三个容器中哪一个，应根据你的需要而定，一般应 遵循下面的原则： 1)如果你需要高效的随即存取，而不在乎插入和删除的效率，使
用vector 2)如果你需要大量的插入和删除，而不关心随即存取，则应使用list 3)如果你需要随即存取，而且关心两端数据的插入和删除，则应使用deque 2、关联容器 (1) map
map是一种关联容器，该容器用唯一的关键字来映射相应的值，即具有key-value功 能, map内部自建一棵红黑树(一种白平衡二又树)，这棵树具有数据自动排序的功能， 所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。这是map的模板：
templat