C++メモ(2):STL容器vector,list,deque,map,set,hashmap

STL容器vector、list、deque、map、set、hashmap
(1)vectorベクトル
1つの配列に相当し、連続したメモリ領域を占有します.

の利点:

は配列サイズを指定しなくてもよい.すなわち、配列のように動作することができ、主にpush_back()およびpop_back()に現れる動的長さを有する.

ランダムアクセスが便利です.下付きオペレータ[]と.at();

省スペース.各位置には値オブジェクトのみが保存され、他の内容(ポインタなど)はありません.

欠点:

内部の挿入と削除の操作効率は低い.この位置に続く一連のコンテンツの移動に関連する可能性がある.

はvectorの最後にpushとpopの操作しかできず、vectorの頭部でpushとpopの操作はできない.

動的に追加されたデータがvectorが現在割り当てている容量capacityを超えた場合、より大きなメモリを再申請し、vectorの内容を新しいメモリにコピーし、元のメモリを解放する必要があります.

適用シーン:効率的なランダムアクセスが必要で、挿入/削除の効率を気にしない場合、または挿入/削除の操作が極めて少ない場合、vectorを使用できます.

(2)list双方向チェーンテーブル
Listの各ノードはvalue、1つの前駆ポインタ、および1つの後方駆動ポインタから構成されます.

の利点:

は連続メモリを使用する必要はありません.

は内部で便利な挿入と削除操作を行うことができる.

は、両端でpushおよびpopを行うことができる.

欠点:

はランダムアクセスをサポートしない、すなわち、下付きオペレータ[]とをサポートしない.at();

はvectorに対してより多くのメモリを消費します.前駆ポインタと後駆動ポインタが多くなったからです.

適用シーン:大量の挿入と削除操作が必要な場合は、ランダムアクセスを気にせずlistを使用します.

(3)deque両端キュー
Dequeは連続メモリの仮想化をもたらします.dequeは一連の連続メモリで構成されており、1つではありません.メモリの末端に行くと、自動的に次のセグメントにジャンプするので、反復器++操作をサポートします.dequeはvectorとlistを機能的に統合した.

の利点:

はランダムアクセスをサポートします.すなわち、下付きオペレータ[]とをサポートする.at();

は内部で便利な挿入と削除操作を行うことができる.

は、両端でpushおよびpopを行うことができる.

欠点:

は、より多くのメモリを消費します.

適用シーン:ランダムアクセスも内部の挿入と削除操作も必要な場合はdequeを使用します.

(4)map/multimap一対一関連
内部は赤黒ツリーとして実装され、格納された内容はkey-valueペアであり、各keyが1つのvalueにのみ対応する場合mapを使用し、複数のvalueに対応する場合multimapを使用する.

の利点:

は自動ソート機能を有し、key値に基づいてソートする.

vectorよりも挿入と削除は速いがlistより遅い.

は、次のテーブルオペレータ[]を使用してデータを取得できます(multimapではサポートされていません).

欠点:

値を挿入するたびに、赤と黒の木を調整する必要があります.

ランダムアクセスはvectorよりlistより遅く、検索の複雑度はO(l o g(n))O(log(n))O(log(n))である.

適用シーン:データ辞書を格納する必要があり、keyに基づいてvalueを簡単に見つける必要がある場合はmapを1対1で使用し、1対多の場合はmultimapを使用します.

(5)set/multisetセット
同じ要素の場合、setは1回しか保存されません.setには重複する要素は含まれませんが、multisetには重複する要素が含まれているため、複数回保存されます.

の利点:

は検索しやすいです.set内部は赤黒ツリーで実現され、自動的にソートされます.

適用シーン:要素が1つのセットに存在するかどうかを検索する必要がある場合は、setが一意に存在し、multisetが一意に存在しない.

(6)hashmapハッシュリスト
キー値をhashテーブルの1つの場所にマッピングすることによって格納およびアクセスします.要素の配列は無秩序です.このようなデータ構造は、挿入、削除、検索などの操作において通常「定数時間」の表現を有する.

の利点:

は検索効率が高く,検索時間の複雑さはO(1)O(1)O(1)であった.通常、mapよりも検索速度が速い(mapの検索時間はO(l o g(n))O(log(n))O(log(n))O(log(n))である.もちろん定数は必ずしもlog(n)より小さいとは限らずhash関数の消費も考慮する必要がある.

欠点:

は、より多くのメモリを消費する必要があります.

構造速度が遅い.

hash衝突が発生する可能性があります.(解決構想:チェーンアドレス法、オープンアドレス法)

適用シーン:検索効率が高く、要素が一定のレベルに達し、メモリの使用量にあまり関心がない場合はhashmapを使用します.