容器扩容策略与迭代器失效
面试考点
这道题是 C++ 面试的高频题。面试官考察你是否理解 vector 的扩容机制(为什么是指数增长)、各种容器操作导致迭代器失效的规则、以及如何安全地在遍历中删除元素。
核心概念
vector 在 push_back 时如果 size 达到 capacity,就会重新分配一块更大的内存(通常是原来的 1.5 倍或 2 倍),把所有元素搬过去,释放旧内存。这个过程叫做"扩容"或"重新分配"(reallocation)。扩容后,所有指向旧内存的迭代器、指针和引用全部失效。
扩容倍数对比
| 实现 | 增长因子 | 说明 |
|---|---|---|
| GCC (libstdc++) | 2x | 简单,但可能浪费内存 |
| MSVC | 1.5x | 内存利用率更高 |
| Clang (libc++) | 2x | 同 GCC |
增长因子必须大于 1,否则 push_back 的均摊时间复杂度无法保证 O(1)。
基本示例
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
// ============================
// 示例1:vector 扩容过程
// ============================
void vector_growth_demo() {
std::vector<int> v;
size_t old_cap = 0;
for (int i = 0; i < 100; i++) {
v.push_back(i);
if (v.capacity() != old_cap) {
std::cout << "size=" << v.size()
<< " capacity=" << v.capacity()
<< " (扩容!)" << std::endl;
old_cap = v.capacity();
}
}
// 可以看到 capacity 按倍数增长
}
// ============================
// 示例2:vector 迭代器失效
// ============================
void vector_invalidation_demo() {
std::vector<int> v = {1, 2, 3, 4, 5};
// 情况1:push_back 可能导致扩容
auto it = v.begin();
std::cout << "扩容前 *it = " << *it << std::endl;
// 预留空间可以避免扩容
v.reserve(100);
// 注意:reserve 之后旧的迭代器也会失效!
it = v.begin(); // 必须重新获取
// 情况2:insert 在插入点之后的迭代器失效
// 如果触发扩容,所有迭代器失效
auto it2 = v.begin() + 2;
v.insert(v.begin() + 1, 99);
// it2 已失效,不能再使用
// 情况3:erase 在删除点之后的迭代器失效
auto it3 = v.begin();
v.erase(v.begin() + 1);
// it3 仍然有效(在删除点之前)
// 但 v.begin() + 4(原来的位置)可能已失效
}
// ============================
// 示例3:安全地在遍历中删除元素
// ============================
void safe_erase_vector() {
std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// 错误写法:迭代器失效
/*
for (auto it = v.begin(); it != v.end(); ++it) {
if (*it % 2 == 0) {
v.erase(it); // it 失效了!++it 是未定义行为
}
}
*/
// 正确写法1:erase 返回下一个有效迭代器
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) {
it = v.erase(it); // erase 返回下一个元素的迭代器
} else {
++it;
}
}
// 正确写法2:C++20 std::erase_if
// std::erase_if(v, [](int x) { return x % 3 == 0; });
// 正确写法3:remove-erase 惯用法
// v.erase(std::remove_if(v.begin(), v.end(),
// [](int x) { return x % 3 == 0; }), v.end());
std::cout << "删除偶数后: ";
for (int x : v) std::cout << x << " ";
std::cout << std::endl;
}
// ============================
// 示例4:list 的迭代器稳定性
// ============================
void list_demo() {
std::list<int> lst = {1, 2, 3, 4, 5};
auto it = lst.begin();
std::advance(it, 2); // 指向 3
// list 的 insert 和 erase 不会使其他迭代器失效
lst.push_back(6); // it 仍然有效
lst.insert(it, 99); // it 仍然指向 3
// erase 只使被删除元素的迭代器失效
auto to_delete = lst.begin();
lst.erase(to_delete); // 只有 to_delete 失效,it 仍然有效
std::cout << "*it = " << *it << std::endl; // 3
}
// ============================
// 示例5:map 的迭代器稳定性
// ============================
void map_demo() {
std::map<int, std::string> m = {
{1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}
};
auto it = m.find(3);
// map 的 insert 不会使任何迭代器失效
m[5] = "five";
std::cout << "insert 后 it->second = " << it->second << std::endl; // "three"
// map 的 erase 只使被删除元素的迭代器失效
m.erase(2); // it 仍然有效
// 安全地在遍历中删除
for (auto it2 = m.begin(); it2 != m.end(); ) {
if (it2->first % 2 == 0) {
it2 = m.erase(it2); // C++11 起 erase 返回下一个迭代器
} else {
++it2;
}
}
}
// ============================
// 示例6:deque 的迭代器失效规则
// ============================
void deque_demo() {
std::deque<int> dq = {1, 2, 3, 4, 5};
// deque 在头尾插入不会使引用失效,但所有迭代器都可能失效
// deque 在中间插入/删除:所有迭代器和引用都失效
dq.push_front(0); // 迭代器可能失效,但引用不失效
dq.push_back(6); // 同上
// 中间操作
dq.insert(dq.begin() + 3, 99); // 所有迭代器和引用失效
}
int main() {
std::cout << "=== vector 扩容 ===" << std::endl;
vector_growth_demo();
std::cout << "\n=== 安全删除 ===" << std::endl;
safe_erase_vector();
std::cout << "\n=== list 稳定性 ===" << std::endl;
list_demo();
std::cout << "\n=== map 稳定性 ===" << std::endl;
map_demo();
return 0;
}各容器迭代器失效规则
| 容器 | insert/push_back | erase | 说明 |
|---|---|---|---|
| vector | 扩容时全部失效;不扩容时插入点后失效 | 删除点及之后失效 | 最不稳定 |
| deque | 头尾插入:迭代器失效,引用不失效;中间插入:全部失效 | 头尾删除:被删元素失效;中间删除:全部失效 | 复杂 |
| list | 不影响其他迭代器 | 只有被删元素失效 | 最稳定 |
| map/set | 不影响其他迭代器 | 只有被删元素失效 | 很稳定 |
| unordered_map/set | 不触发 rehash 时不失效;rehash 时全部失效 | 只有被删元素失效 | rehash 不可控 |
常见问题
为什么 vector 扩容要用指数增长?
如果每次只增加固定大小(如每次加 10),push_back N 次的总拷贝次数是 O(N^2)。指数增长(如 2 倍)保证总拷贝次数是 O(N),push_back 的均摊时间复杂度是 O(1)。
reserve 和 resize 有什么区别?
reserve(n) 只分配内存,不创建元素,size 不变。resize(n) 会创建或销毁元素,size 改变。reserve 用于提前预留空间避免扩容,resize 用于改变容器中元素的数量。
怎么在遍历 vector 时安全删除元素?
用 erase 的返回值更新迭代器:it = v.erase(it)。或者用 remove-erase 惯用法。C++20 提供了 std::erase_if 更简洁。
适用场景
- 需要频繁尾部插入:vector
- 需要频繁头尾插入/删除:deque
- 需要频繁中间插入/删除且要求迭代器稳定:list
- 需要有序查找且迭代器稳定:map/set
注意事项
- vector 扩容后所有迭代器、指针、引用全部失效
- 用 reserve 预留空间可以避免扩容
- erase 返回下一个有效迭代器(C++11 起所有容器都支持)
- 不要在 range-based for 中修改容器大小
- unordered 容器的 rehash 会使所有迭代器失效
总结
vector 扩容采用指数增长(1.5x 或 2x),保证 push_back 的均摊 O(1)。扩容时所有迭代器失效。不同容器的迭代器失效规则差异很大:vector 最不稳定,list 和 map/set 最稳定。面试中最常考的操作:在遍历中安全删除元素(用 erase 返回值或 remove-erase 惯用法)。用 reserve 预留空间可以避免不必要的扩容和迭代器失效。