Why Isn't Vector≪Bool≫ a Stl Container

Why isn't vectorbool a STL container?

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.

If std::vectorbool was rewritten to use the standard vector implementation, how would that break old software?

Firstly, that would be an ABI break. A major reason why changing anything from the standard library is difficult.

Secondly, anything using flip would break:

#include <vector>

int main() {
  std::vector<bool> vec { true };
  vec[0].flip(); // can't be done with regular bool
}

Thirdly, there would probably be other problems due to overload resolution someone probably relies on.

---

Side note: You can always use boost::container::vector instead, which is not specialized for bool.

Why does std::foreach not work with a std::vectorbool?

Reason

The problem stems from the fact that dereferencing an iterator that came from std::vector<bool> doesn't return bool&, but rather a proxy object. Thus, it is not regarded as stl container (thanks to @KillzoneKid).

Fix

Use auto element in the parameter list. In general, if you don't care about the type, use auto&& in the lambda parameter list.

#include <vector>
#include <iostream>
#include <algorithm>

int main () {
    std::vector<bool> list {true, true, false};
    auto reset = [](auto && element){element = false;};

    auto print = [](int element) {std::cout<< element << " ";};
    std::for_each(list.begin(), list.end(),reset);
    std::for_each(list.begin(), list.end(),print);

}

Demo.

Trying to use auto& will trigger compilation error again, as the proxy returned is not lvalue, but rvalue. Thus, auto&& has even more benefits than usual.

Is the use of std::vectorbool objects in C++ acceptable, or should I use an alternative?

There's nothing wrong with vector<bool>, except that it isn't equivalent to a vector<T> were T is the integer type equivalent to bool. This only shows in performance (CPUs only access bytes at a time, where in a vector<bool> every element is stored in one bit) and memory access (a reference to a first element of a vector<bool> is not equivalent to an array like with any other vector<T>.

It is part of the Standard, unfortunately: see section 23.3.7 (C++0x FDIS).

Alternative to vectorbool

Use std::deque if you don't need the array, yes.

Otherwise use an alternative vector that doesn't specialize on bool, such as the one in Boost Container.

Why is std::min_element and company not specialized for std::vectorbool

There is no need to specialize std::min_element for std::vector<bool>. To get the functionality that you want you can just use std::any_of which will stop at the first occurrence.

return !std::any_of(foo.begin(), foo.end(), [](auto e){ return e == false; });

If we change this to std::all_of as Some programmer dude suggests then you do not need to negate the return value, which gives you

return std::all_of(foo.begin(), foo.end(), [](auto e){ return e; });

Which is a little cleaner and easier to understand.

compiler error when pointing to an element of std::vectorbool?

Yes, bool and unsigned char typically take the same amount of memory on their own, but that does not make vector<bool> and vector<unsigned char> the same!

vector<bool> is given very, very special treatment by the standard in order to pack elements as close as possible (which someone in the 1990s thought would be clever, since a bool has one of only two states), and the result is what you've seen: its elements are non-addressable.

Avoid!

---

Related Topics