STLコンフィギュレータとコンテナ、シーケンスコンテナと関連コンテナのまとめ

STLには多くのコンテナタイプが定義されており、これらのタイプはC++で非常に実用的である.しかし、多くの人はなぜコンフィギュレーションとコンテナを呼ぶのか理解していません.以下にまとめます.

シーケンスコンテナ:配列、vector、list、deque、stack、queue、heap、priority-queue.これらのタイプはvalueとして格納され,排出の論理的に線形構造である.ここで、stack、queueはコンフィギュレーションです.なぜコンテナではなくコンフィギュレーションと呼ぶのでしょうか.コンフィギュレーションの意味:ある物のインタフェースを修正して、別の風貌を形成して、adapter(コンフィギュレーション)と呼ばれます.これは私たちがソースコードに深く入り込んで一つ一つ分析する必要があります. 

vector:コードは連続したメモリとして実現され、動的拡張arrayと理解され、ランダムアクセスの特性を有する.ただし、頻繁なランダム挿入、削除には適していません.

list:コードは双方向チェーンテーブル構造に実現され、頻繁にランダムに挿入、削除する操作に適している.

deque:双方向操作キューで、コード実装が複雑です.1つのmapテーブル(STLではなくポインタ配列に似ている)を使用して、ブロックマッピングとして使用され、各アドレスは連続メモリを指し、各連続メモリサイズは同じである.deque内部は反復器startを介してfinishはそれぞれ最初のブロックと最後のブロックを指す.

stack:スタックの特性は一方向操作であり、同じ入口、出口、FILOである.STLでは,dequeは双方向操作の機能を有するため,stackのセットを単独で実現する必要はない.Dequeに基づいて一端を閉じる操作だけでstackの特性を備えている.したがって、stackはadapterです.

queue:キューの特性はFIFOで、一端は一端に出ます.同様にdequeに基づいて,一端のInputと他端のOutputをそれぞれ閉じることで,queueの特性を備えている.だからqueueもadapterです.

heap:アルゴリズムとして提示されます.実装されたのはスタックソートで、vectorが含まれています.

priority-queue:優先順位ソートを実現するためにheapが含まれています.

実際にqueue,stackの下位実装はdequeと同じであることがわかる.セグメントの定量的連続空間からなる.

関連コンテナ:set、map、multiset、multimap、hashtable、hash_map、hash_set、hash_multiset、hash_multimap.これらのタイプはkey-valueとして格納され、keyは一意であり、容器内部にはkeyに基づいてRB-Tree、またはHashテーブルが構築される.keyによってvalueを位置決めします.

(1)mapとsetの挿入削除効率が他のシーケンスコンテナより高いのはなぜですか.
ほとんどの人は、関連コンテナにとってメモリコピーやメモリ移動を行う必要がないため、簡単だと言っています.そうだ、確かにそうだ.setコンテナ内のすべての要素はノードで格納され、ノード構造とチェーンテーブルの差が少なく、親ノードとサブノードを指します.構造図は次のようになります.
　　A
　  /\
　 B C
　/\/\
  D E F G
だから挿入するときは少しだけ変換して、ノードのポインタを新しいノードに向けるだけでいいのです.削除するときと同様に、少し変換して削除ノードへのポインタを他のノードに向けてもOKです.ここでのすべての操作はポインタを交換することであり、メモリの移動とは関係ありません.
(2)なぜinsertのたびに以前保存したiteratorが無効にならないのか.
iteratorここではノードを指すポインタに相当しますが、メモリは変わっていません.メモリを指すポインタはどのように失効しますか(もちろん削除された要素自体は失効しています).vectorに対して、削除と挿入のたびにポインタが無効になる可能性があります.push_を呼び出します.backが末尾に挿入されるのもそうです.内部データの連続保存を保証するために、iteratorが指すブロック内に削除と挿入中に他のメモリで上書きされたか、メモリが解放された可能性があるからです.場合でもpush_backの場合、コンテナの内部空間が足りない可能性があります.新しいメモリが必要です.以前のメモリを解放し、新しいメモリを申請し、既存のデータ要素を新しいメモリにコピーし、最後に挿入する必要がある要素を最後に置くだけで、以前のメモリポインタは自然に使用できません.特にfindなどのアルゴリズムと一緒に使用する場合は、期限切れのiteratorを使用しないことを覚えておきましょう.
したがって、set、map、listの場合、クライアントがエレメントinsert、delete操作を行う場合、操作前の反復器は、操作完了後も有効である(削除されたエレメントを除く).しかしvectorの場合、iteratorが期限切れにならないことを保証する必要があります.
(3)データ要素が多くなるとsetの挿入と検索速度はどうなるのか.
set/mapについては、STLの最下位のRB-Treeを呼び出して実現されています.RB-Treeについては、挿入、削除効率が高いことがわかります.logn.したがって、多くの要素のシーンにも適用されます.多くのファイルシステム、分散スケジューリングは、赤黒ツリーの検索プロパティを利用してインデックスまたはノード情報を格納します.
Set要素は変更できませんか?
Setは集合として格納される要素は1つの値しかなく,valueはkeyであり,keyもvalueである.一般的に、Setの値は読み取り専用であり、変更はできません.しかし必ずしもそうではない.SGI STLのバージョンに基づいて、具体的な分析が必要です.
筆者が使っているバージョンは、反復器で値を変更することができます.

	ite1 = iset.find(23);
	if (ite1 != iset.end())
	{
		cout << "23 found" <

コンパイルは正常に実行されました.その後setソースコードをめくることで、反復器の定義が異なるバージョンが見つかりました.iteratorをconstとして定義しているだけです.iteratorタイプのバージョンでは、Set要素の変更は許可されません.

template,
	class _A = allocator<_k> >
	class set {
public:
	typedef set<_k _pr="" _a=""> _Myt;
	typedef _K value_type;
	struct _Kfn : public unary_function {
		const _K& operator()(const value_type& _X) const
		{return (_X); }
		};
	typedef _Pr value_compare;
	typedef _K key_type;
	typedef _Pr key_compare;
	typedef _A allocator_type;
	typedef _Tree<_k value_type="" _kfn="" _pr="" _a=""> _Imp;
	typedef _Imp::size_type size_type;
	typedef _Imp::difference_type difference_type;
	typedef _Imp::reference reference;
	typedef _Imp::const_reference const_reference;
	typedef _Imp::iterator iterator;
	typedef _Imp::const_iterator const_iterator;
};

だから、反復器を使うときは、読み取り専用と判断したらconst_を直接使うことをお勧めします.iterator、最も保険です.