linuxgazette.net Open in urlscan Pro
209.59.180.101  Public Scan

Form analysis
0 forms found in the DOM

Text Content

"LINUX GAZETTE...MAKING LINUX JUST A LITTLE MORE FUN!"



--------------------------------------------------------------------------------




INTRODUCTION TO STL, STANDARD TEMPLATE LIBRARY

BY SCOTT FIELD



--------------------------------------------------------------------------------

This article is about a new extension to the C++ language, the Standard Template
Library, otherwise known as STL.

When I first proposed the idea of an article on STL, I must say I somewhat
underestimated the depth and breadth of the topic. There is a lot of ground to
cover and there are a number of books describing STL in detail. So I looked at
my original idea and refocussed. Why was I writing an article and what could I
contribute? What would be useful? Was there a need for another STL article.

As I turned the pages of Musser and Saini I could see programming time
dissolving in front of me. I could see late nights disappearing, and on target
software projects reappearing. I could see maintainable code. A year has passed
since then and the software I have written using STL has been remarkably easy to
maintain. And shock horror, other people can maintain it as well, without me!

However, I also remembered that at the beginning it was difficult wading through
the technical jargon. Once I bought Musser & Saini everything fell into place
but before that it was a real struggle and the main thing I yearned for was some
good examples.

Also the third edition of Stroustrup which covers STL as part of C++ was not out
when I started.

So I thought it might be useful to write an article about real life use of STL
for new STL programmers. I always learn faster if I can get my hands on some
good examples, particularly on new subjects like this.

The other thing is, STL is supposed to be easy to use. So theoretically we
should be able to start using STL straight away.

What is STL? STL stands for the Standard Template Library. Possibly one of the
most boring terms in history, for one of the most exciting tools in history. STL
basically consists of a bunch of containers - lists, vectors, sets, maps and
more, and a bunch of algorithms and other components. This "bunch of containers
and algorithms" took some of the brightest people in the world many years to
create.

The purpose of STL is to standardise commonly used components so you don't have
to keep reinventing them. You can just use the standard STL components off the
shelf. STL is also part of C++ now, so there will be no more extra bits and
pieces to collect and install. It will be built into your compiler. Because the
STL list is one of the simpler containers, I thought that it might be a good
place to start in demonstrating the practical use of STL. If you understand the
concepts behind this one, you'll have no trouble with the rest. Besides, there
is an awful lot to a simple list container, as we'll see.

In this article we will see how to define and initialise a list, count elements,
find elements in a list, remove elements, and other very useful operations. In
doing so we will cover two different kinds of algorithms, STL generic algorithms
which work with more than one container, and list member functions which work
exclusively with the list container.

Just in case anyone's wondering, here is a brief rundown on the three main kinds
of STL components. The STL containers hold objects, built in objects and class
objects. They keep the objects secure and define a standard interface through
which we can manipulate the objects. Eggs in an egg container won't roll off the
kitchen bench. They are safe. So it is with objects in STL containers. They are
safe. I know that sounds corny but it's true.

STL algorithms are standard algorithms we can apply to the objects while they
are in the container. The algorithms have well known execution characteristics.
They can sort the objects, remove them, count them, compare them, find a
particular one, merge objects into another container, and carry out many other
useful operations.

STL iterators are like pointers to the objects in the containers. STL algorithms
use iterators to operate on containers. Iterators set bounds for algorithms,
regarding the extent of the container, and in other ways. For example some
iterators only let the algorithms read elements, some allow them to write
elements, some both. Iterators also determine the direction of processing in a
container.

You can obtain iterators to the first position in a container by calling the
container member function begin(). You can call the container end() function to
get the past the end value (where to stop processing).

This is what STL is all about, containers, algorithms, and iterators to allow
the algorithms to work on the elements in the containers. The algorithms
manipulate the objects in a measurable, standard way, and are made aware of the
precise extent of the container via iterators. Once this is done they won't ever
"run off the edge". There are other components which enhance the functionality
of these core component types, such as function objects. We will also look at
some examples of these. For now, lets take a look at the STL list.



--------------------------------------------------------------------------------



DEFINING A LIST

We can define an STL list like this.

 
#include <string>
#include <list>
int main (void) {
  list<string> Milkshakes;
}


Thats to it. You've defined a list. Could it have been any easier? By saying
list<string> Milkshakes you've instantiated a template class list<string>, and
then instantiated an object of that type. But lets not fuss with that. At this
stage you really only need to know that you have defined a list of strings. You
need the header file list to provide the STL list class. I compiled these test
programs using GCC 2.7.2 on my Linux box. For example:

 
g++ test1.cpp -otest1


Note that the include file iostream.h is buried in one of the STL header files.
Thats why it is missing in some of the examples.

