面试题：复杂场景下C++ STL begin迭代器失效的分析与解决

Question

考虑这样一个场景，有一个std::vector<std::vector<int>>的二维容器，在对内部的std::vector<int>进行动态插入或删除元素操作时，外层std::vector<std::vector<int>>的begin迭代器何时会失效？如何在不重新获取begin迭代器的情况下，保证程序能够正确访问到所有内部的std::vector<int>元素？请详细分析并给出解决方案，要求提供完整可运行的代码示例。

Answer 1

1. 外层std::vector<std::vector<int>>的begin迭代器何时会失效

当外层std::vector<std::vector<int>>发生以下情况时，其begin迭代器会失效：

• 内存重新分配：当向std::vector<std::vector<int>>中插入元素，导致其容量不足，需要重新分配内存时，所有指向该std::vector的迭代器（包括begin迭代器）都会失效。这是因为重新分配内存会导致std::vector内部数据存储位置的改变。

2. 如何在不重新获取begin迭代器的情况下，保证程序能够正确访问到所有内部的std::vector<int>元素

可以通过使用智能指针和std::vector<std::shared_ptr<std::vector<int>>>来解决这个问题。std::shared_ptr可以跟踪对象的引用计数，即使std::vector<std::shared_ptr<std::vector<int>>>发生内存重新分配，内部的std::vector<int>对象的内存位置不会改变，迭代器也不会失效。

3. 完整可运行的代码示例

#include <iostream>
#include <vector>
#include <memory>

int main() {
    std::vector<std::shared_ptr<std::vector<int>>> outer;

    // 初始化外层vector
    for (int i = 0; i < 3; ++i) {
        outer.emplace_back(std::make_shared<std::vector<int>>());
    }

    // 向内部vector插入元素
    for (size_t i = 0; i < outer.size(); ++i) {
        for (int j = 0; j < 3; ++j) {
            outer[i]->push_back(i * 3 + j);
        }
    }

    // 获取begin迭代器
    auto it = outer.begin();

    // 动态插入元素到内部vector，不会使外层vector的begin迭代器失效
    (*it)->push_back(100);

    // 遍历所有内部vector的元素
    for (; it != outer.end(); ++it) {
        for (int num : **it) {
            std::cout << num << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

在上述代码中：

• 使用std::vector<std::shared_ptr<std::vector<int>>>来存储内部的std::vector<int>。
• 通过std::make_shared来创建std::vector<int>的智能指针并插入到外层std::vector中。
• 当向内部std::vector<int>动态插入元素时，外层std::vector的begin迭代器不会失效，因为内部std::vector<int>对象的内存位置没有改变，只是其内容发生了变化。
• 最后通过迭代器遍历所有内部std::vector<int>的元素并输出。