一、STL 各容器特点

---

1、std::vector 单端数组容器

std::vector 动态数组容器特点 :

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

2、std::deque 双端队列容器

std::deque 双端队列容器特点 :

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

3、std::list 双向链表容器

std::list 双向列表容器特点 :

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

4、std::set 集合容器

std::set 集合容器特点 :

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

5、std::multiset 多重集合容器

std::multiset 多重集合容器特点 :

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

6、std::map 映射容器

std::map 映射容器特点 :

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

std::map 映射容器 与 std::set 集合容器 的区别是 map 容器存储的是 键值对 元素 , 是 pair 对象 , set 容器 存储的是 单纯的 键 单个元素 ;

7、std::multimap 多重映射容器

std::multimap 多重映射容器特点 :

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

二、STL 各容器特点总结

---

	vector 单端数组	deque 双端队列	list 双向链表	set 集合	multiset 多重集合	map 映射	multimap 多重映射
底层数据结构	单端数组	双端数组	双向链表	红黑二叉树	红黑二叉树	红黑二叉树	红黑二叉树
随机访问 ( 根据下标访问 )	√	√	×	×	×	×	×
元素查询 ( 时间复杂度 )	O(n)	O(n)	O(n)	O(log n)	O(log n)	查询 Key : O(log n)	查询 Key : O(log n)
插入删除 ( 时间复杂度 )	尾端 : O(1) ; 首端和中间 O(n)	首段尾端 : O(1) ; 中间 O(n)	O(1)	O(log n)	O(log n)	O(log n)	O(log n)

三、STL 各容器使用场景示例

---

如果需要 随机访问 , 则使用 vector 单端数组 或 deque 双端数组 容器 ;

如果 需要 在 尾部 频繁 插入 / 删除 , 则使用 vector 单端数组 ;

如果 需要 在 首部 和 尾部 频繁 插入 / 删除 , 则使用 deque 双端数组 ;

如果 需要 在 任意位置 频繁 插入 / 删除 , 则使用 list 双向链表 ;

如果需要保持 元素 有序 且 不重复 , 则使用 set 集合容器 ;

如果需要保持 元素 有序 且 可重复 , 则使用 multiset 多重集合容器 ;