vector VS vector in C++11

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>

Answer 2

vector<bool> is an array of bits. vector<char> is an array of bytes. The former uses less space in exchange for more complicated indexing operations.

Whether vector<char> is actually faster or not is probably a function of architecture, especially cache. If your vector<bool> fits entirely in L1 cache on x86_64 it could be faster than a vector<char> which doesn't.

Usual advice applies, if the performance matters, measure the performance in your application.

Answer 3

Why should we use vector<char> instead of vector<bool>?

Usually, you wouldn't want to prefer vector<char>.

What is the reason that vector<char> is faster?

Usually, vector<char> tends to be slower.

---

Let us discus the drawbacks of vector<bool>.

cppreference: Different elements in the same container can be modified concurrently by different threads, except for the elements of std::vector<bool>

If you need concurrent modification to separate elements within the same container, then a std::vector<bool> must be protected by a lock, while a vector<char> does not. The simpler code for vector<char> is a clear advantage, and may be more efficient assuming high parallelism. If you do have this scenario, don't forget to consider false sharing, though and don't forget to measure.

---

Howard Hinnant has written an article that discusses the pros and cons of vector<bool>. Short version of pros:

It is often both a space and speed optimization over the array of bools data structure if properly implemented.

Short version of cons:

However it does not behave exactly as an array of bools, and so should not pretend to be one.

The argument of the article is not that you shouldn't use vector<bool>, but that vector<bool> should be something other than a specialization of vector, since it doesn't fully conform to the interface that it specializes.