イテレータを回してるときの要素追加

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
アバター
YYSS
記事: 125
登録日時: 14年前
連絡を取る:

イテレータを回してるときの要素追加

#1

投稿記事 by YYSS » 12年前

vectorのイテレータを回してる最中に、要素追加するとエラーになります。

以下ソース

コード:

void C_ObjMgr::MainProcess(){

	//	イテレータ生成
	vector< C_ObjProcess* >::iterator it	= m_ObjPt.begin();
	
	while( it != m_ObjPt.end() ){

		//	オブジェクトが居なかったらリストから外す
		if( (*it)->Obj_Main() == false ){
			it	= m_ObjPt.erase( it );
		}
		else{
			++it;
		}
	}

}

class	C_ObjProcess{

public:
	C_ObjProcess(){}

	virtual	bool	Obj_Main(){		return false;	}
	virtual	void	Obj_Draw(){		return;			}
	virtual	void	Obj_Clear(){	return;			}
};
Obj_Main()内で要素が追加されたりします。


こういうやり方はよくないのでしょうか?
多態性を高めるために、各オブジェクトにC_ObjProcessを継承させ、
オブジェクト生成ごとにC_ObjProcessのポインタを、C_ObjMgrのm_ObjPtに追加するようにしたのですが、
実行時にエラーがでて困ってます;;

こういう構築の仕方はよくないのでしょうか?
アドバイスをくださると幸いです。

アバター
h2so5
副管理人
記事: 2212
登録日時: 14年前
住所: 東京
連絡を取る:

Re: イテレータを回してるときの要素追加

#2

投稿記事 by h2so5 » 12年前

肝心の要素追加している部分のソースコードがないのでなんとも言えないですが、
イテレータ操作中にpush_backなどするとイテレータが破壊される可能性があります。


http://www.geocities.jp/ky_webid/cpp/library/002.html
vector は内部に一括確保した領域を保持しています。 この領域が足りなくなるときに、新しくより広大な領域を確保し、既存の要素をそちらへコピーします。 その後、古い領域は解放されてなくなります。 (内部の具体的な実装はコンパイラ次第ですが、大体の動作はこのような感じです)。

この挙動から、「要素を追加したときには、既存の要素のアドレスが変わり得る」という重要な点に気付きます。 従って、イテレータが指し示していた先も不正な場所になってしまう可能性があります。

そのため、push_back() や insert() を呼び出したとき、それより前の時点で変数に保存しておいたアドレスやイテレータは、 すべて破棄しなければなりません。
解決策として、一時的なvectorを別に用意してそちらに要素を追加していき、後でマージするという方法があります。

アバター
YYSS
記事: 125
登録日時: 14年前
連絡を取る:

Re: イテレータを回してるときの要素追加

#3

投稿記事 by YYSS » 12年前

勉強不足でした;;
h2so5 さんが書きました:肝心の要素追加している部分のソースコードがないのでなんとも言えないですが、
イテレータ操作中にpush_backなどするとイテレータが破壊される可能性があります。
まさに、イテレータ操作中にpush_backをしていました。

ソースはポインタを受け取って追加しているだけです。

コード:

void C_ObjMgr::NewObjEntry( C_ObjProcess *obj ){

	m_ObjPt.push_back( obj );
}
h2so5 さんが書きました: 解決策として、一時的なvectorを別に用意してそちらに要素を追加していき、後でマージするという方法があります。
よかれと思ってやりましたが、逆に手順が増えてしまった気がします・・・


ふと思ったのですが、イテレータを使わずに添え字で指定する方法なら大丈夫なんでしょうか・・・?

コード:

void C_ObjMgr::MainProcess(){
 
    //  イテレータ生成
//    vector< C_ObjProcess* >::iterator it    = m_ObjPt.begin();
    
	int		it = 0;
	while( it < m_ObjPt.size() ){

		//	オブジェクトが居なかったらリストから外す
		if( m_ObjPt[ it ]->Obj_Main() == false ){
			vector< C_ObjProcess* >::iterator it2	= m_ObjPt.begin();
			advance( it2, it );
			m_ObjPt.erase( it2 );
        }
        else{
            ++it;
        }
    }
 
}
イテレータを使ったほうが効率は良いといわれているので、添え字でのアクセスは効率が悪いと思っているのですが、
一時的なvectorを別に用意して、最後に追加する処理を踏まえるとどうなんでしょうか?

アバター
h2so5
副管理人
記事: 2212
登録日時: 14年前
住所: 東京
連絡を取る:

Re: イテレータを回してるときの要素追加

#4

投稿記事 by h2so5 » 12年前

