# Lab 13: Experiment 4

## Prepending One Value to a Container of Size n

### The Experiment

For this experiment, the test is to prepend one value at the front of an existing container:

```theList.insert(theList.begin(), 1);
theVector.insert(theVector.begin(), 1);```
The `Perform the test` step is one of these statements.

As we saw in Experiment #1 and dealt with in Experiment #2, the time to create a container must be considered. So, once again, we have two costs to consider: creating a new container and prepending the new element.

Compile and execute `prepend1.cpp` on the sample range of n.

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

### The Analysis

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

Question #13.4.1: How would you categorize the time it takes to prepend one value at the front of a `list` of size n? Justify your answer.

Question #13.4.2: How would you categorize the time it takes to prepend one value at the front of a `vector` of size n? Justify your answer.

It's time again to look at the difference between `list`s and `vector`s.

#### The `list`

Consider these statements:

```list<int> aList(3);
aList.insert(aList.begin(), 1);```

The declaration preallocates a sequence of three linked nodes, which can be stored anywhere in a computer's memory:

The call to `insert()` follows the same three steps we have seen before with only one minor difference:

1. It allocates a new node to hold the new value.
2. It writes the new value to the new node.
3. It inserts the new node into the list using the head node's next-node pointer, and updates the size of the list.

In Experiment #2, the append operation differed only in what pointer we followed from the header node. As in that same x experiment, the time to insert a value at the front of the `list` is independent of the size of the `list`.

#### The `vector`

The program defines a `vector` of size n:

`vector<int> aVector(n);`
If n is 3, the situation is as follows:

In order to insert a 1 at the front of a `vector` whose size and capacity are the same, the `insert()` function follows these steps:

1. It allocates more space to hold the new value (typically by doubling the capacity of the `vector`):
2. It copies the existing values one position to the right:
3. It writes the new value to the position whose index is 0:
4. It deallocates the old space, associates `aVector` with the new space, and updates the size and capacity attributes:

Again, it's the copying step that consumes the most time, making the prepend a linear-time operation.

Back to the Lab Exercise  |  Forward to the Next Experiment