对STL容器的理解

此文章只是对stl容器的底层实现方式以及优缺点进行一些简单的分析，并不会详细讲解容器内部相关的接口功能。 只希望知道各种容器的优缺点，在需要使用容器时选择更为合适的容器来使用。

1.array：

以线性排列的方式来存储特定类型的数据。 其实类似于普通数组，同样支持随机访问且效率高、存储大小固定，但多了一些类似迭代器访问、获取容器等高级功能。

特点：

1.容器长度固定，不能增删元素，只能改变元素的值。

2.储存空间连续，可以随机访问元素的值。

3.值无任何排序，仅根据插入容器的顺序排列。

2.vector:

和array容器有点类似，但可以扩容，所以支持增删元素。

特点：

1.支持添加和删除元素，当vector的内存空间耗尽时，会进行扩容。

2.在尾部插入和删除元素效率很高，在非尾部插入和删除元素效率很低。如：插入元素时，需要把插入元素后面的元素都往后移动一位，再插入元素。（删除同原理）

3.储存空间连续，可以随机访问元素的值。

4.值无任何排序，仅根据插入容器的顺序排列。

3.deque

和vector容器类似，但在首尾插入元素都很快捷。

1.支持添加和删除元素。

2.在首尾插入元素效率很高，在其他部位插入元素效率很低。

3.并非连续的储存空间。

4.值无序。

PS：如没大量头部插入元素需求，建议还是用vector容器比较好。

4.list

双向链表的形式，在中间插入和删除元素都非常方便快捷，但要访问中间的元素只能从头部或者尾部顺序访问。

特点：

1.插入和删除元素效率极高。

2.访问元素的值，只能通过链头链尾逐一顺序访问。

3.并非连续的储存空间。

4.值无序。

5.set

属于关联容器，通过红黑树实现值的快速查找，而且值的增删效率也非常高。

1.查找效率非常高，虽然比不上vector这种随机访问元素值的效率，但查找二叉树的值，log2的查找效率也是非常非常高的，存储的元素数量每高1倍，查找次数也只增加1次。

2.增删值同样非常高效，他不像vector这种内存连续的容器这样（增加一个元素，在其后面的元素都要往后移动），而是更像list这种链表的形式，叶子节点通过指针指向父节点，修改层级只需改动指针即可，当然，也需要通过一定的方式来旋转红黑树，最终才能完成节点的插入且保持其顺序。

3.并非连续的储存空间。

4.值有序且唯一。

6.map

属于关联容器，和set一样，实现原理也是使用红黑树，但map使用的是<key, value>这种键值对，在红黑树内部通过key来进行排序。

1.直接通过key来获取value效率还是挺高的（类似于set的原理），但如果没有key，想要查找对应的value，就只能通过遍历map了。

2.增删值的效率也非常高（类似于set的原理）

3.并非连续的存储空间。

4.key有序且唯一。

5.value无序且不唯一。