prepend1.cpp
implements this experiment.Timer.h
, and Timer.txt
implement
the timer required by all experiments (there is no Timer.cpp
).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 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.
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.
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:
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
.
vector
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 vector
whose
size and capacity are the same, the insert()
function follows
these steps:
vector
): 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.