青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

白云哥

身披半件長工衣,懷揣一顆地主心

 

C++中遍歷容器對象時需要注意的問題

假設(shè)有這樣一個管理對象的窗口 ActorManager,其實現(xiàn)大概為

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類的實現(xiàn)是這樣:

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

}

有一天,在給Actor添加邏輯的時候,update函數(shù)變成了這樣

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循環(huán)里刪除對象,而實際上卻有幾次遇到類似的問題。
有些問題沒有這么明顯,但也都是出在遍歷容器對象的過程中,某個執(zhí)行函數(shù)刪除了窗口里的對象,從而導(dǎo)致迭代器失效。
 
修改的方法很簡單,給ActorManager添加一個待刪除對象列表
在remove方法中并不真正刪除對象,而是等到update中循環(huán)結(jié)束后再刪除對象。
代碼看起來會是這樣:
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函數(shù)內(nèi)向ActorManager添加新對象。

當(dāng)然,有可能在其他地方會有這樣的需求,同樣也做類似的保護即可。

 

 

問題雖然不大,但是幾次碰到類似的錯誤了。記錄之,并強制要求自己,

在遇到會對容器內(nèi)的對象做for…處理時,一定要謹慎的檢查一下remove接口。

posted on 2010-08-12 23:02 白云哥 閱讀(3024) 評論(15)  編輯 收藏 引用 所屬分類: Others

評論

# re: C++中遍歷窗口對象時需要注意的問題 2010-08-13 00:51 陳梓瀚(vczh)

最佳方法:給對象設(shè)置一個僵尸狀態(tài),讓manager去清除它。  回復(fù)  更多評論   

# re: C++中遍歷窗口對象時需要注意的問題 2010-08-13 01:50 cexer

博主弄復(fù)雜了,這種方法是治標(biāo)不治本的,如果容器中裝的是拷貝刪成本很大的東西,這樣效率就低了。循環(huán)中刪的問題在于刪除操作之后,當(dāng)前迭代器已經(jīng)失效,因此無法更新之使其指向容器中的下一個元素。強行對迭代器進行 ++ 操作更新,會出現(xiàn)訪問異常。所以只要刪除之前,用一個額外的迭代器記住下一個元素的位置就行了。
如下:
//////////////////////////////////////////

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;
}

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

樓上的“僵尸狀態(tài)”也是一個辦法,不過正如它的名字一樣的,“僵尸”是個惡心的存在。程序在某一次循環(huán)中,把一堆元素標(biāo)記為僵尸,這一堆東西必須要等到下一次循環(huán)檢查才能清理掉,如果沒有專門的定時清理機制,這個下一次有可能十分之一柱香之后,也有可能是一萬年,甚至有可能程序流程再也沒有這樣的下一次。在被清理掉之前那一堆僵尸在容器里腐爛發(fā)臭,占用空間內(nèi)存,可能直到最后容器銷毀。可以增加專門定時清理機制,但是復(fù)雜度和成本又得另外計算。所以最好的辦法還是就地處決,并且毀尸滅跡。


  回復(fù)  更多評論   

# re: C++中遍歷窗口對象時需要注意的問題 2010-08-13 11:14 Sunshine Alike

cexer 的方法貌似可行~  回復(fù)  更多評論   

# 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 );
}  回復(fù)  更多評論   

# re: C++中遍歷窗口對象時需要注意的問題 2010-08-15 09:16 白云哥

@cexer


做刪除標(biāo)志是一個方法,但對于對象有可能在其他地方已被刪除的情況將沒法實用(在這種情況下我的例子里的代碼同樣也有問題)

另外,在while循環(huán)中刪除對象,雖然臨時保存了下一個迭代器指針,這個同樣是有問題的.因為刪除容器對象有可能使得之前所保存的迭代器全都失效

如果要用刪除標(biāo)志,這樣是可行的:

for(container::iterator itr = container.begin(); itr != container.end(); )
{
if (itr->second->is_dirty())
itr = container.erase(itr);
else
++itr;
}  回復(fù)  更多評論   

# re: C++中遍歷窗口對象時需要注意的問題 2010-08-15 13:34 cexer

@白云哥
容器循環(huán)中的操作有四種,循環(huán)中查詢,循環(huán)中更改,循環(huán)中刪除,循環(huán)中添加,這些操作都圍繞迭代器進行的。
循環(huán)中查詢,循環(huán)中更改(這兩類操作其實也包含了循環(huán)中循環(huán),循環(huán)中的循環(huán)中的循環(huán),循環(huán)中的循環(huán)中的循環(huán)中的循環(huán)。。。)因為不會改變迭代器的合法性,不會有什么問題。

