CS 1124 — Object Oriented Programming

The STL container class: list

Brief notes on what we can do with an STL list.

First what do we have to do to make the STL linked list template class available?

• Include the appropriate header. Most of the STL containers each have their header file:
  #include <list>
• Since the list template is defined in the std namespace, as usual we have to either modify each occurence with "std::" or alternatively we can write:
  using namespace std;

Now what can we do with a list? First we can declare and construct it. STL containers (including lists) provide a number of constructors:

• Default constructor. Creates an empty list.
  list<int> myList;
• Copy constructor. Copies are made of all the items in myList.
  list<int> anotherList(myList);
• A specified size and item. You can create a list of any size and all the elements will be initialized to the item that you provide with. Below we define a list of eight integers that are all initialized to the value 5..
  list<int> myOtherList(8, 5);
• A specified size. We can create a list of a dozen Elephants, all initialized from the default constructor with:
  list<Elephant> myListofElephants(12);
• From a range of elements. Here we use iterators. Iterators act much like pointers. To construct a list from a range, we have to provide an iterator that refers to the first element in the range and a second iterator refering to the location just after the last element we want. Below we'll use an array of ints to initialize a list.
  int arr[] = {2, 3, 5, 8, 13, 21};
list<int> listOfInts(arr, arr + 6);

We can do a number of other things with our lists through member functions and overloaded operators:

• Compare them. All the comparison operators (such as <, ==, etc.) work for lists:
  if (listOfInts == myOtherList) // do something or other...
• Clear the list. That means delete all the elements from the list.
  listOfInts.clear()
• Reverse the list:
  listOfInts.reverse();
• Add elements at the beginning or end:
  listOfInts.push_front(17); // adds a new element, 17, to the front of the list
listOfInts.push_back(17); // adds a new element, 17, to the back of the list

To do much of anything else with our lists we will have to be able to get iterators to access the elements in the list. How do we declare an iterator? And what can we initialize it to? First the declaration. The type "iterator" is actually a sub-type of its container class. What does that mean? When we declare a variable to be an iterator we have to say what kind of container it is an iterator for. Much as pointers have to be declared based on what kind of thing they point to. For an iterator to a list of ints, we could say:

list<int>::iterator myIterator;

Now to make that iterator refer to something. The easiest thing to start with is the beginning of a list. the list class has a method called begin() that returns an iterator to the start of the list.

myIterator = listOfInts.begin();

Another method that returns an iterator is end(). That does not refer to the last element in the list. Instead it refers to a location beyond then end of the list. What do we use end() for? To check when we've finished with the list. We'll look at an example in a moment, but first we need to be able to do two other things with an iterator.

• How do we move our iterator from one element in the list to the next? The increment operators! Both pre-increment and post-increment will work with our interators.
  myIterator++
++myIterator
• How do we get the data that the iterator is referring to? The dereferencing operator:
  *myIterator

Putting it all together we can construct a loop to print out the contents of a list:

for (list<int>::iterator i = listOfInts.begin(); i != listOfInts.end(); ++i)
     cout << *i << endl;

The loop shown above

1. declares an iterator that can point to items in a list of ints,
2. intializes it to point to the beginning of the list called listOfInts,
3. checks to make sure that the iterator is not pointing off the end of the list,
4. enters the body of the loop to print the element (by dereferencing the iterator)
5. and uses the increment operator to move to the next item in the list, before looping back to step 3.

A couple of important points to remember. First, note that we compare list iterators by checking for == or for !=. Never check for "less than" or any other such inequality to compare list iterators.

Second, we use the increment operator to move from one item to the next. We couldn't do this if we were using pointers in a linked list because the memory used for a list isn't contiguous, instead it may be spread all over and so incrementing with a Node pointer is likely to leave you pointing to some totally unrelated area of memory. But iterators are a special type and using the increment operator has been made to work for them.

With iterators, we can do other things with lists. One important advantage of lists is that is easy and quick to add elements anywhere into a list. There are a few functions that help us, such as the member function insert(). The code below sets an iterator first to the beginning of the list, then increments it to point to the second element. Finally, it inserts a new element just before the second element, so that now 28 is the second element of the list.

list<int>::iterator i = listOfInts.begin();
i++;
listOfInts.insert(i, 28);

It's just as important that we can remove elements. If we want to get rid of the first occurence of 13 in the list, we would first find the item and then erase it. Finding something is a generic operation, which we will talk about more below. Erasing is a member function of the container class. Note that we first need to make sure that we actually did find what we were looking for.

list<int>::iterator where = find(listOfInts.begin(), listOfInts.end(), 13);
if (where != listOfInts.end()) listOfInts.erase(where);

On the other hand, if we want to get rid of all occurences of 13, that's easier. There is a method in the list class that does that!

listOfInts.remove(13); // removes all occurences.

Sorting a list is also done with a member function. The line of code below shows how to sort the whole list.

listOfInts.sort();

The items in the list will be sorted based on the less-than operator for the data that the list holds.

Another way of inserting elements into a list is splicing. The splice member function takes elements out of one container and adds them to another. This is a somewhat unusual function because it has to know not only the range of of elements to splice into, but the container that they come from. The function takes four arguments:

• An iterator to the element to insert the elements before.
• The container holding the elements being inserted.
• Start and end iterators for the range of elements being inserted.

Algorithms

Now that we have iterators we can do lots of other things. In addition to writing loops such as the one above or calling member functions that need iterators, we can also make use of the third major portion of the STL, generic algorithms (the first portion being the containers and the second the iterators). To be able to use the algorithms below, we need to include the appropriate header:

#include <algorithm>

What can we do now? Many more things than we can reasonably talk about here. We'll mention a few. For most generic algorithms the first two arguments are iterators indicating the beginning and the end of the range that the function will act on. Note especially that these functions never know what kind of container they are operating on. They only have the iterators to look at, not the containers.

• find: returns an iterator pointing to the first occurence of the target. If the target is not found, then the function returns its second argument, which is the iterator to end at.
  list<int>::iterator i = find(listOfInts.begin(), listOfInts.end(), 17);
• count: returns a count of elements in the range matching the target. The line below should determine how many times 17 appears in listOfInts.
  int total = count(listOfInts.begin(), listOfInts.end(), 17);
• copy: copies the elements from the starting range (the first two arguments) into a range starting at the third argument. This is a particularly powerful algorithm because the source and the target of the algorithm don't have to be the same type of container. You can copy from a list to an array, or from a vector to a list, or... Of course the elements in the containers have to all be the same type. Warning: you have to make sure that there is enough room in the target container (i.e., the one that you are copying to). copy does not make any checks. It is fast and simple.
  copy(listOfInts.begin(), listOfInts.end(), anArrayOfInts);

Home

Maintained by John Sterling (jsterling@poly.edu). Last updated January 23, 2011