为什么 `std::vector` 的容量扩展会导致迭代器失效？

作者

在 C++ 标准库中，std::vector 是一个连续存储的动态数组。它的大小可以在运行时变化，但其内部实现会在必要时进行重新分配（realloc）。这一步骤会把原有元素复制（或移动）到新的、更大容量的内存块，并释放旧的内存。由于此过程会产生新的地址，所有指向旧内存的指针、引用以及迭代器都会被失效。

1. 迭代器失效的根本原因

  • 连续存储：vector 的所有元素在内存中是连续放置的。
  • 重新分配：当 push_back 或 reserve 触发容量增长时，vector 会申请新的内存块。
  • 拷贝/移动：原有元素被拷贝或移动到新块。
  • 释放旧块：旧内存被释放，任何指向它的迭代器、指针或引用都不再指向有效位置。

因此，一旦容量扩展，所有旧的迭代器都失效。

2. 失效的细节

操作 是否导致容量扩展 迭代器失效 说明
push_back 取决于当前大小是否已达到容量 是（如果扩容） 新元素插入后，旧迭代器失效
reserve(new_cap) 如果 new_cap > 当前容量 是 预留容量时会重新分配
resize(new_size) 如果 new_size > 当前容量 是 同上
insert 若插入后大小 > 容量 是 可能触发扩容
erase 只删除元素 否 只删除，不扩容
clear 只清空元素 否 容量不变
shrink_to_fit() 可能降低容量 是 触发重新分配

3. 如何避免迭代器失效的陷阱

  1. 在扩容前复制迭代器 

    std::vector <int> v = {1,2,3};
auto it = v.begin();
v.reserve(10);          // 扩容
// it 已失效，需重新获得
it = v.begin();

  2. 使用 reserve 提前预留容量 

    std::vector <int> v;
v.reserve(100);  // 预留足够容量，避免后续插入导致失效

  3. 对迭代器进行 std::list 或 std::deque 替代
    这两种容器在插入/删除时不会导致迭代器失效（除非直接删除该元素）。

  4. 使用 std::vector::erase 时保存返回值 

    auto it = std::find(v.begin(), v.end(), value);
if(it != v.end()) {
    it = v.erase(it); // erase 返回新的迭代器
}

  5. 使用指针或引用而非迭代器
    若要保留对元素的引用，需在扩容前拷贝或移动指针，并在必要时更新指针。

4. 代码示例

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector <int> nums{1, 2, 3, 4, 5};
    auto it = std::find(nums.begin(), nums.end(), 3);
    std::cout << "元素 3 的索引: " << std::distance(nums.begin(), it) << '\n';

    // 触发扩容
    nums.reserve(20);

    // 重新获取迭代器
    it = std::find(nums.begin(), nums.end(), 3);
    std::cout << "元素 3 的新索引: " << std::distance(nums.begin(), it) << '\n';

    // 插入新元素
    nums.push_back(6);
    nums.push_back(7);

    // 遍历
    for(const auto& n : nums) {
        std::cout << n << ' ';
    }
    std::cout << '\n';
}

5. 小结

  • std::vector 的内部实现基于连续内存，当容量需要扩大时会重新分配内存，导致所有旧迭代器失效。
  • 在进行可能导致扩容的操作前，提前预留足够容量或在操作后重新获得迭代器。
  • 对于需要长期持有元素引用的场景，考虑使用 std::list、std::deque 或手动管理指针。

了解并掌握迭代器失效的机制，可以帮助你写出更健壮、更安全的 C++ 程序。

发表评论