vector<char> VS vector<bool> in C++11 [closed]

Question

Why should we use vector<char> instead of vector<bool>? What is the reason that vector<char> is faster?

Answer 1

std::vector<bool> is a specialisation of std::vector<T> that's done mainly for space efficiency (debatable). However, it behaves similarly but not equally as a regular std::vector<T>. This is attributed mainly to the fact that std::vector<bool> is not a container in the usual C++ standard library sense but rather an array of bits. Some of the differences between a std::vector<bool> and a regular std::vector are:

• std::vector<bool>::iterator is not a random-access iterator.
• std::vector<bool> is not required to store its elements as a contiguous array.
• std::vector<bool> exposes class std::vector<bool>::reference as a method of accessing individual bits. In particular, objects of this class are returned by operator[], std::vector<bool>::front, std::vector<bool>::back by value.
• std::vector<bool> does not use std::allocator_traits::construct to construct bit values.
• std::vector<bool> does not guarantee that different elements in the same container can be modified concurrently by different threads.
• std::vector<bool> has a different interface (i.e., flip())

These differences except from breaking the conceptual meaning of std::vector as a contiguous container, have also a tendency to break user code, especially when this code is generic (i.e., template code).

To clarify consider the following example:

template<class T> void foo(std::vector<T> &v) {
 T &frnt = v.front();
 ...
}

The above example works for every T except when T = bool. As already mentioned, the reason for this failure is that v.front()'s returned value is a temporary (returns by value) and as such cannot bind to a reference.

To avoid this havoc many coders avoid the use of std::vector<bool> and prefer the use of std::vector<char>. Due to the many problems caused, it is stated by many that use of std::vector<bool> could be considered as a premature optimisation. To the resolution of that matter there are proposals from many distinguished C++ community members. One of these proposals suggests to remove std::vector<bool> under a different name that it will not refer to C++ standard library containers.

Now to the time performance issue, the main problem with std::vector<bool> is that its respective std::algorithm algorithms are not optimised for it. Thus, although you might gain space by using it, it's use might lead to a very significant speed pessimization.

Bibliography

1. vector: More Problems, Better Solutions, Herb Sutter
2. On vector<bool>, Howard Hinnant
3. std::vector<bool>