安全的list

    好久没有写东西了,实在是忙,其实,准确说是懒。

    最近调试客户端地图管理的时候,老是出现对象在视野中进进出出后就会冒出个非法。而非法的原因大多跟list有关,就是在list遍历显示列表的时候,出现了增删操作,而这个是list不能容忍的。由于系统比较大,要改的地方也多,而且好多异常情况也不是一下子就能改好的,当屏幕中的生物对象很多时,就容易出现。

想来想去,就想了一个能安全遍历的list来解决问题。因为在实际上,当遍历到一个list的节点时,会调用节点所含对象的update方法,该方法可能会触发从地图中删除自己或者其他对象,这样list就非法了。

下面是对标准list的简单封装,使之具有安全遍历的特性,遍历过程中可以增删任何节点。原理很简单,就是内部记住遍历的当前节点,在删除时做个比较。

//==========================================================================
/**
* @file      : safelist.h
* @author : PeakGao <peakgao163@163.com>
* created : 2008-11-13   20:21
* purpose : safe list
*/

//==========================================================================

#ifndef __safelist_h__
#define __safelist_h__

#include 
<list>

/** 安全list
对标准list进行了简单封装,使之具有安全遍历的功能(即:在遍历过程中,支持增删节点)

// 普通遍历
for (safelist<int>::const_iterator it = list.begin(); it!=list.end(); ++it)
{
    Info("val = "<<*it<<endl);
}

// 安全遍历(允许在遍历的过程中增删任何数目的节点)
for (safelist<int>::iterator it=list.find_first(); it!=list.end(); it=list.find_next(it))
{
    Info("val = "<<*it<<endl);
    if (*it == 3)
    {
        list.erase(it);
    }
}
*/

template
<class _Ty, class _Ax = std::allocator<_Ty> >
class safelist : public std::list<_Ty, _Ax>
{
public:
    typedef typename std::list
<_Ty, _Ax>    _Mybase;
    typedef typename safelist
<_Ty, _Ax>        _Myt;
    typedef typename _Mybase::_Alloc        _Alloc;

private:
    mutable _Nodeptr    _Cur;    
/// the cursor for for_each

public:
    safelist() : _Mybase(), _Cur(_Myhead) 
{ }
    
explicit safelist(const _Alloc& _Al) : _Mybase(_Al), _Cur(_Myhead) { }
    
explicit safelist(size_type _Count) : _Mybase(_Count), _Cur(_Myhead) { }
    safelist(size_type _Count, 
const _Ty& _Val) : _Mybase(_Count, _Val), _Cur(_Myhead) { }
    safelist(size_type _Count, 
const _Ty& _Val, const _Alloc& _Al) : _Mybase(_Count, _Val, _Al), _Cur(_Myhead) { }
    safelist(
const _Mybase& _Right) : _Mybase(_Right), _Cur(_Myhead) { }
    safelist(
const _Myt& _Right) : _Mybase(_Right), _Cur(_Myhead) { }
    template
<class _Iter>
    safelist(_Iter _First, _Iter _Last) : _Mybase(_First, _Last), _Cur(_Myhead) 
{ }
    template
<class _Iter>
    safelist(_Iter _First, _Iter _Last, 
const _Alloc& _Al) : _Mybase(_First, _Last, _Al), _Cur(_Myhead) { }

    
~safelist()
    
{
        _Cur 
= 0;
    }


    
void clear()
    
{
        _Mybase::clear();
        _Cur 
= _Myhead;
    }


    iterator erase(iterator _Where)
    
{
        _Nodeptr cur 
= _Where._Mynode();
        
if (_Cur == cur)
            _Cur 
= _Nextnode(cur);
        
return _Mybase::erase(_Where);
    }


    
// 用于安全遍历
public:
    iterator find_first()                
return iterator(_Cur = _Nextnode(_Myhead), this); }
    const_iterator find_first() 
const    return const_iterator(_Cur = _Nextnode(_Myhead), this); }

    iterator find_next(iterator cur)
    
{
        
if (cur._Mynode() == _Cur)
            _Cur 
= _Nextnode(_Cur);
        
return iterator(_Cur, this);
    }


    const_iterator find_next(const_iterator cur) 
const
    
{
        
if (cur._Mynode() == _Cur)
            _Cur 
= _Nextnode(_Cur);
        
return const_iterator(_Cur, this);
    }

}
;

posted on 2008-11-15 01:41 PeakGao 阅读(3328) 评论(11)  编辑 收藏 引用 所属分类: C++技术

评论

# re: 安全的list 2008-11-16 09:40 winsty

这个不是线程安全的问题么……  回复  更多评论   

# ????? 2008-11-16 18:45 是什么

看不懂 是什么哦
电脑程序
  回复  更多评论   

# re: 安全的list[未登录] 2008-11-17 10:30 PeakGao

