tags:
  - Cpp

STL Iterator - Iterator Invalidation (Part III)

Iterator Invalidation: A Universal Problem

迭代器失效指的是由于底层容器结构的变化，使得原先获取的迭代器不再指向有效的元素，或者指向错误的元素。这时，如果继续使用原先获取的迭代器就会导致迭代器失效，可能会导致未定义行为，如程序崩溃或错误结果。

迭代器失效并不是 C++ 独有的问题，python、Java 也会遇到相同的问题。我们下面以 std::vector 举例。

Resizable Vector

std::vector 是一个可变数组，这就导致了迭代器失效特别容易发生。因为插入元素可能导致容器的 resize，也就是重新分配一块更大的内存，复制原容器对象，删除原容器对象。一旦原容器对象被删除，就会导致指向某个元素的迭代器现在只想的是一块无效内存。

比如我们有以下的例子，我们先申请一个 std::vector 容器对象并对其进行初始化。之后，当我们调用 vec.shrink_to_fit() 时， GCC 就会释放掉多余分配的内存空间，从而将容量调整为当前的大小（3 个元素）。随后你获取的迭代器 it = vec.begin() 指向当前分配的内存。而当我们调用 vec.push_back(4) 后，std::vector 就会进行扩容。而扩容就会导致我们上面说的迭代器失效。

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec = {1, 2, 3};
    vec.shrink_to_fit();
    auto it = vec.begin();
    vec.push_back(4);
    std::cout << "Iterator points to: " << *it << std::endl; // UB
    return 0;
}

Otherwise

此外，插入元素、删除元素、对容器进行排序也可能会导致迭代器失效。这里就不一一列举了。