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 Control? 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 Remarkables 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 Stroustrustrup 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.
.
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 do not 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 W E'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 will not 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 The Write Elements, Some Both. Iterators Also Determine The Direction of Processing In A Container.
You can obtain itrators to the first position in a contact begin (). You can call the contact () Function to get the paste 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 will not 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 stlist lis.
#include
#include
INT main (void) {
List
}
Thats to it. You've defined a list. Could it have been any easier? By saying list
G Test1.cpp -otest1
Note That The include File iostream.h is buried in one of the site is missing in some of the example.
Now That We Have A List, We can Start Using It to Hold Things. We'll Add Some Strings To The List. There Ipe 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
#include
INT main (void) {
List
Milkshakes.push_back ("chocolate");
Milkshakes.push_back ("strawberry");
Milkshakes.push_front ("limited");
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 itprints before the error message.
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 THESEMUGHOUGHOUT INTINGORYES, BEFORE Printing Them Out.
Here's what i mean.
/ *
|| Using a list to TRACK AND Report Program Messages and Status
* /
#include
#include
#include
INT main (void) {
#define ok 0
#define info 1
#define Warning 2
Int retURN_CODE;
List
List <: string> warningmessages;
// During a Program these Messages Are Loaded At Various Points
Infomessages.push_back ("info: program start");
// Do Work ...
WARNINGMESSAGES.PUSH_BACK ("Warning: No Customer Records Have Been Found"); // DO WORK ...
Return_code = OK;
IF (! infMessages.empty ()) {// there is info message
Infomessages.push_front ("INFORMATIONAL MESSAGES:");
// ... Print The Info Messages List, WE'LL See How Later
RETURN_CODE = INFO;
}
IF (! WarningMesses.empty ()) {// Therevel Warning Messages
WARNINGMESSAGES.PUSH_FRONT ("WARNING Messages:");
// ... Print The Warning Messages List, We'll See How Later
Return_code = warning;
}
// if there.............
IF (Infomessages.empty () && WarningMessages.empty ()) {
COUT << "there" there "tre no message" << 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
#include
#include
INT main (void) {
List
List
Milkshakes.push_back ("chocolate");
Milkshakes.push_back ("strawberry");
Milkshakes.push_front ("limited");
Milkshakes.push_front ("vanilla");
// print the milkshakes
Milkshakes.push_front ("The Milkshake Menu");
Milkshakes.push_back ("*** Thats the End ***");
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 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 can not 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 can not say Milkshakes.begin () 2 to point to the third object in .
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_each algorithm can relieve us of this.
/ *
|| How to Print A Simple STL List Mkii
* /
#include
#include
#include
#include
PrintIt (String & StringToprint) {
Cout << StringToprint << endl;
}
INT main (void) {
List
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 do not need to initialise, test or increment any iterators. For_each () nicely modularises our code .................. ..
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 solid ()
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 tents.
/ *
|| How to count Objects in An Stl List
* /
#include
#include
INT main (void) {
List
Scores.push_back (100); scorers.push_back (80);
Scores.push_back (45); score.push_back (75);
Scores.push_back (99); scores.push_back (100);
INT NUMBEROF100SCORES (0);
Count (Scores.Begin (), ScoreS.end (), 100, Numberof100scores);
Cout << "there" << numberof100scores << "scorers 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
Count 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
#include
#include
Const string toothbrushcode ("0003");
Class isatoothbrush {
PUBLIC:
Bool Operator () (String & SalesRecord) {
Return SalesRecord.substr (0,4) == TOTHBRUSHCODE;
}
}
INT main (void) {
List
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 (),
ISATOTHBRUSH (), NUMBEROTHBRUSHES
Cout << "there" "
<< Numberoftoothbrushes
<< "TOTHBRUSHES SOLD" << Endl;
}
The Output of The Program Isthere 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 ISATOTHBRUSH () () 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 can not 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
#include
#include
Class isatoothbrush {
PUBLIC:
ISATOTHBRUSH (String & IntoothBrushcode):
TOTHBRUSHCODE (INTOTHBRUSHCODE) {}
Bool Operator () (String & SalesRecord) {
Return SalesRecord.substr (0,4) == TOTHBRUSHCODE;
}
Private:
String Toothbrushcode;
}
INT main (void) {
List
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 (),
ISATOTHBRUSH (Variabletoothbrushcode),
Numberoftoothbrushes);
Cout << "there" "
<< Numberoftoothbrushes
<< "TOTHBRUSHES 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 objectsThese 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 (), There 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
#include
#include
INT main (void) {
List
List
FRUIT.PUSH_BACK ("apple");
Fruit.push_back ("pineapple");
Fruit.push_back ("star apple");
Fruititerator = Find (Fruit.begin (), Fruit.eGin (), "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 itrator fruit.erator. 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 Demonstrate Find_if (), Which AccEcts A Function Object As A Parameter, And Uses It To Make A More Complex Assess in WHether An Object Is "Found".
.
/ *
|| How to find things in an Stl List Mkii
* /
#include
#include
#include
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 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
// 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 sale the stl generic algorithm search
Some Characters Are A Little Easier To DEAL WITH IN AT AT A SEQUENCE OF CHARACTERS THAT CAN Be Diffic To Work with. We'll Define An Stl List To Hold The Characters.
List
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 do not know if I'd say that about a null terminated Array of characters.
Lets add some of our favourite character..
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
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..
.......................... ..
/ *
|| How to use the Search Algorithm in An Stl List
* /
#include
#include
#include
INT main (void) {
List
List
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
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
#include
#include
Printit (string & stringtoprint) {cout << StringToprint << endl;}
INT main (void) {
List
List
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 respectiveness. 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
INT main (void) {
List
/ *
|| 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 this at the specified iterator position.
List constructors
WE HAVE BEEN Defining a list like this.list
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
// List now Contains 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
Harry.push_back (1);
Harry.push_back (2);
// define a list and initialise it with the elements in harry
List
// Bill Now Contains 1, 2
ERASING Elements from a list sale 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
INT main (void) {
List
/ *
|| 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.ras (list1.begin ()); // Erase the first element (1) Using An Iterator
List1.ras (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 () Erase Objects from a list. /
|| USING THE LIST MEMBER FUNCTION REMOVE TO Remove Elements
* /
#include
#include
#include
Printit (const string & stringtoprint) {
Cout << StringToprint << endl;
}
INT main (void) {
List
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 ()
.................... ..
/ *
|| Using The Generic Remove Algorithm To Remove List Elements
* /
#include
#include
#include
Printit (String & Astring) {cout << astring << endl;}
INT main (void) {
List
List
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 accounting to new point the end iterator" << endl;
For_each (birds.begin (), newnd, 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 accounting to new paste the end ipaterator
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 use 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 ibo 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
#include
#include
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
List
List
List
For (int i = 0; i CmdlineParameters.pop_front (); // We don't want the program name // Make Sure We Have The Four Mandatory File Namesint 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 The 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 ws specified IF (Flags.Begin (), Flags.end (), ishelpflag ())! = flags.end ()) { COUT << "The Help Flag Was Specified" << endl; } // Open the files and do wherever 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 Touch The Things You Can do with a list. We Haven't Even Got To The Point of Storing A User Defined Class of Object, Alth Thats Not Hard. IF you understand The concends behind The algorithms presented here.................... 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 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. That Shi 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 . 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 key.