CODEWITHSUNDEEP
c++stdvector
Martinsos
Martinsos

Reputation: 1693

Can vector of vectors get reallocated because one of elements got reallocated?

Lets say I have a vector of vectors:

vector< vector<int> > table;

I know that vector can get reallocated if it doesn't have sufficient capacity.
I am wondering if there is a possibility of vector table reallocating if I do this:

table[i].resize(1000);

Is it possible that reallocation of table[i] also reallocates table?

Upvotes: 6

Views: 464

Answers (5)

didierc
didierc

Reputation: 14730

No, it won't have any incidence: the implementation of vectors is based on an array in most case (it's pretty much the idea of vectors), though this is not set in stone in the language specification. At any rate, the dynamic nature of vectors precludes any form of sequence inlined in the data structure, ie. the sequence of elements managed by the vector class cannot be inside the vector class, but is necessarily a chunck of memory located elsewhere, with a pointer in the class.

Your datatype is therefore similar to a dynamic array of pointers to dynamic arrays. Reallocating one pointed array will not have an effect on the pointer array.

Upvotes: 4

user334856
user334856

Reputation:

No. This will not cause a reallocation in table.

The only operator/function called on table is the [] operator, which promises constant time. If re-allocation happened, this would violate the constant time promise.

The reason why you can change the vector size of the sub-vectors (the table[i]s) without requiring additional space to be allocated in the top-level vector is a vector's storage is managed via a pointer to a block of memory. Thus, increasing the amount of elements that a vector uses doesn't actually change the size of the vector object.

table[i].size() changes without changing sizeof(table[i]).

Upvotes: 6

Kerrek SB
Kerrek SB

Reputation: 476970

No, that can't happen. resize doesn't change the size of the vector object – it only changes the dynamic storage that the vector manages. So from the point of view of the outer vector, all the elements remain unchanged (and have the same, small size).

Upvotes: 1

nullptr
nullptr

Reputation: 11058

No. Calling a method of a vector's element wouldn't affect the vector itself.

Consider this as the following call: parent_object.child_object.Method(), where child_object knows nothing about the parent_object. The Method() cannot change state of parent_object.

The same goes for the vector of vectors. (Technically, here you are storing an array of pointers to arrays. Resizing one of the child arrays is a local operation and changes the appropriate pointer, but doesn't change the size of parent array.)

Upvotes: 1

Zdeslav Vojkovic
Zdeslav Vojkovic

Reputation: 14581

No, because the content of table is unchanged - it still contains exactly the same instances as before. Only the storage of table[i] needed to be reallocated. vector contains a pointer to the storage - the size of vector object is always the same, only the referenced array can grow or shrink. Therefore, table[i] is not growing, if that's what you ask - only the array it points to is.

Upvotes: 1

Related Questions