std::vector<bool> : the exception to many rules
suggest changeThe 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 abool
array. at()
,operator []
, and dereferencing of iterators do not return a reference tobool
. Rather they return a proxy object that (imperfectly) simulates a reference to abool
by overloading its assignment operators. As an example, the following code may not be valid forstd::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.