STL底层实现 - milkandbread/summary-interview GitHub Wiki
vector(顺序容器)
deque(双端队列)
list(链表)
set(集合)
multiset
map(key, value)
multimap
| 容器 | 特点 | 内存结构 | 对应头文件 |
|---|---|---|---|
| 向量vector | 1. 查询时间复杂度(O1) 2. 尾部插入和删除时间复杂度(O1) 3. 头部插入和删除的代价很高 |
数组 | |
| 双端队列 deque | 1. 在头部和尾部插入和删除操作的时间复杂度O(1) | 双向链表 | |
| 双向链表 | 对任意位置对插入和删除操作的时间复杂度O(1) | 双端链表 | |
| 集合set | 由节点组成的红黑树，每个节点都包含着一个元素，节点之间以某种作用于元素对的位于排列， 没有两个不同的元素能够拥有相同的次序，具有快速查找对能力。但它以牺牲插入和删除操作的效率为代价 |
二叉树 | |
| 多重集合 multiset |
支持重复元素，具有快速查找的能力.插入/删除操作的时间复杂度为O(log2N) | 二叉树 | |
| 映射map | 由健值对组成的集合，以某种作用于键对上的位次排列，具有快速查找的能力.根据key值快速查找，查找的时间复杂度为O(log2N) | 二叉树 | |
| 多重映射multimap | 一个键可以应对多个值，具有快速查找多能力 | 二叉树 | map |