白云哥

身披半件长工衣,怀揣一颗地主心

 

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

假设有这样一个管理对象的窗口 ActorManager,其实现大概为

class Actor;
class ActorManager
{
public:
void update()
{
for (actors_t::const_iterator itr = m_actors.begin(); itr != m_actors.end(); ++itr)
{
Actir* actor = itr->second;
actor->update();
}
}

void add(Actor* actor)
{
m_actors[actor->get_id()] = actor;
}

void remove(Actor* actor)
{
m_actors.erase(actor->get_id());
}

private:
typedef std::map<int, Actor*> actors_t;
actors_t m_actors;
};

 

而Actor类的实现是这样:

class Actor
{
public:
void update()
{
// ...

}

有一天,在给Actor添加逻辑的时候,update函数变成了这样

void update()
{
// ...

update_buff_effect();

// ...
}

 

再往下

 

class Actor
{
// ...

private:
void update_buff_effect()
{
// ...

apply_hp(-100);
if (get_hp() <= 0)
{
die();
return;
}

// ...
}

 

然后……

 

private:
void die()
{
// ...

ActorManager::getInstance().remove(this);

// ...
}
在写下ActorManager的时候并没有想到会在update循环里删除对象,而实际上却有几次遇到类似的问题。
有些问题没有这么明显,但也都是出在遍历容器对象的过程中,某个执行函数删除了窗口里的对象,从而导致迭代器失效。
 
修改的方法很简单,给ActorManager添加一个待删除对象列表
在remove方法中并不真正删除对象,而是等到update中循环结束后再删除对象。
代码看起来会是这样:
class Actor;
class ActorManager
{
public:
void update()
{
m_is_looping = true;
for (actors_t::const_iterator itr = m_actors.begin(); itr != m_actors.end(); ++itr)
{
Actir* actor = itr->second;
actor->update();
}
m_is_looping = false;

if (!m_removed_actors.empty())
{
for (removed_actors_t::const_iterator itr = m_removed_actors.begin();
itr != m_removed_actors.end(); ++itr)
{
Actor* actor = *itr;
m_actors.erase(actor->get_id());
}
m_removed_actors.clear();
}
}

void add(Actor* actor)
{
m_actors[actor->get_id()] = actor;
}

void remove(Actor* actor)
{
if (!m_is_looping)
m_actors.erase(actor->get_id());
else
m_removed_actors.push_back(actor);
}

private:
typedef std::map<int, Actor*> actors_t;
actors_t m_actors;

typedef std::vector<Actor*> removed_actors_t;
removed_actors_t m_removed_actors;
bool m_is_looping;
};

 

没有给add也加保护的原因是,不会在update函数内向ActorManager添加新对象。

当然,有可能在其他地方会有这样的需求,同样也做类似的保护即可。

 

 

问题虽然不大,但是几次碰到类似的错误了。记录之,并强制要求自己,

在遇到会对容器内的对象做for…处理时,一定要谨慎的检查一下remove接口。

posted on 2010-08-12 23:02 白云哥 阅读(2967) 评论(15)  编辑 收藏 引用 所属分类: Others

评论

# re: C++中遍历窗口对象时需要注意的问题 2010-08-13 00:51 陈梓瀚(vczh)

最佳方法:给对象设置一个僵尸状态,让manager去清除它。  回复  更多评论   

# re: C++中遍历窗口对象时需要注意的问题 2010-08-13 01:50 cexer

博主弄复杂了,这种方法是治标不治本的,如果容器中装的是拷贝删成本很大的东西,这样效率就低了。循环中删的问题在于删除操作之后,当前迭代器已经失效,因此无法更新之使其指向容器中的下一个元素。强行对迭代器进行 ++ 操作更新,会出现访问异常。所以只要删除之前,用一个额外的迭代器记住下一个元素的位置就行了。
如下:
//////////////////////////////////////////

iterator it_this = containter.begin();
iterator it_next;
while ( it_this != container.end() )
{
    it_next = it_this; // 之所以不直接使用 it_next=it_this+1
    ++ it_next;      // 是因为有些容器不支持随机访问,其迭代器不能直接 + n
    do_remove( it_this );
    it_this = it_next;
}

/////////////////////////////////////////////////////

楼上的“僵尸状态”也是一个办法,不过正如它的名字一样的,“僵尸”是个恶心的存在。程序在某一次循环中,把一堆元素标记为僵尸,这一堆东西必须要等到下一次循环检查才能清理掉,如果没有专门的定时清理机制,这个下一次有可能十分之一柱香之后,也有可能是一万年,甚至有可能程序流程再也没有这样的下一次。在被清理掉之前那一堆僵尸在容器里腐烂发臭,占用空间内存,可能直到最后容器销毁。可以增加专门定时清理机制,但是复杂度和成本又得另外计算。所以最好的办法还是就地处决,并且毁尸灭迹。


