C++ Programming: Operations on an Entire List

By Stephen R. Davis

Some C++ programs can deal with data as it arrives and dispense with it. Most programs, however, must store data for later processing. A structure that is used to store data is known generically as a container or a collection. (Many people use the terms interchangeably.)

Beginning programs usually rely heavily on the array for data storage. The array container has a couple of nice properties: It stores and retrieves things quickly. In addition, the array can be declared to hold any type of object in a type-safe way. Weighed against these advantages, however, are two large negatives.

First, you must know the size of the array at the time it is created. This requirement is generally not achievable, although you will sometimes know that the number of elements cannot exceed some “large value.”

Viruses, however, commonly exploit this type of “it can’t be larger than this” assumption, which turns out to be incorrect. There is no real way to “grow” an array except to declare a new array and copy the contents of the old array into the newer, larger version.

Second, inserting or removing elements anywhere within the array involves copying elements within the array. This is costly in terms of both memory and computing time. Sorting the elements within an array is even more expensive.

C++ now comes with the Standard Template Library, or STL, which includes many different types of containers, each with its own set of advantages (and disadvantages).

The C++ Standard Template Library is a very large library of sometimes-complex containers. This session is considered just an overview of the power of the STL.

The STL library defines certain operations on the entire list. For example, the list<T&>::sort() method says “I’ll sort the list for you if you’ll just tell me which objects go first.” You do this by defining operator<(const T&, const T&). This operator is already defined for the intrinsic types and many library classes such as string. For example, you don’t have to do anything to sort a list of integers:

list<int> scores;

The programmer must define her own comparison operator for her own classes if she wants C++ to sort them. For example, the following comparison sorts Student objects by their student ID:

bool operator<(const Student& s1, const Student& s2)
    return s1.ssID < s2.ssID;