STL

STL 索引

STL 方法含义索引

STL 容器

容器底层数据结构时间复杂度有无序可不可重复其他
array数组随机读改 O(1)无序可重复支持快速随机访问
vector数组随机读改、尾部插入、尾部删除 O(1)
头部插入、头部删除 O(n)
无序可重复支持快速随机访问
list双向链表插入、删除 O(1)
随机读改 O(n)
无序可重复支持快速增删
deque双端队列头尾插入、头尾删除 O(1)无序可重复一个中央控制器 + 多个缓冲区,支持首尾快速增删,支持随机访问
stackdeque / list顶部插入、顶部删除 O(1)无序可重复deque 或 list 封闭头端开口,不用 vector 的原因应该是容量大小有限制,扩容耗时
queuedeque / list尾部插入、头部删除 O(1)无序可重复deque 或 list 封闭头端开口,不用 vector 的原因应该是容量大小有限制,扩容耗时
priority_queuevector + max-heap插入、删除 O(log2n)有序可重复vector容器+heap处理规则
set红黑树插入、删除、查找 O(log2n)有序不可重复
multiset红黑树插入、删除、查找 O(log2n)有序可重复
map红黑树插入、删除、查找 O(log2n)有序不可重复
multimap红黑树插入、删除、查找 O(log2n)有序可重复
hash_set哈希表插入、删除、查找 O(1) 最差 O(n)无序不可重复
hash_multiset哈希表插入、删除、查找 O(1) 最差 O(n)无序可重复
hash_map哈希表插入、删除、查找 O(1) 最差 O(n)无序不可重复
hash_multimap哈希表插入、删除、查找 O(1) 最差 O(n)无序可重复

STL 算法

算法底层算法时间复杂度可不可重复
find顺序查找O(n)可重复
sort内省排序O(n*log2n)可重复