Home > Articles > Programming > C/C++

C++ Reference Guide

Hosted by

What You Should Know about <tt>vector&lt;bool&gt;</tt>

Last updated Jan 1, 2003.

The C++98 vector<bool> specialization stores Boolean values as bits rather than as bool variables. In recent years, it became evident that vector<bool> was a mistake. Why is vector<bool> so frowned upon? Which remedies have been proposed so far? And what does this mean to Joe Coder? Here are all the answers.

Good Intentions

The C++ standard specifies in 23.3.5 a specialization of vector for bool elements that "optimizes space allocation." The designers of this specialization certainly meant well. Instead of wasting a whole byte, vector<bool> packs Boolean values as individual bits.

The first problem with this specialization is the "surprise effect." Not all C++ programmers know that when they create a vector<bool> object, the compiler uses the specialized form of this container rather than the primary vector template. This may not seem problematic until you discover that vector<bool> is a very odd beast.

vector<bool>'s elements aren't addressable because C++ doesn't have pointers and references to bits. How does the vector<bool> specialization deal with references and iterators then? The Standard defines a nested class inside vector<bool> called reference. This class "simulates the behavior of references of a single bit in vector<bool>." Consequently, vector<bool>::iterator isn't a random access iterator, as opposed to, say, vector<string>::iterator or vector<char>::iterator.

Let's see how bad things can get:

template <typename T> void func(vector<T> & vec)
{
 T & ref=vec.front(); //works for all types except bool
}

My compiler accepts this code; but at runtime, func<bool> crashes.

In addition to its unusual reference and iterator types, vector<bool> also defines the flip() member function. Needless to say, this member function isn't part of vector's interface.

Premature Optimization

vector<bool> epitomizes the First Rule of Optimization: "premature optimization is evil." This optimization exacts a hefty toll: namely, a quirky interface, speed overhead, and incompatibility with the Standard Library. This optimization isn't optional; it's forced on programmers. The most common technique for bypassing it is using vector<char> instead. Another less familiar workaround is using a different type of allocator. If you specify a different type of allocator, the compiler generates the vector<bool> specialization from the primary vector template:

std::vector<bool, myallocator> realbool; 

This hack is unsuitable for the average C++ programmer, though. Many programmers don't know what allocators are anyway.

Motions and Remonstrations

The first doubts concerning vector<bool> were expressed in the Santa Cruz meeting of the C++ standards committee, in October 1998. Defect Report (DR) 96 states that vector<bool> is not a container, as its reference and pointer types are not references and pointers, and that it forces users to have a space optimization instead of a speed one. In that meeting, most committee members felt that this wasn't a defect.

However, in the subsequent Dublin meeting in April 1999, many members felt that failure to meet Container Requirements (as specified in article 23.1 in the standard) was a defect. There was disagreement as to whether the space optimization required in the standard constituted a defect, though. The committee considered the following resolutions:

  • Decide that DR 96 was Not A Defect, leaving the standard as-is
  • Add a note to the standard explaining that vector<bool> does not meet Container Requirements
  • Remove vector<bool> from the standard
  • Add a new category of container requirements which vector<bool> would meet
  • Rename vector<bool>

Each of these proposals failed to get unanimous support. In the Kona meeting (October 1999), Herb Sutter presented his paper, vector<bool>: More Problems, Better Solutions (PDF), in which he proposed to remove, not just deprecate, vector<bool> from the Standard, or move it to a different namespace. Neither proposal was accepted.

Although the committee didn't actively deprecate vector<bool>, C++ newsgroups and discussion forums have thenceforth advised programmers to stay away from it. In the Lillehammer meeting in April 2005, vector<bool> was discussed again. This time, there was general agreement about deprecating vector<bool> and introducing its functionality under a different name, e.g. bit_vector. With the adoption of this approach, it might be possible to remove the vector<bool> specialization from the next C++ standard. There was another suggestion to state in C++0x that whether vector<bool> refers to the deprecated specialization or to the primary template is implementation-defined. However, this suggestion was rejected.

Epilog

vector<bool> isn't entirely dysfunctional. As long as you are aware of its caveats and quirks (and there are many of them!), it still solves certain programming tasks neatly. However, now that it's officially deprecated, with the possibility of being completely removed from the standard in the future, my advice is to avoid using this specialization in new code.

The history of vector<bool> is yet another reminder as to why premature optimization is evil. It's very expensive, too.