vector の話

C++

vector は vector に対して特殊化されていて、領域を無駄にしないように、ビット単位で格納されるようになっています。
これは使用する領域が少なくなる反面、 &v[0]+i == &v[i] であるという、vector としての特徴の一つを満たさなくなってしまいます。
他にもいくつか、bool 以外の vector と異なる動作をする箇所があります。
そのため、Twitter や掲示板等で vector の話が出るたびに必ずといっていいほど「あれは使うな。失敗作だ」とか「あれはもう忘れろ」という趣旨の発言が見られます。


そういった場面に遭遇するたびに自分は微妙な気分になります。
実際のところ、「大量のビットを格納したいけれどもメモリを無駄にしたくない」という状況がある*1とき、vector 以外の選択肢はどの程度あるんでしょうか？


まず自分で作るという選択肢、これはほとんどの場合は論外でしょう。


次に std::bitset を使うという選択肢。これは、

  • N が定数でないといけないので使える状況が限られる
  • コンテナではないのでイテレータを持たない
  • any と none 関数はあるけれども、all 命令が無い*2
    • これは count() == size() で同じセマンティクスになるけれども、これだと必ず全要素を走査するので、平均して倍の速度差が出る

といった欠点があります（最後の問題は微々たるものですが）。ほとんどの場合は使うことにはならないでしょう。
ただ、動的に確保するのが許容できない場合にはこれを使うしかありません。


あとは boost::dynamic_bitset を使うという選択肢です。
これはよく「vector を使うな」という話題とセットで「代わりに boost::dynamic_bitset を使え」となることが多いのですが、boost::dynamic_bitset は std::bitset を動的にしてちょっと機能を加えているだけです。つまり、

  • コンテナではないのでイテレータを持たない
  • all 命令が無い

という欠点は健在です。
そして動的に処理するなら必須だと思われるのに、

  • dynamic_bitset には insert 的な命令が無い
    • push_backならある

という欠点もあります。
あとは、

  • 標準ライブラリではない
  • dynamic_bitset には現在メンテナがいない

という問題もあります。
もちろんケースによってはこれで十分な場合はあるでしょうし、こちらの方が適している場合もあるでしょうが、一般的に vector の代替になるかと言われると、まず無理です。


そうなると、やはり「大量のビットを格納したいけれどもメモリを無駄にしたくない」という状況では、vector が適している状況は結構多いのではないかと思います。
vector を使えば、vector とインターフェースが同じなので学習コストが非常に小さくなりますし、標準のアルゴリズム関数も使えます。
Effective STL 第18項でも、

vectorがSTLのコンテナとして悪い点は2つしかない。第1に、STLのコンテナではない。第2に、bool型の値が格納されない。この2つを除けば、異議を唱える理由はない。

Effective STL p77 第18項

と言っています。
つまり、この２つの欠点を理解して使う分には全然構わないということです*3。


もちろん vector が全て素晴らしいと言っている訳ではありません。
本来であれば、これは vector の特殊化ではなく、vector_bool といった名前の、全く別のクラスで作るべきでした。
そうすれば、vector の特殊化を知らなかった人が間違って使って誤爆してしまうようなことは無かったでしょう*4。
しかし vector は便利なのです。少なくとも bitset や dynamic_bitset といったライブラリで完全に代用できない程度には。
vector を全力で回避して苦労しつつ実装するより、vector の欠点を理解した上で使って実装した方が、多くの場合は楽になるでしょう。


ということでみんな、vector を dis るのはやめて、明日からどんどん使っていきましょう。

*1:メモリを無駄にしたくないので、まず std::deque や std::vector、std::vector といった選択肢は無くなります

*2:C++03 バージョンのみ。C++11 では all 関数は存在する

*3:ただ、この項のタイトルが「vectorは使わないようにしよう」となっているのはひどいと思います。きっと今の使うなと言われまくっているこの状況は、このタイトルによる影響も大きいでしょう。

*4:これは、欠点を理解して代わりに bitset や dynamic_bitset 等の実装を使ったところで、他人が vector を使ってしまうことが回避できるわけではないので、vector を使わない理由とは関係ありません