时间戳

首页 > 技术文章 > 【C++】STL容器的迭代器erase方法（转载）

【C++】STL容器的迭代器erase方法（转载）

nntzhc 2021-04-01 15:00 原文

https://zhuanlan.zhihu.com/p/322402705

总结

1、关联容器和序列容器都可以用erase的返回值得到下一个有效迭代器。

2、关联容器还可以直接自增得到下一个有效迭代器。

3、不连续容器list和反向迭代器见下文。

前言

C++有几个坑，其中之一就是迭代器失效问题。虽然在新的c++版本里便利一个标准库容器时可以使用 for (auto e : con) ...; 的语法糖。 但是，偶尔在功能需要你进行索引运算，或者在遍历容器的过程中改变容器时，往往就开始抓瞎了。 这里我的本意就是把这些个容器难用的范例给罗列出来，以飨读者。

轻轻松松的关联容器-erase

对于关联型容器set,multiset,map,multimap等的索引都是由红黑树实现，那么插入、删除节点时不会影响到其他节点。 需要注意，在实现了erase方法之后切忌还去使用迭代器，正常递增进入下一轮循环体即可。

auto iter = cont.begin();
while (iter != cont.end();)
{
   //(*iter)->doSomething();
   if (shouldDelete(*iter)) {
       cont.erase(iter++);
   } 
   else {
       ++iter;
   }
}

// erase方法会返回下一个有效的迭代器
auto iter = cont.begin();
while (iter != cont.end();)
{
   //(*iter)->doSomething();
   if (shouldDelete(*iter)) {
       iter = cont.erase(iter); // 使用iter去承接下一个有效的迭代器
   } 
   else {
       ++iter;
   }
}

战战兢兢的序列型容器-erase

在以vector, deque等序列型容器为代表的erase方法里，则没有上文这么轻松，它们删除当前 迭代器的时候顺便影响了其序列索引后边的所有迭代器，它们删除一个元素之后会导致后面所有的元素前移。 因此只有一种写法

// erase方法会返回下一个有效的迭代器
auto iter = cont.begin();
while (iter != cont.end();)
{
   //(*iter)->doSomething();
   if (shouldDelete(*iter)) {
       iter = cont.erase(iter); // 使用iter去承接下一个有效的迭代器
   } 
   else {
       ++iter;
   }
}

谈到了元素删除，就不得不说到remove这个方法，vector容器跟其他的容器不太一样。 remove方法只是将待删除的元素移动到尾部，并没有真正删除，所以此时要想真正删除则需要搭配erase方法来真正地删除。

vec.erase(remove(vec.begin(), vec.end(), x), vec.end());

明明白白的不连续容器-erase

对于同样不连续内存容器list来说，因为其erase方法的灵活性，使用法则跟关联型容器一致。

但是对于另一个容器forward_list来说，它根本没有erase方法，那该怎么办呢？ 对于单向列表，为了节省内存和高性能，极简的结构下也带来了使用的问题。 所以在遍历删除的时候需要新增一个辅助迭代器。

auto prev = flst.before_begin();
auto curr = flst.begin();
while (curr != flst.end()) {
    if (shouldDelete(*curr))
        curr = flst.erase_after(prev);
    else {
        prev = curr;
        ++curr;
    }
}

奇奇怪怪的反向迭代器-erase

当你了解到诸多迭代器删除的办法时，心里呼了一口气，这么危险的接口是谁放出来的? 没准想，当你遇到反向遍历+删除时，又是一个坑。 坑就在于erase的入参只接受正向迭代器。 下面给出反向迭代器的转换示例

auto iter = myList.rbegin();
while (iter != myList.rend();) {
    if (shouldDelete(*iter)) {
        iter = decltype(iter)(myList.erase(std::next(iter).base()));
    }
    else {
        ++iter;
    } 
}

// 节省一点键盘的写法
auto iter = myList.rbegin();
while (iter != myList.rend();) {
    if (shouldDelete(*iter)) {
        iter = decltype(iter)(myList.erase(--(iter.base())));
    }
    else {
        ++iter;
    } 
}

 

推荐阅读