Khan's Notebook GCC/GNU/Linux Delphi/Window Java/Anywhere

路漫漫，长修远，我们不能没有钱
随笔 - 172, 文章 - 0, 评论 - 257, 引用 - 0
数据加载中……

STL Vector 的遍历删除.

Vector 其实就类似动态数组. 事先分配好一定量的内存. 当需要的内存值大于某个阀值. 就重新申请内存. 重新分配. 当小于某个阀值, 也会导致重新分配.(自动收缩部分, stl没有明确规定, 有些库实现了)

正确: code1
      vector<string> vecFiles;
      vector<string>::iterator  it_pos;
      //@todo 已下载文件过滤
      for (it_pos = vecFiles.begin(); it_pos != vecFiles.end(); ) {
        string strTmp = *it_pos;
        if( objDownHis.checkHisList( strTmp.c_str() ) ){ //判断是否已下载过, 已下载则从列表删除
          g_Log << TIME << "file:[" << *it_pos << "] found "<< END; //
          vecFiles.erase(it_pos++);
        }else
          it_pos++;
      }


正确: code2
      vector<string> vecFiles;
      vector<string>::iterator  it_pos;
      //@todo 已下载文件过滤
      for (it_pos = vecFiles.begin(); it_pos != vecFiles.end(); ) { 
        string strTmp = *it_pos;
        if( objDownHis.checkHisList( strTmp.c_str() ) ){ //判断是否已下载过, 已下载则从列表删除
          g_Log << TIME << "file:[" << *it_pos << "] found "<< END; //
          it_pos = vecFiles.erase(it_pos);
        }else
          it_pos++;
      }

错误: code3
      vector<string> vecFiles;
      vector<string>::iterator  it_pos;
      //@todo 已下载文件过滤
      for (it_pos = vecFiles.begin(); it_pos != vecFiles.end(); it_pos++) { 
        string strTmp = *it_pos;
        if( objDownHis.checkHisList( strTmp.c_str() ) ){ //判断是否已下载过, 已下载则从列表删除
          g_Log << TIME << "file:[" << *it_pos << "] found "<< END; //
          vecFiles.erase(it_pos);
        }
      }


code3 错误的原因为, vecFiles.erase(it_pos); 当前的it_pos已经被删除了, 再下一次循环的时候 it_pos++, 访问非法内存..

然后回过头来看code1, vecFiles.erase(it_pos++); 在当前的it_pos已经被删除的时候, it_pos已经指向下一个位置了. 虽然这里逻辑上是错误的. 但是利用c语法的特性产生了一个正确的结果, 算是一个技巧. 不算是一门技术.

code2, it_pos = vecFiles.erase(it_pos); erase删除的时候, 也返回了下一个指针的位置,我们将这个位置保留了, 所以这种做法也是正确的.


另外一个移植性比较好的做法是remove_if 和一个仿函数.

仿函数可以是：
struct check {
    check( Object * objDownHis ) : m_obj( objDownHis ) {}
    check( const check & c ) : m_obj( c.m_obj ) {}

    bool operator()(const string & s) const {
       if ( m_obj->checkHisList( s.c_str() ) {
            g_Log .........
            return true;
       }
       return false;
    }
    Object * m_obj;
};

vecFiles.erase( std::remove_if( vecFile.begin(), vecFile.end(), check( &objDownHis ) );


鸣谢p大, lancey, jackz 排名不分先后.. 全按交流时间顺序...

posted on 2009-12-08 13:29 Khan 阅读(6168) 评论(5)  编辑 收藏 引用 所属分类: GCC/G++ 、跨平台开发

评论

# re: STL Vector 的遍历删除.  回复  更多评论   

>code3 错误的原因为, vecFiles.erase(it_pos); 当前的it_pos已经被删除
>了, 再下一次循环的时候 it_pos++, 访问非法内存..

>然后回过头来看code1, vecFiles.erase(it_pos++); 在当前的it_pos已经被
>删除的时候, it_pos已经指向下一个位置了. 虽然这里逻辑上是错误的. 但是利
>用c语法的特性产生了一个正确的结果, 算是一个技巧. 不算是一门技术.

我对这种的说法有不同看法：
it_pos无所谓删除不删除，it_pos 的行为就像指针一样，指针本身不会被删除，被删除的是指针指向的内容。我想楼主可能对迭代器失效的理解有偏差（建议在网上查一查相关的资料再看看）
我觉得，code1、2、3没有什么本质区别，都有可能产生迭代器失效的问题。
一个原则：对vector只要做了删除或是增加动作，就要示迭代器已经无效，必须重新从vector对象获取新的迭代器的值，而不能用临时变量、后缀自增等方法……
remove_if+erase的版本才是可读性最好且没什么问题的。

个人愚见，请博主笑纳……



2009-12-08 18:43 | 唐风

# re: STL Vector 的遍历删除.  回复  更多评论   

傻傻的开发的
2009-12-10 10:23 | 梦芭莎内衣

# re: STL Vector 的遍历删除.  回复  更多评论   

code1的做法: 对非连续内存容器是可行的 对连续内存容器是不可取的
code1中会出现漏删 而不是内存越界
2009-12-10 17:45 | yisa

# re: STL Vector 的遍历删除.  回复  更多评论   

@yisa

我用代码验证了下，的确是这样:
欢迎去我的空间讨论交流 hi.baidu.com/bmrs
1 /*
2 DATE: 2010.6.25
3 内容:关于vector的遍历删除
4 任何改变 vector 长度的操作都会使已存在的迭代器失效。例如，在调用 push_back 之后，就不能再信赖指向 vector 的迭代器的值了。
5 */
6 #include <iostream>
7 #include <vector>
8 #include <string>
9 #include <cstring>
10 using namespace std;
11
12 typedef vector<int> V;
13 typedef vector<int>::iterator VIT;
14 V v1;
15
16
17 int main()
18 {
19 for(int i=0; i<10; ++i)
20 v1.push_back(i);
21
22 VIT it = v1.begin();
23 VIT it2;
24 for(; it!=v1.end(); ++it)
25 cout<<*it<<" ";
26 cout<<endl<<v1.end()-v1.begin()<<endl; //vector容器的iterator是支持加减操作的,这在其他类型的迭代器中很少见
27 VIT it0 = v1.begin()+1; // 1
28 it2 = v1.begin()+3; // 3
29 VIT it3 = it2+1; // 4
30 cout<<"*it0="<<*it0<<" *it2="<<*it2<<" *it3="<<*it3<<endl;
31
32 for(it=v1.begin(); it!=v1.end(); ++it)
33 {
34 if(*it == 3)
35 {
36 cout<<"in for: before erase,*it="<<*it<<endl;
37 VIT tmp = it;
38 VIT r = v1.erase(it++);
39 cout<<"in for: after erase,*tmp="<<*tmp<<endl;
40 cout<<"in for: after it++ ,*it="<<*it<<endl;
41 cout<<"in for: after erase,*r="<<*r<<endl;
42 if(r == tmp)
43 cout<<"A random access iterator pointing to the new location of the element that followed the last element erased by the function call, which is the vector end if the operation erased the last element in the sequence."<<endl;
44 break;
45 }
46 }
47
48 cout<<"*it0="<<*it0<<" *it2="<<*it2<<" *it3="<<*it3<<endl;
49 return 0;
50 }
2010-06-25 16:04 | glq

# re: STL Vector 的遍历删除.  回复  更多评论   

的说法是的范德萨阿士发送到发送到大夫阿士大夫士大夫士大夫撒大撒的
2015-06-12 17:07 | 、开开

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理