  回复  更多评论   

# re: C++中遍历窗口对象时需要注意的问题 2010-08-13 11:14 Sunshine Alike

cexer 的方法貌似可行~  回复  更多评论   

# re: C++中遍历窗口对象时需要注意的问题 2010-08-14 18:30 yrj

简化一下

iterator it_this = containter.begin();
iterator it_tmp;
while ( it_this != container.end() )
{
it_tmp = it_this;
++it_this; 
do_remove( it_tmp );
}  回复  更多评论   

# re: C++中遍历窗口对象时需要注意的问题 2010-08-15 09:16 白云哥

@cexer


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

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

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

for(container::iterator itr = container.begin(); itr != container.end(); )
{
if (itr->second->is_dirty())
itr = container.erase(itr);
else
++itr;
}  回复  更多评论   

# re: C++中遍历窗口对象时需要注意的问题 2010-08-15 13:34 cexer

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

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

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

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

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

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

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

# re: C++中遍历窗口对象时需要注意的问题 2010-08-15 14:27 白云哥

@cexer

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

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


#include <vector>
#include <iostream>

typedef std::vector<int> 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;
}  回复  更多评论   

# re: C++中遍历容器对象时需要注意的问题 2010-08-15 14:50 cexer

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

# re: C++中遍历容器对象时需要注意的问题 2010-08-15 15:07 白云哥

@cexer

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


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


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

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

看起来确实是“有可能”,这依赖于具体的实现 :)
  回复  更多评论   

# re: C++中遍历容器对象时需要注意的问题 2010-08-15 15:14 cexer

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

# re: C++中遍历容器对象时需要注意的问题 2010-08-15 15:17 白云哥

@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的实现,红黑树,在插入和删除对象后因为要做平衡,所以同样也有可能导致迭代器的失效


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

# re: C++中遍历容器对象时需要注意的问题 2010-08-15 15:19 cexer

可以结合两种方法。删除用标记缓存删除的方法,添加用缓存延迟添加的方法好。  回复  更多评论   

# re: C++中遍历容器对象时需要注意的问题 2010-08-15 15:29 cexer

@白云哥

[[[[“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为什么失效,有点好奇,删除操作也要内存重分配,我觉得这是不好的实现。
  回复  更多评论   

# re: C++中遍历容器对象时需要注意的问题 2010-08-22 22:51 yisa

@cexer
这个方法也有局限性,
如果出现了
A对象的update 执行中把B对象给干掉了, 而不走运的是: "在迭代过程中, B正是A的下一个对象", 一样要报销了
STL的迭代中的迭代是外置的,
lz这样的需求下, 必须使用内置迭代.
即: 容器需要记录当前迭代位置, 如果发生删除 需要更新当前迭代位置.  回复  更多评论   

# re: C++中遍历容器对象时需要注意的问题 2010-08-22 22:57 yisa

突然发现您也是做游戏的
我的QQ: 348360855 组队吧!

对容器在游戏开发中的应用, 我这边有比较完善的解决方案(兼顾安全与性能, 针对游戏逻辑应用, 在降低bug率, 提高程序安全性, 性能上都远胜STL)
希望能切磋技术和分享经验  回复  更多评论   


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


导航

统计

常用链接

留言簿(4)

随笔分类

随笔档案

相册

我的链接

搜索

最新评论

阅读排行榜

评论排行榜