Questions about std::vector and std::deque

[neverhoodboy]

In the standard, vector is described as below:
A vector is a kind of sequence 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().

What does "other than bool" mean? What kind of scenario will cause
the above identity to fail if T is bool?

The second question is about deque. In the standard, deque is
described as below:
A deque is a kind of sequence that, like a vector (23.2.4), supports
random access iterators. In addition, it supports constant time insert
and erase operations at the beginning or the end; insert and erase in
the middle take linear time. That is, a deque is especially optimized
for pushing and popping elements at the beginning and end. As with
vectors, storage management is handled automatically.

Note that the constant time insert and erase operations at the
beginning or the end is non-amortized, as opposed to vector.
With random access support and automatic storage management, how does
deque achieve that performance?

Thanks!

 

[Richard Damon]

In the standard, vector is described as below:
A vector is a kind of sequence 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().

What does "other than bool" mean? What kind of scenario will cause
the above identity to fail if T is bool?

The standard defines vector<bool> differently, with the expectation that
vector<bool> will pack the bits into the vector for minimal space usage.
As such, you can't get the address of an element, as C++ pointers are at
best "char" pointers, not bit pointers.

 

[Juha Nieminen]

Note that the constant time insert and erase operations at the
beginning or the end is non-amortized, as opposed to vector.
With random access support and automatic storage management, how does
deque achieve that performance?

std::deque allocates blocks of memory. When one block gets full, it
allocates a new block (rather than reallocating the entire data
structure like std::vector does).

That means that while the elements of one block are in consecutive
memory locations, elements in different blocks aren't. (It also means
that pointers to the elements don't get invalidated if new elements
are added to the beginning or ending of the deque.)