C++博客-白云哥-最新评论

re: C++中遍历容器对象时需要注意的问题

cexer — Sun, 15 Aug 2010 07:29:00 GMT

@白云哥

［［［［“Because vectors keep an array format, erasing on positions other than the vector end also moves all the elements after the segment erased to their new positions”

“This invalidates all iterator and references to elements after position or first.”

删除对象后会让迭代器之后的对象移动，因此而导致迭代器失效

map的实现，红黑树，在插入和删除对象后因为要做平衡，所以同样也有可能导致迭代器的失效］］］］

就这两条原因，不会使迭代器失效，我所说的迭代器失效，是指容纳它数据结构的内存不存在。对于连续内存的容器，删除进行元素移位，迭代器的内存还在，对于非连续内存的操作，map,list,set之类的都链式的实现，这类的结点销毁的应该只是链当前结点，对其它结点的只有修改，所以不应该失效。至于2010为什么失效，有点好奇，删除操作也要内存重分配，我觉得这是不好的实现。

cexer 2010-08-15 15:29 发表评论

re: C++中遍历容器对象时需要注意的问题

cexer — Sun, 15 Aug 2010 07:19:00 GMT

可以结合两种方法。删除用标记缓存删除的方法，添加用缓存延迟添加的方法好。

cexer 2010-08-15 15:19 发表评论

re: C++中遍历容器对象时需要注意的问题

白云哥 — Sun, 15 Aug 2010 07:17:00 GMT

@cexer

http://www.cplusplus.com/reference/stl/vector/erase/

这里是一个比较好的描述

“Because vectors keep an array format, erasing on positions other than the vector end also moves all the elements after the segment erased to their new positions”

“This invalidates all iterator and references to elements after position or first.”

删除对象后会让迭代器之后的对象移动，因此而导致迭代器失效

map的实现，红黑树，在插入和删除对象后因为要做平衡，所以同样也有可能导致迭代器的失效

当然最终是不是会出现迭代器错误，这依赖于标准库的具体实现，另外还可能包括其优化方法

白云哥 2010-08-15 15:17 发表评论

re: C++中遍历容器对象时需要注意的问题

cexer — Sun, 15 Aug 2010 07:14:00 GMT

@白云哥
呵呵，学习了，看来还是你的办法稳当。这确实是标准库的实现相关的，我上面说的也都是基于估计它的一般实现，很好奇2010的vector是怎么样实现的，会出现这种失效的问题。

cexer 2010-08-15 15:14 发表评论

re: C++中遍历容器对象时需要注意的问题

白云哥 — Sun, 15 Aug 2010 07:07:00 GMT

@cexer

是的，这个依赖于标准库的实现
我用vs2010会出现迭代器失效，程序立即终止
在mac os下用gcc没有问题

但这个确实是有问题的，标准里是否有相关描述我不是很清楚，但是可以看这里，别人介绍的方法也是我上面说的

http://stackoverflow.com/questions/1038708/erase-remove-contents-from-the-map-or-any-other-stl-container-while-iterating

总之是不能用“先保存迭代器，再删除”的方法，因为在删除的时候“有可能”会导致迭代器失效

看起来确实是“有可能”，这依赖于具体的实现 :)

白云哥 2010-08-15 15:07 发表评论

re: C++中遍历容器对象时需要注意的问题

cexer — Sun, 15 Aug 2010 06:50:00 GMT

@白云哥
你看到只删除了一半，是因为对于vector这种容器，移除前面元素，后面的元素会整体往移一位，本来指向下一个元素的迭代器指向了下下个元素，后面的循环会漏掉下一个元素，这个我在上面也说过的。对于list,set,map之类的就能完全删除。需要从中间删除的容器，最好不要用vector，元素移位的操作不是常数时间的。

cexer 2010-08-15 14:50 发表评论

re: C++中遍历窗口对象时需要注意的问题

白云哥 — Sun, 15 Aug 2010 06:27:00 GMT

@cexer

“在循环中保存下一个迭代器的方法：对于删除操作是没有任何问题的”
这个确定是有问题的，我就是好几次遇到了这样的问题才写的这个总结

