STL101 Part B - List and Iterators

Introduction

The idea of this second article is to cover another container, namely std::list, discuss the differences between the two, and from this to discuss the different types of iterators and why they exist.

As with the first article, you can run this by copying the code below and pasting it into a console app. I will be stepping through the code as I explain it, but this allows you to create the project without downloading a zip.

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <functional>

using std::cout;
using std::vector;
using std::endl;
using std::sort;
using std::ostream_iterator;
using std::copy;
using std::back_inserter;
using std::list;
using std::random_shuffle;
using std::back_inserter;

int main(int argc, char* argv[])
{
    list<int> intList;

    int i;
    for (i=0; i < 30; ++i, intList.push_back(i));

    cout << "Print list pushed from back\n\n";

    copy(intList.begin(), intList.end(), ostream_iterator<int>(cout, ", "));

    intList.clear();

    for (i=0; i < 30; ++i, intList.push_front(i));

    cout << "\n\nPrint list pushed from front\n\n";

    copy(intList.begin(), intList.end(), ostream_iterator<int>(cout, ", "));

    std::list<int>::reverse_iterator rit = intList.rbegin();
    std::list<int>::reverse_iterator rend = intList.rend();

    cout << "\n\nPrint list in reverse order using reverse iterators\n\n";

    for(;rit != rend;++rit)
        cout << *rit << ", ";

    // Oops
//    random_shuffle(intList.begin(), intList.end());

    vector<int> vecInt;

    copy (intList.begin(), intList.end(), back_inserter(vecInt));

    cout << "\n\nPrint vector in reverse order\n\n";

    copy(vecInt.rbegin(), vecInt.rend(), ostream_iterator<int>(cout, ", "));

    random_shuffle(vecInt.rbegin(), vecInt.rend());

    cout << "\n\nPrint shuffled vector\n\n";

    copy(vecInt.begin(), vecInt.end(), ostream_iterator<int>(cout, ", "));

    cout << endl;

    return 0;
}

As previously discussed, STL describes containers in terms of performance, not in terms of implementation. However the performance specifications pretty much define what sort of container a vector is, as the only container that offers instant lookup is an array. The problem with an array is the possibility that an insert not at the end will always require recreating the entire array in new memory (and one at the end may do also ) and also that this will invalidate any iterators in memory. A list on the other hand offers the slowest lookup - the only way to find an item in a linked list is to start at one end and keep looking until you find what you want. Adding items and insertions are, however, cheap.

list<int> intList;

int i;
for (i=0; i < 30; ++i, intList.push_back(i));

cout << "Print list pushed from back\n\n";

copy(intList.begin(), intList.end(), ostream_iterator<int>(cout, ", "));

intList.clear();

for (i=0; i < 30; ++i, intList.push_front(i));

cout << "\n\nPrint list pushed from front\n\n";

copy(intList.begin(), intList.end(), ostream_iterator<int>(cout, ", "));

This code creates a list of ints, and shows that we can add items to the start or end of the list, using push_front and push_back. This is in contrast to vector, which requires use of the insert function to add to the front, because like insert, adding to the front is always costly in vector. push_back may not be, if space has been preallocated, either by the user or through the vector's grow policy.

std::list<int>::reverse_iterator rit = intList.rbegin();
std::list<int>::reverse_iterator rend = intList.rend();

cout << "\n\nPrint list in reverse order using reverse iterators\n\n";

for(;rit != rend;++rit)
    cout << *rit << ", ";

One thing I hoped to do with these articles is generate some discussion on STL and learn some things. One thing I learned from the last article, (although it was something I knew in general), is that I can grab both iterators I want to use in a loop before calling the loop. I don't know why it never occurred to me to do this with STL before, I certainly do it every other time. What's the big deal ? Well, I'm saving myself a function call in each iteration.

I've done this in the manner I have to show you reverse iterators. Reverse iterators still step with ++, but they step from back to front.

    // Oops
//    random_shuffle(intList.begin(), intList.end());

random_shuffle, as it's name suggests, puts the items in the container into random order. Uncomment it and try to compile, you'll find it won't work. That is because this algorithm requires a random access iterator. I chose to show this algorithm as a way of highlighting the different iterator types, so now I've set up the contrived example, let's take a look...

There are five iterator types to my knowledge. The first is a forward iterator. As it's name suggests it can only move forward through the container. The second is a bi-directional iterator. This is what list has, and as the name suggests, one can move from an item to the one next or the one prior. Finally, we have random access iterators, such as found in vector. They allow lookup of any item by specifying it's position using an array element syntax. Additionally we have input iterators and output iterators. We've already used an output iterator, to output our container to a stream. As the names suggest, one is for input only, the other for output only. Both these iterator types are Forward Iterators.

The reason then that random_shuffle will not work for a list is that it requires a random access iterator. Each algorithm requires the iterator type that allows for maximum efficiency in the implementation of the algorithm. Some algorithms, such as sort, are replaced by a member function in list, which is a sorting algorithm which takes advantage of the particular layout of a list in order to provide an optimised solution for this container. If your container offers a member function, ALWAYS use it instead of the general solution.

vector<int> vecInt;

copy (intList.begin(), intList.end(), back_inserter(vecInt));

cout << "\n\nPrint vector in reverse order\n\n";

copy(vecInt.rbegin(), vecInt.rend(), ostream_iterator<int>(cout, ", "));

random_shuffle(vecInt.rbegin(), vecInt.rend());

cout << "\n\nPrint shuffled vector\n\n";

copy(vecInt.begin(), vecInt.end(), ostream_iterator<int>(cout, ", "));

Another piece of magic the STL provides via iterators is that containers can be mixed in functions. Here we copy the list into a vector. The copy algorithm is destructive - it assumes that the space exists to insert the items being copied and copies over items already present. The back_inserter adaptor fixes this problem by inserting each element being copied at the end of the container, making space as it goes.

For the sake of the exercise we call random_shuffle on the vector, and sure enough, it works and our items are now in a random order.

STL offers a number of container types and defines them in terms of efficiency so that we can make choices based on the nature of our application. Many algorithms do work with list, and the point of the framework is really that abstraction through the iterator mechanism allows us to copy containers into each other, and to write algorithms once that can be used with many container types. Iterators can be written for any structure that contains data, and the algorithms are then immediately available for that structure. Of course, generalisation should never occur at the cost of efficiency and so the different iterator types are provided and some incompatibilities exist, but without these the framework would not be geared in a way that warns us if we try to take a path that incurs significant performance costs.