C++的容器

最近在做一些leetcode的题，有时选择了用C++来写，离不开一些C++容器的使用。于是总结一下C++容器。

顺序性容器

vector是一种动态数组，在内存中具有连续的存储空间，支持快速随机访问。由于具有连续的存储空间，所以在插入和删除操作方面，效率比较慢。
默认的构造函数是构造一个初始长度为0的内存空间，且分配的内存空间是以2的倍数动态增长的。
在push_back的过程中，若发现分配的内存空间不足，则重新分配一段连续的内存空间，其大小是现在连续空间的2倍，再将原先空间中的元素复制到新的空间中。
clear函数只是把vector的size清为零，但vector中的元素在内存中并没有消除，所以在使用vector的过程中会发现内存消耗会越来越多，导致内存泄露，现在经常用的方法是swap函数来进行解决。
利用swap函数，和临时对象交换，使V对象的内存为临时对象的内存，而临时对象的内存为V对象的内存。交换以后，临时对象消失，释放内存。
1
2
3
4
5
vector<int> V;
V.push_back(1);
V.push_back(2);
vector<int>().swap(V);
//或者 V.swap(vector<int>());

deque支持双端插入数据。deque的内存空间分布是小片的连续，小片间用链表相连，实际上内部有一个map的指针。deque空间的重新分配要比vector快，重新分配空间后，原有的元素是不需要拷贝的。

支持常数时间从容器任何位置插入和移除元素的容器。不支持快速随机访问。它通常实现为双向链表。

map是一种关联容器，该容器用唯一的关键字来映射相应的值，即具有key-value功能。map内部自建一棵红黑树（一种自平衡二叉树），这棵树具有数据自动排序的功能，所以在map内部所有的数据都是有序的，以二叉树的形式进行组织。

queue是一个队列，实现先进先出功能。queue是在deque的基础上封装的。

stack是实现先进后出的功能，和queue一样，也是内部封装了deque。

第一个图为简化图（其中粗线部分是重点的容器），第二个图为完整容器分类图