The std::vector<bool> specialization has a flip() member function that inverts all values.

Detailed description Link to heading

If std::vector<bool> allocated a bool array to store the values, its size in bits would be N * sizeof(bool) * CHAR_BIT (and thus at least N * CHAR_BIT), because sizeof(bool) >= 1 despite the fact that a boolean value can be encoded in a single bit. However, the standard allows implementations to apply special optimizations to the std::vector<bool> specialization. For example, an implementation might store each bool value in a single bit.

Even though sizeof(bool) will most likely be 1, the standard doesn’t require that: it only guarantees sizeof(bool) >= 1. The standard explicitly mentions this. By default sizeof(bool) is 4 when compiling for Darwin/PowerPC, and there is a dedicated GCC flag -mone-byte-bool that makes sizeof(bool) == 1. On MSVC 4.2 bool was just a typedef for int.

To implement this optimization, an implementation can allocate an array of some integer values that the CPU is more comfortable working with (for example, unsigned long) and then manipulate individual bits using bitwise operations.

If we need to invert all stored values, a simple pass over all elements and flipping each one is far from the most optimal solution, because extracting each bit from the underlying unsigned long requires several bitwise operations, and then additional ones to write the new value. A more efficient approach suggests itself: invert the whole unsigned long at once. This way, instead of iterating over all elements and flipping each one, we iterate over all stored unsigned long words and invert each one, thus inverting CHAR_BIT * sizeof(unsigned long) consecutive bits of our vector. To support such optimized behavior, and also to make the std::vector<bool> interface overlap more with std::bitset, the flip() member function was added.

Of course, flip() only makes sense for the std::vector<bool> specialization, so other std::vector<T> instantiations don’t provide this member function.

Example Link to heading

#include <cassert>
#include <vector>

int main() {
    std::vector v{true, false};
    v.flip();
    assert((v == std::vector{false, true}));
}