Why isn't vector<bool> a STL container?

c++ vector stl containers bitvector
P0W picture P0W · Jul 22, 2013 · Viewed 48.5k times · Source

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 bools.

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?

Answer

Mark B picture Mark B · Jul 22, 2013

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.

Related questions

What's the benefit of std::back_inserter over std::inserter?

As far as I can tell, anywhere std::back_inserter works in an STL algorithm, you could pass an std::inserter constructed with .end() instead: std::copy(l.begin(), l.end(), std::back_inserter(dest_list)); std::copy(l.begin(), …

Read More
What is the easiest way to initialize a std::vector with hardcoded elements?

I can create an array and initialize it like this: int a[] = {10, 20, 30}; How do I create a std::vector and initialize it similarly elegant? The best way I know is: std::vector<int> ints; ints.push_back(10); ints.…

Read More
How do I erase an element from std::vector<> by index?

I have a std::vector<int>, and I want to delete the n'th element. How do I do that? std::vector<int> vec; vec.push_back(6); vec.push_back(-17); vec.push_back(12); vec.erase(???);

Read More