面试题：C++ set容器删除元素时的迭代器失效分析及优化

Question

在C++ STL的set容器中，遍历并删除部分元素可能会导致迭代器失效。请详细阐述迭代器失效的原因，以及如何在删除元素时避免因迭代器失效导致程序出错，同时实现高效删除操作。给出完整的代码示例，并解释优化策略。

Answer 1

迭代器失效原因

在std::set中，当删除一个元素时，该元素对应的迭代器会失效。这是因为std::set通常以红黑树等平衡二叉搜索树实现，删除操作会改变树的结构。一旦结构改变，指向被删除节点的迭代器就不再有效，继续使用会导致未定义行为。

避免迭代器失效及高效删除操作方法

1. 使用erase返回的迭代器：erase成员函数会返回下一个有效的迭代器，利用这一点可以在删除元素后继续正确遍历。
2. 逆序删除：从后往前删除元素，这样在删除当前元素时，前面的迭代器不会失效。但对于std::set，由于其内部有序，这种方法不太适用，所以主要采用第一种方法。

代码示例

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 2, 3, 4, 5};

    auto it = mySet.begin();
    while (it != mySet.end()) {
        if (*it % 2 == 0) { // 删除偶数
            it = mySet.erase(it);
        } else {
            ++it;
        }
    }

    // 输出剩余元素
    for (int num : mySet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

优化策略解释

1. 利用erase返回的迭代器：在while循环中，当判断元素满足删除条件时，调用erase并将返回值重新赋值给it。这样it就指向了下一个有效元素，保证了迭代的连续性。
2. 减少不必要的操作：在不满足删除条件时，仅递增迭代器，避免了多余的函数调用，提高了效率。