4.2 コンテナの選択

既定の標準 C++ ライブラリの 10 個のコンテナのうち、特定の問題の解決に最適なコンテナの型を選択する場合、解決方法が明白なこともありますが、いくつか選択肢がある場合もあります。判断が難しい場合には、さまざまなコンテナを使用して実際の実行時間を比較し、最適な選択肢を見つけるような場合もあります。ほとんどの場合は、以下の単純な条件が判断に役立ちます。

値へはどのようにアクセスするか。
ランダムアクセスが重要な場合は、vector または deque を使用します。連続アクセスが必要な場合は、他のいずれかの構造が適しています。

コレクションで値が維持される順序は重要か。
値の順序を決める方法は多数あります。コンテナの寿命を通して厳密な順序付けが重要な場合は、セットへ挿入したものを自動的に挿入順に配置する set のデータ構造は、明白に適した選択です。
たとえば、多数を一度に挿入するときの最後の 1 つのように、順序の1 か所だけが重要な場合、値を list または vector に配置し、結果として生じる構造を適切な時点でソートする方法が最も簡単です。
構造に値が保持される順序が、挿入される順序と関連付けられている場合、stack、queue、list が最適な選択肢です。

構造体のサイズは実行中に大きく変化するか。
変化する場合、list または set が最適な選択肢です。要素がコレクションから削除された後も、vector や deque は大きなバッファを維持し続けます。逆に、コレクションのサイズが相対的に一定の場合、同じ数の要素を保持している list や set よりも、vector や deque が使用するメモリーの方が小さいということになります。

コレクションのサイズを推定することは可能か。
vector データ構造は、reserve() メンバー関数を使用して、指定されたサイズのメモリーのブロックを事前に割り当てる方法を提供します。この機能は、他のコンテナでは提供されません。

値がコレクションに含まれているかどうかを確認するテストを頻繁に行うか。
頻繁に行う場合は、set コンテナまたは map コンテナが最適な選択肢です。set または map に値が含まれているかどうかを確認するためのテストは、コンテナのサイズの対数という、非常に簡単な手順で実行することができます。一方、他の型のコレクションに値が含まれるかどうかを確認するテストでは、値とコンテナに格納されている各要素との比較が要求されます。

コレクションにはインデックスが付けられているか。つまり、コレクションをキーと値の組み合わせとして表示することは可能か。
キーが 0 と上限値の間の整数である場合、vector または deque を使用する必要があります。一方、キー値が文字、文字列、またはユーザー定義の型など、他の順序付きデータ型の場合は、map コンテナを使用することができます。

値を相互に関連付けることは可能か。
標準 C++ ライブラリで提供されるコンテナに格納されている値はすべて、他の同種の値と同値であるかどうかをテストできる必要がありますが、すべての値が小なり演算子 <を認識できるようにする必要はありません。ただし、左不等演算子を使用して順序付けを行うことができない値は、set または map に格納することができます。

コレクションから頻繁に、最大値を検出したり削除したりするか。
頻繁に行う場合、priority queue が最適なデータ構造です。

値は構造のどこへ挿入または削除されるか。
値を中間に挿入したり、削除したりする場合は、list が最適な選択肢です。値を先頭だけに挿入する場合、deque または list が適しています。値を末尾だけに挿入したり、削除したりする場合は、stack または queue が論理的な選択肢です。

2 つ以上のシーケンスを 1 つのシーケンスにマージする操作を頻繁に行うか。
頻繁に行う場合、コレクションが順序通りに維持されているかどうかによって、set または list が最適な選択肢となります。2 つのセットのマージは非常に効果的な操作です。コレクションが順序付けられいなくても、クラスリストから有効な splice() メンバー関数を使用できる場合、この操作は他のコンテナでは利用できないため、リストのデータ型が適しています。

*値へはどのようにアクセスするか。*	ランダムアクセスが重要な場合は、*vector* または *deque* を使用します。連続アクセスが必要な場合は、他のいずれかの構造が適しています。
*コレクションで値が維持される順序は重要か。*	値の順序を決める方法は多数あります。コンテナの寿命を通して厳密な順序付けが重要な場合は、セットへ挿入したものを自動的に挿入順に配置する *set* のデータ構造は、明白に適した選択です。たとえば、多数を一度に挿入するときの最後の 1 つのように、順序の1 か所だけが重要な場合、値を *list* または *vector* に配置し、結果として生じる構造を適切な時点でソートする方法が最も簡単です。構造に値が保持される順序が、挿入される順序と関連付けられている場合、*stack、queue、list* が最適な選択肢です。
*構造体のサイズは実行中に大きく変化するか。*	変化する場合、*list* または *set* が最適な選択肢です。要素がコレクションから削除された後も、*vector* や *deque* は大きなバッファを維持し続けます。逆に、コレクションのサイズが相対的に一定の場合、同じ数の要素を保持している list や set よりも、vector や deque が使用するメモリーの方が小さいということになります。
*コレクションのサイズを推定することは可能か。*	*vector* データ構造は、`reserve()` メンバー関数を使用して、指定されたサイズのメモリーのブロックを事前に割り当てる方法を提供します。この機能は、他のコンテナでは提供されません。
*値がコレクションに含まれているかどうかを確認するテストを頻繁に行うか。*	頻繁に行う場合は、*set* コンテナまたは *map* コンテナが最適な選択肢です。set または map に値が含まれているかどうかを確認するためのテストは、コンテナのサイズの対数という、非常に簡単な手順で実行することができます。一方、他の型のコレクションに値が含まれるかどうかを確認するテストでは、値とコンテナに格納されている各要素との比較が要求されます。
*コレクションにはインデックスが付けられているか。つまり、コレクションをキーと値の組み合わせとして表示することは可能か。*	キーが 0 と上限値の間の整数である場合、*vector* または *deque* を使用する必要があります。一方、キー値が文字、文字列、またはユーザー定義の型など、他の順序付きデータ型の場合は、*map* コンテナを使用することができます。
*値を相互に関連付けることは可能か。*	標準 C++ ライブラリで提供されるコンテナに格納されている値はすべて、他の同種の値と同値であるかどうかをテストできる必要がありますが、すべての値が小なり演算子 `<`を認識できるようにする必要はありません。ただし、左不等演算子を使用して順序付けを行うことができない値は、*set* または *map* に格納することができます。
*コレクションから頻繁に、最大値を検出したり削除したりするか。*	頻繁に行う場合、*priority queue* が最適なデータ構造です。
*値は構造のどこへ挿入または削除されるか。*	値を中間に挿入したり、削除したりする場合は、*list* が最適な選択肢です。値を先頭だけに挿入する場合、*deque* または *list* が適しています。値を末尾だけに挿入したり、削除したりする場合は、*stack* または *queue* が論理的な選択肢です。
*2 つ以上のシーケンスを 1 つのシーケンスにマージする操作を頻繁に行うか。*	頻繁に行う場合、コレクションが順序通りに維持されているかどうかによって、*set* または *list* が最適な選択肢となります。2 つのセットのマージは非常に効果的な操作です。コレクションが順序付けられいなくても、クラスリストから有効な `splice()` メンバー関数を使用できる場合、この操作は他のコンテナでは利用できないため、リストのデータ型が適しています。