如何用std::list反向迭代器删除元素？反向算法遇迭代器失效问题

先看这个删除指定元素前后元素的简单正向算法：

void forwardRemoveAlgorithm(std::list<int> &list, int removeAround)
{
    for(std::list<int>::iterator it=list.begin(); it!=list.end(); ++it)
    {
        if(*it==removeAround)
        {
            list.erase(std::prev(it));
            list.erase(std::next(it));
        }
    }
}

该算法运行正常（暂不考虑副作用）：

std::list<int> myList = {1,2,3,4,5};
forwardRemoveAlgorithm(myList,3);
for(int elem : myList) std::cout<<elem<<std::endl;  // 输出 1 3 5

但实现对应的反向算法时会遇到迭代器失效问题：

void reverseRemoveAlgorithm(std::list<int> &list, int removeAround)
{
    for(std::list<int>::reverse_iterator it = list.rbegin(); it!=list.rend(); ++it)
    {
        if(*it==removeAround)
        {
            std::list<int>::iterator forwardEquivalent = std::next(it).base();
            list.erase(std::prev(forwardEquivalent)); // 使it失效，导致下一轮迭代崩溃
            list.erase(std::next(forwardEquivalent));
        }
    }
}

问题在于std::list没有针对reverse_iterator的erase()函数，转换为正向迭代器后删除元素会导致原反向迭代器的底层正向迭代器失效，进而引发迭代崩溃。

1. 修复反向遍历算法 #

核心思路是删除元素前先保存下一个迭代位置，利用erase()的返回值重新构造有效迭代器，避免失效迭代器被使用：

void reverseRemoveAlgorithm(std::list<int> &list, int removeAround)
{
    for (auto it = list.rbegin(); it != list.rend(); )
    {
        if (*it == removeAround)
        {
            // 转换为正向迭代器：reverse_iterator的base()指向*it的下一个元素
            auto forward_it = it.base();
            // 删除当前元素的前一个元素（反向遍历中的"后一个"元素），erase返回下一个有效迭代器
            forward_it = list.erase(std::prev(forward_it));
            // 删除当前元素的后一个元素（反向遍历中的"前一个"元素）
            list.erase(std::next(forward_it));
            // 用有效正向迭代器重新构造反向迭代器，继续遍历
            it = std::list<int>::reverse_iterator(forward_it);
        }
        else
        {
            ++it;
        }
    }
}

测试验证：

std::list<int> myList = {1,2,3,4,5};
reverseRemoveAlgorithm(myList,3);
for(int elem : myList) std::cout<<elem<<std::endl;  // 输出 1 3 5

2. 可切换正向/反向遍历的模板版本 #

通过模板参数指定迭代器类型，在编译期区分正向/反向迭代器，封装通用删除逻辑：

#include <iterator>
#include <list>

// 通用删除逻辑：统一转换为正向迭代器处理前后元素删除
template<typename Iterator>
void removeAroundElement(std::list<typename Iterator::value_type>& list, Iterator it)
{
    using ValueType = typename Iterator::value_type;
    std::list<ValueType>::iterator forward_it;

    // 编译期区分正向/反向迭代器
    if constexpr (std::is_same_v<Iterator, typename std::list<ValueType>::iterator>)
    {
        forward_it = it;
    }
    else if constexpr (std::is_same_v<Iterator, typename std::list<ValueType>::reverse_iterator>)
    {
        forward_it = std::prev(it.base());
    }

    // 删除前一个元素，erase返回下一个有效迭代器
    forward_it = list.erase(std::prev(forward_it));
    // 删除后一个元素
    list.erase(std::next(forward_it));
}

// 模板遍历算法：支持正向/反向迭代器切换
template<typename Iterator>
void removeAround(std::list<typename Iterator::value_type>& list, typename Iterator::value_type removeAround)
{
    for (Iterator it = Iterator(list.begin()); it != Iterator(list.end()); )
    {
        if (*it == removeAround)
        {
            // 保存下一个迭代位置，避免当前迭代器失效
            Iterator next_it = it;
            ++next_it;
            // 执行删除
            removeAroundElement(list, it);
            // 跳转到下一个有效位置
            it = next_it;
        }
        else
        {
            ++it;
        }
    }
}

使用示例：

// 正向遍历调用
std::list<int> list1 = {1,2,3,4,5};
removeAround<std::list<int>::iterator>(list1, 3);
// 输出 1 3 5

// 反向遍历调用
std::list<int> list2 = {1,2,3,4,5};
removeAround<std::list<int>::reverse_iterator>(list2, 3);
// 输出 1 3 5

内容的提问来源于stack exchange，提问作者GholGoth21