質問している内容と添付しているコードの内容が一致していません。
要素を削除しているコードではなく、追加しているコードを貼るべきでしょう。

他の方法として、要素追加後の要素数に見当がつく場合、
追加前にreserveすることでイテレータの破壊を防止することができます。

YuO
記事: 947
登録日時: 14年前
住所: 東京都世田谷区

Re: イテレータを回してるときの要素追加

#5

投稿記事 by YuO » 12年前

なんとなく思うことなのですが,Obj_Main関数が色々とやり過ぎていませんか。
「オブジェクトが存在するかどうかの確認」

「それ以外の処理」
は分離できないのでしょうか。

分離できるのであれば,分離した方が見通しがよくなると思いますが。

例えば確認処理がbool virtual C_ObjProcess::hasObject() const = 0;だとして,

コード:

m_ObjPt.erase(std::remove_if(m_ObjPt.begin(), m_ObjPt.end(), std::not1(std::mem_fn(&C_ObjProcess::hasObject))), m_ObjPt.end());
と,削除自体は一行になります。

もちろん,このままではメモリリークが発生するため,std::shared_ptrを使うのでしょうが,
std::shared_ptr使うとnot1とmem_fnの組み合わせがそのままでは使えなくなるので,ラムダ式を使って,

コード:

m_ObjPt.erase(std::remove_if(m_ObjPt.begin(), m_ObjPt.end(), [] (const std::shared_ptr<C_ObjProcess> & p) { return !p->hasObject(); }), m_ObjPt.end());
のようになりますが。
# shared_ptrが絡んだときのnot1とmem_fnとbindの使い方がよくわからない……ラムダ式より面倒になりそうな予感しかしない……。

アバター
YYSS
記事: 125
登録日時: 14年前
連絡を取る:

Re: イテレータを回してるときの要素追加

#6

投稿記事 by YYSS » 12年前

返答遅れてすみません;;
h2so5 さんが書きました:質問している内容と添付しているコードの内容が一致していません。
要素を削除しているコードではなく、追加しているコードを貼るべきでしょう。
追加しているコードは少し深いところにあるので、ちょっと見づらいかもしれませんが

※敵オブジェクトの場合

コード:

//	メイン	================================================================================================================================
bool C_ZakoObj::Obj_Main(){

	(this->*MovePattern)();		//	行動関数ポインタ
	MoveAdd();					//	移動

	//	回転するタイプ
	if( m_RotaAdd )	m_RotaAngle		+= m_RotaAdd;

	AnimeAct();

	//	敵が画面から外れたら消す
	if( GetDelLineArea( 1 ) && CheckLimitCountOver() ){
		m_Flag	= false;
	}
	EnemyDelete();									//	Lifeが0なら大破
	m_MutekiTime	-= m_MutekiTime == 0 ? 0 : 1;	//	無敵時間を減らす
	m_FlameCount	++;								//	毎フレームカウント

	return	m_Flag;
}
MovePattern内で敵弾オブジェクトや、エフェクトオブジェクトが生成されます。
MovePatternは行動パターンの関数をいれます。

行動パターン関数

コード:

void C_ZakoObj::MovePattern001(){

	if( Judge( 80, 120, 10 ) ){
		Bullet->nway( m_X, m_Y, 1, GetAngleToPlayer(), 0, 4.0, e_BULLET_DAEN, m_Element );
	}
}
Bullet->nwayでオブジェクトが追加されます。
内部でNewObjEntryが呼ばれます。

h2so5 さんが書きました:他の方法として、要素追加後の要素数に見当がつく場合、
追加前にreserveすることでイテレータの破壊を防止することができます。
reserveという手がありましたか、参考にさせていただきます。

YuO さんが書きました: 例えば確認処理がbool virtual C_ObjProcess::hasObject() const = 0;だとして,

コード:

m_ObjPt.erase(std::remove_if(m_ObjPt.begin(), m_ObjPt.end(), std::not1(std::mem_fn(&C_ObjProcess::hasObject))), m_ObjPt.end());
と,削除自体は一行になります。

もちろん,このままではメモリリークが発生するため,std::shared_ptrを使うのでしょうが,
std::shared_ptr使うとnot1とmem_fnの組み合わせがそのままでは使えなくなるので,ラムダ式を使って,

コード:

m_ObjPt.erase(std::remove_if(m_ObjPt.begin(), m_ObjPt.end(), [] (const std::shared_ptr<C_ObjProcess> & p) { return !p->hasObject(); }), m_ObjPt.end());
のようになりますが。
高度すぎて理解できませんでした///
参考にする前に解読したいと思いますw

閉鎖

“C言語何でも質問掲示板” へ戻る