STLで一番最初に目にするのが、このvectorだと思います。
使い方が分かりやすく、「配列」と機能が非常に似ているため、
（そもそもvectorの中身は配列なのですが…）
使う機会は多々あると思います。

しかし、vectorにはいくつかの落とし穴があります。
それを紹介しようというのが今回の趣旨です。
考えてみれば当たり前のことなんですが、
知らない人のためになればと思います。

まず、std::vectorの内部実装はただの配列です。
vectorの特徴の一つに可変長がありますが、
その機能をつけるためのアプローチによって、
いくつかの弊害が発生します。

ところで、配列はデータが連続してメモリに確保されます。
例えば、配列の要素数が50ならば、
要素一つのデータ量×50個分の領域をメモリに確保し、
そのメモリの位置を基にして各要素にアクセスします。

vectorの中身は配列だといいましたが、
可変長配列ということは、サイズが定まっていませんから、
上のように連続した領域を確保するのは不可能です。
これはどうしているかというと、
まず、適当なサイズの領域を確保し、足らなくなったら、
新しくもっと大きな領域を確保し、そこにデータを移します。

つまり、vectorは拡張できる配列というよりは、
拡張できるように"みせかけている"配列ですね。

さて、このような仕様のどこに落とし穴があるのでしょうか。

まず、vectorでは中のデータが連続していなければならないので、
挿入・削除のたびに、その後ろ全部のデータの位置を置き換えます。
これには非常に時間がかかります。
特に、頻繁に追加・削除が行われる状況では、
ある程度の工夫を施さないと、とても時間がかかってしまいます。

加えて、データの位置が変わるということは、追加・削除する度に、
その後ろ、もしくはデータ全てを指すポインタ、イテレータは全て無効になります。
ですから、vectorの要素を指すポインタ、イテレータを使うときには要注意です。
別の要素を指したり、データの全移行が行われた場合には、
全く関係のないものを指したりするため危険です。

このように、vectorをサイズが可変の配列と捉えていると痛い目を見ます。
ランダムアクセスの恩恵を得るのは楽ではないのです。

うーん、こういうコラム的な日記を読めるので、このmixCはなかなか好きですね～　＾＾

私もvectorをよく使います。内部も配列だった、というのは始めて知りました。サイズを拡張するのに時間がかかることや、内部でアドレスが変わるってのは知っていましたが、内部も配列だったんですね・・・。確かに、配列なら[]でアクセスできますからね～。

いやいや、勉強になりました。

そんな時はpoolの出番？
http://www.kmonos.net/alang/boost/classes/pool.html

追加すると
・　配列のように添え字でアクセスすると例外が発生する可能性がある
・　使用する領域が大きくなる場合は内部領域を拡張しますが、使用する領域が小さくなっても一度拡大した内部領域は勝手に小さくならない。
・　vectorが特殊化されていて、他の時と挙動が違う。
というのも落とし穴として挙げられますね。

　ところで
＞挿入・削除のたびに、その後ろ全部のデータの位置を置き換えます
これに関しては普通の配列も同じですよね？

＞山崎さん
私も、コラムは好きです[e]140[/e]
むしろ、私は学ぶ身でありながら、
こういう風な日記が増えるといいなあ、
と思って書いた節があります。

＞Dixqさん
ほお、こんなものがあるんですね。
速度の問題はある程度解決できそうですね。
Boostはあまりよく知りませんが、
このpoolも次期の標準規格に搭載されるんですかね？

＞Justyさん
さすが、お詳しいですね[e]198[/e]
私なんかよりも、Justyさんのような熟練者にコラムを書いてもらいたいです。
＞＞挿入・削除のたびに、その後ろ全部のデータの位置を置き換えます
＞これに関しては普通の配列も同じですよね？
そうですね。vectorのデータが連続で置かれてることを知らないと、
挿入・削除でのリスクも知らない人がいるかな、
と思って書いた節がありますが、
落とし穴ってわけでもないですかね…。

＞コラム
　うーん、今の情勢だとちょっと難しいんですよね。
　ちょっと考えてみます。


＞挿入・削除でのリスク
　なるほど。知らない人からすれば落とし穴ということは出来ますね。


＞pool
　C++0xには含まれていなかったと思います。


※　ところで、pool(pool_alloc?)をどう使ってvectorの問題を解決するんでしょう……？