標準 C++ ライブラリは、プログラミングに関するほとんどの問題の解決に使用されるコンテナを提供します。しかし、これに含まれない古典的なコンテナの型も多数あります。ほとんどの場合、提供されるコンテナが、削除されたコンテナが提供してきた従来の用途に加え、より広範囲の用途に簡単に適用できるためです。表 7 は、ライブラリに含まれていないコンテナの型とその単純な代替例を示します。
表 7 -- 標準 C++ ライブラリにないコンテナの型
提供されないコンテナの型 | 標準 C++ ライブラリの代替 |
---|---|
ツリー |
set データ型は、2 等分探索木の形式を使用して内部的に実装されます。ツリーを使用して解決されるほとんどの問題で、set データ型が適切な代替となります。 |
多次元配列 |
vector は他の vector を要素として保持できるため、このような構造を簡単に作成することができます。 |
グラフ |
グラフの 1 つの表現は、他のマップを保持するマップとして簡単に作成することができます。この型の構造は、9.3.2 節で説明する問題の例として記述されています。 |
疎の配列 |
これは、9.3.2 節で説明するグラフ表現の特殊な代替です。 |
ハッシュテーブル |
ハッシュテーブルは、アクセスと解除の演算をインデックス付け演算に変換することによって、償却済みの一定時間のアクセスと、要素の挿入および削除を提供します。標準 C++ ライブラリでは、要素として list (または set さえも) を保持する vector (または deque) として、ハッシュテーブルを簡単に作成することができます。7.3 節 で説明する基数ソートに関する問題の例に、同様の構造が記述されています。ただし、この例には値をインデックスに変換するためのハッシュ関数の呼び出しは含まれていません。 |
一部の set 機能 |
標準 C++ ライブラリでは set データ型が特定の順序で並べられ、set 演算 (和集合、積集合、など) は、比較不可能な値のコレクション (たとえば、複素数) では実行できません。list を代替として使用することはできますが、汎用アルゴリズムを list と共に使用することはできないため、特別な set 演算関数を作成する必要があります。 |