Are Std::Vector Elements Guaranteed to Be Contiguous

Are std::vector elements guaranteed to be contiguous?

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

Why is std::vector contiguous?

If std::vector didn't guarantee contiguousness, a new container would be invented which did.

The contiguity guarantee makes it easier to inter-operate with existing code that expects a contiguous array, and also gives very good performance because it is cache-friendly. (Inserting/deleting in the middle is in practice very fast for moderate sizes because of this.)

Copying the array on expansion is surprisingly cheap - if you append to a vector a million elements one at a time, each element will have been copied on average around once.

Why isn't a vector of a vector guaranteed to be contiguous? (or is it?)

Each of your vector inside the vector of vectors is an individual object, and as such is responsible for it's storage. So, no, it is by no means guaranteed to be contiguous, in fact I can 't really see a situation where it could happen that the data stored in the outer vector and it's inner vectors is one contiguous block of memory ever.

Are std::vector elements contiguous in physical memory?

The memory used to store the data in a vector must be at contiguous addresses as those addresses are visible to the code.

In a typical case on most modern CPUs/OSes, that will mean the virtual addresses must be contiguous. If those virtual addresses cross a page boundary, then there's a good chance that the physical addresses will no longer be contiguous.

I should add that this is only rarely a major concern. Modern systems have at least some support for such fragmented memory usage right down to the hardware level in many cases. For example, many network and disk controllers include "scatter/gather" capability, where the OS uses the page tables to translate the virtual addresses for the buffer to physical addresses, then supplies a number of physical addresses directly to the controller, which then gathers the data from those addresses if it's transferring from memory to peripheral or "scatters" the data out to those addresses if it's transferring from peripheral to memory.

How does std::vector support contiguous memory for custom objects of unknown size

Your concept of size is flawed. A std::vector<type> has a compile time known size of space it is going to take up. It also has a run time size that it may use (this is allocated at run time and the vector holds a pointer to it). You can picture it laid out like

+--------+
|        |
| Vector |
|        |
|        |
+--------+
     |
     |
     v
+-------------------------------------------------+
|         |         |         |         |         |
| Element | Element | Element | Element | Element |
|         |         |         |         |         |
+-------------------------------------------------+

So when you have a vector of things that have a vector in them, each Element becomes the vector and then those point of to their own storage somewhere else like

+--------+
|        |
| Vector |
|        |
|        |
+----+---+
     |
     |
     v
+----+----+---------+---------+
| Object  | Object  | Object  |
|  with   |  with   |  with   |
| Vector  | Vector  | Vector  |
+----+----+----+----+----+----+
     |         |         |    +---------+---------+---------+---------+---------+
     |         |         |    |         |         |         |         |         |
     |         |         +--->+ Element | Element | Element | Element | Element |
     |         |              |         |         |         |         |         |
     |         |              +-------------------------------------------------+
     |         |    +-------------------------------------------------+
     |         |    |         |         |         |         |         |
     |         +--->+ Element | Element | Element | Element | Element |
     |              |         |         |         |         |         |
     |              +-------------------------------------------------+
     |    +-------------------------------------------------+
     |    |         |         |         |         |         |
     +--->+ Element | Element | Element | Element | Element |
          |         |         |         |         |         |
          +---------+---------+---------+---------+---------+

This way all of the vectors are next to each other, but the elements the vectors have can be anywhere else in memory. It is for this reason you don't want to use a std:vector<std::vector<int>> for a matrix. All of the sub vectors get memory to wherever so there is no locality between the rows.

Do note that this applies to all of the allocator aware containers as they do not store the elements inside the container directly. This is not true for std::array as, like a raw array, the elements are part of the container. If you have an std::array<int, 20> then it is at least sizeof(int) * 20 bytes in size.

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

Yes, that is a valid assumption (*).

From the C++03 standard (23.2.4.1):

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

(*) ... but watch out for the array being reallocated (invalidating any pointers and iterators) after adding elements to it.

std::vector contiguous meaning

Contiguous in this context means that sequentially numbered vector's elements are located next to each other in memory space. For example, if an element i is located at the address a, and has a size of s, then the element i+1 would be located at the address a+s, the element i+2 would be at a+s+s, and so on.

This is important for two reasons:

Contiguous requirement makes random access possible - you can compute the location of any element based on vector's base address and element's index
You can predict locality of reference - processing vector elements sequentially is the same as processing array elements sequentially for the purposes of cache behavior analysis.

Is data storage in std::vector continuous? [duplicate]

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

Also do check array being reallocated (invalidating any pointers and iterators) after adding elements to it.

Also check this article:- Cringe not: Vectors are guaranteed to be contiguous

contiguity is in fact part of the vector abstraction. It’s so
important, in fact, that when it was discovered that the C++98
standard didn’t completely guarantee contiguity, the C++03 standard
was amended to explicitly add the guarantee.

Also from the C++ FAQ

#include <vector>
#include "Foo.h"  /* get class Foo */

// old-style code that wants an array
void f(Foo* array, unsigned numFoos);

void g()
{
  std::vector<Foo> v;
  ...
  f(v.empty() ? NULL : &v[0], v.size());  ← safe
}

The funny expression v.empty() ? NULL : &v[0] simply passes the NULL pointer if v is empty, otherwise passes a pointer to the first (zeroth) element of v. If you know a priori that v is not empty, you can change that to simply &v[0].
In general, it means you are guaranteed that &v[0] + n == &v[n], where v is a std::vector<T> and n is an integer in the range 0 .. v.size()-1.

However v.begin() is not guaranteed to be a T*, which means v.begin() is not guaranteed to be the same as &v[0]:

void g()
{
  std::vector<Foo> v;
  ...
  f(v.begin(), v.size());  ← Error!! Not Guaranteed!!
    ^^^^^^^^^-- cough, choke, gag; not guaranteed to be the same as &v[0]
}

Is a vector of arrays contiguous?

Is a vector of arrays contiguous?

No, it is not. std::array may contain padding or even additional members at the end. More details, e.g., here:

Is the data in nested std::arrays guaranteed to be contiguous?
Is the size of std::array defined by standard

But I believe this is very unlikely to happen and you can simply check such situations by comparing 2 * sizeof(double) with sizeof(std::array<double, 2>).

Are Std::Vector Elements Guaranteed to Be Contiguous