Lab 13: Experiment 2

Appending One Value to a Container of Size n

Files

• append1.cpp implements this experiment.
• Timer.h, and Timer.txt implement the timer required by all experiments (there is no Timer.cpp).

The Experiment

For this experiment, the test is to append a single value to the end of an existing container:

theList.push_back(1);
theVector.push_back(1);

As we saw in the previous experiment, creating a new container takes time. This means that in this experiment, we actually have two times: creating a new container and appending the new element. Because we only wanted to measure the time for the second operation, we'll ignore the first.

Compile and execute the program on the sample range of n.

Enter the results of this experiment into the spreadsheet that you started for Experiment #1. Because we want to ignore the time that it takes to create a new container, subtract the result you got from Experiment 1 from these results for each n. These values will be the time it takes to do the append operation. Graph them.

The Analysis

Using the categories in Experiment #1 and your new graph, answer these questions:

Question #13.2.1: How would you categorize the time it takes to append one value to the end of a list of size n? Justify your answer.

Question #13.2.2: How would you categorize the time it takes to append one value to the end of a vector of size n? Justify your answer.

Let's explore what's going on behind the scenes.

The list

The program begins with a list of size n:

list<int> aList(n);

The program then calls push_back() to append a 1 to aList:

aList.push_back(1);

1. It allocates a new node to store the new value:
2. It stores the value in the node:
3. It attaches the node to the list by first going through the previous-node pointer in the head node and updating the pointers in the header node, the last node, and the new node. Finally it updates the size of the list, and we end up with this:

The time for these three steps is independent of the number of values in the list; it doesn't matter how large the list is to begin with; adding one more always takes the same amount of time.

The vector

The program also defines a vector of size n:

vector<int> aVector(n);

When a vector is declared this way, the size and capacity are the same. So if we again consider the case where n is 3, we can visualize aVector as follows:

The program then calls push_back() to append a single value to this vector:

aVector.push_back(1);

1. It allocates a new array that is bigger than the old array (typically by doubling the current capacity):
2. It copies the existing values from the old array to the new array:
3. It places the new value at the next position in the new array:
4. It deallocates the old array:
5. It updates the array of aVector:

All of these steps take constant time except for Step 2. This copying takes time proportional to n because for each of the n values, we must copy the value into the new array.