STL反復器(二)反復器の失効状況分析

文書ディレクトリ

前言

1.連続空間式記憶vectordeque

2.チェーンテーブルストレージlist

三.赤黒ツリーストレージmap set

前言

反復器の失効の問題は具体的な状況の具体的な分析が必要です:最も重要なのは容器のメモリの中の記憶方式を分析して、操作を行った後に全体の空間が再分配されたかどうか、あるいはどの空間が失効したかを判断します.
次に、3つの異なるメモリストレージ方式における反復器の失効状況を分析する.連続メモリ空間式メモリ2.チェーンテーブル式記憶3.ブラックツリーストレージ(最下位はチェーンテーブルストレージ)

一.れんぞくくうかんしききおくvectordeque

まずvectorはシーケンスコンテナであり,連続記憶空間であることを理解し,1つの空間が使用できなくなった場合,ブロック全体を再割り当てする必要がある.ではvectorではeraseがpos位置の要素を落とす限り、>=posの反復器、ポインタ、参照が失効し、
さらにpush_back,空間が再割り当てされた場合,すべての反復器が無効になり,再割り当てがなければすべて有効になる
同様にdequeはvectorメモリストレージと同様に、あまり説明されません.

void test1() {
	vector<int> vec{ 1,2,3,4,5 };
	vec.reserve(10);
	auto beg = vec.begin();
	auto end = --vec.end();


#if 0 //erase
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it == 3) {
			vec.erase(it);
			break;
		}
	}
#endif

#if 1 //push_back
	vec.push_back(6);

#endif
	cout << *beg << endl;
	cout << *end << endl;
}

二.チェーンテーブルストレージlist

listメモリに格納されているのは双方向チェーンテーブル構造であるため、eraseが無効になったのは削除要素へのポインタ、push_backは反復器を無効にしません.双方向チェーンテーブルの原理を組み合わせると、理解しにくくありません.

void test2() {
	list<int> vec{ 1,2,3,4,5 };
	auto beg = vec.begin();
	auto end = --vec.end();


#if 1 //erase
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it == 3) {
			vec.erase(it);
			break;
		}
	}
#endif

#if 0 //push_back
	vec.push_back(6);

#endif
	cout << *beg << endl;
	cout << *end << endl;
}

三.赤黒ツリーストレージmap set

この2つのコンテナの下部原理は赤黒ツリー(実質的な下部かポインタか)であるため、erase操作が発生すると、削除された要素の反復器だけが無効になります.Insert操作時に反復器は無効になりません

void test3() {
	set<int> vec{ 1,2,3,4,5 };
	auto beg = vec.begin();
	auto end = --vec.end();


#if 0 //erase
	for (auto it = vec.begin(); it != vec.end(); it++) {
		if (*it == 3) {
			vec.erase(it);
			break;
		}
	}
#endif

#if 1 //insert
	vec.insert(6);

#endif
	cout << *beg << endl;
	cout << *end << endl;
}