四、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()直接在容器里面做，省去放入这个动作，因此更高效。