@是什么
是这样的,当list的操作很简单时,遍历list几乎没有什么问题,也可以在遍历的时候删除当前节点,如:
for (std::list<int>::iterator it=list.begin(); it!=list.end();)
{
if (条件为真)
it = list.erase(it); // 删除当前节点
else
++it;
}

但是当这个list不是很简单的遍历时,而且删除的时候也不是很显式的在遍历过程中时,就很容易出问题,如:

void MapManager::update(...)
{
// typedef std::list<Entity*> DisplayList;
for (DisplayList::iterator it=mDisplayList.begin(); it!=mDisplayList.end();)
{
(*it)->update(...);
}
}

但是(*it)->update(...);会调用到另一个模块中去了,可能会这样调用:
void Entity::update(...)
{
//...
MapManager->removeEntity(this);
}

而removeEntity会涉及到erase节点:
void MapManager::removeEntity(Entity* e)
{
mDisplayList.remove(e);
}

如果Entity的update方法中,发现自己的生命期已经结束的话,就会删除自己,这样MapManager::update里面就非法了,这是一个站在砖头上拿掉砖头的问题,必定非法。这个safelist就是为了支持在遍历列表的过程中能安全的erase任何节点。

可能你们没有碰到该类问题,或者使用list的时候没有那么复杂,所以一时没法去了解。  回复  更多评论   

# re: 安全的list 2008-11-17 14:33 不懂

std::list<int>::iterator itTmp;

for (std::list<int>::iterator it=list.begin(); it!=list.end();)
{
if (条件为真)
{
itTmp = it;
++itTmp;
it = list.erase(it); // 删除当前节点
it = itTmp;
}
else
++it;
}
  回复  更多评论   

# re: 安全的list 2008-11-18 08:38 不懂

但是当这个list不是很简单的遍历时,而且删除的时候也不是很显式的在遍历过程中时,就很容易出问题  回复  更多评论   

# re: 安全的list 2008-11-18 08:38 不懂

但是当这个list不是很简单的遍历时,而且删除的时候也不是很显式的在遍历过程中时,就很容易出问题

如果真有这样的问题,那就是框架有问题  回复  更多评论   

# re: 安全的list[未登录] 2008-11-18 08:58 PeakGao

@不懂
理论上是这样,框架彻底的好就没有问题,但是在游戏更新时,经常有生命期结束的对象,这样的对象需要从地图上面移除,就涉及到从列表中erase,而生命期结束是根据update的调用进行检测的。当然可以有另一个办法,就是将检测放到一个时钟里面,而不是在list的遍历过程中,但是这样会需要好多多余的时钟。再有一种办法,就是对象要移除时,只设置一个需要移除的标志,在下一轮遍历前才真正移除。发现越说越复杂了,总之,这个功能就是用于list遍历很复杂时,也能安全的工作。你的这几行,参考我上面的,就一句it=list.erase(it)迭代器不需要临时保存的!!
for (std::list<int>::iterator it=list.begin(); it!=list.end();)
{
if (条件为真)
{
itTmp = it; // 多余
++itTmp; // 多余
it = list.erase(it); // 删除当前节点
it = itTmp; // 多余
}
else
++it;
}   回复  更多评论   

# re: 安全的list 2008-11-18 09:29 Jeff Chen

LZ的情况,我也遇到过,困惑过。当我看完jabberd2的代码后,觉得它的做法比较好。

方法如下:
程序每次先遍历所有的Connection时,无效的Connection将自己移入一个CloseList中。
在遍历所有的Connection后,程序接着清理CloseList里的Connection。

这样做的好处,不会出现LZ这种list“重入”的问题,而且可以灵活处理不需要的对象。  回复  更多评论   

# re: 安全的list 2008-11-18 17:06 LOGOS

顶楼上
mark it & lazy delete

这样做在在逻辑上更为完整,相对于作者直接删除对象而言
  回复  更多评论   

# re: 安全的list[未登录] 2008-11-20 13:35 PeakGao

@Jeff Chen
你这种其实就是我上面说的这个意思:“再有一种办法,就是对象要移除时,只设置一个需要移除的标志,在下一轮遍历前才真正移除。”,不过你的说法好像有问题哦,遍历时根本不知道是无效的Connection哦,而且不能在遍历的过程中将节点移入到另一个列表,这样会挂的  回复  更多评论   

# re: 安全的list(更简单的用法) 2009-01-08 08:46 canaan

http://zhgn.vicp.net/boke/200901071529.htm
List.erase(p)的用法  回复  更多评论   


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


<2012年2月>
2930311234
567891011
12131415161718
19202122232425
26272829123
45678910

导航

统计

常用链接

留言簿(9)

随笔分类(67)

随笔档案(65)

搜索

最新评论

阅读排行榜

评论排行榜