一、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 多重集合容器 ;