Now that we have a list, we can start using it to hold things. We'll add some
strings to the list. There is an important thing called the value type of the
list. The value type is the type of the object the list holds. In this case the
value type of the list is string, as the list holds strings.



--------------------------------------------------------------------------------



INSERTING ELEMENTS INTO A LIST WITH THE LIST MEMBER FUNCTIONS PUSH_BACK AND
PUSH_FRONT

 
#include <string>
#include <list>

int main (void) {
  list<string> Milkshakes;
  Milkshakes.push_back("Chocolate");
  Milkshakes.push_back("Strawberry");
  Milkshakes.push_front("Lime");
  Milkshakes.push_front("Vanilla");
}


We now have a list with four strings in it. The list member function push_back()
places an object onto the back of the list. The list member function
push_front() puts one on the front. I often push_back() some error messages onto
a list, and then push_front() a title on the list so it prints before the error
messages.



--------------------------------------------------------------------------------



THE LIST MEMBER FUNCTION EMPTY()

It is important to know if a list is empty. The empty() list member function
returns true if the list is empty. Empty is a deceptively simple concept. I
often use it in the following way. Throughout a program I use push_back() to put
error messages onto a list. Then by calling empty() I can tell if the program
has reported any errors. If I define one list for informational messages, one
for warnings, and one for serious errors, I can easily tell what types of errors
have occurred just by using empty().

I can populate these lists throughout the program, then smarten them up with a
title, or maybe sort them into categories, before printing them out.

Here's what I mean.

 
/*
|| Using a list to track and report program messages and status 
*/
#include <iostream.h>
#include <string>
#include <list>

int main (void) {
  #define OK 0 
  #define INFO 1
  #define WARNING 2

  int return_code;

  list<string> InfoMessages;
  list<:string> WarningMessages;

  // during a program these messages are loaded at various points
  InfoMessages.push_back("Info: Program started");
  // do work...
  WarningMessages.push_back("Warning: No Customer records have been found");
  // do work...

  return_code = OK; 

  if  (!InfoMessages.empty()) {          // there were info messages
     InfoMessages.push_front("Informational Messages:");
     // ... print the info messages list, we'll see how later
     return_code = INFO;
  }

  if  (!WarningMessages.empty()) {       // there were warning messages
     WarningMessages.push_front("Warning Messages:");
     // ... print the warning messages list, we'll see how later
     return_code = WARNING;              
  }

  // If there were no messages say so.
  if (InfoMessages.empty() && WarningMessages.empty()) {
     cout << "There were no messages " << endl;
  }

  return return_code;
}




--------------------------------------------------------------------------------



PROCESSING ELEMENTS IN A LIST WITH A FOR LOOP

We will want to be able to iterate through any list, to, for example, print all
the objects in the list to see the effect of various operations on a list. To
iterate through a list, element by element we can proceed as follows

 
/*
|| How to print the contents of a simple STL list. Whew! 
*/
#include <iostream.h>
#include <string>
#include <list>

int main (void) {
list<string> Milkshakes;
list<string>::iterator MilkshakeIterator;

  Milkshakes.push_back("Chocolate");
  Milkshakes.push_back("Strawberry");
  Milkshakes.push_front("Lime");
  Milkshakes.push_front("Vanilla");

  // print the milkshakes
  Milkshakes.push_front("The Milkshake Menu");
  Milkshakes.push_back("*** Thats the end ***");
  for (MilkshakeIterator=Milkshakes.begin(); 
         MilkshakeIterator!=Milkshakes.end(); 
          ++MilkshakeIterator) {
    // dereference the iterator to get the element
    cout << *MilkshakeIterator << endl;
  }	
}


In this program we define an iterator, MilkshakeIterator. We set
MilkshakeIterator to the first element of the list. To do this we call
Milkshakes.begin() which returns an iterator to the beginning of the list. We
then compare MilkshakeIterator to the end of list value Milkshakes.end(), and
stop when we get there.

The end() function of a container returns an iterator to the position one past
the end of the container. When we get there, we stop processing. We cannot
dereference the iterator returned by a container's end() function. We just know
it means we have passed the end of the container and should stop processing
elements. This holds for all STL containers.

In the above example at each pass through the for loop we dereference the
iterator to obtain the string, which we print.

In STL programming we use one or more iterators in every algorithm. We use them
to access objects in a container. To access a given object we point the iterator
at the required object, then we dereference the iterator.

The list container, in case you're wondering, does not support adding a number
to a list iterator to jump to another object in the container. That is, we
cannot say Milkshakes.begin()+2 to point to the third object in the list,
because the STL list is implemented as a double linked list, which does not
support random access. The vector and deque containers, other STL containers, do
provide random access.

