Click here to Skip to main content
12,511,544 members (52,164 online)
Click here to Skip to main content
Add your own
alternative version

Stats

164.1K views
30 bookmarked
Posted

STL101 Part B - List and Iterators

, 24 Feb 2002
Rate this:
Please Sign up or sign in to vote.
My second STL article covers std::list and discusses different iterator types
<!-- Add the rest of your HTML here -->

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Christian Graus
Software Developer (Senior)
Australia Australia
Programming computers ( self taught ) since about 1984 when I bought my first Apple ][. Was working on a GUI library to interface Win32 to Python, and writing graphics filters in my spare time, and then building n-tiered apps using asp, atl and asp.net in my job at Dytech. After 4 years there, I've started working from home, at first for Code Project and now for a vet telemedicine company. I owned part of a company that sells client education software in the vet market, but we sold that and I worked for the owners for five years before leaving to get away from the travel, and spend more time with my family. I now work for a company here in Hobart, doing all sorts of Microsoft based stuff in C++ and C#, with a lot of T-SQL in the mix.

You may also be interested in...

Pro
Pro

Comments and Discussions

 
Generalgood~~ Pin
areaofgod27-Jun-07 10:09
memberareaofgod27-Jun-07 10:09 
General&#19981;&#38169; Pin
akinwzh29-Nov-06 23:53
memberakinwzh29-Nov-06 23:53 
GeneralRe: ?? Pin
Christian Graus30-Nov-06 0:11
staffChristian Graus30-Nov-06 0:11 
GeneralRe: ?? Pin
ken_tompson16-Oct-07 17:03
memberken_tompson16-Oct-07 17:03 
GeneralUsing STL in MFC Application projects Pin
Anonymous20-Aug-03 8:57
sussAnonymous20-Aug-03 8:57 
GeneralRe: Using STL in MFC Application projects Pin
Christian Graus20-Aug-03 11:14
memberChristian Graus20-Aug-03 11:14 
GeneralRe: Using STL in MFC Application projects Pin
Anonymous20-Aug-03 16:19
sussAnonymous20-Aug-03 16:19 
GeneralCould you add explanation on insertion Pin
Anthony_Yio18-Aug-03 17:52
memberAnthony_Yio18-Aug-03 17:52 
GeneralRe: Could you add explanation on insertion Pin
Christian Graus18-Aug-03 17:53
memberChristian Graus18-Aug-03 17:53 
QuestionAnd if we want to keep a list sorted? Pin
Nemanja Trifunovic25-Feb-02 5:51
memberNemanja Trifunovic25-Feb-02 5:51 
AnswerRe: And if we want to keep a list sorted? Pin
Jörgen Sigvardsson25-Feb-02 6:06
memberJörgen Sigvardsson25-Feb-02 6:06 
GeneralRe: And if we want to keep a list sorted? Pin
Nemanja Trifunovic25-Feb-02 6:24
memberNemanja Trifunovic25-Feb-02 6:24 
GeneralRe: And if we want to keep a list sorted? Pin
Sasha Djurovic25-Feb-02 6:50
memberSasha Djurovic25-Feb-02 6:50 
GeneralRe: And if we want to keep a list sorted? Pin
Christian Graus25-Feb-02 8:49
memberChristian Graus25-Feb-02 8:49 
GeneralRe: And if we want to keep a list sorted? Pin
Sasha Djurovic25-Feb-02 13:25
memberSasha Djurovic25-Feb-02 13:25 
GeneralRe: And if we want to keep a list sorted? Pin
Jörgen Sigvardsson25-Feb-02 8:23
memberJörgen Sigvardsson25-Feb-02 8:23 
GeneralRe: And if we want to keep a list sorted? Pin
Nemanja Trifunovic25-Feb-02 9:18
memberNemanja Trifunovic25-Feb-02 9:18 
GeneralRe: And if we want to keep a list sorted? Pin
Jörgen Sigvardsson25-Feb-02 10:04
memberJörgen Sigvardsson25-Feb-02 10:04 
GeneralRe: And if we want to keep a list sorted? Pin
Nemanja Trifunovic25-Feb-02 10:13
memberNemanja Trifunovic25-Feb-02 10:13 
GeneralRe: And if we want to keep a list sorted? Pin
Jörgen Sigvardsson25-Feb-02 10:31
memberJörgen Sigvardsson25-Feb-02 10:31 
GeneralRe: And if we want to keep a list sorted? Pin
Tim Smith25-Feb-02 11:28
memberTim Smith25-Feb-02 11:28 
GeneralRe: And if we want to keep a list sorted? Pin
Jörgen Sigvardsson25-Feb-02 20:11
memberJörgen Sigvardsson25-Feb-02 20:11 
GeneralRe: And if we want to keep a list sorted? Pin
Christian Graus25-Feb-02 8:08
memberChristian Graus25-Feb-02 8:08 
GeneralRe: And if we want to keep a list sorted? Pin
Jörgen Sigvardsson25-Feb-02 8:45
memberJörgen Sigvardsson25-Feb-02 8:45 
GeneralRe: And if we want to keep a list sorted? Pin
Christian Graus25-Feb-02 8:54
memberChristian Graus25-Feb-02 8:54 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.160929.1 | Last Updated 25 Feb 2002
Article Copyright 2002 by Christian Graus
Everything else Copyright © CodeProject, 1999-2016
Layout: fixed | fluid