在容器的遍历中使用迭代器删除元素

问题

• 小伙伴在 std::map 的遍历中使用 map.erase(iter++) 删除元素，稣在审查代码时提醒：最好养成习惯使用 iter = map.erase(iter)，因为对于其它容器，前者可能是错的。

分析

先跑代码测试，再讲道理：

例一

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

int main() {
  // std::list<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  // std::deque<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (const auto& e : c) {
    std::cout << e << ' ';
  }
  std::cout << '\n';

  for (auto iter = c.begin(); iter != c.end();) {
    if (*iter & 1) {  // remove odd elements
      // iter = c.erase(iter);  // This is correct in all cases

      c.erase(iter++);  // For list/map/set, this is correct;
                        // but for deque/vector, this may crash!
    } else {
      ++iter;
    }
  }

  for (const auto& e : c) {
    std::cout << e << ' ';
  }
  std::cout << '\n';
}

使用 gcc version 12.2.0 (Debian 12.2.0-14) 测试：

$ g++ -std=c++20 crash.cpp -o crash

$ ll
-rwxr-xr-x  1 618 618  32K  7月13日 15:56 crash*
-rw-r--r--  1 618 618  741  7月13日 15:55 crash.cpp

$ ./crash
0 1 2 3 4 5 6 7 8 9
fish: Job 1, './crash' terminated by signal SIGSEGV (Address boundary error)

在 std::vector（和 std::deque）中，删除元素会导致后续元素移动，当删除最后一个元素 9 时，有以下具体步骤：

• 对 iter 取值（给 erase），它指向 9；
• iter++，使 iter 变成 end；
• erase 9 使“现 end”前移了一位，那么 iter 指向的“原 end”就不再是“现 end”；
• 循环条件 iter != c.end(); 满足，继续循环……

其它容器，比如 std::list（链表）、std::map/std::set（红黑树），其删除操作不会影响到其他迭代器，所以使用 .erase(iter++) 是安全且高效的。

例二

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

int main() {
  std::vector<int> c = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
  for (const auto& e : c) {
    std::cout << e << ' ';
  }
  std::cout << '\n';

  for (auto iter = c.begin(); iter != c.end();) {
    if (2 == *iter || 3 == *iter) {  // remove 2 and 3
      // iter = c.erase(iter);  // This is correct in all cases

      c.erase(iter++);  // for vector, this is incorrect!
    } else {
      ++iter;
    }
  }

  for (const auto& e : c) {
    std::cout << e << ' ';
  }
  std::cout << '\n';
}

删除 std::vector 中相邻的元素，结果漏删了 3。

解决

唯一安全并通用的方式是 iter = c.erase(iter);，要养成习惯。

附录

• Erase-Remove Idiom in C++