循環(huán)中添加和刪除則不一樣,循環(huán)中添加有可能導(dǎo)致所有元素內(nèi)存重分配,導(dǎo)致所有迭代器失效,而刪除操作一般來說不會產(chǎn)生內(nèi)存重分配的情況,目前std內(nèi)的容器應(yīng)該都是如此(七分分析三分猜測,正確性八九不離十)。

所以循環(huán)中刪除只會使當(dāng)前刪除操作的迭代器失效,使得不能更新之使其指向下一個元素,而不會影其它迭代器。如list這類的容器,所有元素內(nèi)存都是單獨分配的,針對添加操作進行一次單獨的內(nèi)存分配,不會影響到現(xiàn)在有迭代器的合法性 ,但有可能刪除操作導(dǎo)致元素重排,元素移位,使得循環(huán)不完全,漏掉元素。

循環(huán)中添加如果導(dǎo)致內(nèi)存重分配,則會使所有現(xiàn)有的迭代器失效,例如vector,string這類容器要保證其內(nèi)存是連續(xù)的,添加時內(nèi)存有可能會重分配,導(dǎo)致以前的迭代器全部失效。

所以針對循環(huán)中添加和刪除的幾種解決方法分析如下:
在循環(huán)中保存下一個迭代器的方法:對于刪除操作是沒有任何問題的(關(guān)于你說的“刪除容器對象有可能使得之前所保存的迭代器全都失效”,目前std內(nèi)的容器應(yīng)該都不會發(fā)生這種情況),但對于添加操作,則只適用于非連續(xù)內(nèi)存的容器如list,不適用于連續(xù)內(nèi)存的容器如vector。這個辦法優(yōu)點是沒有時間空間的成本,缺點是對于添加操作,有些容器不支持。

使用緩存進行延遲操作的方法:對于刪除和添加都適用,只是需要在所有接口中小心管理m_is_looping,避免重入的問題。優(yōu)點是添加和刪除都適用,缺點是空間時間的效率損失最大。

使用刪除標(biāo)志延遲刪除的方法:對于刪除操作適用,也不存在其它地方刪除會出問題的情況,因為這個方法實際上是把循環(huán)中刪除的操作轉(zhuǎn)化為一個循環(huán)中更改的操作,所有迭代器都不會失效。即使刪除操作會導(dǎo)致容器內(nèi)存重分配,這個辦法也可行,這是其優(yōu)點,缺點是不能用于循環(huán)中添加的操作。  回復(fù)  更多評論   

# re: C++中遍歷窗口對象時需要注意的問題 2010-08-15 14:27 白云哥

@cexer

“在循環(huán)中保存下一個迭代器的方法:對于刪除操作是沒有任何問題的”
這個確定是有問題的,我就是好幾次遇到了這樣的問題才寫的這個總結(jié)

下面是根據(jù)你的方法寫的測試程序,運行一下,刪除容器的第一個數(shù)據(jù)后,原來的迭代器就失效了


#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;
}  回復(fù)  更多評論   

# re: C++中遍歷容器對象時需要注意的問題 2010-08-15 14:50 cexer

@白云哥
你看到只刪除了一半,是因為對于vector這種容器,移除前面元素,后面的元素會整體往移一位,本來指向下一個元素的迭代器指向了下下個元素,后面的循環(huán)會漏掉下一個元素,這個我在上面也說過的。對于list,set,map之類的就能完全刪除。需要從中間刪除的容器,最好不要用vector,元素移位的操作不是常數(shù)時間的。  回復(fù)  更多評論   

# re: C++中遍歷容器對象時需要注意的問題 2010-08-15 15:07 白云哥

@cexer

是的,這個依賴于標(biāo)準(zhǔn)庫的實現(xiàn)
我用vs2010會出現(xiàn)迭代器失效,程序立即終止
在mac os下用gcc沒有問題


但這個確實是有問題的,標(biāo)準(zhǔn)里是否有相關(guān)描述我不是很清楚,但是可以看這里,別人介紹的方法也是我上面說的


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

總之是不能用“先保存迭代器,再刪除”的方法,因為在刪除的時候“有可能”會導(dǎo)致迭代器失效

看起來確實是“有可能”,這依賴于具體的實現(xiàn) :)
  回復(fù)  更多評論   

# re: C++中遍歷容器對象時需要注意的問題 2010-08-15 15:14 cexer

@白云哥
呵呵,學(xué)習(xí)了,看來還是你的辦法穩(wěn)當(dāng)。這確實是標(biāo)準(zhǔn)庫的實現(xiàn)相關(guān)的,我上面說的也都是基于估計它的一般實現(xiàn),很好奇2010的vector是怎么樣實現(xiàn)的,會出現(xiàn)這種失效的問題。  回復(fù)  更多評論   

# 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.”


刪除對象后會讓迭代器之后的對象移動,因此而導(dǎo)致迭代器失效


