Any guarantees with vector<bool> iterators?

Question

cppreference says that the iterators for the vector<bool> specialization are implementation defined and many not support traits like ForwardIterator (and therefore RandomAccessIterator).

cplusplus adds a mysterious "most":

The pointer and iterator types used by the container are not necessarily neither pointers nor conforming iterators, although they shall simulate most of their expected behavior.

I don't have access to the official specification. Are there any iterator behaviors guaranteed for the vector<bool> iterators?

More concretely, how would one write standards-compliant code to insert an item in the middle of a vector<bool>? The following works on several compilers that I tried:

std::vector<bool> v(4);
int k = 2;
v.insert(v.begin() + k, true);

Will it always?

Answer 1

The fundamental problem with vector<bool>'s iterators is that they are not ForwardIterators. C++14 [forward.iterators]/1 requires that ForwardIterators' reference type be T& or const T&, as appropriate.

Any function which takes a forward iterator over a range of Ts is allowed to do this:

T &t = *it;
t = //Some value.

However, vector<bool>'s reference types are not bool&; they're a proxy object that is convertible to and assignable from a bool. They act like a bool, but they are not a bool. As such, this code is illegal:

bool &b = *it;

It would be attempting to get an lvalue reference to a temporary created from the proxy object. That's not allowed.

Therefore, you cannot use vector<bool>'s iterators in any function that takes ForwardIterators or higher.

However, your code doesn't necessarily have to care about that. As long as you control what code you pass those vector<bool> iterators to, and you don't do anything that violates how they behave, then you're fine.

As far as their interface is concerned, they act like RandomAccessIterators, except for when they don't (see above). So you can offset them with integers with constant time complexity and so forth.

vector<bool> is fine, so long as you don't treat it like a vector that contains bools. Your code will work because it uses vector<bool>'s own interface, which it obviously accepts.

It would not work if you passed a pair of vector<bool> iterators to std::sort.