| array |
数组 |
随机读改 O(1) |
无序 |
可重复 |
支持随机访问 |
| vector |
数组 |
随机读改、尾部插入、尾部删除 O(1)；头部插入、头部删除 O(n) |
无序 |
可重复 |
支持随机访问 |
| deque |
双端队列 |
头尾插入、头尾删除 O(1) |
无序 |
可重复 |
一个中央控制器 + 多个缓冲区，支持首尾快速增删，支持随机访问 |
| forward_list |
单向链表 |
插入、删除 O(1) |
无序 |
可重复 |
不支持随机访问 |
| list |
双向链表 |
插入、删除 O(1) |
无序 |
可重复 |
不支持随机访问 |
| stack |
deque / list |
顶部插入、顶部删除 O(1) |
无序 |
可重复 |
deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时 |
| queue |
deque / list |
尾部插入、头部删除 O(1) |
无序 |
可重复 |
deque 或 list 封闭头端开口，不用 vector 的原因应该是容量大小有限制，扩容耗时 |
| priority_queue |
vector + max-heap |
插入、删除 O(log2n) |
有序 |
可重复 |
vector 容器+heap 处理规则 |
| set |
红黑树 |
插入、删除、查找 O(log2n) |
有序 |
不可重复 |
|
| multiset |
红黑树 |
插入、删除、查找 O(log2n) |
有序 |
可重复 |
|
| map |
红黑树 |
插入、删除、查找 O(log2n) |
有序 |
不可重复 |
|
| multimap |
红黑树 |
插入、删除、查找 O(log2n) |
有序 |
可重复 |
|
| unordered_set |
哈希表 |
插入、删除、查找 O(1) 最差 O(n) |
无序 |
不可重复 |
|
| unordered_multiset |
哈希表 |
插入、删除、查找 O(1) 最差 O(n) |
无序 |
可重复 |
|
| unordered_map |
哈希表 |
插入、删除、查找 O(1) 最差 O(n) |
无序 |
不可重复 |
|
| unordered_multimap |
哈希表 |
插入、删除、查找 O(1) 最差 O(n) |
无序 |
可重复 |
|