如何避免迭代器失效

在 C++ STL 中，迭代器失效是一个常见的问题，主要发生在对容器进行插入、删除等操作后，原有的迭代器可能会失效，继续使用这些迭代器可能会导致未定义的行为。

什么是迭代器失效？

以下是一些具体的例子：

对 std::vector 进行 push_back 操作可能会导致所有迭代器失效。这是因为 std::vector 在内存中是连续存储的，当容量不足以容纳新元素时，std::vector 会重新分配内存，这会导致原有的迭代器失效。

std::vector<int> vec = {1, 2, 3};
auto it = vec.begin();
vec.push_back(4);
// 此时 it 可能已经失效，继续使用 it 可能会导致未定义的行为

对 std::list 或 std::vector 进行 erase 操作会导致被删除元素的迭代器失效。此外，在 std::vector 中，被删除元素之后的所有迭代器也会失效。

std::list<int> lst = {1, 2, 3};
auto it = lst.begin();
lst.erase(it);
// 此时 it 已经失效，继续使用 it 会导致未定义的行为

对 std::map 进行 insert 或 erase 操作不会导致其他迭代器失效。但是，被 erase 的迭代器会失效。

std::map<int, int> m = {{1, 2}, {3, 4}};
auto it = m.begin();
m.erase(it);
// 此时 it 已经失效，继续使用 it 会导致未定义的行为

总的来说，对 STL 容器进行修改操作时，需要特别注意迭代器失效的问题。在使用迭代器时，应确保迭代器是有效的，避免出现未定义的行为。

顺序容器删除元素

在 C++ STL 中，对于顺序容器（如 vector、deque），erase 函数会删除迭代器所指向的元素，并返回下一个有效的迭代器。在删除元素后，被删除元素之后的所有迭代器都会失效。因此，不能使用 erase(it++) 的方式来删除元素，因为这样会导致未定义的行为。正确的做法是使用 erase 函数的返回值来更新迭代器，如下所示：

std::vector<int> vec = {1, 2, 3, 4, 5};
auto it = vec.begin();
while (it != vec.end()) {
    if (*it % 2 == 0) { // 删除偶数元素
        it = vec.erase(it); // erase 返回下一个有效的迭代器
    } else {
        ++it;
    }
}

在上述代码中，我们遍历 vector，并删除所有的偶数元素。在删除元素时，我们使用 it = vec.erase(it); 来更新迭代器 it，这样可以确保 it 始终指向一个有效的元素。

关联容器删除元素

在C++中，关联容器（如map、set、multimap、multiset等）的erase方法用于删除元素。当你删除一个元素时，指向该元素的迭代器会失效，但其他迭代器不会受到影响。这是因为关联容器通常是基于树结构实现的，删除一个节点不会影响到其他节点的位置。

erase方法的返回类型是void，这意味着它不会返回一个新的有效迭代器。因此，如果你在遍历容器的过程中删除元素，你需要小心处理迭代器。一种常见的做法是使用it++（先使用，后自增）。

这是一个具体的例子：

std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

for(auto it = myMap.begin(); it != myMap.end(); ) {
    if(it->first == 2) {
        myMap.erase(it++);
    } else {
        ++it;
    }
}

在这个例子中，我们遍历myMap并删除键为2的元素。我们使用it++来先获取当前迭代器的值，然后再自增。这样，即使erase方法使当前迭代器失效，it++也已经返回了下一个有效的迭代器。