CODEWITHSUNDEEP
c++stdvector
johnbakers
johnbakers

Reputation: 24760

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

I know std::vector elements are guaranteed contiguous in memory.

So then why can't you expect a vector containing other vectors to have the total collection contiguous?

The vector is supposed to guarantee contiguous memory layout for its enclosed items, and if those enclosures are also vectors, then I'd expect the full contents of the top-most vector to be in contiguous memory.

But there seems to be some contention on this issue as to whether or not this is true. Can one safely rely on it or not? Some folks seem to go out of their way to achieve this, while I'd think it is guaranteed.

Upvotes: 1

Views: 943

Answers (6)

jogojapan
jogojapan

Reputation: 69977

I think the most correct formal way of answering this (as opposed to describing existing implementations) is based on §23.3.6.1/1:

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

Note that this talks about the addresses &v[i] of individual elements of the vector and implies, in particular, that each element of the vector has constant size sizeof(T) (because that's how pointer arithmetic works).

This means it is impossible for the elements of a vector to change size at run-time. If a vector<vector<T>> was implemented as one contiguous block of memory, the members of the outer vector, being themselves vectors, would be allowed to change size.

Therefore, there must be an extra level of indirection, i.e., the individual vectors must contain some sort of pointer to a variable-size data structure stored at a different place.

Upvotes: 3

dtech
dtech

Reputation: 49289

To put it simply - std::vector guarantees the elements are stored contiguously. But that only includes the element's member data, in the case of vector that would be its size, capacity and stuff like that, plus the pointer to the actual vector data.

So, a vector of vectors will give you a contiguous vector of vectors, but those vectors will have their data dynamically allocated on arbitrary memory addresses.

Since an object size needs to be known at compile time, you cannot have objects with varying size, the only way to do this is to use dynamic memory allocation. If you had a custom vector of fixed size that uses no dynamic memory allocation internally, then a std::vector<customVector> would store the customVectors contiguously, but you will still have the additional auxiliary members which will "interrupt" the actual contiguity of the customVector element data.

Upvotes: 0

Vite Falcon
Vite Falcon

Reputation: 6645

Let's look at the (logical) memory layout of vector:

[size:4/8 bytes]
[capacity:4/8 bytes]
[other datamembers:n bytes]
*[elements:size*sizeof(element) bytes] << one contiguous memory (pointer to heap)

With a vector of vectors it looks like this:

[size:4/8 bytes]
[capacity:4/8 bytes]
[other datamembers:n bytes]
* [
    [Vector:0]
        [size:4/8 bytes]
        [capacity:4/8 bytes]
        [other datamembers:n bytes]
        *[elements:size*sizeof(element) bytes] << pointer to contiguous memory for elements
    [Vector:1]
        [size:4/8 bytes]
        [capacity:4/8 bytes]
        [other datamembers:n bytes]
        *[elements:size*sizeof(element) bytes]
    [Vector:2]
        [size:4/8 bytes]
        [capacity:4/8 bytes]
        [other datamembers:n bytes]
        *[elements:size*sizeof(element) bytes]
    ...
    ...
] << contiguous memory of vectors

This means that a vector has a pointer to contiguous memory storing vectors, each of which stores their elements pointing to another heap with contiguous memory storing the elements.

But if you managed to create an allocator to be used by the vector, such that it would allocate blocks of memory that are contiguous, you'd still face issues where if one of the nested vectors gets removed, the memory is no longer contiguous. Not to mention the situation of having the nested vector having different sizes.

Depending on your use-case you can either use the customer contiguous block memory allocator for a vector of vector, or just do it the old way of manually allocating and deallocating one contiguous block of memory.

Upvotes: 0

didierc
didierc

Reputation: 14730

The problem is that the vector template doesn't contain the data it handle "inline", or directly. Another way of saying it that the vector class boxes the data array it holds: the vector class holds a pointer to the memory area containing the array of elements. It is structurally equivalent to:

template <typename T>
struct vector_eq {
    T *ptr;
};

and not

template <typename T>
struct vector_neq {
    T arr[SIZE];
};

which would require SIZE to be known at compile time (ie. a constexpr), for arr elements to be included in the struct.

I imagine thar it should be possible to specialise vector<vector<T>> to contain a pointer to a single block of memory, and have its methods return ad hoc instances of vector<T> sharing slices of that memory block, although the logic behind it would probably be a bit hairy.

Upvotes: 0

Parker Kemp
Parker Kemp

Reputation: 765

A vector is an object containing a pointer to the actual array.

A vector of vectors would be an object with a pointer to an array of objects, each of which points to its own array elsewhere on the heap. So no, they would never be contiguous in the way that you're asking.

Upvotes: 3

Mats Petersson
Mats Petersson

Reputation: 129374

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.

Upvotes: 5

Related Questions