std::vector<bool> : the exception to many rules

The standard (section 23.3.7) specifies that a specialization of vector<bool> is provided, which optimizes space by packing the bool values, so that each takes up only one bit. Since bits aren’t addressable in C++, this means that several requirements on vector are not placed on vector<bool>:

• The data stored is not required to be contiguous, so a vector<bool> can’t be passed to a C API which expects a bool array.
• at(), operator [], and dereferencing of iterators do not return a reference to bool. Rather they return a proxy object that (imperfectly) simulates a reference to a bool by overloading its assignment operators. As an example, the following code may not be valid for std::vector<bool>, because dereferencing an iterator does not return a reference:

std::vector<bool> v = {true, false};
for (auto &b: v) { } // error

Similarly, functions expecting a bool& argument cannot be used with the result of operator [] or at() applied to vector<bool>, or with the result of dereferencing its iterator:

void f(bool& b);
f(v[0]);             // error
f(*v.begin());       // error

The implementation of std::vector<bool> is dependent on both the compiler and architecture. The specialisation is implemented by packing n Booleans into the lowest addressable section of memory. Here, n is the size in bits of the lowest addressable memory. In most modern systems this is 1 byte or 8 bits. This means that one byte can store 8 Boolean values. This is an improvement over the traditional implementation where 1 Boolean value is stored in 1 byte of memory.

Note: The below example shows possible bit-wise values of individual bytes in a traditional vs. optimized vector<bool>. This will not always hold true in all architectures. It is, however, a good way of visualizing the optimization. In the below examples a byte is represented as [x, x, x, x, x, x, x, x].

Traditional std::vector<char> storing 8 Boolean values:

std::vector<char> trad_vect = {true, false, false, false, true, false, true, true};

Bitwise representation:

[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0], 
[0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,1], [0,0,0,0,0,0,0,1]

Specialized std::vector<bool> storing 8 Boolean values:

std::vector<bool> optimized_vect = {true, false, false, false, true, false, true, true};

Bitwise representation:

[1,0,0,0,1,0,1,1]

Notice in the above example, that in the traditional version of std::vector<bool>, 8 Boolean values take up 8 bytes of memory, whereas in the optimized version of std::vector<bool>, they only use 1 byte of memory. This is a significant improvement on memory usage. If you need to pass a vector<bool> to an C-style API, you may need to copy the values to an array, or find a better way to use the API, if memory and performance are at risk.