Pushing and Popping

Section 13.5 Pushing and Popping

Most work with vectors needs to be done with functions instead of operators.

If you look up documentation for vector on a site like cppreference.com, you will find the functions void vector<T>::push_back(T value) and void vector<T>::pop_back(). The syntax vector<T> is used to indicate “a vector of the type T” where T could be anything - string, int, etc... So vector<T>::push_back says something like “the push_back function for a vector of any type ’T’”.

🔗

These functions can be used to add or remove elements from the end of a vector. push_back(T value) takes a value of the type the vector can contain (type T) and adds it to the end of the vector. pop_back() simply removes the last element.

🔗

vector<int> values = {1, 2, 3};
values.push_back(4);            // now 1,2,3,4
values.push_back(5);            // now 1,2,3,4,5
values.pop_back();              // now 1,2,3,4
values.pop_back();              // now 1,2,3
values.pop_back();              // now 1,2

We pushed integers because values is a vector of integers. If we had a vector of strings, we would push strings instead:

🔗

vector<string> words = {"Hello"};
words.push_back("there");            // now {"Hello", "there"}
words.push_back("world");            // now {"Hello", "there", "world"}

The end of a vector is the “normal” location to add or remove elements due to the way the data is stored. All of the elements of a vector are stored in one contiguous block of memory. We are not allowed to have gaps in the middle. The way that the compiler figures out where a given element is in memory is by doing a calculation that looks like:

🔗

\begin{equation*} \text{address of element} = \text{start address of data} + (\text{index of element} * \text{size of each element}) \end{equation*}

🔗

For example, if the data starts at memory address \(1000\) and each element takes up 4 bytes, the address of the element at index 3 would be calculated as:

\begin{equation*} 1000 + (3 * 4) = 1012 \end{equation*}

🔗

That math assumes that there are no gaps in the data. If there were, we could not just multiply the index by the size of each element to find the address.

🔗

So if we want to remove something from the middle, everything after the removed item needs to shift over to fill in the hole that was made.

🔗

Figure 13.5.1. Removing the 6 from `counts` would require moving the 3 and 14 over to fill the gap.
🔗

Similarly, to insert something in the middle, we would first need to move all of the elements after that point over to make room for the new element before we insert it.

🔗

This is much slower, especially in a long vector. So to encourage us to add and remove elements at the end, there is only pop_back() and push_back and not a pop_front() or pop_middle().

🔗

Checkpoint 13.5.1.

Which BEST explains why it is generally more efficient to add or remove elements from the end of a vector rather than the beginning or middle?

🔗

Because all the data in a vector is stored in one contiguous block of memory.
Because it is easier to calculate the position of elements at the end.
Because the beginning and middle of a vector are read-only.
Because the end of a vector is stored in a special location in memory.

🔗

Checkpoint 13.5.2.

Given this sequence of operations, what would nums contain?

🔗

vector<int> nums;
nums.push_back(8);
nums.push_back(3);
values.pop_back();
nums.push_back(5);
nums.push_back(4);
values.pop_back();
nums.push_back(9);

8 5 9
9 5 8
3 5 9
9 3 5

🔗

Checkpoint 13.5.3.

Given this sequence of operations, what would nums contain?

🔗

vector<int> nums;
nums.push_back(2);
nums.push_back(4);
nums.push_back(3);
values.pop_back();
values.pop_back();
nums.push_back(1);

2 1
1 2
3 1
1 3

🔗

You have attempted of activities on this page.

🔗

Prev Top Next