标准库容器概述
| 名称 | 类型 | 插入性能 | 删除性能 | 查找性能 | 何时使用 |
|---|---|---|---|---|---|
vector |
顺序 | 平均 O(1) 在末尾；否则 O(N) | 平均 O(1) 在末尾；否则 O(N) | O(1) | 默认容器。使用其他容器前先用分析器确认 |
list |
顺序 | O(1) 在开始和结束处，以及插入位置 | O(1) 在开始和结束处，以及删除位置 | O(1) 访问第一个或最后一个元素；否则 O(N) | 极少使用。一般使用 vector
|
forward_list |
顺序 | O(1) 在开始处和插入位置 | O(1) 在开始处和删除位置 | O(1) 访问第一个元素；否则 O(N) | 极少使用。一般使用 vector
|
deque |
顺序 | O(1) 在开始或结束处；否则 O(N) | O(1) 在开始或结束处；否则 O(N) | O(1) | 通常不需要；使用 vector
|
array |
顺序 | N/A | N/A | O(1) | 需要固定大小的数组来替换标准 C 风格数组 |
queue |
容器适配器 | 取决于底层容器；对于 list 和 deque 是 O(1) |
取决于底层容器；对于 list 和 deque 是 O(1) |
N/A | 需要先进先出（FIFO）结构 |
priority_queue |
容器适配器 | 取决于底层容器；对于 vector 是平均 O(log(N))，对于 deque 是 O(log(N)) |
取决于底层容器；对于 vector 和 deque 是 O(log(N)) |
N/A | 需要具有优先级的队列 |
stack |
容器适配器 | 取决于底层容器；对于 list 和 deque 是 O(1)，对于 vector 是平均 O(1) |
取决于底层容器；对于 list、vector 和 deque 是 O(1) |
N/A | 需要先进后出（FILO）/后进先出（LIFO）结构 |
set multiset
|
排序关联 | O(log(N)) | O(log(N)) | O(log(N)) | 需要具有相等查找、插入和删除时间的排序元素集合 |
map multimap
|
排序关联 | O(log(N)) | O(log(N)) | O(log(N)) | 需要将键与值关联的排序集合，即关联数组 |
unordered_map unordered_multimap
|
无序关联/哈希表 | 平均情况 O(1)；最坏情况 O(N) | 平均情况 O(1)；最坏情况 O(N) | 平均情况 O(1)；最坏情况 O(N) | 需要将键与值关联，不需要元素排序 |
unordered_set unordered_multiset
|
无序关联/哈希表 | 平均情况 O(1)；最坏情况 O(N) | 平均情况 O(1)；最坏情况 O(N) | 平均情况 O(1)；最坏情况 O(N) | 需要具有相等查找、插入和删除时间的元素集合，不需要排序 |
bitset |
特殊 | N/A | N/A | O(1) | 需要一组标志位 |
注意：
vector应该是您的默认容器！实践中，在现代 CPU 上由于内存和缓存的工作方式，以及对于list或forward_list，您首先需要迭代到您想要插入或删除元素的位置，所以vector中的插入和删除操作通常比list或forward_list更快。list或forward_list的内存可能是碎片化的，因此迭代比vector慢。文章来源地址https://www.toymoban.com/news/detail-811590.html
文章来源：https://www.toymoban.com/news/detail-811590.html
到了这里，关于标准库容器概述的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
