Hands On C++ Lab 13 Exercise

Lab 13: The `list` Class Template

Introduction

We have seen that the vector provides one means of storing a sequence of values provided by the standard template library (STL). STL also provides another container for storing sequences of values called a list. With the exception of subscript (operator[], at()), capacity(), and reserve(), any of the operations that can be applied to a vector can also be applied to a list. If the two containers are this similar, what is the difference between them?

Today's exercise is to explore the differences between these two containers, to understand how they differ, and to identify the circumstances under which each should be used.

To explore the differences, we have designed four timing experiments, in which we will:

compare the time needed to append one value to the end of a list of length n against the time to append one value to the end of vector of length n.
compare the time needed to append n values to the end of an initially empty list against the time to append n values to the end of an initially empty vector.
compare the time needed to prepend n values to the beginning of an initially empty list against the time to prepend n values to the beginning of an initially empty vector.
compare the time needed to prepend one value to the beginning of a list of length n against the time to prepend one value to the beginning of vector of length n.

In each case, the value n will be entered from the keyboard.

The `Timer` Class

To measure the elapsed time in each experiment, we have provided a Timer class stored in the file Timer.h. This class computes time in seconds akin to a stopwatch timer, and can be manipulated via the following operations:

   Timer aTimer;      // construct aTimer as a Timer object

   aTimer.Start();    // start aTimer running

   aTimer.Stop();     // stop aTimer from running

   aTimer.Reset();    // reset aTimer to zero

   cout << aTimer;    // display the value of aTimer

   aTimer.Seconds()   // return the current value of aTimer

The Timer class is built using the clock() function from ctime, an ANSI C library. As such it should be portable to any platform that supports ANSI C. This also means that the Timer class is only as accurate as the underlying C clock() function...

Getting Started

Begin by creating a new directory in which to store your work for this exercise. Make it your working directory, and save copies of Timer.h and Timer.doc (there is no Timer.cpp), and then continue.

Comparing `list` and `vector`

Recall that a statement

   vector<int> aVector(3);

defines aVector as an object capable of storing three int values, and initializes each element to zero. We can visualize such an object as follows:

In this case, the size and the capacity of aVector are both 3.

One key point to understand about a vector is that the elements of a vector are allocated in adjacent memory locations. That is, aVector[0] is physically next to aVector[1], which is physically next to aVector[2], and so on.

By contrast, a statement:

   list<int> aList(3);

preallocates a sequence of linked nodes, consisting of a header node and three additional nodes. These nodes can be anywhere in a program's free store of memory. We can visualize these nodes as follows:

These nodes are connected together using pointers, a special kind of variable that can store the physical address of an object. Each node contains two such pointers: one pointing to the next-node in the sequence, and one pointing to the previous-node in the sequence.

The key thing to understand is this: since they are connected using pointers, the nodes in a list need not be in adjacent memory locations -- they can be anywhere in a program's free store of memory. That is, from aList, we can get to the header node, from its next-node member we can get to the first node, from the next-node member of the first node we can get to the second node, and so on. This means that a list's nodes can be scattered throughout memory and the sequencing of values is determined solely by the next-node and previous-node members of the nodes. By contrast, a vector's elements must be in physically adjacent memory locations -- any value whose index is i must be physically adjacent to the values whose indices are i-1 and i+1.

This difference in adjecent storage vs. non-adjacent storage is the primary difference between the vector and the list, and it is the reason vector has some operations that list does not. For example, because the elements of a vector are stored in adjacent memory locations, the subscript operation can be performed efficiently for a vector. An expression

   aVector[i]

is a simple arithmetic computation that can be done independently of the size of the vector:

   aVector.array + (i * sizeof(int))

By contrast, trying to access the element of a list whose index is i would require that we start at the first node, follow its pointer to the second node, follow its pointer to the third node, and so on until we reach the ith node, an operation that would take time proportional to the size of the list. Because this is so time-consuming compared to the vector, the designers of the list decided to not provide a subscript operation for class list to discourage this sort of "random access" within a list.

The Experiments

Each of the following experiments uses the Timer class to determine the time to perform a given operation on a vector and on a list.

Experiment 1: Appending n Values to an Empty Container

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

Experiment 3: Prepending n Values to an Empty Container

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

Phrases you should now understand:

vector, list, Constant Time, Linear Time, Quadratic Time, Pointer.

Submit:

The graphs you create during this exercise, plus a short essay in which you explain the circumstances under which it is appropriate to store a sequence of values in a vector, as opposed to those in which one should choose a list.

Back to This Lab's Home Page

Back to the Prelab Questions

Forward to the Homework Projects

Lab 13: The list Class Template