STL中各类容器详细介绍

STL介绍

STL（Standard Template Library），即标准模板库，是一个具有工业强度的，高效的C++程序库。它被容纳于C++标准程序库（C++ Standard Library）中，是ANSI/ISO C++标准中最新的也是极具革命性的一部分。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

C++STL提供的数据结构

1. Sequence Containers：维持顺序的容器。

(a). vector：

动态数组，在堆中分配内存，是我们最常使用的数据结构之一。

特点：

底层结构 : 底层由动态数组实现 , 特点是存储空间连续 ;
访问遍历 : 支持随机访问迭代器 , 可使用下标访问 , 访问元素非常快 O(1) 复杂度 ;
插入 / 删除 : 尾部插入 / 删除效率高 O(1) 复杂度 ; 中间和头部插入/删除效率低 , 由于存储空间连续 , 需要将插入 / 删除位置之后的元素依次改变位置 , O(n) 复杂度 ;
空间效率 : 底层实现时 , 会事先预留一些额外空间 , 以减少重新分配的次数 ;
使用场景 : 需要随机访问且频繁在尾部进行操作的场景 ; 如果频繁增删元素则不适用该容器 ;

时间复杂度：

实现原理：

简单理解，就是vector是利用上述三个指针来表示的，基本示意图如下：
在这里插入图片描述
两个关键大小：
大小：size=_Mylast - _Myfirst；
容量：capacity=_Myend - _Myfirst；
分别对应于resize()、reserve()两个函数。

size表示vector中已有元素的个数，capacity表示vector最多可存储的元素的个数；

为了降低二次分配时的成本，vector实际配置的内存空间大小会比客户需求的更大一些，以备将来扩充，这就是capacity的概念。即capacity>=size，当等于时，容器此时已满，若再要加入新的元素时，就要重新进行内存分配，整个vector的数据都要移动到新内存。

vector:扩容机制：

vector 容器扩容的过程需要经历以下 3 步：

1. 完全弃用现有的内存空间，重新申请更大的内存空间；

2. 将旧内存空间中的数据，按原有顺序移动到新的内存空间中；

3. 最后将旧的内存空间释放。

因为 vector 扩容需要申请新的空间，所以扩容以后它的内存地址会发生改变。vector 扩容是非常耗时的，为了降低再次分配内存空间时的成本，每次扩容时 vector 都会申请比用户需求量更多的内存空间（这也就是 vector 容量的由来，即 capacity>=size），以便后期使用。VS里面扩容机制是1.5倍扩容，gcc里面是2倍扩容。

(b). list：

双向链表，也可以当作 stack 和 queue 来使用。有个缺点，链表不支持快速随机读取。

特点

底层结构 : 底层由双向链表实现 , 特点是存储空间不连续 ;
访问遍历 : 不支持随机访问迭代器 , 只能通过迭代器进行访问 ;
插入 / 删除 : 任意位置插入 / 删除效率都很高 ;
空间效率 : 每个元素都需要分配额外的空间 , 存储当前元素的前驱元素和后继元素 ;
使用场景 : 需要在任意位置频繁插入 / 删除操作的场景 ;

时间复杂度：

(c). deque：

双端队列，是一种优化了的、对序列两端元素进行添加和删除操作的基本序列容器。它允许较为快速地随机访问，但它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小。它不需要重新分配空间，所以在两端端增删元素比vector 更有效。

特点：

底层结构 : 底层由双向队列实现 , 特点是存储空间连续 ;
访问遍历 : 支持随机访问迭代器 , 其性能比 vector 动态素组要低 ;
插入 / 删除 : 头部和尾部插入 / 删除效率高 , O(1) 复杂度 ; 中间插入/删除效率低 , 由于存储空间连续 , 需要将插入 / 删除位置之后的元素依次改变位置 , 比 vector 动态数组要快一些 ;
空间效率 : 底层实现时比 vector 的结构要复杂 , 也会事先预留一些额外空间 , 以减少重新分配的次数 ;
使用场景 : 需要随机访问且频繁在首部和尾部进行操作的场景 ; 如果频繁在中部增删元素则不适用该容器 ;

实现原理：

deque 是由一段一段的定量的连续空间构成。一旦有必要在 deque 前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在 deque 的头端或者尾端。deque 最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。
既然 deque 是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。

deque 采取一块所谓的 map（不是 STL 的 map 容器）作为主控，这里所谓的 map 是一小块连续的内存空间，其中每一个元素（此处成为一个结点）都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是 deque的存储空间的主体。

时间复杂度：

(d). array：

固定大小的数组，一般在刷题时我们不使用。

(e). forward_list：

单向链表，一般在刷题时我们不使用。

2. Container Adaptors：基于其它容器实现的数据结构。

(a). stack：

后入先出（LIFO）的数据结构，默认基于 deque 实现。stack 常用于深度优先搜
索、一些字符串匹配问题以及单调栈问题。

(b). queue：

先入先出（FIFO）的数据结构，默认基于 deque 实现。queue 常用于广度优先
搜索。

(c). priority_queue：

最大值先出的数据结构，默认基于vector实现堆结构。它可以在O(n log n)
的时间排序数组，O(log n) 的时间插入任意值，O(1) 的时间获得最大值，O(log n) 的时
间删除最大值。priority_queue 常用于维护数据结构并快速获取最大或最小值。

3. Associative Containers：实现了排好序的数据结构。

(a). set：

有序集合，元素不可重复，底层实现默认为红黑树，它可以在 O(n log n) 的时间排序数组，O(log n) 的时间插入、删除、查找任何节点。这里注意，set 和 priority_queue 都可以用
于维护数据结构并快速获取最大最小值，但是它们的时间复杂度和功能略有区别，如
priority_queue 默认不支持删除任意值，而 set 获得最大或最小值的时间复杂度略高，具
体使用哪个根据需求而定。

特点：

底层结构 : 底层由红黑树实现 , 红黑树是一种平衡二叉搜索树 , 存储空间不连续 ;
访问遍历 : 不支持随机访问迭代器 , 不能通过过下标访问 , 只能通过迭代器进行访问 ;
插入 / 删除 : 查询 / 插入 / 删除效率为 O(log n) 复杂度 ;
排序方式 : 默认使用 less 仿函数 , 即 < 运算符进行排序 ; 也可以自定义排序规则仿函数 ;
使用场景 : 需要有序集合且元素不重复的场景 ;

时间复杂度：

增删改查都近似 = O(log N)

(b). multiset：

支持重复元素的 set。

(c). map：

有序映射或有序表，在 set 的基础上加上映射关系，可以对每个元素 key 存一个
值 value。

特点：

底层结构 : 底层由红黑树实现 , 红黑树是一种平衡二叉搜索树 , 存储空间不连续 ; 存储的元素是键值对元素 ;
访问遍历 : 不支持随机访问迭代器 , 不能听过下标访问 , 只能通过迭代器进行访问 ;
插入 / 删除 : 查询 / 插入 / 删除效率为 O(log n) 复杂度 ; 与 set 集合容器相同 ;
排序方式 : 默认使用 less 仿函数 , 即 < 运算符进行排序 ; 也可以自定义排序规则仿函数 ; map 映射容器不允许重复的键 , multimap 多重映射容器允许重复的键 ;
使用场景 : 需要有序键值对且元素不重复的场景 ;