容器扩容策略与迭代器失效 ​

面试考点 ​

这道题是 C++ 面试的高频题。面试官考察你是否理解 vector 的扩容机制(为什么是指数增长)、各种容器操作导致迭代器失效的规则、以及如何安全地在遍历中删除元素。

核心概念 ​

vector 在 push_back 时如果 size 达到 capacity,就会重新分配一块更大的内存(通常是原来的 1.5 倍或 2 倍),把所有元素搬过去,释放旧内存。这个过程叫做"扩容"或"重新分配"(reallocation)。扩容后,所有指向旧内存的迭代器、指针和引用全部失效。

扩容倍数对比 ​

实现增长因子说明
GCC (libstdc++)2x简单,但可能浪费内存
MSVC1.5x内存利用率更高
Clang (libc++)2x同 GCC

增长因子必须大于 1,否则 push_back 的均摊时间复杂度无法保证 O(1)。

基本示例 ​

cpp
#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_backerase说明
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 预留空间可以避免不必要的扩容和迭代器失效。