Why isn't vector<bool> a STL container?
bitvector, c++, containers, stl, vector
Solution
For space-optimization reasons, the C++ standard (as far back as C++98) explicitly calls out `vector<bool>` as a special standard container where each bool uses only one bit of space rather than one byte as a normal bool would (implementing a kind of "dynamic bitset"). In exchange for this optimization it doesn't offer all the capabilities and interface of a normal standard container.
In this case, since you can't take the address of a bit within a byte, things such as `operator[]` can't return a `bool&` but instead return a proxy object that allows to manipulate the particular bit in question. Since this proxy object is not a `bool&`, you can't assign its address to a `bool*` like you could with the result of such an operator call on a "normal" container. In turn this means that `bool *pb =&v[0];` isn't valid code.
On the other hand `deque` doesn't have any such specialization called out so each bool takes a byte and you can take the address of the value return from `operator[]`.
Finally note that the MS standard library implementation is (arguably) suboptimal in that it uses a small chunk size for deques, which means that using deque as a substitute isn't always the right answer.
Problem
Item 18 of Scott Meyers's book Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library says to avoid `vector <bool>` as it's not an STL container and it doesn't really hold `bool`s. The following code: ``` vector <bool> v; bool *pb =&v[0]; ``` will not compile, violating a requirement of STL containers. Error: ``` cannot convert 'std::vector<bool>::reference* {aka std::_Bit_reference*}' to 'bool*' in initialization ``` `vector<T>::operator []` return type is supposed to be `T&`, but why is it a special case for `vector<bool>`? What does `vector<bool>` really consist of? The Item further says: ``` deque<bool> v; // is a STL container and it really contains bools ``` Can this be used as an alternative to `vector<bool>`? Can anyone please explain this?