【C++】STL 容器总结 ( STL 各容器特点

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