How to zero a vector<bool>?

Question

I have a vector<bool> and I'd like to zero it out. I need the size to stay the same.

The normal approach is to iterate over all the elements and reset them. However, vector<bool> is a specially optimized container that, depending on implementation, may store only one bit per element. Is there a way to take advantage of this to clear the whole thing efficiently?

bitset, the fixed-length variant, has the set function. Does vector<bool> have something similar?

Answer 1

There seem to be a lot of guesses but very few facts in the answers that have been posted so far, so perhaps it would be worthwhile to do a little testing.

#include <vector>
#include <iostream>
#include <time.h>

int seed(std::vector<bool> &b) {
    srand(1);
    for (int i = 0; i < b.size(); i++)
        b[i] = ((rand() & 1) != 0);
    int count = 0;
    for (int i = 0; i < b.size(); i++)
    if (b[i])
        ++count;
    return count;
}

int main() {
    std::vector<bool> bools(1024 * 1024 * 32);

    int count1= seed(bools);
    clock_t start = clock();
    bools.assign(bools.size(), false);
    double using_assign = double(clock() - start) / CLOCKS_PER_SEC;

    int count2 = seed(bools);
    start = clock();
    for (int i = 0; i < bools.size(); i++)
        bools[i] = false;
    double using_loop = double(clock() - start) / CLOCKS_PER_SEC;

    int count3 = seed(bools);
    start = clock();
    size_t size = bools.size();
    bools.clear();
    bools.resize(size); 
    double using_clear = double(clock() - start) / CLOCKS_PER_SEC;

    int count4 = seed(bools);
    start = clock();
    std::fill(bools.begin(), bools.end(), false);
    double using_fill = double(clock() - start) / CLOCKS_PER_SEC;


    std::cout << "Time using assign: " << using_assign << "\n";
    std::cout << "Time using loop: " << using_loop << "\n";
    std::cout << "Time using clear: " << using_clear << "\n";
    std::cout << "Time using fill: " << using_fill << "\n";
    std::cout << "Ignore: " << count1 << "\t" << count2 << "\t" << count3 << "\t" << count4 << "\n";
}

So this creates a vector, sets some randomly selected bits in it, counts them, and clears them (and repeats). The setting/counting/printing is done to ensure that even with aggressive optimization, the compiler can't/won't optimize out our code to clear the vector.

I found the results interesting, to say the least. First the result with VC++:

Time using assign: 0.141
Time using loop: 0.068
Time using clear: 0.141
Time using fill: 0.087
Ignore: 16777216        16777216        16777216        16777216

So, with VC++, the fastest method is what you'd probably initially think of as the most naive -- a loop that assigns to each individual item. With g++, the results are just a tad different though:

Time using assign: 0.002
Time using loop: 0.08
Time using clear: 0.002
Time using fill: 0.001
Ignore: 16777216        16777216        16777216        16777216

Here, the loop is (by far) the slowest method (and the others are basically tied -- the 1 ms difference in speed isn't really repeatable).

For what it's worth, in spite of this part of the test showing up as much faster with g++, the overall times were within 1% of each other (4.944 seconds for VC++, 4.915 seconds for g++).