Directory: lab14
append1.cpp
implements this experiment.Timer.h
, and Timer.doc
implements
the timer required by all experiments (there is no Timer.cpp
).For this experiment, the test is to append just one value to the end of an existing container:
theList.push_back(1); theVector.push_back(1);One of these statements is the
Perform the test
statement
in the test algorithms.
However, as we saw in the previous experiment, creating a new container comes at a cost. Consequently, in this experiment, we actually have two costs: creating a new container and appending the new element. We really only want to bother with the second operation, so we'll have to ignore the first.
Compile and run the program on the sample range of n.
Enter the results of this experiment into the spreadsheet that you started for Experiment #1. Since we want to ignore the time that it takes to create a new container (computed in Experiment #1), subtract each result for this experiment from the result you got in Experiment #1 for each value of n. These differences will be the time it takes to do the append. Graph these differences.
Using the categories in Experiment #1 and your new graph, answer these questions:
Question #14.2.1: How would you categorize the time it takes to append one value to the
end of a list
of size n? Justify your answer.
Question #14.2.2: How would you categorize the time it takes to append one value to
the end of a vector
of size n? Justify your
answer.
Let's explore what's going on behind the scenes.
list
The program begins with a list
of size n
:
list<int> aList(n);For simplicity, suppose that
n
is 3, in which case we have
a list
like this:
The program then calls push_back()
to append a 1 to aList
:
aList.push_back(1);To append a 1 to the
list
, the push_back()
operation
performs these three steps:
list
by first going through the
previous-node pointer in the head node and updating the pointers in
the header node, the last node, and the new node. Finally it
updates the size of the list
, and we end up with this:
The time for these three steps is independent of the number of
values in the list; it doesn't matter how large the list
is
to begin with; adding one more always takes the same amount of time.
vector
The program also defines a vector
of size n:
vector<int> aVector(n);
When a vector
is declared this way, the size and capacity are
the same. So if we again consider the case where n is 3, we
can visualize aVector
as follows:
The program then calls push_back()
to append a single value
to this vector
:
aVector.push_back(1);Since the size and capacity of
aVector
are the same, the
push_back()
operation follows these steps:
aVector
:
All of these steps take constant time except for the step that copies
the values from the old array to the new array; this copying takes
time proportional to n---for each of the n
values,
copy the value into the new array.