The above program printed the contents of the list. Anyone reading it can
immediately see how it works. It uses standard iterators and a standard list
container. There is not much programmer dependent stuff in it, or a home grown
list implementation. Just standard C++. That's an important step forward. Even
this simple use of STL makes our software more standard.



--------------------------------------------------------------------------------



PROCESSING ELEMENTS IN A LIST WITH THE STL GENERIC ALGORITHM FOR_EACH

Even with an STL list and iterator we are still initialising, testing, and
incrementing the iterator to iterate through a container. The STL generic
for_each algorithm can relieve us of that work.

 
/*
|| How to print a simple STL list MkII
*/
#include <iostream.h>
#include <string>
#include <list>
#include <algorithm>

PrintIt (string& StringToPrint) {
  cout << StringToPrint << endl;
}

int main (void) {
  list<string> FruitAndVegetables;
  FruitAndVegetables.push_back("carrot");
  FruitAndVegetables.push_back("pumpkin");
  FruitAndVegetables.push_back("potato");
  FruitAndVegetables.push_front("apple");
  FruitAndVegetables.push_front("pineapple");

  for_each  (FruitAndVegetables.begin(), FruitAndVegetables.end(), PrintIt);
}


In this program we use the STL generic algorithm for_each() to iterate though an
iterator range and invoke the function PrintIt() on each object. We don't need
to initialise, test or increment any iterators. for_each() nicely modularises
our code. The operation we are performing on the object is nicely packaged away
in a function, we have gotten rid of the loop, and our code is clearer.

The for_each algorithm introduces the concept of an iterator range, specified by
a start iterator and an end iterator. The start iterator specifies where to
start processing and the end iterator signifies where to stop processing, but is
not included in the range.



--------------------------------------------------------------------------------



COUNTING ELEMENTS IN A LIST WITH THE STL GENERIC ALGORITHM COUNT()

The STL generic algorithms count() and count_if() count occurrences of objects
in a container. Like for_each(), the count() and count_if() algorithms take an
iterator range.

Lets count the number of best possible scores in a list of student's exam
scores, a list of ints.

 
/*
|| How to count objects in an STL list
*/
#include <list>
#include <algorithm>

int main (void) {
  list<int> Scores;

  Scores.push_back(100); Scores.push_back(80);
  Scores.push_back(45); Scores.push_back(75);
  Scores.push_back(99); Scores.push_back(100);

  int NumberOf100Scores(0);	
  count (Scores.begin(), Scores.end(), 100, NumberOf100Scores);

  cout << "There were " << NumberOf100Scores << " scores of 100" << endl;
}


The count() algorithm counts the number of objects equal to a certain value. In
the above example it checks each integer object in a list against 100. It
increments the variable NumberOf100Scores each time a container object equals
100. The output of the program is

 
  There were 2 scores of 100




--------------------------------------------------------------------------------



COUNTING ELEMENTS IN A LIST WITH THE STL GENERIC ALGORITHM COUNT_IF()

count_if() is a much more interesting version of count(). It introduces a new
STL component, the function object. count_if() takes a function object as a
parameter. A function object is a class with at least operator () defined. Some
STL algorithms accept function objects as parameters and invoke operator () of
the function object for each container object being processed.

Function objects intended for use with STL algorithms have their function call
operator returning true or false. They are called predicate function objects for
this reason. An example will make this clear. count_if() uses the passed in
function object to make a more complex assessment than count() of whether an
object should be counted. In this example we will count toothbrushes sold. We
will refer to sales records containing a four character product code and a
description of the product.

 
/*
|| Using a function object to help count things
*/
#include <string>
#include <list>
#include <algorithm>

const string ToothbrushCode("0003");

class IsAToothbrush {
public:  
bool operator() ( string& SalesRecord ) {
    return SalesRecord.substr(0,4)==ToothbrushCode;
  }	
};

int main (void) {
  list<string> SalesRecords;

  SalesRecords.push_back("0001 Soap");
  SalesRecords.push_back("0002 Shampoo");
  SalesRecords.push_back("0003 Toothbrush");
  SalesRecords.push_back("0004 Toothpaste");
  SalesRecords.push_back("0003 Toothbrush");

  int NumberOfToothbrushes(0);	
  count_if (SalesRecords.begin(), SalesRecords.end(), 
             IsAToothbrush(), NumberOfToothbrushes);

  cout << "There were " 
       << NumberOfToothbrushes 
       << " toothbrushes sold" << endl;
}


The output of the program is

 
There were 2 toothbrushes sold


The program works as follows: A function object class is defined, IsAToothbrush.
Objects of this class can determine whether a sales record is a toothbrush sales
record or not. Their function call operator () will return true if a record is a
toothbrush sales record and false otherwise.

