Lab 14: Experiment 4

Prepending One Value to a Container of Size n

Files

Directory: lab14

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

The Experiment

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

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

As seen in Experiment #1 and as dealt with in Experiment #2, we know that the time to create a container must be considered. So, as in Experiment #2, we have two costs: creating a new container and prepending the new element.

Compile and run the program 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 #14.4.1: How would you categorize the time it takes to prepend one value to the beginning of a list of size n? Justify your answer.

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

It's again time 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 experiment, the time to insert a value at the beginning 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 beginning 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.