File: field.html

package info (click to toggle)
lg-issue34 3-1
links: PTS
area: main
in suites: sarge
size: 4,396 kB
ctags: 194
sloc: ansic: 261; sh: 186; makefile: 34
file content (1235 lines) | stat: -rw-r--r-- 43,905 bytes
<!--startcut ==========================================================-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<title>Introduction to STL LG #34</title>
</HEAD>
<BODY BGCOLOR="#FFFFFF" TEXT="#000000" LINK="#0000FF" VLINK="#A000A0"
ALINK="#FF0000">
<!--endcut ============================================================-->

<H4>
"Linux Gazette...<I>making Linux just a little more fun!</I>"
</H4>

<P> <HR> <P> 
<!--===================================================================-->

<center>
<H1><font color="maroon">Introduction to STL, Standard Template Library</font></H1>
<H4>By <a href="mailto:sfield@idx.com.au">Scott Field</a></H4>
</center>
<P> <HR> <P>  

This article is about a new extension to the C++ language, the Standard
Template Library, otherwise known as STL.
<P>
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. 
<P>
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!
<P>
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.
<P>
Also the third edition of Stroustrup which covers STL as part of C++ was
not out when I started.
<P>
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.
<P>
The other thing is, STL is supposed to be easy to use. So theoretically we
should be able to start using STL straight away.
<P>
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. 
<P>
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. 
<P>
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.
<P>
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.
<P>
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.
<P>
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.
<P>
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).
<P>
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.
<P> <HR> <P> 
<H4>Defining a List</H4>
<P>
We can define an STL list like this.
<PRE> 
#include &lt;string&gt;
#include &lt;list&gt;
int main (void) {
  list&lt;string&gt; Milkshakes;
}
</PRE> 
Thats to it. You've defined a list. Could it have been any easier? 
By saying list&lt;string&gt; Milkshakes you've instantiated a template class 
list&lt;string&gt;, 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:
<PRE> 
g++ test1.cpp -otest1
</PRE> 
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.
<P>
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.
<P> <HR> <P> 
<H4>Inserting elements into a list with the list member functions push_back 
and push_front</H4>
<PRE> 
#include &lt;string&gt;
#include &lt;list&gt;

int main (void) {
  list&lt;string&gt; Milkshakes;
  Milkshakes.push_back("Chocolate");
  Milkshakes.push_back("Strawberry");
  Milkshakes.push_front("Lime");
  Milkshakes.push_front("Vanilla");
}
</PRE> 
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. 
<P> <HR> <P> 
<H4>The list member function empty()</H4>
<P>
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(). 
<P>
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.
<P>
Here's what I mean.
<PRE> 
/*
|| Using a list to track and report program messages and status 
*/
#include &lt;iostream.h&gt;
#include &lt;string&gt;
#include &lt;list&gt;

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

  int return_code;

  list&lt;string&gt; InfoMessages;
  list&lt:string&gt; 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 &lt;&lt; "There were no messages " &lt;&lt; endl;
  }

  return return_code;
}
</PRE> 
<P> <HR> <P> 
<H4>Processing elements in a list with a for loop</H4>
<P>
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 
<PRE> 
/*
|| How to print the contents of a simple STL list. Whew! 
*/
#include &lt;iostream.h&gt;
#include &lt;string&gt;
#include &lt;list&gt;

int main (void) {
list&lt;string&gt; Milkshakes;
list&lt;string&gt;::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 &lt;&lt; *MilkshakeIterator &lt;&lt; endl;
  }	
}
</PRE> 
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.
<P>
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.
<P>
In the above example at each pass through the for loop we dereference the 
iterator to obtain the string, which we print. 
<P>
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.
<P>
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.
<P>
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.
<P> <HR> <P> 
<H4>Processing elements in a list with the STL generic algorithm for_each</H4>
<P>
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.
<PRE> 
/*
|| How to print a simple STL list MkII
*/
#include &lt;iostream.h&gt;
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

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

int main (void) {
  list&lt;string&gt; 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);
}
</PRE> 
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. 
<P>
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.
<P> <HR> <P> 
<H4>Counting elements in a list with the STL generic algorithm count()</H4>
<P>
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.
<P>
Lets count the number of best possible scores in a list of student's exam 
scores, a list of ints.
<PRE> 
/*
|| How to count objects in an STL list
*/
#include &lt;list&gt;
#include &lt;algorithm&gt;

