# Lab 14: Experiment 2

## Appending One Value to a Container of Size n

### Files

Directory: `lab14`

### The Experiment

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

```theList.push_back(1);
theVector.push_back(1);```
One of these statements is the `Perform the test` statement in the test algorithms.

However, as we saw in the previous experiment, creating a new container comes at a cost. Consequently, in this experiment, we actually have two costs: creating a new container and appending the new element. We really only want to bother with the second operation, so we'll have to ignore the first.

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

Enter the results of this experiment into the spreadsheet that you started for Experiment #1. Since we want to ignore the time that it takes to create a new container (computed in Experiment #1), subtract each result for this experiment from the result you got in Experiment #1 for each value of n. These differences will be the time it takes to do the append. Graph these differences.

### The Analysis

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

Question #14.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 #14.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);`
For simplicity, suppose that `n` is 3, in which case we have a `list` like this:

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

`aList.push_back(1);`
To append a 1 to the `list`, the `push_back()` operation performs these three steps:
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);`
Since the size and capacity of `aVector` are the same, the `push_back()` operation follows these steps:
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 the step that copies the values from the old array to the new array; this copying takes time proportional to n---for each of the `n` values, copy the value into the new array.

Back to the Lab Exercise  |  Forward to the Next Experiment