STL 中 erase 的那些坑

STL 中 erase 的坑估计不少人都踩过, 自认为已经免疫了, 结果最近又踩了次坑, 于是怒发此文

大多人肯定都是从最简单的坑踩过来的:

some_container a;
for(iterator it = a.begin(); it != a.end(); ++it)
{
    if(shouldDelete(it))
    {
        a.erase(it);
    }
}

这个属于初级的坑, 对于所有 STL 容器都会出问题, 大体原因就是 erase 之后 it 已经是无效的了

于是, 大多数人给出了如下两种方案

方案一:

it = a.erase(it);

方案二:

a.erase(it++);

然后皆大欢喜的认为搞定一切了

你以为坑都填满了? 图样图森破

首先, map::erase 在标准中可是不返回 iterator 的:

void erase(iterator position);

然而, 万恶的微软并不遵循标准, 对于 map::erase 也返回了 iterator, 于是, 跟着微软走的猴子们开开心心的解决下一个 BUG 去了

遵循标准的猴子们问候了下 STL 的祖宗, 然后花大力气把所有 erase 都改成了方案二 erase(it++) 的版本, 认为天下终于太平了

… 吗? 图样图森破, 来用你的编译器试试如下代码吧:

deque a;
a.push_back(something);
iterator it = a.begin();
a.erase(it++);
assert(it == a.end());

如何? boom 了吧? 这就是这次我踩到的坑, erase(it++) 对于 map 之流工作的很好, 但是对于 deque 却不是你想象的那样

虽然先执行了 it++ 使 it 变成了 end(), 可是 erase 之后还是导致 it 失效了

用比较容易懂的方式来解释就是:

• 把 deque 当成数组, iterator 当成数组下标
• 现在我们有一个长度为 1 的数组, 下标为 0
• 我们先移动了下标到 1, 此时我们的 end() 正好也是 1, 皆大欢喜
• 然后我们删掉了下标为 0 的元素, 于是, end() 也相应变成 0 了, 可惜我们之前保存的下标为 1, 于是 1 != 0 了

map 之流为什么没问题呢? 因为不是这种下标的形式, 而是类似指针是否为空这种判断依据

结论:

• 操蛋的 STL 标准
• 虽然很操蛋, 但是还是努力记住吧, 有返回 iterator 的, 请使用方案一, 返回 void 的, 请使用方案二, 不要梦想能够使用同一种方案了
• 当然你要是执迷不悟只跟着微软那套的话我也没办法 (:з」∠)

over

转载请注明来自: http://zsaber.com/blog/?p=45

既然都来了, 有啥想法顺便留个言呗? (无奈小广告太多, 需审核, 见谅)