Hands On C++ Lab 13 Experiment 4

Experiment 4: Prepending 1 Value to a Container of Size n

Save a copy of prepend2.cpp in your directory. Using your text editor, open prepend2.cpp and take a few moments to examine what it does. What we want it to do is as follows:

   0. Read n.
   1. Determine the time to prepend 1 value to a list of size n.
      a. Define a list of size n.
      b. Define a Timer.
      c. Start the Timer.
      d. 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 1 value to a vector of size n.
      a. Define a vector of size n.
      b. Reset the Timer.
      c. Start the Timer.
      d. Insert 1 at the beginning of the vector.
      e. Stop the Timer.
      f. Display the value of the Timer.

Take a few moments to add the necessary statements to make prepend2.cpp reflect this logic.

Compile and link prepend2.cpp, and then download and print a clean piece of graph paper. As before, we will 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 results from the previous 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 to your graph indicating what it 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 1 value to a list of length n compared to the time required to prepend 1 value to a vector of length n.

Analysis of Experiment 4

As we have seen, a statement like

   list aList(3);

preallocates a sequence of three linked nodes, which can be anywhere in a program's free store of memory:

Since the nodes in a list can be anywhere in the program's free store, calling

   insert(aList.begin(), 1);

follows the same three steps we have seen before:

allocates a new node to hold the new value
write the new value to the new node; and
inserts the new node into the list using the head node's next-node member, and updates the size of the list.

We can visualize the result as follows:

As before, these actions require constant time, so the time to insert a value at the beginning of the list is independent of the size of the list.

We then defined a vector of size n:

   vector<int> aVector(n);

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

In order to insert() a 1 at the beginning of a vector whose size and capacity are the same, the insert() operation must:

allocate more space to hold the new value (typically by doubling the capacity of the vector):
copy the existing values one position to the right;
write the new value to the position whose index is 0; and
deallocate the old space, associate aVector with the new space, and update the size and capacity members.

Needless to say, the allocation, copying and deallocation all take time. More precisely, prepending a single value to a vector of size n requires that the n values be copied "out of the way" to make room for the new value. You should thus have observed that this is a linear time operation.

Because such copying is not required for a list, the list is generally superior to a vector for problems that require values to be inserted at the beginning or the middle of the container.

Back to the List of Experiments