The count_if() algorithm will process container objects in the range specified
by the first and second iterator parameters. It will increment
NumberOfToothbrushes for each object in the container for which
IsAToothbrush()() returns true.

The net result is that NumberOfToothbrushes will contain the number of sales
records where the product code was "0003", that is, where the product was a
toothbrush.

Note that the third parameter to count_if(), IsAToothbrush(), is a temporary
object constructed with it's default constructor. The () do not signify a
function call. You are passing a temporary object of class IsAToothbrush to
count_if(). count_if() will internally invoke IsAToothbrush()() for each object
in the container.



--------------------------------------------------------------------------------



A MORE COMPLEX FUNCTION OBJECT WITH THE STL GENERIC ALGORITHM COUNT_IF()

We can further develop the idea of the function object. Assume we need to pass
more information to a function object. We cannot do this using the function call
operator, because that must be defined to take only an object of the value type
of the list. However by specifying a non-default constructor for IsAToothbrush
we can initialise it with whatever information we need. We might need to have a
variable code for a toothbrush for example. We can add this extra information
into the function object as follows:

 
/*
|| Using a more complex function object
*/
#include <iostream.h>
#include <string>
#include <list>
#include <algorithm>

class IsAToothbrush {
public:
  IsAToothbrush(string& InToothbrushCode) : 
      ToothbrushCode(InToothbrushCode) {}
  bool operator() (string& SalesRecord) {
    return SalesRecord.substr(0,4)==ToothbrushCode;
}	
private:
  string ToothbrushCode; 	
};

int main (void) {
  list<string> SalesRecords;

  SalesRecords.push_back("0001 Soap");
  SalesRecords.push_back("0002 Shampoo");
  SalesRecords.push_back("0003 Toothbrush");
  SalesRecords.push_back("0004 Toothpaste");
  SalesRecords.push_back("0003 Toothbrush");

  string VariableToothbrushCode("0003");

  int NumberOfToothbrushes(0);	
  count_if (SalesRecords.begin(), SalesRecords.end(), 
              IsAToothbrush(VariableToothbrushCode),
                 NumberOfToothbrushes);
  cout << "There were  "
       << NumberOfToothbrushes 
       << " toothbrushes matching code "
       << VariableToothbrushCode
       << " sold" 
       << endl;
}


The output of the program is

 
There were  2 toothbrushes matching code 0003 sold


This example shows how to pass information to the function object. You can
define any constructors that you like and you can do any processing in the
function object that you like, well, that the compiler will tolerate anyhow.

You can see that function objects really extend the basic counting algorithm.

At this stage we have covered



 * defining a list
 * adding elements to a list
 * how to tell if a list is empty
 * how to iterate through a list using a for loop
 * how to iterate through a list using the STL generic algorithm for_each
 * the begin() and end() list member functions and their meaning
 * the concept of iterator ranges and the fact that the last position of a range
   is not processed
 * how to count objects in a list using the STL generic algorithms count() and
   count_if()
 * how to define function objects

These examples were chosen to show commonly needed list operations. If you
understand these basic principles you will have no trouble using STL
productively. Mind you it does take some practice. We'll now extend our
knowledge with some more complicated operations, both list member functions and
STL generic algorithms.



--------------------------------------------------------------------------------



FINDING OBJECTS IN A LIST USING THE STL GENERIC ALGORITHM FIND()

How do we find something in a list? The STL generic algorithms find() and
find_if() will do that. Like for_each(), count(), and count_if(), these
algorithms take an iterator range, specifying what part of a list or any other
container for that matter, to process. As usual the first iterator specifies
where to start processing, the second iterator specifies where to stop
processing. The position specified by the second iterator is not included in
processing.

Here's how find() works.

 
/*
|| How to find things in an STL list
*/
#include <string>
#include <list>
#include <algorithm>

int main (void) {
  list<string> Fruit;
  list<string>::iterator FruitIterator;

  Fruit.push_back("Apple");
  Fruit.push_back("Pineapple");
  Fruit.push_back("Star Apple");

  FruitIterator = find (Fruit.begin(), Fruit.end(), "Pineapple");

  if (FruitIterator == Fruit.end()) {  
    cout << "Fruit not found in list" << endl; 
  }
  else {
   cout << *FruitIterator << endl;
  }
}


The output of the program will be

 
Pineapple


If find does not find the specified object, it returns the past the end iterator
Fruit.end(). Otherwise it returns an iterator to the found list object.



--------------------------------------------------------------------------------



FINDING OBJECTS IN A LIST USING THE STL GENERIC ALGORITHM FIND_IF()