map的實現(xiàn),紅黑樹,在插入和刪除對象后因為要做平衡,所以同樣也有可能導(dǎo)致迭代器的失效


當(dāng)然最終是不是會出現(xiàn)迭代器錯誤,這依賴于標(biāo)準(zhǔn)庫的具體實現(xiàn),另外還可能包括其優(yōu)化方法  回復(fù)  更多評論   

# re: C++中遍歷容器對象時需要注意的問題 2010-08-15 15:19 cexer

可以結(jié)合兩種方法。刪除用標(biāo)記緩存刪除的方法,添加用緩存延遲添加的方法好。  回復(fù)  更多評論   

# 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.”

刪除對象后會讓迭代器之后的對象移動,因此而導(dǎo)致迭代器失效


map的實現(xiàn),紅黑樹,在插入和刪除對象后因為要做平衡,所以同樣也有可能導(dǎo)致迭代器的失效]]]]

就這兩條原因,不會使迭代器失效,我所說的迭代器失效,是指容納它數(shù)據(jù)結(jié)構(gòu)的內(nèi)存不存在。對于連續(xù)內(nèi)存的容器,刪除進行元素移位,迭代器的內(nèi)存還在,對于非連續(xù)內(nèi)存的操作,map,list,set之類的都鏈?zhǔn)降膶崿F(xiàn),這類的結(jié)點銷毀的應(yīng)該只是鏈當(dāng)前結(jié)點,對其它結(jié)點的只有修改,所以不應(yīng)該失效。至于2010為什么失效,有點好奇,刪除操作也要內(nèi)存重分配,我覺得這是不好的實現(xiàn)。
  回復(fù)  更多評論   

# re: C++中遍歷容器對象時需要注意的問題 2010-08-22 22:51 yisa

@cexer
這個方法也有局限性,
如果出現(xiàn)了
A對象的update 執(zhí)行中把B對象給干掉了, 而不走運的是: "在迭代過程中, B正是A的下一個對象", 一樣要報銷了
STL的迭代中的迭代是外置的,
lz這樣的需求下, 必須使用內(nèi)置迭代.
即: 容器需要記錄當(dāng)前迭代位置, 如果發(fā)生刪除 需要更新當(dāng)前迭代位置.  回復(fù)  更多評論   

# re: C++中遍歷容器對象時需要注意的問題 2010-08-22 22:57 yisa

突然發(fā)現(xiàn)您也是做游戲的
我的QQ: 348360855 組隊吧!

對容器在游戲開發(fā)中的應(yīng)用, 我這邊有比較完善的解決方案(兼顧安全與性能, 針對游戲邏輯應(yīng)用, 在降低bug率, 提高程序安全性, 性能上都遠勝STL)
希望能切磋技術(shù)和分享經(jīng)驗  回復(fù)  更多評論   


只有注冊用戶登錄后才能發(fā)表評論。
網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問   Chat2DB   管理


導(dǎo)航

統(tǒng)計

常用鏈接

留言簿(4)

隨筆分類

隨筆檔案

相冊

