1236 lines
43 KiB
HTML
1236 lines
43 KiB
HTML
<!--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 <string>
|
|
#include <list>
|
|
int main (void) {
|
|
list<string> Milkshakes;
|
|
}
|
|
</PRE>
|
|
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:
|
|
<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 <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");
|
|
}
|
|
</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 <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;
|
|
}
|
|
</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 <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;
|
|
}
|
|
}
|
|
</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 <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);
|
|
}
|
|
</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 <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;
|
|
}
|
|
</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 <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;
|
|
}
|
|
</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 <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;
|
|
}
|
|
</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 <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;
|
|
}
|
|
}
|
|
</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 <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;
|
|
}
|
|
}
|
|
</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<char> 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 << "We have " << NumberOfNullCharacters << endl;
|
|
</PRE>
|
|
Let's find the character '1'
|
|
<PRE>
|
|
list<char>::iterator Iter;
|
|
Iter = find(Characters.begin(), Characters.end(), '1');
|
|
cout << "We found " << *Iter << 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 <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;
|
|
}
|
|
</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 <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);
|
|
}
|
|
</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 <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
|
|
*/
|
|
}
|
|
</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<int> 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<int> 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<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
|
|
</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 <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;
|
|
}
|
|
</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 <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);
|
|
|
|
}
|
|
</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 <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);
|
|
}
|
|
</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 <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
|
|
|
|
}
|
|
</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<int>::iterator,
|
|
or list<char>::iterator, or list<string>::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 © 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 ============================================================-->
|