Are std::vector elements guaranteed to be contiguous?

Question

My question is simple: are std::vector elements guaranteed to be contiguous? In order word, can I use the pointer to the first element of a std::vector as a C-array?

If my memory serves me well, the C++ standard did not make such guarantee. However, the std::vector requirements were such that it was virtually impossible to meet them if the elements were not contiguous.

Can somebody clarify this?

Example:

std::vector<int> values;
// ... fill up values

if( !values.empty() )
{
    int *array = &values[0];
    for( int i = 0; i < values.size(); ++i )
    {
        int v = array[i];
        // do something with 'v'
    }
}

Answer 1

Yes, the elements of a std::vector are guaranteed to be contiguous.

Answer 2

The standard does in fact guarantee that a vector is continuous in memory and that &a[0] can be passed to a C function that expects an array.

The exception to this rule is vector<bool> which only uses one bit per bool thus although it does have continuous memory it can't be used as a bool* (this is widely considered to be a false optimization and a mistake).

BTW, why don't you use iterators? That's what they're for.

Answer 3

cplusplus.com:

Vector containers are implemented as dynamic arrays; Just as regular arrays, vector containers have their elements stored in contiguous storage locations, which means that their elements can be accessed not only using iterators but also using offsets on regular pointers to elements.

Answer 4

As other answers have pointed out, the contents of a vector is guaranteed to be continuous (excepting bool's weirding).

The comment that I wanted to add, is that if you do an insertion or a deletion on the vector, which could cause the vector to reallocate it's memory, then you will cause all of your saved pointers and iterators to be invalidated.

Answer 5

This was missed from C++98 standard proper but later added as part of a TR. The forthcoming C++0x standard will of course contain this as a requirement.

From n2798 (draft of C++0x):

23.2.6 Class template vector [vector]

1 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 where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

Answer 6

See: Is it safe to assume that STL vector storage is always contiguous?

Answer 7

As other's have already said, vector internally uses a contiguous array of objects. Pointers into that array should be treated as invalid whenever any non-const member function is called IIRC.

However, there is an exception!!

vector<bool> has a specialised implementation designed to save space, so that each bool only uses one bit. The underlying array is not a contiguous array of bool and array arithmetic on vector<bool> doesn't work like vector<T> would.

(I suppose it's also possible that this may be true of any specialisation of vector, since we can always implement a new one. However, std::vector<bool> is the only, err, standard specialisation upon which simple pointer arithmetic won't work.)