当前位置:网站首页>C++ STL容器篇

C++ STL容器篇

2020-11-10 08:45:50 osc_dh3qbz0a

容器 底层数据结构 时间复杂度 有无序 可不可重复 其他
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) 无序 可重复

版权声明
本文为[osc_dh3qbz0a]所创,转载请带上原文链接,感谢
https://my.oschina.net/u/4403720/blog/4710495

随机推荐