CIS Logo SVC Logo

   Computing & Information Systems
   Department

 

Schoology Facebook        Search CIS Site      Tutorials

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, remove them, find their average, find their maximum value, and print them. It also uses template functions in some places and non-template functions in others, 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;

   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.

For removing an item from the list, the following function is used. It is a generic (template) function, designed to handle a list of just about anything. (It is assumed that we can input an item of type T using the >> operator.) The find algorithm is used much like above to locate the item. If it can be found, we use the erase class function to remove it from the list. The iterator p is used to temporarily hold the location of the item to be removed. Note that the version below has been simplified a little by removing the check to see if the list is empty. (It is generally a good idea to see that a list is nonempty before attempting some operation on it.)


template <class T> void Remove(list<T> & L)
   {
   T Target;
   list<T>::iterator p;

   cout << "Enter number to be removed: ";
   cin >> Target;

   p = find(L.begin(), L.end(), Target);
   if (p == L.end())
      cout << "Could not find and remove this item" << endl;
   else
      L.erase(p);
   }

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 approximately as follows:


cout << *max_element(L.begin(), L.end());

No description of the function for printing the list is needed since it is the same as the template function used in the previous example. 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, much like in our function for printing. Here is the function, in slightly simplified form:


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++

Author: Br. David Carlson with contributions by Br. Isidore Minerd
Last updated: August 27, 2009
Disclaimer