[转侯捷]关于容器erase的正确使用

wjywhl

C++ Primer 答客问 (13) 1999.11.07

日昨 jyhuang 来我处一叙。我们谈到 generic programming
以及 STL，都兴致盎然。其中的一个讨论，引发後续数封 email
往返与 sample 测试。结果颇为有趣，结论亦值得注意。
志之於斯，以为永记。

●vector 的元素删除

话头从 container 的元素删除说起。jyhuang 观察到「如果 vector 或 list
的最後一个元素符合删除条件，程式会有问题」。他给我这样一个片段：

template <typename T>
void print_elements(T elem) { cout << elem << " "; }

void (*pfi)(int) = print_elements; // 函式指标，做为 function object 用
...
int ia[7] = {0,1,2,3,4,5,6};
vector<int> ivec(ia, ia+7);
for_each(ivec.begin(), ivec.end(), pfi); // 0 1 2 3 4 5 6

for (vector<int>::iterator it = ivec.begin(); it != ivec.end(); it++) {
  if (*it % 2) // 把奇数去掉
    ivec.erase(it);
}
for_each(ivec.begin(), ivec.end(), pfi); // 0 2 4 6 正确！


如果把 array 和 vector 的初值改为：

int ia[8] = {0,1,2,3,4,5,6,7};
vector<int> ivec(ia, ia+;

则上述程式会当掉。


●I don't think so...

我不相信 STL 会有这麽差劲的表现。所以多做了几次测试如下。

(1) 把 array 和 vector 的初值改为：

int ia[7] = {0,1,2,3,4,5,7};
vector<int> ivec(ia, ia+7);

程式结果为 0 2 4 7。结果不对，但不会当掉。

(2) 把 array 和 vector 的初值改为：

int ia[7] = {0,1,3,5,7,9,7};
vector<int> ivec(ia, ia+7);

程式结果为 0 3 7 7。错得离谱，但不会当掉。

(3) 把 array 和 vector 的初值改为：

int ia[7] = {0,2,4,6,0,4,7};
vector<int> ivec(ia, ia+7);

程式执行时会当掉。


我於是多做了一些观察，然後知道，上述这些动作根本上是完全
不对的。第一个 sample 之执行结果正确，完全是凑巧。

问题不在「最後一个元素是否符合删除条件」，而在对 iterator
特性的认识。当我们做了 ivec.erase(it) 动作，vector 便动态
减缩了一个元素（逻辑上，後继元素向前递补），而 it 不变。
之後 for 回圈的第三部份述句要求 it++，造成 it 跳过了一个元素...。

看实例：

(1) 初值为 {0,1,2,3,4,5,6}

第一次迭代，发现是偶数： ★ 以下以 e 表示 end()
0 1 2 3 4 5 6 e
^
第二次迭代，发现是奇数：
0 1 2 3 4 5 6 e
  ^
於是将  '1'  删除，vector 变成：
0 2 3 4 5 6 e
  ^
第三次迭代，发现是奇数（这时已发生错误，因为 '2' 被跳过，没有检查）：
0 2 3 4 5 6 e
    ^
於是将 '3' 删除，vector 变成：
0 2 4 5 6 e
    ^
第四次迭代，发现是奇数（这时已发生错误，因为 '4' 被跳过，没有检查）：
0 2 4 5 6 e
      ^
於是将 '5' 删除，vector 变成：
0 2 4 6 e
      ^
第五次迭代，发现 it == vec.end()，於是跳离回圈：
0 2 4 6 e
        ^
此时 vector 剩馀 0 2 4 6，阴错阳差地与正确结果吻合。


(2) 初值为 {0,2,4,6,0,4,7}

第一次迭代，发现是偶数： ★ 以下以 e 表示 end()
0 2 4 6 0 4 7 e
^
第二次迭代，发现是偶数：
0 2 4 6 0 4 7 e
  ^
第三次迭代，发现是偶数：
0 2 4 6 0 4 7 e
    ^
第四次迭代，发现是偶数：
0 2 4 6 0 4 7 e
      ^
第五次迭代，发现是偶数：
0 2 4 6 0 4 7 e
        ^
第六次迭代，发现是偶数：
0 2 4 6 0 4 7 e
          ^
第七次迭代，发现是奇数：
0 2 4 6 0 4 7 e
            ^
於是将 '7' 删除，vector 变成：
0 2 4 6 0 4 e
            ^
第八次迭代，it 越过了 end()，造成越界错误。回圈何时结束，未可知也：
0 2 4 6 0 4 e ? ? ? ? ? ?
              ^

我的结论：

iterator 只适用於在「不更动 container 布局」的条件下，
对 container 做巡访动作。否则，对 iterator 的取值行为，
直观下极易误用。

我记得《C++ Primer》中提过这个观念，但一下子找不出页数。


●应该怎麽做？

要解决上述问题（在 vector 中删除符合某条件的所有元素），
应该使用泛型演算法 remove_if() 再搭配 vector 的 erase()：

it = remove_if(ivec.begin(), ivec.end(), bind2nd(modulus<int>(), 2));
ivec.erase(it, ivec.end());


●list 的元素删除

面对 list，不可以直接对其 iterator 做算术运算，因为 list
的元素并不连续储存於记忆体中（《C++ Primer》p.266）。

那麽是不是应该延用泛型演算法 remove_if() 呢？不！
《C++ Primer》p.607 说：

-- quote ---
由於 list 不支持随机存取，merge(), remove(), reverse(), sort(),
和 unique() 等泛型演算法最好不要施行於 list objects 身上。
上述每一个演算法在 list 之中都有对应的成员函式可用：

* list::merge() 将两个排序过的 lists 合并在一起。
* list::remove() 将「与某数值相等」的元素移除掉。
* list::remove_if() 将「与某条件相符」的元素移除掉。
* list::reverse() 将 list 中的元素逆向排列。
* list::sort() 对 list 元素排序。
* list::splice() 将某个 list 的元素搬移到另一个 list 上。
* list::unique() 删除某一元素的连续副本。
-- unquote ---

所以，我们应该这麽做：

int ia[7] = {0,1,2,3,4,5,6};
list<int> ilist(ia, ia+7);
ilist.remove_if(bind2nd(modulus<int>(), 2));


* * * * * * * * * * * * * * * * * * * * * * * *

jyhuang wrote (1999/11/07) :

> 我突然想起一个问题，就是我们常说 STL，其实 C++ standard
> 纳入後给了它 C++ Standard Library 这个名称，C++ Standard
> Library 抽掉一些原 STL 的东西，也加上一些东西。虽然大家
> 习惯称 STL，会不会让人误会是在说 standard 之前的那个 STL 呢？
> 例如 C++ Standard Library 包含 string, iostream 等等，
> 在原 STL 中是没有的。我们可以说用 list<> or vector<> 来
> 写程式是用 STL，但是用到 string 可能这样说法就有问题了。

我的习惯是，传统 STL 范畴内的东西，我还是用 STL 这个词。
其他的东西，我便用 C++ Standard Library 这个词。
string 是个不折不扣的 container，但我习惯上不以
STL component 来称呼它。当然，这只是我个人习惯。

整个 C++ Standard Library 事实上几乎都已成为 template 的天下了。


* * * * * * * * * * * * * * * * * * * * * * * *

william wrote (1999/11/0 :

>> 我的结论：
>>
>> iteator 只适用於在「不更动 container 布局」的条件下，
>> 对 container 做巡访动作。否则，对 iterator 的取值行为，
>> 直观下极易误用。
>>
>> 我记得《C++ Primer》中提过这个观念，但一下子找不出页数。
>
> 现在手边没有《C++ Primer》,
> 我就拿《The C++ Programming Language》为例吧!
>
> §16.3.6 的最後一个程式例子（中译本 p.16-34）有讲到这一点,
> §19.2 的最後一段（中译本 p.19-3）也再强调一次：
>
> 有效的（valid）iterator 会真的指向一个元素，
> 可透过它来间接取值（用 *、[]、或 ->）。
> 如果 iterator 并未被初始化过、或是当容器的大小已被重订过
> （§16.3.6、§16.3.8）、或是当容器已被销毁、
> 或是当 iterator 是指向序列末端时（§18.2），
> iterator 就算失效了。
>
> 若再往前追溯, PH 版的 STL 规格书（1995/10/31 版）的 §8.1.1（p.24）
> 对於 vector 也有这麽几段话：
>
> Reallocaion invalidates all the referenes, pointers, and iterators
> referring to the elements in the sequence.
> （这句话後来被 ISO/ANSI C++ 规格书抄在 §23.2.4.2 里）
>
> "erase" invalidates all the iterators and references
> after the point of the "erase".
> （这句话後来被 ISO/ANSI C++ 规格书抄在 §23.2.4.3 里）

* * * * * * * * * * * * * * * * * * * * * * * *

dyliu wrote (1999/11/07) :

>On 07 Nov 1999 07:33:20 GMT, jjhou.bbs@bbs.cs.nthu.edu.tw (jjhou)
>wrote:
>>我的结论：
>>iterator 只适用於在「不更动 container 内容」的条件下，
>>对 container 做巡访动作。否则，对 iterator 的取值行为，
>>直观下极易误用。
>>我记得《C++ Primer》中提过这个观念，但一下子找不出页数。
>>●应该怎麽做？
>>要解决上述问题（在 vector 中删除符合某条件的所有元素），
>>应该使用泛型演算法 remove_if() 和 erase()：
>> it = remove_if(ivec.begin(), ivec.end(), bind2nd(modulus<int>(), 2));
>> ivec.erase(it, ivec.end());

> 我记得今年的 C++ Report 里有一篇文章就是在谈删除的问题
> 讲的蛮详细的, 但我忘了是哪一期. 这篇文章我印像比较深刻
> 的是谈到如何实作出 remove() 这类的 algorithm 的部分, 乍看
> 之下似乎简单其实不然. 我的感想是要正确地运用 STL 实在不
> 是简单的一件事.
>

wjywhl

//vector的删除：

// vector usage of erase and itertor
#include <vector>
#include <iostream>
#include <functional>
#include <iterator>
#include <algorithm>

template <class elemType>
void print_elements(elemType elem)
{
    std::cout << elem << std::endl;
}

void (*pfi)(int) = print_elements;

int main(void)
{
    int ia[11] = {0,2,4,6,0,4,7,9,10,20,5};
    std::vector<int> ivec(ia, ia+11);
   
    std::cout << "before erase奇数:\n";
    for_each(ivec.begin(), ivec.end(), pfi); // 0 1 2 3 4 5 6   
   
    /* error   
    for (std::vector<int>::iterator it = ivec.begin(); it != ivec.end(); it++)
    {
               
        std::cout << "found \n";
        if(*it % 2 !=0)
         ivec.erase(it);
    }
    */
   
    // ok
    std::vector<int>::iterator it = ivec.begin();
    it = remove_if(ivec.begin(), ivec.end(), std::bind2nd(std::modulus<int>(), 2));
    if(it != ivec.end())
    {
        std::cout << "found \n";
        ivec.erase(it, ivec.end());
    }   
      

    std::cout << "after erase 奇数:\n";
    for_each(ivec.begin(), ivec.end(), pfi); // 0 2 4 6 正确！
   
    getchar();
    return 0;
}