There is another more powerful version of find(). This example demonstrates
find_if(), which accepts a function object as a parameter, and uses it to make a
more complex assessment of whether an object is "found".

Say we have records containing events and dates stored in chronological order in
a list. We wish to find the first event that took place in 1997.

 
/*
|| How to find things in an STL list MkII 
*/
#include <string>
#include <list>
#include <algorithm>

class EventIsIn1997 {
public:
 bool operator () (string& EventRecord) {
   // year field is at position 12 for 4 characters in EventRecord	
   return EventRecord.substr(12,4)=="1997";
  }  
};

int main (void) {
  list<string> Events;

// string positions 0123456789012345678901234567890123456789012345	
  Events.push_back("07 January  1995  Draft plan of house prepared");
  Events.push_back("07 February 1996  Detailed plan of house prepared");
  Events.push_back("10 January  1997  Client agrees to job");
  Events.push_back("15 January  1997  Builder starts work on bedroom");
  Events.push_back("30 April    1997  Builder finishes work");

  list<string>::iterator EventIterator = 
      find_if (Events.begin(), Events.end(), EventIsIn1997());

  // find_if completes the first time EventIsIn1997()() returns true 
  // for any object. It returns an iterator to that object which we 
  // can dereference to get the object, or if EventIsIn1997()() never
  // returned true, find_if returns end()
  if (EventIterator==Events.end()) {  
    cout << "Event not found in list" << endl; 
  }
  else {
   cout << *EventIterator << endl;
  }
}


The output of the program will be

 
10 January  1997  Client agrees to job




--------------------------------------------------------------------------------



FINDING SEQUENCES IN A LIST USING THE STL GENERIC ALGORITHM SEARCH

Some characters are a little easier to deal with in an STL container. Lets look
at a sequence of characters that can be difficult to work with. We'll define an
STL list to hold the characters.

 
  list<char> Characters;


We now have a rock solid sequence of characters that knows how to manage it's
own memory without any help. It knows precisely where it starts and ends. That's
a useful thing. I don't know if I'd say that about a null terminated array of
characters.

Lets add some of our favourite characters to the list.

 
  Characters.push_back('\0');
  Characters.push_back('\0');
  Characters.push_back('1');
  Characters.push_back('2');


How many null characters have we got?

 
  int NumberOfNullCharacters(0);
  count(Characters.begin(), Characters.end(), '\0', NumberOfNullCharacters);
  cout << "We have " << NumberOfNullCharacters << endl;


Let's find the character '1'

 
  list<char>::iterator Iter;
  Iter = find(Characters.begin(), Characters.end(), '1');
  cout << "We found " << *Iter << endl;


This example is intended to show that STL containers allow you to handle null
characters in a more standard way. Now lets search a container for two nulls
with the STL search algorithm.

The STL generic algorithm search() searches a container, as you may have
guessed, but for a sequence of elements, unlike find() and find_if() which
search for a single element.

 
/*
|| How to use the search algorithm in an STL list
*/
#include <string>
#include <list>
#include <algorithm>

int main ( void ) { 

  list<char> TargetCharacters;
  list<char> ListOfCharacters;

  TargetCharacters.push_back('\0');
  TargetCharacters.push_back('\0');

  ListOfCharacters.push_back('1');
  ListOfCharacters.push_back('2');
  ListOfCharacters.push_back('\0');
  ListOfCharacters.push_back('\0');

  list<char>::iterator PositionOfNulls = 
    search(ListOfCharacters.begin(), ListOfCharacters.end(), 
            TargetCharacters.begin(), TargetCharacters.end());

  if (PositionOfNulls!=ListOfCharacters.end())
    cout << "We found the nulls" << endl;
}


The output of the program will be

 
We found the nulls


The search algorithm finds the first occurrence of one sequence in another
sequence. In this case we search for the first occurrence of TargetCharacters
which is a list containing two null characters, in ListOfCharacters.

The parameters for search are two iterators specifying a range to search, and
two more iterators specifying a range to search for. So we are looking for the
entire range of the TargetCharacters list, in the entire range of
ListOfCharacters.

If TargetCharacters is found, search will return an iterator to the first
character in ListOfCharacters where the sequences matched. If a match is not
found, search will return the past the end value ListOfCharacters.end().



--------------------------------------------------------------------------------



SORTING A LIST USING THE LIST MEMBER FUNCTION SORT()

To sort a list we use the list member function sort(), not the generic algorithm
sort(). All the algorithms we have been using up till now have been generic
algorithms. However in STL, sometimes a container will supply it's own
implementation of a particular algorithm, either through necessity or for
enhanced performance.

In this case the list container has it's own sort because the generic sort
algorithm only sorts containers which provide random access to the elements
inside. The list container does not provide random access to the elements in the
list, because it is implemented as a linked list. A special sort() member
function is needed which can sort a linked list.

