コンテナと値型・ポインタ型

（これは2010-11-14に書いた故OCNブログの記事を移植したものです）

STL コンテナ クラス テンプレート（std::vector, std::list など）や MFC/ATL コレクション クラス テンプレート（CArray / CAtlArray, CList / CAtlList）のテンプレート引数に、値型をつかうかポインタ型を使うか迷ったことはありませんか？

もちろんポリモーフィズムを使うときは当然ポインタ型を使うしかないわけですが、例えば、int や double などのプリミティブ型のほか、以下のような比較的小さい構造体 Vector3F を引数にするときは、迷わずテンプレート引数に値型を選ぶと思います。

struct Vector3F
{
  float x, y, z;
};

class Polyline
{
public:
  std::wstring Name;
public:
  std::vector<Vector3F> PositionsArray;
  //std::vector<Vector3F*> PositionPtrsArray; // こちらは要素の寿命管理が面倒なので普通やらない。
};

std::vector は連続性が保証されているので、テンプレート引数を値型にしておけば、コンテナを通常の Vector3F の生配列として扱うこともできるし、何より値型を使うことで煩わしい new/delete を自前で記述する必要が無くなります。値型をうまく使うとデータ参照の局所性が向上することで効率も良くなります。

ですが、上記 Polyline のようなディープコピーのコストが比較的高くつくクラスをコンテナにぶち込む場合（たとえば std::vector<Polyline> など）はどうでしょうか？

Name フィールド、PositionsArray フィールドはともに可変長なので、もし長大なデータを格納していた場合、代入演算子 std::vector<Polyline>::operator=() やコピーコンストラクタによるコピーは完全なディープコピーとなって、かなり高コストになります。
これはいわゆる配列の配列＝ジャグ配列（たとえば std::vector<std::vector<double>> など）にも言えることです。

特に配列コンテナをソートする場合は、要素のスワップ（交換、移動）の際に代入演算子による要素のコピーが行なわれるはずなので、ジャグ配列の要素が頻繁にコピーされる場合はすさまじいパフォーマンス低下が見込まれます（ちなみにコンテナに入れる型は、代入演算子とコピーコンストラクタが呼び出せる＝public になっている必要がある）。

こういうときはポインタ型の配列 std::vector<std::shard_ptr<Polyline>> などとして、std::vector::operator=() によるコピーがハンドルのみのコピーとなるようにする手もあります。別に生ポインタの配列 std::vector<Polyline*> でも構わないんですが、寿命管理が煩雑になる（要素を削除するときは明示的にその要素を delete しないといけない）ので、パフォーマンス上どうしてもスマートポインタが使えない場合以外ではお勧めしません。

なお、C++11 (C++0x) のムーブコンストラクタが使える状況では、おそらくソート中のスワップ時にコピーコンストラクタではなくムーブコンストラクタが起動するので、テンプレート引数にスマートポインタでなく値型を使ったとしても、ソートのパフォーマンス面でのデメリットは低減できると思われます（むしろ値型を使うべき？）。

ちなみに、std::vector<T>::clear() を実行しても、予約された領域を解放するわけではない（配列の各要素に対してデストラクタ ~T() を呼び出すが、配列自体の領域を解放するわけではない）ので、上手く使えばメモリ断片化防止になりますが、下手をすれば無駄にメモリを食ったままの状況が続きかねません。なお、std::vector では内部で placement new が使用されていて、clear() 呼び出しによって各要素に対して明示的なデストラクタ呼び出しが実行されます。このため、std::vector<std::shard_ptr<T>>::clear() を実行すると、shared_ptr のデストラクタが実行され、参照カウントがきちんと減少するようになっている模様。なかなか良くできています（MSVC の実装で確認）。

ヒープの生成と破棄を下手に繰り返すと速度低下やメモリ断片化の要因になるので使いどころが難しいんですが、単純にメモリの無駄遣いを避けたければ、swap 技法などで不要な領域を解放するか、C++11 の std::vector::shrink_to_fit() を適宜使いましょう。

なお、コンテナ末尾への要素追加だけでなく、先頭への要素追加も頻繁に行なう場合は、std::vector でなく std::deque を使うと良い（領域の拡張が行なわれない限り、どちらの操作も定数時間で完了する）と言われているのですが、VC++ における実装の場合、std::vector に比べて std::deque の末尾要素追加は2倍以上の時間がかかるので、やはりよほどの理由がない限り std::vector の採用が一番無難なようです。

余談

ついでに言っておくと、MFC/ATL の CArray / CAtlArray, CList / CAtlList は STL と比べて機能性や操作性がかなり貧弱なので、これまたよほどの理由がない限り std::vector, std::list を採用したほうが良いです。ただ、VC++ の std::vector, std::list のデバッグ バージョンでは、オーバーラン チェックが入るために、速度性能が CAtlArray, CAtlList などのそれに比べて著しく劣る（ただし std::vector の実装を見る限り、_ITERATOR_DEBUG_LEVEL で制御できる模様）ので、STL への移行を検討している人達は注意しておいたほうが良いかもしれません。リリースビルドでは当然冗長なオーバーラン チェックは入りません。

なお、std::vector, std::list, std::map などの STL コンテナは、MFC/ATL のコレクションと違って、VC++ ビジュアル デバッガーでのコンテナ内部階層の要素表示が既定で可能になっているのも重要です。MFC/ATL コレクションで同じことをやろうとすると結構設定が面倒なんですが、これもまたいつか解説しようかな……

そういえば CRT の qsort() よりも std::sort() を使うほうがよい、とよく言われていますが（関数オブジェクトがインライン化される）、int×20,000要素の乱数をぶちこんだ動的配列に対して性能比較したら、確かにリリースビルドの場合で実際2倍くらいの差が出ました。これはかなり大きい。

あと STL は配列だろうがリストだろうが同じアルゴリズム関数テンプレートが適用できるのが強みです。後からコンテナの種類を変えたくなったときも、最初に互換性のある書き方をしておけば簡単にコンテナを入れ替えることができます（テンプレートによる静的ダックタイピング）。