CODEWITHSUNDEEP
c++vectoriterator
xan
xan

Reputation: 7731

Any guarantees with vector<bool> iterators?

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?

Upvotes: 10

Views: 684

Answers (2)

Nicol Bolas
Nicol Bolas

Reputation: 473946

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.

C++20 update:

Because the C++20 concept iterator categories allow for proxy iterators, vector<bool>::iterator is now a valid std::random_access_iterator. This means you can pass them to any algorithm that is constrained on that concept or a higher-level one.

However, these are only the algorithms in the std::ranges namespace. The regular std:: algorithms still use the old definition, which vector<bool>::iterator doesn't allow.

C++23 update.

Algorithms which take non-mutable old-style are now required to take types conforming to the corresponding iterator concept. So if a function took a non-mutable RandomAccessIterator, then it is required to accept a std::random_access_iterator conforming type.

Upvotes: 9

Pete Becker
Pete Becker

Reputation: 76418

C++14 [vector.bool]/2:

Unless described below, all operations have the same requirements and semantics as the primary vector template, except that operations dealing with the bool value type map to bit values in the container storage and allocator_traits::construct (20.7.8.2) is not used to construct these values.

Upvotes: 5

Related Questions