You'll find this with STL. For various reasons the containers will supply extra
functions, where necessary for efficiency or where special performance gains can
be made by taking advantage of some special feature of a container's structure.

 
/*
|| How to sort an STL list
*/
#include <string>
#include <list>
#include <algorithm>

PrintIt (string& StringToPrint) { cout << StringToPrint << endl;}

int main (void) {
  list<string> Staff;
  list<string>::iterator PeopleIterator;

  Staff.push_back("John");
  Staff.push_back("Bill");
  Staff.push_back("Tony");
  Staff.push_back("Fidel");
  Staff.push_back("Nelson"); 

  cout << "The unsorted list " << endl;
  for_each(Staff.begin(), Staff.end(), PrintIt );

  Staff.sort();

  cout << "The sorted list " << endl;
  for_each(Staff.begin(), Staff.end(), PrintIt); 
}


The output is

 
The unsorted list 
John
Bill
Tony
Fidel
Nelson
The sorted list 
Bill
Fidel
John
Nelson
Tony




--------------------------------------------------------------------------------



INSERTING ELEMENTS IN A LIST WITH THE INSERT() LIST MEMBER FUNCTION

The list member functions push_front() and push_back() add elements to the front
and back of a list respectively. You can also add an object at any point in a
list with insert().

insert() can add one object, a number of copies of an object, or a range of
objects. Here are some examples of inserting objects into a list.

 
/*
|| Using insert to insert elements into a list.
*/
#include <list>

int main (void) {
  list<int> list1;

  /*
  || Put integers 0 to 9 in the list
  */
  for (int i = 0; i < 10; ++i)  list1.push_back(i);   

  /*
  || Insert -1 using the insert member function
  || Our list will contain -1,0,1,2,3,4,5,6,7,8,9
  */
  list1.insert(list1.begin(), -1); 

  /*
  || Insert an element at the end using insert
  || Our list will contain -1,0,1,2,3,4,5,6,7,8,9,10
  */
  list1.insert(list1.end(), 10);

  /*
  || Inserting a range from another container
  || Our list will contain -1,0,1,2,3,4,5,6,7,8,9,10,11,12
  */
  int IntArray[2] = {11,12};
  list1.insert(list1.end(), &IntArray[0], &IntArray[2]);

  /*
  || As an exercise put the code in here to print the lists!
  || Hint: use PrintIt and accept an interger
  */
}


Note that the insert() function adds one or more elements at the position of the
iterator you specify. Your elements will appear in the list before the element
that was at the specified iterator position.



--------------------------------------------------------------------------------



LIST CONSTRUCTORS

We have been defining a list like this.

 
  list<int> Fred; 


You can also define a list and initialise it's elements like this

 
  // define a list of 10 elements and initialise them all to 0
  list<int> Fred(10, 0);
  // list now contains 0,0,0,0,0,0,0,0,0,0


Or you can define a list and initialise it with a range from another STL
container, which doesn't have to be a list, just a container with the same value
type.

 
  vector<int> Harry;
  Harry.push_back(1); 
  Harry.push_back(2); 

  // define a list and initialise it with the elements in Harry
  list<int> Bill(Harry.begin(), Harry.end());
  // Bill now contains 1,2




--------------------------------------------------------------------------------



ERASING ELEMENTS FROM A LIST USING LIST MEMBER FUNCTIONS

The list member function pop_front() removes the first element from a list.
pop_back() removes the last element. The member function erase() erases the
element pointed to by an iterator. There is another erase() function which can
erase a range of elements.

 
/*
|| Erasing objects from a list
*/
#include <list>

int main (void) {
  list<int> list1;   // define a list of integers

  /*
  || Put some numbers in the list
  || It now contains 0,1,2,3,4,5,6,7,8,9
  */
  for (int i = 0; i < 10; ++i)  list1.push_back(i);

  list1.pop_front();    // erase the first element 0

  list1.pop_back();     // erase the last element 9

  list1.erase(list1.begin());  // erase the first element (1) using an iterator

  list1.erase(list1.begin(), list1.end());  // erase all the remaining elements

  cout << "list contains " << list1.size() << " elements" << endl;
}


The output will be

 
list contains 0 elements




--------------------------------------------------------------------------------



REMOVING ELEMENTS FROM A LIST USING THE LIST MEMBER FUNCTION REMOVE()

The list member function remove() erases objects from a list.

 
/*
|| Using the list member function remove to remove elements
*/
#include <string>
#include <list>
#include <algorithm>

PrintIt (const string& StringToPrint) {
  cout << StringToPrint << endl;
}

