vector<bool>

「vector< bool >は省メモリだけど遅い」と言われますが、どのぐらい遅いのか。検証します

検証条件

• vector< bool >で宣言した配列と、bool[]で宣言した配列それぞれについて、以下のコードを実行する

// 10^8回の代入
for(int i=0; i<10000; i++) {
    for(int j=0; j<10000; j++) {
        v[j] = (i%2);
    }
}

• 開始から終了までにかかった時間と、使用メモリ量を計測
  • 時間はclock()を使ってμs単位で計測(読みづらかったのでmsに換算)
  • 使用メモリ量はsizeof(v)を使用
  • 生成にかかる時間は対象外

検証結果

型	メモリ使用量[byte]	実行速度[ms](100回計測した平均値)
vector< bool >	24(※1)	1703.82
bool[]	10000	494.2

めっちゃ遅い(3.45倍ぐらい)

(※1 : vector< bool >をsizeof()すると実際のデータ格納領域は含まれないらしい
ただ、vector< bool >は1ビット単位で管理してると聞いた覚えもあるので、単純に考えると1/8ぐらいになってるのかも…？)

せっかくなので他にも検証

型	メモリ使用量[byte]	実行速度[ms](100回計測した平均値)
vector< bool >	24(※1)	1703.82
bool[]	10000	494.20
vector< bool >(iteratorでループ)	24(※1)	2729.79
bitset	1256	1424.48

結論：vector< bool >は遅い(確信)

ちなみにここまで遅いのはboolのときだけです。intとかなら結構マシ