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

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?

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.

The problems is that vector<bool> returns a proxy reference object instead of a true reference, so that C++98 style code bool * p = &v[0]; won't compile. However, modern C++11 with auto p = &v[0]; can be made to compile if operator& also returns a proxy pointer object. Howard Hinnant has written a blog post detailing the algorithmic improvements when using such proxy references and pointers.

Scott Meyers has a long Item 30 in More Effective C++ about proxy classes. You can come a long way to almost mimic the builtin types: for any given type T, a pair of proxies (e.g. reference_proxy<T> and iterator_proxy<T>) can be made mutually consistent in the sense that reference_proxy<T>::operator&() and iterator_proxy<T>::operator*() are each other's inverse.

However, at some point one needs to map the proxy objects back to behave like T* or T&. For iterator proxies, one can overload operator->() and access the template T's interface without reimplementing all the functionality. However, for reference proxies, you would need to overload operator.(), and that is not allowed in current C++ (although Sebastian Redl presented such a proposal on BoostCon 2013). You can make a verbose work-around like a .get() member inside the reference proxy, or implement all of T's interface inside the reference (this is what is done for vector<bool>::bit_reference), but this will either lose the builtin syntax or introduce user-defined conversions that do not have builtin semantics for type conversions (you can have at most one user-defined conversion per argument).

TL;DR: no vector<bool> is not a container because the Standard requires a real reference, but it can be made to behave almost like a container, at least much closer with C++11 (auto) than in C++98.

vector<bool> contains boolean values in compressed form using only one bit for value (and not 8 how bool[] arrays do). It is not possible to return a reference to a bit in c++, so there is a special helper type, "bit reference", which provides you a interface to some bit in memory and allows you to use standard operators and casts.

Many consider the vector<bool> specialization to be a mistake.

In a paper "Deprecating Vestigial Library Parts in C++17"
There is a proposal to Reconsider vector Partial Specialization.

> There has been a long history of the bool partial specialization of > std::vector not satisfying the container requirements, and in > particular, its iterators not satisfying the requirements of a random > access iterator. A previous attempt to deprecate this container was > rejected for C++11, N2204.

---

> One of the reasons for rejection is that it is not clear what it would > mean to deprecate a particular specialization of a template. That > could be addressed with careful wording. The larger issue is that the > (packed) specialization of vector offers an important > optimization that clients of the standard library genuinely seek, but > would not longer be available. It is unlikely that we would be able to > deprecate this part of the standard until a replacement facility is > proposed and accepted, such as N2050. Unfortunately, there are no such > revised proposals currently being offered to the Library Evolution > Working Group.

Look at how it is implemented. the STL builds vastly on templates and therefore the headers do contain the code they do.

for instance look at the stdc++ implementation here.

also interesting even though not an stl conforming bit vector is the llvm::BitVector from here.

the essence of the llvm::BitVector is a nested class called reference and suitable operator overloading to make the BitVector behaves similar to vector with some limitations. The code below is a simplified interface to show how BitVector hides a class called reference to make the real implementation almost behave like a real array of bool without using 1 byte for each value.

class BitVector {
public:
  class reference {
    reference &operator=(reference t);
    reference& operator=(bool t);
    operator bool() const;
  };
  reference operator[](unsigned Idx);
  bool operator[](unsigned Idx) const;      
};

this code here has the nice properties:

BitVector b(10, false); // size 10, default false
BitVector::reference &x = b[5]; // that's what really happens
bool y = b[5]; // implicitly converted to bool 
assert(b[5] == false); // converted to bool
assert(b[6] == b[7]); // bool operator==(const reference &, const reference &);
b[5] = true; // assignment on reference
assert(b[5] == true); // and actually it does work.

This code actually has a flaw, try to run:

std::for_each(&b[5], &b[6], some_func); // address of reference not an iterator

will not work because assert( (&b[5] - &b[3]) == (5 - 3) ); will fail (within llvm::BitVector)

this is the very simple llvm version. std::vector<bool> has also working iterators in it. thus the call for(auto i = b.begin(), e = b.end(); i != e; ++i) will work. and also std::vector<bool>::const_iterator.

However there are still limitations in std::vector<bool> that makes it behave differently in some cases.

This comes from http://www.cplusplus.com/reference/vector/vector-bool/ > Vector of bool This is a specialized version of vector, which is used > for elements of type bool and optimizes for space. > > It behaves like the unspecialized version of vector, with the > following changes: > > - The storage is not necessarily an array of bool values, but the library implementation may optimize storage so that each value is
> stored in a single bit. > - Elements are not constructed using the allocator object, but their value is directly set on the proper bit in the internal storage. > - Member function flip and a new signature for member swap. > - A special member type, reference, a class that accesses individual bits in the container's internal storage with an interface that
> emulates a bool reference. Conversely, member type const_reference is > a plain bool. > - The pointer and iterator types used by the container are not necessarily neither pointers nor conforming iterators, although they
> shall simulate most of their expected behavior. > > These changes provide a quirky interface to this specialization and > favor memory optimization over processing (which may or may not suit > your needs). In any case, it is not possible to instantiate the > unspecialized template of vector for bool directly. Workarounds to > avoid this range from using a different type (char, unsigned char) or > container (like deque) to use wrapper types or further specialize for > specific allocator types. > > bitset is a class that provides a similar functionality for fixed-size > arrays of bits.