int main (void) {
  list<string> Birds;

  Birds.push_back("cockatoo");
  Birds.push_back("galah");
  Birds.push_back("cockatoo");
  Birds.push_back("rosella");
  Birds.push_back("corella");

  cout << "Original list with cockatoos" << endl;
  for_each(Birds.begin(), Birds.end(), PrintIt); 

  Birds.remove("cockatoo"); 

  cout << "Now no cockatoos" << endl;
  for_each(Birds.begin(), Birds.end(), PrintIt); 
  
}


The output will be

 
Original list with cockatoos
cockatoo
galah
cockatoo
rosella
corella
Now no cockatoos
galah
rosella
corella




--------------------------------------------------------------------------------



REMOVING ELEMENTS FROM A LIST WITH THE STL GENERIC ALGORITHM REMOVE()

The generic algorithm remove() works in a different way to the list member
function remove(). The generic version does not change the size of the
container.

 
/*
|| Using the generic remove algorithm to remove list elements
*/
#include <string>
#include <list>
#include <algorithm>

PrintIt(string& AString) { cout << AString << endl; }

int main (void) {
  list<string> Birds;
  list<string>::iterator NewEnd;

  Birds.push_back("cockatoo");
  Birds.push_back("galah");
  Birds.push_back("cockatoo");
  Birds.push_back("rosella");
  Birds.push_back("king parrot");

  cout << "Original list" << endl; 
  for_each(Birds.begin(), Birds.end(), PrintIt);

  NewEnd = remove(Birds.begin(), Birds.end(), "cockatoo"); 

  cout << endl << "List according to new past the end iterator" << endl; 
  for_each(Birds.begin(), NewEnd, PrintIt);

  cout << endl << "Original list now. Care required!" << endl; 
  for_each(Birds.begin(), Birds.end(), PrintIt);
}


The output will be

Original list
cockatoo
galah
cockatoo
rosella
king parrot

 
List according to new past the end iterator
galah
rosella
king parrot

 
Original list now. Care required!
galah
rosella
king parrot
rosella
king parrot


The generic remove() algorithm returns an iterator specifying a new end to the
list. The range from the beginning to the new end (not including the new end)
contains the elements left after the remove. You can then erase the range from
the new end to the old end using the list member function erase.



--------------------------------------------------------------------------------



PARTITIONING A LIST WITH THE STL GENERIC ALGORITHM STABLE_PARTITION() AND USING
THE LIST MEMBER FUNCTION SPLICE()

We will finish off with a slightly more complicated example. It demonstrates the
STL generic stable_partition() algorithm and one variation of the list member
function splice(). Notice the use of function objects, and the absence of loops.
Control passes through a series of simple statements, which are calls to STL
algorithms.

stable_partition() is an interesting function. It rearranges elements so that
those which satify a certain condition come before those which do not. It
preserves the relative order of the two groups of elements. An example will make
this clear.

Splice splices the elements of another list into the list. It removes the
elements from the source list.

In this example we want to accept some flags and four filenames from the command
line. The filenames must appear in order. By using stable_partition() we can
accept the flags at any position relative to the filenames and get them together
without disturbing the order of the filename parameters.

Due to the readily available counting and finding algorithms we can call these
algorithms as necessary to determine which flag was set rather than setting
other flags in our program. I find containers are very convenient for managing
small amounts of variable dynamic data like this.

 
/*
|| Using the STL stable_partition algorithm
|| Takes any number of flags on the command line and 
|| four filenames in order.
*/
#include <string>
#include <list>
#include <algorithm>

PrintIt ( string& AString ) { cout << AString << endl; }

class IsAFlag {
public: 
  bool operator () (string& PossibleFlag) {
    return PossibleFlag.substr(0,1)=="-";
  }
};

class IsAFileName {
public:  
  bool operator () (string& StringToCheck) {
    return !IsAFlag()(StringToCheck);
  }
};

class IsHelpFlag {
public:  
  bool operator () (string& PossibleHelpFlag) {
    return PossibleHelpFlag=="-h";
  }
};

