Hands On C++ Lab 13 Experiment 3

Experiment 3: Prepending n Values to an Empty Container

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

   0. Read n
   1. Determine the time to prepend n values to an empty list:
      a. Define an empty list.
      b. Define a Timer.
      c. Start the Timer.
      d. For each value iin the range 0..n-1:
           Insert 1 at the beginning of the list.
      e. Stop the Timer.
      f. Display the value of the Timer.
   2. Determine the time to prepend n values to an empty vector:
      a. Define an empty vector.
      b. Reset the Timer.
      c. Start the Timer.
      d. For each value iin the range 0..n-1:
            Insert 1 at the beginning of the vector.
      e. Stop the Timer.
      f. Display the value of the Timer.

Compile and link prepend1.cpp, and download and print a clean piece of graph paper. As before, we will be plotting the times 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 results from the previous two experiments. Label your sentence Prediction.

As before, begin by running the program using the value 50000, and use the 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 describing what the graph shows.

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 prepend n values to an empty list compared to the time required to prepend n values to an empty vector.

Analysis of Experiment 3

Let's use the preceding information to see what happened in Experiment 3. We began with an empty list:

   list<int> aList;

which we saw before looks like this:

We then used insert() to prepend a value to this list:

   insert(aList.begin(), 1);

and repeated this operation n times. Similar to what we saw in Experiment 1, the insert() function simplistically:

allocates a new node to store the new value:
stores the value in the node:
attaches the node to the list using the next-node member of the head node (since this always points to the first node), and updates the size of the list:

By specifying that insert() insert the new value at aList.begin(), the effect is to tell insert() to perform the insertion just after the head node. (In fact, the list::begin() function member simply returns the value of the head node's next-node member.)

It follows that appending one value always takes these three steps, so that an insert() takes constant time for a list. If prepending one value takes constant time, prepending n values should take time proportional to n, or linear time, which should be what you observed in this experiment.

Let's compare what happens when the insert() is used on a vector. We began with an empty vector:

   vector<int> aVector;

which we have seen looks like this:

We then used insert() to prepend n values to it:

   insert(aVector.begin(), 1);

and called this function n times.

It should be evident that the insert() operation must increase the size of aVector to make room for the new value. However, where push_back() could allocate more memory than needed and leave the trailing elements empty, insert() cannot leave the initial elements of a vector empty, or else an expression like

   aVector[0]

will no longer access the first value in the vector. Instead, insert() must:

allocate a new array that is one larger than the previous one:
copy the values from the old array forward one position in the new array:
store the new value at position 0 in the new array:
deallocate the old array:
update the members of aVector:

It should be evident that having to copy the n values means that inserting one value has linear timer.

However, unlike push_back(), insert() is unable to preallocate more space than is immediately necessary. As a result, every call to insert() at the beginning of the vector must copy n values to make room for the new value. Put differently, each pass through our loop calls insert() which must copy n values, and since our loop runs n times, the entire operation requires time proportional to n^2. Inserting n values at the beginning of a vector is thus a quadratic time operation, as you should have experienced.

As you experienced, quadratic time operations are very expensive, and should be avoided whenever possible. For this reason, problems that involve any significant number insertions at any position other than the end of the container should be done using the list, not the vector. (Of course, if the problem requires "random access" to the container's values, then that forces you to use the vector, since the subscript operation is not defined for the list.)

Back to the List of Experiments