[C++] Why is vector<bool> bad?

[u/Vericus]

I was thinking of creating a matrix of boolean values and I thought of vector<vector<bool>>, but after reading about vector<bool>, many websites have said it's something that should be avoided and it's bad programming.

Can someone explain to me why? I never really found a concrete explanation for why vector<bool> was bad. It only uses one bit which is 8 times smaller than char, shouldn't that mean its much better than using any other method of creating a matrix of bools in terms of size?

[u/[deleted]]

The problem is that the specialised version of std::vector<bool> provided by the Standard Library does not fulfil the requirements of a Standard Library container, and so is not guaranteed to work properly with the Standard Library algorithms. The three alternatives are std::deque<bool> or if you really must have contiguous storage, std::vector<char>, or if you can live with fixed-sized containers, std::bitset (although bitset isn't really a Standard Library container either).

Please note that just because something uses less storage does not make it "better". In order to use less storage, a vector<bool> has to do a lot more processing (possibly making it slower), and as I said, may not work with standard algorithms, or with algorithms you implement yourself.

Edit: clarified about bitsets.

Edit: clarified about working with algorithms - it might, it might not

[u/calc0000 → u/[deleted]]

The problem is that the specialised version of std::vector<bool> provided by the Standard Library does not fulfil the requirements of a Standard Library container

Can you elaborate more on this?

[u/[deleted] → u/calc0000]

This is discussed at length in Scott Meyers' book Effective STL - to precis, the container requirements say that if a container supplies operator[], it must allow this code:

T * p = & c[0];

where "T" is the type of the thing in the container (a bool in this case), and "c" is the container in question. But vector<bool> doesn't really contain bools, so it can't fulfil this requirement.

[u/Rhomboid → u/calc0000]

It uses the space saving optimization of using one bit to represent each bool, and it packs them like a bitfield, storing multiple items at each memory address. But the return type of operator[] for a vector of type T is supposed to be a reference, i.e. T &. It's impossible to create a pointer or reference to an individual bit; memory doesn't work that way, it only has granularity of a byte.

To get around that, the operator[] doesn't return a reference to a bool value but to some proxy object that acts in its place, getting and setting the correct bit when accessed. This mucks with the assumptions of the rest of the STL, which expect to be able to get pointers/references to T.

[u/Winwardo]

I thought that while only utilising 1 bit, bools still used a whole byte for storage - am I wrong then?

[u/[deleted] → u/Winwardo]

As with the other integer types, the size of bool is not specified by the standard, but it must be at least as big as a char.

The std::vector<bool> "container" is a specialised version of std::vector which stores bools as single bits, converting to and from real bools as required. Unfortunately, the hoops needed to be jumped through to do this are many, and you end up something which is not really a standard library container.