C++学习随笔——关联容器的迭代器失效问题

kitanoki / 2024-08-27 / 原文

常见关联容器的迭代器失效规则
std::map 和 std::set：

插入元素：
插入新元素不会使任何已有的迭代器失效。你可以在插入新元素后继续使用所有现有的迭代器。

删除元素：
删除某个元素会导致指向该元素的迭代器失效。除此之外，所有指向其他元素的迭代器仍然有效。
如果在遍历过程中删除元素，应该小心处理迭代器。通常做法是使用 erase 函数时，将其返回值（下一个有效迭代器）赋给当前迭代器。

点击查看代码

#include <iostream>
#include <map>

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

    for (auto it = myMap.begin(); it != myMap.end(); ) {
        if (it->first == 2) {
            it = myMap.erase(it);  // 删除后 it 被更新为指向下一个元素的迭代器
        } else {
            ++it;
        }
    }

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

点击查看代码

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};

    for (auto it = myMap.begin(); it != myMap.end(); ) {
        if (it->first == 2) {
            it = myMap.erase(it);  // 删除后 it 被更新为指向下一个元素的迭代器
        } else {
            ++it;
        }
    }

    for (const auto& pair : myMap) {
        std::cout << pair.first << ": " << pair.second << std::endl;
    }

    return 0;
}

如何避免迭代器失效问题

在插入操作后：

对于 std::map、std::set，不需要特别处理，插入操作不会使现有迭代器失效。
对于 std::unordered_map 和 std::unordered_set，在插入操作后，如果需要继续使用迭代器，建议重新获取或避免频繁插入操作。

在删除操作后：

始终使用 erase 返回的迭代器（指向删除元素后的下一个有效元素）继续遍历。不要尝试使用指向已删除元素的迭代器。

在遍历容器时：

如果要在遍历时修改容器，尤其是删除操作，确保迭代器的安全性，遵循上面提到的规则。
使用 std::vector 等序列容器时，删除操作可能导致所有迭代器失效，应特别注意。