One question about vector push_back

Question

I just noticed that for vector push_back it is push back a reference to the element.

void push_back ( const T& x );

My question is does the memory layout changed after push_back?

For example, I have an array first which containing five elements and the layout is like this.

|          |          |          |          |          |              
|   A1     |     A2   |   A3     |    A4    |    A5    |

Now I have a vector v

v.push_back(A3)

Now, how does the memory look like?

How does the vector store the elements here?

How does the vector access the element?

Answer 1

A vector stores by value not by reference.

When you re-add the same element, a copy will be stored at the end. If you do not want to make a copy of the values you are inserting into the vector, then you should use pointers instead.

Example:

std::vector<std::string> v;
string s = "";
v.push_back(s);
s = "hi";
v.push_back(s);

v now contains 2 different elements, one with an empty string, and one with a string which contains "hi". Both strings in the vector remain independent from s.

Note: The internal implementation details of an STL container can vary, there is no guarantee that it will be implemented a certain way; however, the semantics of how an STL container works, will remain the same no matter what the internal implementation is.

Answer 2

|   A1     |     A2   |   A3     |    A4    |    A5    |   A3     |

The elements (like everything in the STL) are stored by value.

Vectors access elements just like built-in arrays.

Answer 3

Now, how does the memory look like? and How does the vector store the elements here?

There are two possible outcomes:

1. The vector's memory block is not large enough to contain the items, therefore the underlying memory is reallocated. Objects are copied (using their copy constructors) to their new locations. Then the push_back'd object is copied (by value) to the end.
2. The vector's memory block is large enough, new elements are copied (by value) to the end.

How does the vector access the element?

The same way you access a C-style array. BasePointer + index * sizeof(type)

Answer 4

vector::push_back accepts a reference and then reads the value at the reference to copy it into the vector.

So the resulting vector would be

| A3 |

Note that when the vector is resized to accommodate the new data, it may move the old data to a new location, invalidating old references into it. So if the list A1, A2, … A5 is v,

v.push_back(A3)

will invalidate A3 as A3 references data inside v. The only way to keep a handle to data inside a vector as it grows is to save the index; references, pointers, and iterators will not do.