int main (int argc, char *argv[]) {

list<string> CmdLineParameters;       // the command line parameters
list<string>::iterator StartOfFiles;  // start of filenames 
list<string> Flags;                   // list of flags
list<string> FileNames;               // list of filenames

for (int i = 0; i < argc; ++i) CmdLineParameters.push_back(argv[i]);

CmdLineParameters.pop_front(); // we don't want the program name

// make sure we have the four mandatory file names
int NumberOfFiles(0);
count_if(CmdLineParameters.begin(), CmdLineParameters.end(), 
       IsAFileName(), NumberOfFiles);

cout << "The " 
     << (NumberOfFiles == 4 ? "correct " : "wrong ")
     << "number (" 
     << NumberOfFiles 
     << ") of file names were specified" << endl;

// move any flags to the beginning
StartOfFiles = 
  stable_partition(CmdLineParameters.begin(), CmdLineParameters.end(), 
         IsAFlag()); 

cout << "Command line parameters after stable partition" << endl;
for_each(CmdLineParameters.begin(), CmdLineParameters.end(), PrintIt);

// Splice any flags from the original CmdLineParameters list into Flags list. 
Flags.splice(Flags.begin(), CmdLineParameters,
       CmdLineParameters.begin(), StartOfFiles);

if (!Flags.empty()) {
  cout << "Flags specified were:" << endl;
  for_each(Flags.begin(), Flags.end(), PrintIt);
}
else {
  cout << "No flags were specified" << endl;
} 

// parameters list now contains only filenames. Splice them into FileNames list.
FileNames.splice(FileNames.begin(), CmdLineParameters, 
       CmdLineParameters.begin(), CmdLineParameters.end());

if (!FileNames.empty()) {
  cout << "Files specified (in order) were:" << endl;
  for_each(FileNames.begin(), FileNames.end(), PrintIt);
}
else {
  cout << "No files were specified" << endl;
} 

// check if the help flag was specified
if (find_if(Flags.begin(), Flags.end(), IsHelpFlag())!=Flags.end()) {
  cout << "The help flag was specified" << endl;
}

// open the files and do whatever you do

}


Given this command line:

 
test17 -w linux -o is -w great


the output is

 
The wrong number (3) of file names were specified
Command line parameters after stable partition
-w
-o
-w
linux
is
great
Flags specified were:
-w
-o
-w
Files specified (in order) were:
linux
is
great




--------------------------------------------------------------------------------



CONCLUSION

We have only touched on the things you can do with a list. We haven't even got
to the point of storing a user defined class of object, although thats not hard.

If you understand the concepts behind the algorithms presented here you should
have no trouble using the rest. The important thing with STL is to get the
basics right.

The key to STL is really the iterator. STL algorithms take iterators as
parameters. They take iterator ranges, sometimes one range, sometimes two. STL
containers provide the iterators. Thats why we say list<int>::iterator, or
list<char>::iterator, or list<string>::iterator.

Iterators have a well defined heirarchy. They have varying "powers". Some
iterators provide read only access to a container, some write only. Some can
only iterate forwards, some are bidirectional. Some iterators provide random
access to a container.

STL algorithms require a certain "power" of iterator. If the container doesnt
provide an iterator of that power, the algorithm will not compile. For example,
the list container only provides bidirectional iterators. The generic sort()
algorithm requires random access iterators. Thats why we need the special list
member function sort().

To really use STL properly you will need to carefully study the various kinds of
iterators. You need to see just what kinds of iterators are provided by what
containers. You then need to see what type of iterators the algorithms require.
You need, of course to understand what kinds of iterators you can have.



--------------------------------------------------------------------------------



USING STL IN THE FIELD

During the past year I have written a number of commercial C++ programs using
STL. It reduced my effort and almost eliminated logic errors in all cases.

The largest program is about 5000 lines. Probably the most striking thing about
it is its speed. It reads and extensively processes a 1-2 Mb transaction file in
about twenty seconds. It was developed with GCC 2.7.2 on Linux and now runs on a
HP-UX machine. It uses over 50 function objects and many containers ranging in
size from small lists to a map with over 14,000 elements.

The function objects in the program are in a hierarchy where top level function
objects call lower level ones. I used the STL algorithms for_each(), find(),
find_if(), count() and count_if() extensively. I reduced nearly all of the
internals of the program to STL algorithm calls.

STL tended to automatically organise my code into distinct control and support
sections. By carefully crafting function objects and giving them meaningful
names I managed to move them out of sight and concentrate on the flow of control
in my software.

There is much more to know about STL programming and I hope you have enjoyed
working through these examples.

The two books in the bibliography both have active errata pages on the web so
you can keep them right up to date.

Stroustrup has an advice section at the back of each chapter which is excellent,
especially for beginners and the whole book is in a much more conversational
style than the earlier editions. It is also much larger. There are of course
quite a few other books on STL in the bookshops. Have a look and see what you
can find.



BIBLIOGRAPHY

The STL Tutorial and Reference Guide, David Musser and Atul Saini. Addison
Wesley 1996.

The C++ Programming Language 3e, Bjarne Stroustrup. Addison Wesley 1997.



--------------------------------------------------------------------------------



COPYRIGHT © 1998, SCOTT FIELD
PUBLISHED IN ISSUE 34 OF LINUX GAZETTE, NOVEMBER 1998



--------------------------------------------------------------------------------





--------------------------------------------------------------------------------