Hands On C++ Lab 13 Experiment 2

Experiment 2: Appending 1 Value to a Container of Size n

Save a copy of append2.cpp in your directory. Using your text editor, open append2.cpp and take a few moments to examine what it does. The basic algorithm we want it to perform is as follows:

   0. Read n.
   1. Determine the time to append 1 value to a list of length n:
      a. Define a list of length n.
      b. Define a Timer.
      c. Start the Timer.
      d. Append 1 to the end of the list.
      e. Stop the Timer.
      f. Display the value of the Timer.
   2. Determine the time to append 1 value to a vector of length n:
      a. Define a vector of length n.
      b. Reset the Timer.
      c. Start the Timer.
      d. Append 1 to the end of the vector.
      e. Stop the Timer.
      f. Display the value of the Timer.

append2.cpp contains a partial implementation of this algorithm. Add the necessary statements to append2.cpp to complete the implementation of this algorithm. Then compile and link append2.cpp.

Download and print a clean piece of graph paper. We will again be plotting the time for the values 5000, 10000, 15000, 20000, 25000, 30000, 35000, 40000, 45000 and 50000 (unless your instructor has alternative values for you to use). On the back of your piece of "graph paper," write a sentence or two in which you predict what you will observe, based on your experience in Experiment 1. Label your sentence Prediction.

As before, begin by running the program using the value 50000, to establish the upper bounds, and use these results to establish the scale on your graph's Time axis. Then use your program to generate the times for the remaining values, and add points to the graph for these times, boxing those corresponding to list times, and circling those corresponding to vector times. Add a legend to your graph to indicate which line goes with which object and a title naming the experiment whose results are shown in the graph.

On the back of your piece of graph paper, review your prediction. Write a short paragraph in which you characterize each of these operations as constant, linear or quadratic time, and given any general conclusions you can draw about the time required to append one value to a list of length n compared to the time required to append one value to a vector of length n.

Analysis of Experiment 2

Let's see what just happened. We began with a list of size and capacity n:

   list<int> aList(n);

For simplicity, suppose that n is 3, in which case we have a list like this:

We then called push_back() to append a 1 to aList:

   aList.push_back(1);

To append a 1 to the list, the push_back() operation performs the same three steps it performed in Experiment 1. It:

allocates a new node to store the new value,
stores the value in the node, and
attaches the node to the list using the previous-node pointer in the head node, and updates the size of the list.

As before, the time for these three steps is constant and independent of the number of values in the list. Where we appended n values in Experiment 1 (and thus observed a linear time), we are only appending one value in this experiment (and thus observe a constant time).

That is, where appending n values to an empty list took time proportional to n, appending 1 value to a list of size n takes constant time, regardless of the size of the list.

We then defined a vector of size n:

   vector<int> aVector(n);

If we again consider the case where n is 3, we can visualize aVector as follows:

Since we were preallocating the vector in Experiment 2, the size and capacity of aVector are both 3.

We then call 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 must

allocate a new array that is bigger than the old array (typically by doubling the current capacity):
copy the existing values from the old array to the new array:
place the new value at the next position in the new array:
deallocate the old array:
update the members of aVector:

The times to allocate memory (step 1), store the new value (step 3), deallocate memory (step 4) and update the members of aVector (step 5) are all fairly constant. However, the time to perform the copying in step 2 is proportional to the size of the vector, hence you should have observed a linear time for this operation.

Back to the List of Experiments