面试题：C++ STL中begin迭代器在哪些常见场景下会失效

Question

请举例说明在C++ STL容器（如std::vector、std::list、std::map等）中，哪些操作会导致begin迭代器失效，并简要解释原因。

Answer 1

1. std::vector：
   • 内存重新分配操作：当std::vector的容量（capacity）不足以容纳新元素时，会进行内存重新分配，如调用push_back、insert（在可能导致容量不足时）等操作。这是因为std::vector内部以连续内存存储元素，重新分配内存后，原来指向旧内存的begin迭代器就失效了，因为内存地址发生了改变。例如：

#include <vector>
#include <iostream>
int main() {
    std::vector<int> vec;
    auto it = vec.begin();
    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
        // 当vec容量不足重新分配内存后，it可能失效
    }
    // 这里it可能已经失效，不能再安全使用
    return 0;
}

2. std::list：
   • 删除操作：调用erase方法删除元素时，若删除的是begin指向的元素，begin迭代器会失效。因为std::list是双向链表结构，删除节点后链表结构发生改变，原来指向被删除节点的begin迭代器不再有效。例如：

#include <list>
#include <iostream>
int main() {
    std::list<int> lst = {1, 2, 3};
    auto it = lst.begin();
    lst.erase(it);
    // 这里it已经失效，lst.begin()指向新的首元素
    return 0;
}

3. std::map：
   • 删除操作：与std::list类似，当使用erase删除begin指向的元素时，begin迭代器会失效。因为std::map通常以红黑树等平衡二叉树数据结构实现，删除节点会改变树的结构，使得原来指向被删除节点的begin迭代器不再有效。例如：

#include <map>
#include <iostream>
int main() {
    std::map<int, int> m = {{1, 10}, {2, 20}};
    auto it = m.begin();
    m.erase(it);
    // 这里it已经失效，m.begin()指向新的首元素
    return 0;
}