我的鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲午夜国产成人av电影男同| 欧美影院视频| 一区二区三区四区五区精品视频 | 欧美日本中文字幕| 欧美国产三级| 欧美色中文字幕| 国产精品福利片| 国产日韩在线视频| 在线日韩欧美视频| 一区二区精品| 欧美一区激情| 欧美激情一区二区三区在线| 日韩一级精品视频在线观看| 亚洲午夜精品国产| 久久国产一区二区三区| 久久综合999| 国产精品久久久久9999吃药| 国产一区二区三区四区五区美女 | 一区二区三区在线视频观看 | 亚洲日本欧美| 亚洲欧美日韩区| 欧美成人在线免费视频| 一个人看的www久久| 欧美在线观看视频一区二区| 你懂的国产精品| 国产欧美 在线欧美| 最新日韩在线视频| 久久精品亚洲精品| 亚洲精品一级| 久久网站免费| 国产乱码精品1区2区3区| 亚洲精品1区| 久久视频免费观看| 99视频精品在线| 久久五月天婷婷| 国产网站欧美日韩免费精品在线观看 | 欧美日韩免费观看一区三区| 欧美日韩国产一中文字不卡| 国产一区二区三区自拍| 一区二区不卡在线视频 午夜欧美不卡在 | 欧美久久久久久| 韩日欧美一区二区三区| 亚洲曰本av电影| 91久久在线| 午夜精品久久| 国产精品xxx在线观看www| 99精品免费网| 亚洲国产精品成人精品 | 国产精品成人av性教育| 亚洲精品中文字幕在线| 另类激情亚洲| 久久都是精品| 国产真实乱子伦精品视频| 香港久久久电影| 亚洲一区二区三区免费观看 | 日韩视频专区| 欧美sm视频| 久久久久高清| 一区久久精品| 美女亚洲精品| 狼狼综合久久久久综合网| 一区二区三区在线不卡| 另类专区欧美制服同性| 久久国产精品亚洲77777| 国产精自产拍久久久久久| 亚洲欧美激情诱惑| 亚洲男人的天堂在线aⅴ视频| 国产精品久久77777| 午夜一区不卡| 欧美一区亚洲二区| 在线观看av不卡| 免费亚洲电影| 欧美精品在线观看播放| 在线中文字幕一区| 亚洲视频电影在线| 国产乱码精品一区二区三区五月婷 | 欧美成人中文字幕| 欧美韩日亚洲| 亚洲欧美成人网| 欧美在线3区| 亚洲黄色毛片| 99视频在线观看一区三区| 国产精品男gay被猛男狂揉视频| 欧美亚洲一区二区在线| 久久精品久久综合| 亚洲乱码精品一二三四区日韩在线| 欧美国产免费| 欧美插天视频在线播放| 亚洲一区久久| 亚洲电影第1页| 亚洲免费成人av电影| 国产欧美一区二区三区沐欲| 欧美11—12娇小xxxx| 欧美日韩国产影院| 亚洲一区二区四区| 亚洲少妇一区| 国产九九精品视频| 久久黄色影院| 久久看片网站| 亚洲精品日产精品乱码不卡| 亚洲欧洲一区二区天堂久久| 欧美日本不卡视频| 午夜在线一区| 久久精品夜色噜噜亚洲aⅴ| 在线观看久久av| 亚洲国产精品久久91精品| 欧美区亚洲区| 欧美中文字幕在线视频| 久久久久久亚洲精品中文字幕| 91久久国产综合久久| 99精品欧美一区二区三区| 国产欧美日韩视频在线观看| 麻豆精品在线观看| 欧美日韩不卡在线| 久久精品国产第一区二区三区| 久久久九九九九| 夜夜嗨av一区二区三区四区 | 午夜精品亚洲一区二区三区嫩草| 久久久久久电影| 午夜精品一区二区三区电影天堂| 欧美经典一区二区三区| 欧美高清在线视频| 狠狠色狠色综合曰曰| 欧美成人午夜激情| 久久精品国产99精品国产亚洲性色 | 韩国在线一区| 亚洲欧美一区二区三区极速播放 | 亚洲欧美一区二区三区在线| 一区二区三区黄色| 免费久久精品视频| 美女被久久久| 在线不卡中文字幕| 久久精品国产综合| 欧美一区二粉嫩精品国产一线天| 欧美日韩裸体免费视频| 亚洲另类在线视频| 亚洲婷婷在线| 国产精品99一区二区| 一本综合久久| 亚洲制服丝袜在线| 亚洲欧美国产77777| 欧美午夜精品久久久久久孕妇| 亚洲国产99| 一本大道av伊人久久综合| 欧美精品一区视频| 一区二区三区高清视频在线观看| 宅男噜噜噜66国产日韩在线观看| 欧美日韩一区二区三区在线看| 99re热这里只有精品视频 | 狠狠综合久久| 久久先锋影音| 亚洲欧洲一二三| 亚洲桃色在线一区| 国产美女扒开尿口久久久| 久久国产精品亚洲77777| 欧美.www| 亚洲一卡久久| 国产日韩在线一区| 奶水喷射视频一区| 夜夜夜精品看看| 欧美在线视频观看免费网站| 狠狠入ady亚洲精品| 麻豆91精品91久久久的内涵| 亚洲日本成人女熟在线观看| 亚洲欧美激情诱惑| 有码中文亚洲精品| 欧美日韩国内| 久久久久久久一区二区三区| 亚洲狼人综合| 久热国产精品| 亚洲午夜羞羞片| 在线观看成人av| 国产精品国产三级国产aⅴ入口| 欧美一区二区三区免费观看| 欧美激情一区三区| 欧美一区二区成人| 99re这里只有精品6| 国产亚洲欧美日韩一区二区| 欧美黑人国产人伦爽爽爽| 亚洲欧美一区二区三区久久 | 欧美不卡在线| 性刺激综合网| 一区二区三区高清在线观看| 激情综合网激情| 国产精品日韩欧美| 欧美插天视频在线播放| 欧美一区三区二区在线观看| 日韩亚洲欧美高清| 欧美高清在线视频观看不卡| 欧美一区激情视频在线观看| 日韩午夜高潮| 亚洲国产日韩欧美| 狠狠色综合网站久久久久久久| 国产精品v日韩精品v欧美精品网站| 久久久噜噜噜久久人人看| 亚洲欧美在线免费观看| 在线一区日本视频| 亚洲精品欧美日韩专区| 亚洲国产精品成人一区二区| 欧美电影电视剧在线观看|