Are std::vector elements guaranteed to be contiguous?

Question

My question is simple: are std::vector elements guaranteed to be contiguous? In other words, 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'
    }
}

Seizing

I know that you're in trouble if you mutate values inside that if block. I don't know the answer to your question, though, so I'm just leaving a comment. :) – Neustria

@Greg: What trouble – can you elaborate a little? – Whelan

I suppose he meant that pushing new values may trigger a "realloc" which would cause the array to become invalid. – Seizing

Calls that mutate values, specifically that change its size (e.g., push_back()), may prompt a reallocation of the underlying vector that invalidates the pointer copied into array. It's the same principle behind using a vector::iterator instead of a pointer into the vector. :) – Neustria

Ok. I was reading that if you mutate the values, i.e., assign to the elements. This should never cause any trouble, I believe. – Whelan

Yeah, I put the ``'s around values to try to make it clear I was talking about the class itself, not the values contained within it. :) Unfortunate naming and all that. I don't think it's really an issue in the general case where this question is relevant though-- why would someone grab a pointer to the memory, then start mucking with the vector instead of using the pointer? Silliness. – Neustria

Answer 1

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().

Logbook

This is also stated in ISO 14882, 2nd Edition: Section 23.2.4 [lib.vector]: "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()." – Villiers

so s,TR,TC, :) Actually C++03 is also called C++98-TC1 (technical corrigendum) from what i read – Perdu

@litb: Correct. I keep forgetting which is which. – Logbook

What about vectors of vectors? İnner vectors are right after last group's inner vectors? – Elfrieda

How is bool special as T in vector? According "The elements of a vector are stored contiguously, meaning that if v is a vector where T is some type other than bool". – Filia

@huseyin tugrul buyukisik did you learn the answer to this? I am also wondering how this works – Hood

@huseyin tugrul buyukisik It is of course true, but it is the instances of subsequentstd::vector that are contiguous. Eg.: instd::vector<std::vector<int>> v the elements v[0], v[1], ... are stored subsequently in memory, but the element v[0].back() and v[1].front() are not guaranteed to be. – Lamartine

@Filia std::vector<bool> is allowed to be optimised for space by using only (roughly) one bit instead of an entire byte. The best reference I could quickly dig out was this: en.cppreference.com/w/cpp/container/vector_bool – Lamartine

Answer 2

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

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.

Ardeb

The elements would still be stored in a contiguous memory block, it would just be in a different place. The question was specifically about contiguity. – Gibeon

But the existing pointers and iterators would be invalidated. – Ardeb

Good point. You should put that into your answer to clarify what you mean. – Gibeon

Now I know why my program was segfaulting yesterday, when I looped through it in a double loop removing certain elements :) Thanks! – Ostiole

@user2891462: #7958716 – Ardeb

@BillLynch Thanks! That is what I ended up going for, but I couldn't fathom what the segfault was about. – Ostiole

Thank you, insertion screw up memory, there is my segfault come from :p – Tildie

Does swap & push_back also break pointers and iterators? – Gosser

@iaomw: 1. vector.push_back(3) is an insertion, so it invalidates iterators. 2. I wouldn't expect swap(vector[3], vector[4]) to invalidate iterators, since no new memory is allocated, but I have no reference to back that up. 3. swap(vector_1, vector_2) is interesting. I probably wouldn't trust the iterators after this, but I don't know for sure if they continue to be valid. – Ardeb

pop_back does not reallocate the memory. – Vivienviviene

Answer 3

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.

Brace

> BTW, why don't you use iterators? That's what they're for. Maybe he read the Alexanrescu's new paper on the topic: boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/… – Monophysite

Thanks for the link, I'll at it to my reading list (I try not to miss Alexandresu's articles) – Brace

Mwahaha, everyone seems to be talking about that presentation these days. Look, the discussion is still hot about it: groups.google.com/group/comp.lang.c++.moderated/browse_thread/… – Perdu

If you read it carefully, Alexandrescu's article doesn't really say "Don't use iterators in C++", it says "Check out D". The approach he describes in that paper is strikingly similar to any existing languages and frameworks that have absorbed the functional heritage (List, Scheme, Haskell) and I seriously doubt whether yet-another-C-based-syntax is an ideal starting point for better list handling. Some time last year I briefly tried to persuade him to turn his considerable talents towards improving an already-established language like C# instead, but with I fear no success! :) – Galvani

Answer 4

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.)

Tart

The user is not allowed to specialize std::vector, and all other vectors are required to use contiguous storage. Therefore, std::vector<bool> is (fortunately) the only standard vector that's weird. (I'm strongly of the opinion that this specialization should be deprecated and replaced by e.g. a std::dynamic_bitset with much the same functionality. It's not a bad data structure, it's just not a vector.) – Sapele

Answer 5

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

Stanleigh

Answer 6

I found this thread because I have a use case where vectors using contiguous memory is an advantage.

I am learning how to use vertex buffer objects in OpenGL. I created a wrapper class to contain the buffer logic, so all I need to do is pass an array of floats and a few config values to create the buffer. I want to be able to generate a buffer from a function based on user input, so the length is not known at compile time. Doing something like this would be the easiest solution:

void generate(std::vector<float> v)
{
  float f = generate_next_float();
  v.push_back(f);
}

Now I can pass the vector's floats as an array to OpenGL's buffer-related functions. This also removes the need for sizeof to determine the length of the array.

This is far better than allocating a huge array to store the floats and hoping I made it big enough, or making my own dynamic array with contiguous storage.

Caesar

this function doesn't make any sense to me. do you mean to be passing a reference or a pointer to v rather than v itself? because passing v alone will cause a copy to be made inside the function, which will cease to exist after the function ends. Thus you are pushing something onto the vector only to delete the vector when the function ends. – Filet

Answer 7

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.

Infringe