下面是根据你的方法写的测试程序，运行一下，删除容器的第一个数据后，原来的迭代器就失效了

#include
#include

typedef std::vector container_type;
container_type m_container;

void do_remove(container_type::iterator itr)
{
m_container.erase(itr);
}

int main()
{
for (int i = 0; i < 100; ++i)
{
m_container.push_back(i);
}

container_type::iterator it_this = m_container.begin();
container_type::iterator it_next;
while (it_this != m_container.end())
{
it_next = it_this;
++it_next;

do_remove(it_this);

it_this = it_next;
}

return 0;
}

白云哥 2010-08-15 14:27 发表评论

re: C++中遍历窗口对象时需要注意的问题

cexer — Sun, 15 Aug 2010 05:34:00 GMT

@白云哥
容器循环中的操作有四种，循环中查询，循环中更改，循环中删除，循环中添加，这些操作都围绕迭代器进行的。
循环中查询，循环中更改（这两类操作其实也包含了循环中循环，循环中的循环中的循环，循环中的循环中的循环中的循环。。。）因为不会改变迭代器的合法性，不会有什么问题。

循环中添加和删除则不一样，循环中添加有可能导致所有元素内存重分配，导致所有迭代器失效，而删除操作一般来说不会产生内存重分配的情况，目前std内的容器应该都是如此（七分分析三分猜测，正确性八九不离十）。

所以循环中删除只会使当前删除操作的迭代器失效，使得不能更新之使其指向下一个元素，而不会影其它迭代器。如list这类的容器，所有元素内存都是单独分配的，针对添加操作进行一次单独的内存分配，不会影响到现在有迭代器的合法性，但有可能删除操作导致元素重排，元素移位，使得循环不完全，漏掉元素。

循环中添加如果导致内存重分配，则会使所有现有的迭代器失效，例如vector，string这类容器要保证其内存是连续的，添加时内存有可能会重分配，导致以前的迭代器全部失效。

所以针对循环中添加和删除的几种解决方法分析如下：
在循环中保存下一个迭代器的方法：对于删除操作是没有任何问题的（关于你说的“删除容器对象有可能使得之前所保存的迭代器全都失效”，目前std内的容器应该都不会发生这种情况），但对于添加操作，则只适用于非连续内存的容器如list，不适用于连续内存的容器如vector。这个办法优点是没有时间空间的成本，缺点是对于添加操作，有些容器不支持。

使用缓存进行延迟操作的方法：对于删除和添加都适用，只是需要在所有接口中小心管理m_is_looping，避免重入的问题。优点是添加和删除都适用，缺点是空间时间的效率损失最大。

使用删除标志延迟删除的方法：对于删除操作适用，也不存在其它地方删除会出问题的情况，因为这个方法实际上是把循环中删除的操作转化为一个循环中更改的操作，所有迭代器都不会失效。即使删除操作会导致容器内存重分配，这个办法也可行，这是其优点，缺点是不能用于循环中添加的操作。

cexer 2010-08-15 13:34 发表评论

re: C++中遍历窗口对象时需要注意的问题

白云哥 — Sun, 15 Aug 2010 01:16:00 GMT

@cexer

做删除标志是一个方法,但对于对象有可能在其他地方已被删除的情况将没法实用(在这种情况下我的例子里的代码同样也有问题)

另外,在while循环中删除对象,虽然临时保存了下一个迭代器指针,这个同样是有问题的.因为删除容器对象有可能使得之前所保存的迭代器全都失效

如果要用删除标志,这样是可行的:

for(container::iterator itr = container.begin(); itr != container.end(); )
{
if (itr->second->is_dirty())
itr = container.erase(itr);
else
++itr;
}

白云哥 2010-08-15 09:16 发表评论

re: C++中遍历窗口对象时需要注意的问题

yrj — Sat, 14 Aug 2010 10:30:00 GMT

简化一下

iterator it_this = containter.begin();
iterator it_tmp;
while ( it_this != container.end() )
{
it_tmp = it_this;
++it_this;　
do_remove( it_tmp );
}

yrj 2010-08-14 18:30 发表评论