コンテナライブラリ - cppreference.com

コンテナライブラリは、キュー、リスト、スタックのような一般的なデータ構造をプログラマが簡単に実装することを可能とする汎用のクラステンプレートとアルゴリズムのコレクションです。 コンテナはシーケンスコンテナ、連想コンテナ、非順序連想コンテナの3種類に分類され、それぞれ違った操作をサポートするよう設計されています。

コンテナは要素のために確保した記憶域空間を管理し、それらに直接またはイテレータ (ポインタに似た性質のオブジェクト) を通してアクセスするためのメンバ関数を提供します。

ほとんどのコンテナは少なくともいくつかのメンバ関数を共通して持っており、機能性を共有しています。 特定のアプリケーションに対してどのコンテナがベストかはその提供される機能性だけではなく、異なるワークロードに対する効率性にもよります。

シーケンスコンテナ

シーケンスコンテナはシーケンシャルアクセスが可能なデータ構造を実装しています。

連想コンテナ

連想コンテナは高速に (O(log n) の計算量で) 検索可能なソート済みのデータ構造を実装しています。

非順序連想コンテナ

非順序連想コンテナは高速に (償却 O(1)、ワーストケースでは O(n) の計算量で) 検索可能なソートされていない (ハッシュされた) データ構造を実装しています。

コンテナアダプタ

コンテナアダプタはシーケンシャルコンテナに対して異なるインタフェースを提供します。

スパン

span はオブジェクトの隣接したシーケンスに対する非所有ビューです。 その記憶域は何らかの別のオブジェクトによって所有されます。

イテレータの無効化

読み取りのみのメンバ関数はイテレータや参照を無効化しません。 コンテナの内容を変更するメンバ関数は、以下の表に示すように、イテレータや参照を無効化する場合があります。

ここで、挿入はコンテナに1個以上の要素を追加するあらゆるメンバ関数を指し、削除はコンテナから1個以上の要素を削除するあらゆるメンバ関数を指します。

• 挿入関数の例としては std::set::insert、 std::map::emplace、 std::vector::push_back、 std::deque::push_front などがあります。
  • std::unordered_map::operator[] もマップに要素を挿入する場合があるため挿入関数に数えられます。

• 削除関数の例としては std::set::erase、 std::vector::pop_back、 std::deque::pop_front、 std::map::clear などがあります。
  • clear はすべてのイテレータと参照を無効化します。 すべての要素を削除するので、これも論理的には上記のルールに従います。

終端イテレータに関しては特に述べておく価値があります。 一般的にこのイテレータは、削除されない要素を指す普通のイテレータのように振る舞います。 そのため、 std::set::end は無効化されることは決してなく、 std::unordered_set::end は再ハッシュが発生した場合のみ無効化され、 std::vector::end は常に無効化される (変更された要素より常に後にあるので) といった感じです。

これにはひとつ例外があります。 std::deque の最後の要素の削除は終端イテレータを無効化します。 それがコンテナの削除された要素でなくとも (あるいは要素でさえなくとも) です。 std::deque のイテレータの一般的なルールと組み合わせると、 std::deque::end を無効化しない唯一の変更操作は、最初の要素を削除するもののみという結論になります。

メンバ関数表