【C++】C++遍历容器时进行擦除操作

遍历容器时进行擦除（erase）操作需要特别注意迭代器失效问题。

浩水飞鸽(晴雨)

937人浏览 · 2025-06-01 08:45:05

浩水飞鸽(晴雨) · 2025-06-01 08:45:05 发布

文章目录

C++ 遍历与擦除操作

C++ 遍历与擦除操作

在 C++ 中，遍历容器时进行擦除（erase）操作需要特别注意迭代器失效问题。不同容器类型有不同的处理方式。

一、顺序容器（vector, deque, list）

1. vector 和 deque（连续内存容器）

#include <iostream>
#include <vector>
#include <deque>

int main() {
    // vector 示例
    std::vector<int> vec = {1, 2, 3, 4, 5, 6, 7, 8, 9};
    
    // 删除所有偶数元素
    for (auto it = vec.begin(); it != vec.end(); ) {
        if (*it % 2 == 0) {
            // erase 返回下一个有效迭代器
            it = vec.erase(it);
        } else {
            ++it;
        }
    }
    
    std::cout << "Vector after erase: ";
    for (int n : vec) std::cout << n << " "; // 输出: 1 3 5 7 9
    std::cout << "\n\n";
    
    // deque 示例
    std::deque<int> deq = {10, 20, 30, 40, 50, 60};
    
    // 删除大于30的元素
    for (auto it = deq.begin(); it != deq.end(); ) {
        if (*it > 30) {
            it = deq.erase(it);
        } else {
            ++it;
        }
    }
    
    std::cout << "Deque after erase: ";
    for (int n : deq) std::cout << n << " "; // 输出: 10 20 30
    std::cout << "\n\n";
    
    return 0;
}

2. list（链表容器）

#include <iostream>
#include <list>

int main() {
    std::list<std::string> words = {"apple", "banana", "cherry", "date", "elderberry"};
    
    // 删除长度超过5的单词
    for (auto it = words.begin(); it != words.end(); ) {
        if (it->length() > 5) {
            it = words.erase(it); // erase 返回下一个迭代器
        } else {
            ++it;
        }
    }
    
    std::cout << "List after erase: ";
    for (const auto& word : words) std::cout << word << " "; // 输出: apple date
    std::cout << "\n\n";
    
    return 0;
}

二、关联容器（map, set）

1. map 和 set

#include <iostream>
#include <map>
#include <set>

int main() {
    // map 示例
    std::map<int, std::string> students = {
        {101, "Alice"}, {102, "Bob"}, {103, "Charlie"}, 
        {104, "David"}, {105, "Eve"}
    };
    
    // 删除学号大于103的学生
    for (auto it = students.begin(); it != students.end(); ) {
        if (it->first > 103) {
            it = students.erase(it); // C++11 起返回下一个迭代器
        } else {
            ++it;
        }
    }
    
    std::cout << "Students after erase:\n";
    for (const auto& [id, name] : students) {
        std::cout << id << ": " << name << "\n";
    }
    // 输出: 
    // 101: Alice
    // 102: Bob
    // 103: Charlie
    std::cout << "\n";
    
    // set 示例
    std::set<int> primes = {2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 删除非质数
    for (auto it = primes.begin(); it != primes.end(); ) {
        if (*it == 4 || *it == 6 || *it == 8 || *it == 9 || *it == 10) {
            it = primes.erase(it);
        } else {
            ++it;
        }
    }
    
    std::cout << "Primes: ";
    for (int n : primes) std::cout << n << " "; // 输出: 2 3 5 7
    std::cout << "\n\n";
    
    return 0;
}

三、C++11 新方法：erase-remove 惯用法（vector, deque, list）

#include <iostream>
#include <vector>
#include <algorithm> // 需要包含 algorithm 头文件

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 删除所有奇数
    auto new_end = std::remove_if(numbers.begin(), numbers.end(), 
        [](int n) { return n % 2 != 0; });
    
    numbers.erase(new_end, numbers.end());
    
    std::cout << "After erase-remove: ";
    for (int n : numbers) std::cout << n << " "; // 输出: 2 4 6 8 10
    std::cout << "\n\n";
    
    return 0;
}

四、C++20 新方法：std::erase_if（所有容器）

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <list>

int main() {
    // vector 示例
    std::vector<int> vec = {1, 2, 3, 4, 5, 6};
    std::erase_if(vec, [](int n) { return n % 3 == 0; });
    std::cout << "Vector: ";
    for (int n : vec) std::cout << n << " "; // 输出: 1 2 4 5
    std::cout << "\n\n";
    
    // map 示例
    std::map<int, std::string> data = {
        {1, "one"}, {2, "two"}, {3, "three"}, {4, "four"}
    };
    std::erase_if(data, [](const auto& item) {
        return item.first % 2 == 0;
    });
    std::cout << "Map: ";
    for (const auto& [key, val] : data) std::cout << key << ":" << val << " "; 
    // 输出: 1:one 3:three
    std::cout << "\n\n";
    
    // set 示例
    std::set<int> nums = {10, 20, 30, 40, 50};
    std::erase_if(nums, [](int n) { return n > 25 && n < 45; });
    std::cout << "Set: ";
    for (int n : nums) std::cout << n << " "; // 输出: 10 20 50
    std::cout << "\n\n";
    
    // list 示例
    std::list<std::string> fruits = {"apple", "banana", "cherry", "date"};
    std::erase_if(fruits, [](const std::string& s) { return s.length() < 6; });
    std::cout << "List: ";
    for (const auto& fruit : fruits) std::cout << fruit << " "; // 输出: banana cherry
    std::cout << "\n";
    
    return 0;
}

关键注意事项总结

迭代器失效规则：
- 连续容器（vector, deque）：擦除元素会使指向被删除元素及之后的所有迭代器失效
- 节点容器（list, map, set）：只使指向被删除元素的迭代器失效

安全擦除模式：

for (auto it = container.begin(); it != container.end(); ) {
    if (condition) {
        it = container.erase(it); // 使用返回值更新迭代器
    } else {
        ++it; // 没有删除时递增
    }
}

现代 C++ 最佳实践：
- C++11 起：使用 erase 返回值更新迭代器
- C++17 起：使用结构化绑定简化 map 遍历
- C++20 起：优先使用 std::erase_if 全局函数
性能考虑：
- vector/deque：中间擦除成本高（O(n)）
- list：擦除成本低（O(1)）
- map/set：擦除成本为 O(log n)

特殊技巧：

反向遍历避免迭代器失效（vector/deque）：

for (auto it = vec.rbegin(); it != vec.rend(); ) {
    if (condition) {
        it = decltype(it)(vec.erase(std::next(it).base()));
    } else {
        ++it;
    }
}