Lab 13: Experiment 4

Prepending One Value to a Container of Size n

Files

• prepend1.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 prepend one value at the front of an existing container:

theList.insert(theList.begin(), 1);
theVector.insert(theVector.begin(), 1);

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 lists and vectors.

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);

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.