prepend1.cppimplements this experiment.
Timer.docimplements the timer required by all experiments (there is no
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);The
Perform the teststep is just one of these statements.
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.
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
listof 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
vectorof size n? Justify your answer.
It's again time to look at the difference between
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:
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
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 beginning of a
size and capacity are the same, the
insert() function follows
aVectorwith 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.