• <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>

            白云哥

            身披半件長(zhǎng)工衣,懷揣一顆地主心

             

            C++中遍歷容器對(duì)象時(shí)需要注意的問題

            假設(shè)有這樣一個(gè)管理對(duì)象的窗口 ActorManager,其實(shí)現(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類的實(shí)現(xiàn)是這樣:

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

            }

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

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

             

             

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

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

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

            評(píng)論

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

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

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

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

            iterator it_this = containter.begin();
            iterator it_next;
            while ( it_this != container.end() )
            {
                it_next = it_this; // 之所以不直接使用 it_next=it_this+1
                ++ it_next;      // 是因?yàn)橛行┤萜鞑恢С蛛S機(jī)訪問,其迭代器不能直接 + n
                do_remove( it_this );
                it_this = it_next;
            }

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

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


              回復(fù)  更多評(píng)論   

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

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

            # re: C++中遍歷窗口對(duì)象時(shí)需要注意的問題 2010-08-14 18:30 yrj

            簡(jiǎn)化一下

            iterator it_this = containter.begin();
            iterator it_tmp;
            while ( it_this != container.end() )
            {
            it_tmp = it_this;
            ++it_this; 
            do_remove( it_tmp );
            }  回復(fù)  更多評(píng)論   

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

            @cexer


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

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

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

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

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

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

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

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

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

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

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

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

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

            @cexer

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

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


            #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ù)  更多評(píng)論   

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

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

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

            @cexer

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


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


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

            總之是不能用“先保存迭代器,再刪除”的方法,因?yàn)樵趧h除的時(shí)候“有可能”會(huì)導(dǎo)致迭代器失效

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

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

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

            # re: C++中遍歷容器對(duì)象時(shí)需要注意的問題 2010-08-15 15:17 白云哥

            @cexer

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

            這里是一個(gè)比較好的描述

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


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


            map的實(shí)現(xiàn),紅黑樹,在插入和刪除對(duì)象后因?yàn)橐銎胶猓酝瑯右灿锌赡軐?dǎo)致迭代器的失效


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

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

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

            # re: C++中遍歷容器對(duì)象時(shí)需要注意的問題 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.”

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


            map的實(shí)現(xiàn),紅黑樹,在插入和刪除對(duì)象后因?yàn)橐銎胶猓酝瑯右灿锌赡軐?dǎo)致迭代器的失效]]]]

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

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

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

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

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

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

            導(dǎo)航

            統(tǒng)計(jì)

            常用鏈接

            留言簿(4)

            隨筆分類

            隨筆檔案

            相冊(cè)

            我的鏈接

            搜索

            最新評(píng)論

            閱讀排行榜

            評(píng)論排行榜

            久久久久久精品免费看SSS| 久久九九亚洲精品| 久久天天躁狠狠躁夜夜2020 | 三级韩国一区久久二区综合| 久久九九久精品国产免费直播| 精品久久人人爽天天玩人人妻 | 香蕉99久久国产综合精品宅男自 | 久久亚洲精品国产亚洲老地址| 99re这里只有精品热久久| 国产精品无码久久四虎| 久久亚洲精品无码观看不卡| 久久综合伊人77777| 国产成人无码精品久久久免费| 狠狠久久综合伊人不卡| 久久久久久国产精品免费免费| 66精品综合久久久久久久| 一级做a爱片久久毛片| 2020久久精品国产免费| 久久久久综合网久久| 久久精品成人免费看| 欧美久久亚洲精品| 亚洲精品乱码久久久久久久久久久久 | 久久国产精品无码一区二区三区 | 久久久久亚洲AV无码专区体验| 久久无码国产专区精品| 久久精品国产亚洲AV久| 国产精品久久久福利| 狠狠色丁香婷婷久久综合五月| 久久久久久精品久久久久| 久久99热国产这有精品| 国产成人精品久久免费动漫| 99久久精品国产一区二区 | 好属妞这里只有精品久久| 99久久国产综合精品网成人影院| 国产ww久久久久久久久久| 久久久黄色大片| 久久国产精品99精品国产987| 久久97久久97精品免视看| 亚洲∧v久久久无码精品| 婷婷综合久久狠狠色99h| 亚洲精品乱码久久久久久按摩 |