CODEWITHSUNDEEP
c++language-lawyer
OutOfBound
OutOfBound

Reputation: 2004

Understanding std::vector specification

The draft for the c++14 standard n4140 [vector.overview]/1 states the following:

A vector is a sequence container that supports random access iterators. In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time. Storage management is handled automatically, though hints can be given to improve efficiency. The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

Why is the identity &v[n] == &v[0] + n for all 0 <= n < v.size() true for all types except bool? As far as my understanding goes, C++ is byte adressed. So this should only hold true for types, that are one byte in size.

Upvotes: 0

Views: 325

Answers (2)

Barry
Barry

Reputation: 303027

Because vector<bool> is not just a vector that holds bools. It is an entirely different sort of beast. There is a partial specialization for it - and it behaves as a dynamic bitset, storing 8 bools in one byte. So that identity does not hold. Indeed, you cannot even get a bool& out of a vector<bool>, you only get proxy references.

So this should only hold true for types, that are one byte in size.

The size here doesn't matter. &v[n] == &v[0] + n holds for all types, except bool. For bool, this is ill-formed, because &v[0] isn't a valid expression at all (much less a pointer).

To word this in a different way. For all T except for bool, vector<T> behaves a lot like a T[] with dynamic, known length. v[i] is a specific T, &v[i] is a pointer to a specific T. Everything you know and love about arrays applies to vector. Like that pointer identity.

But vector<bool> is not a bool[]. v[i] is not a specific bool, it is an object that is convertible to bool. &v[i] is not a pointer to a specific bool, it is not even a valid expression because v[i] isn't an lvalue.

Things you try to do with vector<T> for unknown T that work with every other T fail with bool, like:

std::vector<T> v = ...;
for (auto& elem : v) { ... } // ok for every T. except bool.

Upvotes: 4

doug
doug

Reputation: 4289

&v[0] is a pointer to the type enclosed by the vector (except for vector<bool>). &v[0]+ n changes the pointer to point to the n'th element regardless of how large the element is in bytes.

As Barry noted, a vector<bool>' is a specialization to reduce the space consumed and pack bits. It's unlike all othervector` containers. This become problematic when doing something like:

vector<bool> b{true, false};
auto& val=b[0];

val is not a reference to a bool!

Upvotes: 4

Related Questions