std::vector contiguous meaning

Question

I've read in a lot of places like here that std::vector is always contiguous, but I didn't find an explanation to the meaning of this or why is this important?

Does this mean that they have a fixed place in memory or what?

Answer 1

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.

Answer 2

The elements in a std::vector occupy a contiguous block of memory. A std::vector is an improved array.

This is important because it means access to an arbitrary element is fast. Because the size and number of elements is known, you can look up any element quickly.

The drawback is that any reorganization, such as inserting or deleting an element in the middle, is an expensive operation as it requires all others to be shuffled to maintain contiguity.

Other data structures such as lists allow easier reorganization with other tradeoffs.

Answer 3

It means that you can always get to the address of the next element via pointer arithmetic.

Answer 4

As none of the answers mentioned it:

Thanks to this feature of std::vector you can do things like

std::ifstream file( "file.txt", std::ios::ate | std::ios::binary );
std::vector<char> vec;
if (!file)
{
    file.seekg(0, std::ios_base::end);
    auto fileSize = file.tellg();
    vec.resize(fileSize);

    file.seekg(0, std::ios_base::beg);

    // here we leverage contiguous memory in std::vector
    file.read(&vec[0], fileSize);
}

where you avoid reading/writing element by element.

This can be used since C++03, as mentioned in 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().

Answer 5

It means that there are no holes in a std::vector's internal memory representation. It looks like this in memory:

Each square represents an address in memory, and every orange one an element occupied by the vector.

Most other containers are not contiguous. For example, a std::forward_list looks like this in memory:

Here, again, the orange addresses contain the elements of the container. But they are scattered across memory. There are also grey elements; they represent the additional memory needed by the list so that each elements knows where the next element is found.^[*]

As you can imagine, the clear and concise memory representation of std::vector gives you a lot of advantages. It explains why std::vector has some operations other containers lack, or why those operations run in constant time. For example, in order to get to the n-th element, you just perform one addition (base address + n). It also explains why you can safely take &v[0] and perform pointer arithmetics on it.

---

^{[*] This is a bit of a simplification, because the example has char elements, but the pointers in the list occupy more memory than single chars on typical C++ implementations. A more realistic diagram would use 4 or 8 grey squares for every element, because that's the size of one pointer on typical modern machines.}