re: 关于list容器的问题！

lucky_fox — Sun, 12 Mar 2006 15:18:00 GMT

比较好的解决方法是考虑利用erase的返回值来作为删除后下一元素的位置！
int ia[]={0,1,1,2,3,5,8,13,21,34,55,89,144};
list ilist(ia,ia+12);
list::iterator il_iter=ilist.begin();
for(int i=1;il_iter!=ilist.end();i++)
{

if(i%2!=0)
{
il_iter = ilist.erase(il_iter);
}
else
{
il_iter++;
}

}

il_iter=ilist.begin();

for(;il_iter!=ilist.end();il_iter++)
{
cout<<*il_iter<<"\n";
}

return 0;

lucky_fox 2006-03-12 23:18 发表评论

re: 关于list容器的问题！

lucky_fox — Fri, 10 Mar 2006 16:06:00 GMT

这样好像又可以了
int ia[]={0,1,1,2,3,5,8,13,21,34,55,89,144,233};
list ilist(ia,ia+14);
list::iterator il_iter=ilist.begin();

int ct=ilist.size();
for(int i=0;i {

il_iter=ilist.erase(il_iter);
if(il_iter!=ilist.end())
il_iter++;
}
il_iter=ilist.begin();
for(;il_iter!=ilist.end();il_iter++)
cout<<*il_iter<

lucky_fox 2006-03-11 00:06 发表评论

re: 关于list容器的问题！

lucky_fox — Fri, 10 Mar 2006 03:11:00 GMT

根据上面的提示对程序做了如下的修改：
#include
#include
#include
#include
#include
#include
using namespace std;

int main()
{

int ia[]={0,1,1,2,3,5,8,13,21,34,55,89};
list ilist(ia,ia+12);
list::iterator il_iter=ilist.begin();
ilist.remove_if(binder2nd(modulus(),2));
for(;il_iter!=ilist.end();il_iter++)
cout<<*il_iter<<"\n";
return 0;
}
但是编译有错
error C2955: 'binder2nd' : use of class template requires template argument list
该如何更正呢？

lucky_fox 2006-03-10 11:11 发表评论

re: 关于list容器的问题！

lucky_fox — Fri, 03 Mar 2006 04:09:00 GMT

●vector 的元素删除

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

template
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 ivec(ia, ia+7);
for_each(ivec.begin(), ivec.end(), pfi); // 0 1 2 3 4 5 6

for (vector::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 ivec(ia, ia+8);

则上述程式会当掉。

●I don't think so...

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

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

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

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

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

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

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

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

int ia[7] = {0,2,4,6,0,4,7};
vector 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(), 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 ilist(ia, ia+7);
ilist.remove_if(bind2nd(modulus(), 2));

lucky_fox 2006-03-03 12:09 发表评论