int main (void) {
  list&lt;int&gt; 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 &lt;&lt; "There were " &lt;&lt; NumberOf100Scores &lt;&lt; " scores of 100" &lt;&lt; endl;
}
</PRE> 
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
<PRE> 
  There were 2 scores of 100
</PRE> 
<P> <HR> <P> 
<H4>Counting elements in a list with the STL generic algorithm count_if()</H4>
<P>
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. 
<P>
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.
<PRE> 
/*
|| Using a function object to help count things
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

const string ToothbrushCode("0003");

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

int main (void) {
  list&lt;string&gt; 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 &lt;&lt; "There were " 
       &lt;&lt; NumberOfToothbrushes 
       &lt;&lt; " toothbrushes sold" &lt;&lt; endl;
}
</PRE> 
The output of the program is
<PRE> 
There were 2 toothbrushes sold
</PRE> 
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.
<P>
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.
<P>
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. 
<P>
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.
<P> <HR> <P> 
<H4>A more complex function object with the STL generic algorithm count_if()</H4>
<P>
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:
<PRE> 
/*
|| Using a more complex function object
*/
#include &lt;iostream.h&gt;
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

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&lt;string&gt; 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 &lt;&lt; "There were  "
       &lt;&lt; NumberOfToothbrushes 
       &lt;&lt; " toothbrushes matching code "
       &lt;&lt; VariableToothbrushCode
       &lt;&lt; " sold" 
       &lt;&lt; endl;
}
</PRE> 
The output of the program is
<PRE> 
There were  2 toothbrushes matching code 0003 sold
</PRE> 
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. 
<P>
You can see that function objects really extend the basic counting algorithm.
<P>
At this stage we have covered 
<P>
<ul>
<li> defining a list
<li> adding elements to a list 
<li> how to tell if a list is empty
<li> how to iterate through a list using a for loop
<li> how to iterate through a list using the STL generic algorithm for_each
<li> the begin() and end() list member functions and their meaning
<li> the concept of iterator ranges and the fact that the last position of a
 range is not processed
<li> how to count objects in a list using the STL generic algorithms 
 count() and count_if()
<li> how to define function objects
</ul>
<P>
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.
<P> <HR> <P> 
<H4>Finding objects in a list using the STL generic algorithm find()</H4>
<P>
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. 
<P>
Here's how find() works.
<PRE> 
/*
|| How to find things in an STL list
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

int main (void) {
  list&lt;string&gt; Fruit;
  list&lt;string&gt;::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 &lt;&lt; "Fruit not found in list" &lt;&lt; endl; 
  }
  else {
   cout &lt;&lt; *FruitIterator &lt;&lt; endl;
  }
}
</PRE> 
The output of the program will be 
<PRE> 
Pineapple
</PRE> 
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.
<P> <HR> <P> 
<H4>Finding objects in a list using the STL generic algorithm find_if()</H4>
<P>
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".
<P>
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.
<PRE> 
/*
|| How to find things in an STL list MkII 
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

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&lt;string&gt; 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&lt;string&gt;::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 &lt;&lt; "Event not found in list" &lt;&lt; endl; 
  }
  else {
   cout &lt;&lt; *EventIterator &lt;&lt; endl;
  }
}
</PRE> 
The output of the program will be 
<PRE> 
10 January  1997  Client agrees to job
</PRE> 
<P> <HR> <P> 
<H4>Finding sequences in a list using the STL generic algorithm search</H4>
<P>
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.
<PRE> 
  list&lt;char&gt; Characters;
</PRE> 
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.
<P>
Lets add some of our favourite characters to the list.
<PRE> 
  Characters.push_back('\0');
  Characters.push_back('\0');
  Characters.push_back('1');
  Characters.push_back('2');
</PRE> 
How many null characters have we got?
<PRE> 
  int NumberOfNullCharacters(0);
  count(Characters.begin(), Characters.end(), '\0', NumberOfNullCharacters);
  cout &lt;&lt; "We have " &lt;&lt; NumberOfNullCharacters &lt;&lt; endl;
</PRE> 
Let's find the character '1'
<PRE> 
  list&lt;char&gt;::iterator Iter;
  Iter = find(Characters.begin(), Characters.end(), '1');
  cout &lt;&lt; "We found " &lt;&lt; *Iter &lt;&lt; endl;
</PRE> 
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.
<P>
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. 
<PRE> 
/*
|| How to use the search algorithm in an STL list
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

int main ( void ) { 

  list&lt;char&gt; TargetCharacters;
  list&lt;char&gt; 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&lt;char&gt;::iterator PositionOfNulls = 
    search(ListOfCharacters.begin(), ListOfCharacters.end(), 
            TargetCharacters.begin(), TargetCharacters.end());

  if (PositionOfNulls!=ListOfCharacters.end())
    cout &lt;&lt; "We found the nulls" &lt;&lt; endl;
}
</PRE> 
The output of the program will be
<PRE> 
We found the nulls
</PRE> 
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.
<P>
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.
<P>
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().
<P> <HR> <P> 
<H4>Sorting a list using the list member function sort()</H4>
<P>
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.
<P>
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.
<P>
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.   
<PRE> 
/*
|| How to sort an STL list
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

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

int main (void) {
  list&lt;string&gt; Staff;
  list&lt;string&gt;::iterator PeopleIterator;

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

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

  Staff.sort();

  cout &lt;&lt; "The sorted list " &lt;&lt; endl;
  for_each(Staff.begin(), Staff.end(), PrintIt); 
}
</PRE> 
The output is
<PRE> 
The unsorted list 
John
Bill
Tony
Fidel
Nelson
The sorted list 
Bill
Fidel
John
Nelson
Tony
</PRE> 
<P> <HR> <P> 
<H4>Inserting elements in a list with the insert() list member function</H4>
<P>
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().
<P>
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.
<PRE> 
/*
|| Using insert to insert elements into a list.
*/
#include &lt;list&gt;

