Software Design Using C++
STL: Lists
The General Concept
Lists in the STL are essentially doubly-linked lists. That is, one can
traverse them (using iterators) in either the forward or backward direction.
A wide range of class functions is available, as well as the algorithms that
can be applied to any STL container. In addition, a number of comparison
operators can be applied to lists, such as == and <.
Examples
The First Example
The list.cpp example is a fairly simple one.
Note that it includes the header files list and
algorithm . The first one obviously is for use of the STL's lists.
The second is needed because we use the foreach algorithm.
The main function begins by creating a list of characters
and placing items at the end using code like the following:
list<char> L;
L.push_back('A');
|
We next print the list in two ways. One way is to use a generic (template)
function. A slightly simplified version of this function is shown below.
It uses an iterator which runs through each item of the list from start to
end. Each item pointed to along the way is printed.
template <class T> void PrintA(list<T> & L)
{
list<T>::iterator p;
for (p = L.begin(); p != L.end(); p++)
cout << *p << " ";
}
|
Another way to print is to use the foreach algorithm. It is used
to execute a function on each item in a given range (here the entire list).
The range to use is specified by using an iterator to the starting location
as the first parameter and an iterator to one past the ending location as
the second parameter. The function to be executed for each item is supplied
as the third parameter to foreach . Here is the code, simplified
a little for clarity:
void PrintItem(char Item)
{
cout << Item << " ";
}
|
void PrintB(list<char> & L)
{
for_each(L.begin(), L.end(), PrintItem);
}
|
The Second Example
The second example, list2.cpp,
is an interactive program that allows the user to insert integers into
a list, sort them, find their average, find their
maximum value, and print them. It also uses a template function in one
place and non-template functions in other places, just to show some of the
variety of what can be done.
For adding new numbers to the list, it has both push_back ,
to push an item onto the end, and push_front to insert an
item at the front of the list. To insert an item before an existing one
in the list, the following function is used, shown in slightly simplified
form. Note that it is not a generic function since the parameter is fixed
as a list of integers. It could be rewritten as a generic function that
would handle a list of items of some arbitrary type T.
void InsertBefore(list<int> & L)
{
int Item, Target;
list<int>::iterator p;
Item = GetNum();
cout << "Insert this number before what number? ";
cin >> Target;
cin.get();
p = find(L.begin(), L.end(), Target);
if (p == L.end())
cout << "Could not find this number, so no insertion";
else
L.insert(p, Item);
}
|
Note the use of the find algorithm to locate the number before
which to insert. The first parameter to this algorithm is where to start in
the list, while the second parameter is (one past) the stopping location
for the search. If the find algorithm returns an iterator to
this latter location, that means that the target item could not be found.
If the target is found, the insert class function is used to
place the new item before the target.
Sorting of the list is accomplished by using the sort class
function. The syntax is simply L.sort(). You might wonder why we do not
use the sort algorithm. The reason is that although it works for
many of the container classes, it does not work for lists! That is because
the sort algorithm only works on containers for which we can
specify a range using what are called random access iterators.
These iterators allow you to jump around within the container (as with a
vector). A list only allows use of bidirectional iterators, ones
that let you go forward or backward in the list. For this reason, then,
the standard sort algorithm is not available.
To find the maximum value in the list, the max_element algorithm
is used. It takes as parameters the usual two iterators to specify the range
to be considered and returns an iterator to the largest item. In the example
program the * is used to get the value pointed to by this
iterator. The code is as follows:
cout << *max_element(L.begin(), L.end());
|
The function for printing the list is short, so let's skip over that.
However, let's take a brief look at the function used to find the average of the
numbers in the list. This is not a generic function. In fact, it would
not make sense to try to average a list of characters or something similar.
So, this function was designed to handle a list of integers only. Note how
convenient it is to have a size class function with which to
look up the size of the list. The total of the list items is accumulated by
stepping through the items with an iterator. Here is the function:
void Average(list<int> & L)
{
int Count;
float Sum;
list<int>::iterator p;
Count = L.size();
if (Count == 0)
cout << "No average can be found; list empty" << endl;
else
{
Sum = 0.0;
for (p = L.begin(); p != L.end(); p++)
Sum = Sum + *p;
cout << "Average is " << Sum / Count << endl;
}
}
|
Further Information
Should you wish to make a list of objects belonging to a class that you
have designed, note that you will have to provide overloaded operators
(such as ==, !=, <, and >) for objects of your class. The exact operators
that have to be overloaded is likely to be compiler-dependent. The STL
needs these comparison operators because it contains routines that sort
and search through a list of these objects.
There is, of course, much more that can be done with lists. See the
references for more information.
Related Item
Linked Lists Intermediate Topic.
Back to the main page for Software Design Using C++
|