iterator的遍历删除问题

本博客主要是分析在iterator遍历的过程中删除元素之后如何继续遍历的问题。

问题描述

我们在写代码的过程中，总是会碰到这样的场景，即在遍历一个array或者list的时候，如果碰到某个满足条件的元素就删除之，然后继续遍历。对于这种场景我们在c++的stl中经常会写出如下的代码，以list为例子

list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
for (auto it = ls.begin(); it != ls.end(); it++) {
    if (*it == 2) {
        ls.erase(it);
    }
}

这种代码其实会出现严重的错误，因此我这边简要说明下，这种写法为什么会出现问题，以及正确的写法。（正确的写法在网上都能找到，我这边主要是对其为什么需要这样做进行补充）。

问题分析

list中的erase

如图所示，list当中存放着元素0, 1, 2, 99, 3, 4，当我们调用erase来删除元素1的时候，此时ite指向的元素1被链表移除，因此ite++不再指向链表中的下一个元素，而是一个不确定的量，所以我们要记住erase函数的入参不能够被后续操作。

list中的erase源码

从源码中我们可以看出，我们首先获取position的next_node和prev_node，然后分别修改next_node和prev_node的prev和next指针，将position从链表中删除，最后返回next_node的iterator，因此我们可以修改遍历为如下：

list<int> ls;
ls.push_back(1);
ls.push_back(2);
ls.push_back(3);
for (auto it = ls.begin(); it != ls.end(); ) {
    if (*it == 2) {
        it = ls.erase(it);
    } else {
        it++;
    }
}

vector中的erase

对于vector，其erase操作也是类似的，源码中，直接将position + 1到end部分的元素copy到position位置。对于vector来说，其iterator是普通指针，position指的就是数组的位置，因此在erase之后，我们只需要返回当前的数组位置就可以了。