list和vector的遍历删除 很普通的算法,在一个循环中检查每个元素,判断条件,如果为真,就删除这个节点,再继续循环.看似简单,但是却一个不大不小的陷阱,这种小问题的结论,总是记不住,每次遇到的时候,都得写一个测试程序来验证,干脆总结一下,做个结论 最简单的方法

#include
std::remove_if(_First, _Last, Predicate)

STL是用模板实现,简单高效,但是很多情况下,需要在循环中处理其他逻辑,不能直接使用这个函数 用erase删除

erase有两种原型,删除一个节点和区段删除,对于vector和list,这个操作的定义都是相同的

template < class _TYPE, class _A > iterator
vector::erase(iterator Iterator );

查看STL的源代码,这个函数返回的iterator,是指向下一个有效的节点,(如果没有,就指向end),注意这个定义,在for循环中不能再调用it++,不然这样就等同于”it+=2″.如果要想在循环中正确的遍历下去,必须要处理erase的返回值,因为调用list::erase(iterator it)之后,it指向一个被销毁的值,再调用it++,就会内存异常,vector尽管没有这样的问题,但是在边界也会出现错误。正确的处理很简单

iterator _Last = end();
for (iterator _First = begin(); _First != _Last; )
if (*_First == _Val)
_First = erase(_First);
else
++_First;
}

如果打开STL库里面的文件,会发现这个也就是list:remove()的实现 推论

遍历删除其实是一个数据结构的问题,其他程序设计语言都存在类似的情况,比如python的list类型,delphi中的TList类,都可以采用相同的处理方法.

本文地址: http://lutaf.com/20.htm 鲁塔弗原创文章,欢迎转载,请附带原文链接