四、STL与容器
约 806 字大约 3 分钟
2026-05-09
STL容器了解哪些
序列容器:维护元素的线性序列
vector:动态数组,支持快速随机访问
deque:双端队列,两端高效插入/删除
list:双向链表,任意位置高效插入/删除
forward_list:单向链表,更节省空间
array:固定大小数组,更安全的原生数组替代
关联容器:基于键值对的有序存储(基于红黑树)
set/multiset:有序唯一/非唯一键集合
map/multimap:有序键值对集合,键唯一/非唯一
无序关联容器:基于哈希表的存储
unordered_set/unordered_multiset
unordered_map/unordered_multimap
STL中allocator的作用
allocator是 STL 中的内存管理器:负责分配 / 释放内存、构造 / 销毁对象;
这是 STL 容器高效的关键 —— 容器可以先预分配一大块内存,需要时再构造对象,不用频繁申请 / 释放内存。
c++中 STL中迭代器失效的场景
内存重新分配(vector, string, deque),元素位置移动(插入/删除导致),数据结构重构(关联容器删除时),这些情况会导致迭代器失效
c++的map和unordered_map有什么区别和实现原理
map 是基于红黑树实现的有序关联容器,元素按 key 升序排列,查找、插入、删除复杂度为 O(logN)。
unordered_map 是基于哈希表实现的无序关联容器,元素无序存储,查找、插入、删除的平均复杂度为 O(1),最坏 O(n)。
c++中 unordered_map的负载因子与rehash机制
unordered_map的负载因子是已存储元素数量与桶数组大小的比值。
当负载因子超过预设的最大负载因子时,容器会自动执行 rehash:创建一个新的、更大的桶数组,并将所有现有元素重新哈希到新的数组中,以降低每个桶的平均元素数,从而保证 O(1) 平均时间复杂度的操作性能。
vector底层原理和扩容过程
Vector是C++ STL中的动态数组容器,底层使用连续内存存储元素,支持随机访问。
当容量不足时,会进行扩容操作,通常以一定比例(如2倍)分配新内存,拷贝原有元素并释放旧内存
push_back()和emplace_back()的区别
push_back() 在容器尾部添加元素时,会先构造一个临时对象,然后通过拷贝或移动构造函数将其添加到容器中。
emplace_back() 直接在容器尾部构造元素,避免了临时对象的创建,通常更高效。
就是说push_back()在容器外面做东西,做好后在放进容器中;emplace_back()直接在容器里面做,省去放入这个动作,因此更高效。
