prepend1.cppimplements this experiment.
Timer.txtimplement the timer required by all experiments (there is no
For this experiment, the test is to prepend one value at the front of an existing container:
ThetheList.insert(theList.begin(), 1); theVector.insert(theVector.begin(), 1);
Perform the teststep 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
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 #13.4.1: How would you categorize the time it takes to prepend one value at the front of a
listof 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
vectorof size n? Justify your answer.
It's time again 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
x experiment, the time to insert a value at the front of the
list is independent of the size of the
The program defines a
vector of size n:
If n is 3, the situation is as follows:vector<int> aVector(n);
In order to insert a 1 at the front 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.