int main (void) {
  list&lt;int&gt; list1;

  /*
  || Put integers 0 to 9 in the list
  */
  for (int i = 0; i &lt; 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
  */
}
</PRE> 
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.
<P> <HR> <P> 
<H4>List constructors</H4>
<P>
We have been defining a list like this.
<PRE> 
  list&lt;int&gt; Fred; 
</PRE> 
You can also define a list and initialise it's elements like this
<PRE> 
  // define a list of 10 elements and initialise them all to 0
  list&lt;int&gt; Fred(10, 0);
  // list now contains 0,0,0,0,0,0,0,0,0,0
</PRE> 
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.
<PRE> 
  vector&lt;int&gt; Harry;
  Harry.push_back(1); 
  Harry.push_back(2); 

  // define a list and initialise it with the elements in Harry
  list&lt;int&gt; Bill(Harry.begin(), Harry.end());
  // Bill now contains 1,2
</PRE> 
<P> <HR> <P> 
<H4>Erasing elements from a list using list member functions</H4>
<P>
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.
<PRE> 
/*
|| Erasing objects from a list
*/
#include &lt;list&gt;

int main (void) {
  list&lt;int&gt; 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 &lt; 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 &lt;&lt; "list contains " &lt;&lt; list1.size() &lt;&lt; " elements" &lt;&lt; endl;
}
</PRE> 
The output will be
<PRE> 
list contains 0 elements
</PRE> 
<P> <HR> <P> 
<H4>Removing elements from a list using the list member function remove()</H4>
<P>
The list member function remove() erases objects from a list.
<PRE> 
/*
|| Using the list member function remove to remove elements
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

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

int main (void) {
  list&lt;string&gt; Birds;

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

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

  Birds.remove("cockatoo"); 

  cout &lt;&lt; "Now no cockatoos" &lt;&lt; endl;
  for_each(Birds.begin(), Birds.end(), PrintIt); 
  
}
</PRE> 
The output will be 
<PRE> 
Original list with cockatoos
cockatoo
galah
cockatoo
rosella
corella
Now no cockatoos
galah
rosella
corella
</PRE> 
<P> <HR> <P> 
<H4>Removing elements from a list with the STL generic algorithm remove()</H4>
<P>
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.
<PRE> 
/*
|| Using the generic remove algorithm to remove list elements
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

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

int main (void) {
  list&lt;string&gt; Birds;
  list&lt;string&gt;::iterator NewEnd;

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

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

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

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

  cout &lt;&lt; endl &lt;&lt; "Original list now. Care required!" &lt;&lt; endl; 
  for_each(Birds.begin(), Birds.end(), PrintIt);
}
</PRE> 
The output will be
<PRE>
Original list
cockatoo
galah
cockatoo
rosella
king parrot
<BR> 
List according to new past the end iterator
galah
rosella
king parrot
<BR> 
Original list now. Care required!
galah
rosella
king parrot
rosella
king parrot
</PRE> 
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.
<P> <HR> <P> 
<H4>Partitioning a list with the STL generic algorithm stable_partition()
and using the list member function splice()</H4>
<P>
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.
<P>
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. 
<P>
Splice splices the elements of another list into the list. It removes 
the elements from the source list.
<P>
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. 
<P>
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.
<PRE> 
/*
|| Using the STL stable_partition algorithm
|| Takes any number of flags on the command line and 
|| four filenames in order.
*/
#include &lt;string&gt;
#include &lt;list&gt;
#include &lt;algorithm&gt;

PrintIt ( string& AString ) { cout &lt;&lt; AString &lt;&lt; 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&lt;string&gt; CmdLineParameters;       // the command line parameters
list&lt;string&gt;::iterator StartOfFiles;  // start of filenames 
list&lt;string&gt; Flags;                   // list of flags
list&lt;string&gt; FileNames;               // list of filenames

for (int i = 0; i &lt; 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 &lt;&lt; "The " 
     &lt;&lt; (NumberOfFiles == 4 ? "correct " : "wrong ")
     &lt;&lt; "number (" 
     &lt;&lt; NumberOfFiles 
     &lt;&lt; ") of file names were specified" &lt;&lt; endl;

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

cout &lt;&lt; "Command line parameters after stable partition" &lt;&lt; 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 &lt;&lt; "Flags specified were:" &lt;&lt; endl;
  for_each(Flags.begin(), Flags.end(), PrintIt);
}
else {
  cout &lt;&lt; "No flags were specified" &lt;&lt; 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 &lt;&lt; "Files specified (in order) were:" &lt;&lt; endl;
  for_each(FileNames.begin(), FileNames.end(), PrintIt);
}
else {
  cout &lt;&lt; "No files were specified" &lt;&lt; endl;
} 

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

// open the files and do whatever you do

}
</PRE> 
Given this command line:
<PRE> 
test17 -w linux -o is -w great
</PRE> 
the output is
<PRE> 
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
</PRE> 
<P> <HR> <P> 
<H4>Conclusion</H4>
<P>
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.
<P>
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.
<P>
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&lt;int&gt;::iterator,
or list&lt;char&gt;::iterator, or list&lt;string&gt;::iterator.
<P>
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.
<P>
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().
<P>
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.
<P> <HR> <P> 
<H4>Using STL in the field</H4>
<P>
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.
<P>
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.
<P>
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.
<P>
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.
<P>
There is much more to know about STL programming and I hope you have enjoyed
working through these examples.
<P>
The two books in the bibliography both have active errata pages on the web
so you can keep them right up to date.
<P>
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.
<P>
<H4>Bibliography</H4> 
The STL Tutorial and Reference Guide, David Musser and Atul Saini. 
Addison Wesley 1996.
<P>
The C++ Programming Language 3e, Bjarne Stroustrup.
Addison Wesley 1997.

<!--===================================================================-->
<P> <hr> <P> 
<center><H5>Copyright &copy; 1998, Scott Field <BR> 
Published in Issue 34 of <i>Linux Gazette</i>, November 1998</H5></center>

<!--===================================================================-->
<P> <hr> <P> 
<A HREF="./index.html"><IMG ALIGN=BOTTOM SRC="../gx/indexnew.gif" 
ALT="[ TABLE OF CONTENTS ]"></A>
<A HREF="../index.html"><IMG ALIGN=BOTTOM SRC="../gx/homenew.gif"
ALT="[ FRONT PAGE ]"></A>
<A HREF="./nw_burger.html"><IMG SRC="../gx/back2.gif"
ALT=" Back "></A>
<A HREF="./anderson.html"><IMG SRC="../gx/fwd.gif" ALT=" Next "></A>
<P> <hr> <P> 
<!--startcut ==========================================================-->
</BODY>
</HTML>
<!--endcut ============================================================-->