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

Question

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?

Solution 1

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.

Solution 2

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.

Solution 3

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.

Solution 4

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.

Solution 5

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.

View more solutions

Comments

[Oktalist]

It was a design mistake in C++98, now retained for compatibility.

[πάντα ῥεῖ]

So, I'm also wondering why std::vector<bool> shouldn't compile. I also remember it's a specialization.

[chris]

@g-makulik, It's not that the use of it won't compile, just that you can't store the address of an element in a pointer to bool, since the element doesn't have its own address.

[chris]

Perhaps this will help: stackoverflow.com/questions/670308/alternative-to-vectorbool

[πάντα ῥεῖ]

@chris Ah, I see! Right yes, you can't do that.

[Oktalist]

@g-makulik std::vector<bool> v; will compile. &v[0] will not (taking address of a temporary).

[P0W]

@Oktalist What is with deque<bool> then ?

[Bartek Banachewicz]

@PrashantSrivastava It's not specialized for bool and thus keeps reasonable behaviour.

[TemplateRex]

vector<bool> has a bad rep but not entirely justifiably so: isocpp.org/blog/2012/11/on-vectorbool

[jrh]

Semi-related: 1 bit per bool in Array C++, if anyone's wondering why you can get the reference of a bool in a C style bool array. Note that bool[] arrays aren't packed with 1 bit per bool like vector<bool> is.

[Ped7g]

"says to avoid vector <bool> as it's not an STL container and it doesn't really hold bools." - that's irritating claim to me. What does it hold then, red herrings? The C++ bool type doesn't have standardized implementation, you can't rely on any particular feature of it (in standard portable C++ source), except using it as bool, that should work, and that also works with vector<bool> well. Its size is undefined and the vector<bool> just takes this to another level (no address), to gain particular benefit of size optimization. Recommending general "avoid" is like: "bloat your SW".

[qwr]

Is this question asking about STL vector<bool> or C++ standard library vector<bool>?

[Konrad Rudolph]

@PrashantSrivastava deque<bool> isn’t specialised so it’s literally just a deque holding bools.

[Ivan Smirnov]

@PrashantSrivastava vector<bool> has a specific template implementation. I guess, other STL containers, such as deque<bool>, don't, so they hold bool-s like any other types.

[P0W]

do we have any other data type for which any other STL container is specialized or explicitly called ?

[Sergio Basurco]

Does this apply for C++11 std::array<bool> ?

[underscore_d]

@chuckleplant no, std::array is merely a templated wrapper around a raw array of T[n] with some helper functions like size(), copy/move semantics, and iterators added to make it STL-compatible - and (thankfully) it does not violate its own principles to (note my scepticism of these:) 'specialise' for 'bool'.

[underscore_d]

This doesn't answer the question directly. At best, it requires the reader to infer which things explained in this general summary make it non-STL.

[andy boot]

Here is a questions asking a similar thing in rust where they disallowed single bit booleans stackoverflow.com/questions/48875251/…

[Uri Raz]

Just a nit pick - the sizeof(bool) isn't necessarily a byte. stackoverflow.com/questions/4897844/…