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
- コンテナではないのでイテレータを持たない
- all 命令が無い
という欠点は健在です。
そして動的に処理するなら必須だと思われるのに、
- dynamic_bitset には insert 的な命令が無い
- push_backならある
という欠点もあります。
あとは、
- 標準ライブラリではない
- dynamic_bitset には現在メンテナがいない
という問題もあります。
もちろんケースによってはこれで十分な場合はあるでしょうし、こちらの方が適している場合もあるでしょうが、一般的に vector
そうなると、やはり「大量のビットを格納したいけれどもメモリを無駄にしたくない」という状況では、vector
vector
Effective STL 第18項でも、
vector
Effective STL p77 第18項がSTLのコンテナとして悪い点は2つしかない。第1に、STLのコンテナではない。第2に、bool型の値が格納されない。この2つを除けば、異議を唱える理由はない。
と言っています。
つまり、この2つの欠点を理解して使う分には全然構わないということです*3。
もちろん vector
本来であれば、これは vector の特殊化ではなく、vector_bool といった名前の、全く別のクラスで作るべきでした。
そうすれば、vector
しかし vector
vector
ということでみんな、vector
*1:メモリを無駄にしたくないので、まず std::deque
*2:C++03 バージョンのみ。C++11 では all 関数は存在する
*3:ただ、この項のタイトルが「vector
*4:これは、欠点を理解して代わりに bitset や dynamic_bitset 等の実装を使ったところで、他人が vector