ブール値のベクトルを使用すると、動的ビットセットよりも遅くなりますか? 質問する

ここで大きく左右されるのは、操作するブール値の数です。

bitset と はどちらも、vector<bool>通常、ブール値が 1 ビットのみとして格納されるパック表現を使用します。

一方では、単一の値にアクセスするためにビット操作という形でいくらかのオーバーヘッドが発生します。

一方、これは、より多くのブール値がキャッシュに収まることも意味します。

ブール値を多く使用している場合 (エラトステネスのふるいを実装する場合など)、キャッシュにブール値をさらに多く収めると、ほとんどの場合、最終的な利益が得られます。メモリ使用量の削減によって得られる利益は、ビット操作による損失よりもはるかに大きくなります。

反対意見のほとんどは、std::vector<bool>それが標準のコンテナではない (つまり、コンテナの要件を満たしていない) という事実に帰着します。私の意見では、これは主に期待の問題です。 と書かれているので、多くの人がそれがコンテナであると期待しており (他の種類のベクターはコンテナです)、 がコンテナではないvectorという事実に否定的な反応を示すことが多いのです。vector<bool>

ベクターを実際にコンテナーとして必要とする方法で使用している場合は、おそらく他の組み合わせを使用する必要があり、 または のいずれかでもdeque<bool>問題vector<char>なく動作します。考えるただし、そうする前に、vector<bool>一般的に避けるべきアドバイス（私の意見ではひどい）がたくさんありますが、なぜそれを避けるべきなのか、またはどのような状況でそれがあなたにとって本当に違いを生むのかについてはほとんど、またはまったく説明されていません。

はい、他の方法の方がうまくいく状況はあります。そのような状況に陥っている場合、他の方法を使用するのは明らかに良い考えです。しかし、まず、本当にそのような状況に陥っているかどうかを確認してください。vector<char>トレードオフについて十分な説明をせずに、「Herb は を使用するべきだと言っています」などと言う人は、信用すべきではありません。

実際の例を挙げてみましょう。コメントで言及されていたので、エラトステネスの篩について考えてみましょう。

#include <vector>
#include <iostream>
#include <iterator>
#include <chrono>

unsigned long primes = 0;

template <class bool_t>
unsigned long sieve(unsigned max) {
    std::vector<bool_t> sieve(max, false);
    sieve[0] = sieve[1] = true;

    for (int i = 2; i < max; i++) {
        if (!sieve[i]) {
            ++primes;
            for (int temp = 2 * i; temp < max; temp += i)
                sieve[temp] = true;
        }
    }
    return primes;
}

// Warning: auto return type will fail with older compilers
// Fine with g++ 5.1 and VC++ 2015 though.
//
template <class F>
auto timer(F f, int max) {
    auto start = std::chrono::high_resolution_clock::now();
    primes += f(max);
    auto stop = std::chrono::high_resolution_clock::now();

    return stop - start;
}

int main() {
    using namespace std::chrono;

    unsigned number = 100000000;

    auto using_bool = timer(sieve<bool>, number);
    auto using_char = timer(sieve<char>, number);

    std::cout << "ignore: " << primes << "\n";
    std::cout << "Time using bool: " << duration_cast<milliseconds>(using_bool).count() << "\n";
    std::cout << "Time using char: " << duration_cast<milliseconds>(using_char).count() << "\n";
}

ignore: 34568730
Time using bool: 2623
Time using char: 3108

ignore: 34568730
Time using bool: 2359
Time using char: 3116

ignore: 3987474
Time using bool: 72
Time using char: 249