C++STL解説 part01 コンテナ

C++STL解説

コンテナ †

コンテナとはその名の通り”入れ物”です。データを入れておくためのクラスですね。
コンテナには次のような分類と種類があります。
それぞれに特徴があり、向いている処理・向いていない処理があります。

• シークエンスコンテナ

  • vector
    動的配列。ランダムアクセス可能。特に他のコンテナを使う必要がなければこれを使えばいいでしょう。

  • deque
    双方向キュー。ランダムアクセス可能。先頭と末尾への要素の入出が高速。

  • list
    双方向リスト。双方向シーケンシャルアクセス可能。要素の挿入・削除（リスト演算）が高速。

  • string
    文字列。ランダムアクセス可能。文字列に特化したコンテナで多数の文字列操作演算が用意されている。

• 連想コンテナ

  • set
    集合。探索が高速。重複する値は扱えない。（set内には同じ値を入れることができない）

  • multiset
    値の重複が可能なset。

  • map
    連想配列（辞書とも言う）。”キー”と”値”のペアを管理する。探索が高速。重複するペアは扱えない。

  • multimap
    ペアの重複が可能なmap。

この時点で各コンテナの説明が理解できなくても気にしないでください。
これから１つずつ詳細に説明していきます。

要素の要件 †

コンテナに入れられるオブジェクトは次の決まりを守ったもの出なければなりません。

1. コピーコンストラクタ又はコピー代入演算子でコピーが可能。
2. 上記のコピー演算中に例外を投げてはならない。
3. コピー後、オリジナルとコピーは等値比較で等しくなければならない。

まず１．ですが、コンテナにオブジェクトが入れられるとき、そのオブジェクトのコピーがコンテナに入れられます。そのためコピーコンストラクタが必要になります。
また、各コンテナの操作又はアルゴリズムの適応時には要素のコピー代入が行われることがあります。そのためコピー代入演算子が必要になります。

次に２．です。例えばA,Bはそれぞれ１０個の要素が入っているコンテナとします。
Aの要素をすべてBにコピーしようとしたとき、４個目までの要素のコピーに成功して５個目の要素のコピー中に例外が投げられてしまうと、Bの４個目まではAのコピー、６個目以降は元のBのままという中途半端な状態になってしまいます。（Bの５個目の要素の状態はコピーのどの段階で例外が発生したかによります。）

#ref(): File not found: "copy_failure.jpg" at page "C++STL解説 part01 コンテナ"

最後に３．。オブジェクトのコピー後にオリジナルとコピーが等しくない場合、さまざまなコンテナ操作やアルゴリズムの適応に支障が生じます。
例えばalgorithmヘッダ内のsort関数は通常クイックソートで実装されており、クイックソートでは初めにピボット要素のコピーが行われます。
もしそのときオリジナルとコピーが等しくなければソートはめちゃくちゃになるでしょう。

結構面倒だと思ったでしょうか？でも安心してください。組み込み型（intやdoubleのようなC++に最初から用意されている型）は１〜３をすべて満たします。
自分でクラスを作ってそれをコンテナに入れようとしている人はそのクラスが１〜３の要件を満たすかどうかを確認してください。