368 Part V: Optional Features

Input a name (input an x to terminate list) Adams

Davis Valentine Smith Wilson

x

Sorted output:

Adams

Davis

Smith

Valentine

Wilson

Press any key to continue . . .

The list container provides a large set of operators. Simple operations include insert, swap, and erase. This same container also gives the pro­ grammer the ability to automatically iterate through the list invoking the same user-defined function on each object.

The operation that the list cannot provide is random access. Because objects can be snapped together in any order, there is no quick way for the list class to return the nth object.

Iterators

The STLList sample program presented in the prior section uses a destruc­ tive approach to iterating through the list. The pop_front() method moves the user through the list by removing the first object in each case.

The programmer iterates through an array by providing the index of each ele­ ment. However, this technique doesn’t work for containers like list that don’t allow for random access. One could imagine a solution based upon methods such as getFirst() and getNext(); however, the designers of the STL wanted to provide a common method for traversing any type of container. For this, the STL defines the iterator.

An iterator is an object that points to the members of a container. In general, every iterator supports the following functions:

A class can return an iterator that points to the first member of the collection.

The iterator can be moved from one member to the next.

The program can retrieve the element pointed to by the iterator.

Chapter 28: Standardizing on the Standard Template Library 369

The code necessary to iterate through a list is different from that necessary to traverse a vector (to name just two examples). However, the iterator hides these details.

The following STLListUserClass program uses an iterator to traverse an STL list in a non-destructive way:

// STLListUserClass - use a list to contain and sort a // user defined class

#include <list> #include <string> #include <cstdio> #include <cstdlib> #include <iostream>

using namespace std;

//Student - some example user defined class class Student

{

public:

Student(char* pszName, int id)

{

name = new string(pszName); ssID = id;

}

string* name; int ssID;

};

//the following function is required to support the

//sort operation

bool operator<(Student& s1, Student& s2)

{

return s1.ssID < s2.ssID;

}

// define the collection of students list<Student> students;

int main(int argc, char* pArgs[])

{

//add three student objects to the list students.push_back(*new Student(“Marion Haste”, 10)); students.push_back(*new Student(“Dewie Cheatum”, 5)); students.push_back(*new Student(“Stew Dent, Sr.”, 15));

//now sort the list

students.sort();

//and iterate through the list:

//1) allocate an iterator that points to the first

//element in the list

370 Part V: Optional Features

list<Student>::iterator iter = students.begin();

//2) continue to loop through the list until the iterator

//hits the end of the list

while(iter != students.end())

{

// 3) retrieve the Student that the iterator points at Student& s = *iter;

cout << s.ssID << “ - “ << *s.name << endl;

//4) now move the iterator over to the next element

//int the list

iter++;

}

system(“PAUSE”); return 0;

}

This program defines a list of user-defined Student objects (rather than simple names). Three calls to push_back() add elements to the list (hard­ coding these calls keeps the program smaller). The call to sort() is the same as that used in the STLList program.

The sort() function within the Standard Template Library classes

requires the user to overload the “less than” operator. (This is one of the few places where a user-defined operator other than assignment is required.) operator<(Student&, Student&) is invoked by the expression s1 < s2 when both s1 and s2 are of type Student.

The program allocates an iterator iter to navigate its way through the list. Look carefully at the iterator declaration: list<Student>::iterator is an iterator to a list container of Student objects. The strong typing is demon­ strated clearly by the assignment (see Step 3 in preceding code): *iter returns a reference to a Student object.

The output of this program appears as follows:

5 - Dewie Cheatum

10 - Marion Haste

15 - Stew Dent, Sr.

Press any key to continue . . .

Chapter 28: Standardizing on the Standard Template Library 371

How a sort() sorts

I have glossed over an interesting point: How does the sort() method know which of two elements in the list is “bigger”? In other words, what determines the sort order? C++ defines its own sorting order for some types. For example, C++ knows which of two ints is larger. In addi­ tion, the STL sorted the collection of ASCII strings contained in the name collection using the same rules that a dictionary uses.

The STLList program did not need to take any special measures when sorting names. C++ does not know which of two Student objects

is larger — the global function ::operator <(Student&, Student&) serves this pur­ pose. The sort() method invokes this function as it makes its way through the list to determine the proper sort order.

As an experiment, reverse the sense of the operator<() function as follows:

return s1.ssID > s2.ssID;

The result is a list sorted in the exact opposite direction.

Using Maps

Maps are one other class of collection. There are a number of different types of maps, but they all share a common property: Maps are designed to allow elements to be stored and retrieved quickly according to some key or index. The following next program demonstrates the principle.

For example, a school may register students by a unique identification number. This ID is used in every facet of school life. This ID is used to retrieve student information, check out books from the library, and assign grades in courses. It is important that any program be able to retrieve a stu­ dent by his or her student ID quickly and efficiently.

The following STLMap program creates and uses a collection of Student objects, which are keyed by ID:

//STLMap - use a map container to retain a collection of

//objects ordered by a key

#include <cstdio> #include <cstdlib> #include <iostream> #include <sstream> #include <string> #include <map>

372 Part V: Optional Features

using namespace std;

//SC - Student comparison function; designed to determine

//the sorting order of the students

struct SC

{

bool operator()(const int id1, const int id2) const

{

return id1 < id2;

}

};

//the map actually contains a Pair; the left element

//being the key while the right element is the data (in

//this case Student)

class Student; typedef Student* SP;

typedef pair<const int, Student*> Pair; typedef map<int, SP, SC> Map;

typedef map<int, SP, SC>::iterator MapIterator;

//collection of Students Map students;

//Student - define the important properties of a student

//including the key use when looking him/her up

//from the student rolls(student id)

class Student

{

public:

Student(char* pszName, int id)

:studentIDKey(id), name(pszName) {}

//getKey - the key is used as an index into the map const int getKey() { return studentIDKey; }

//display - create a meaningful output

//for a Student object

string display()

{

ostringstream out;

out << studentIDKey << “ - “ << name; return out.str();

}

protected:

//Student elements are keyed by student id const int studentIDKey;

//the name of the student (plus any other data) string name;

};

int main(int argc, char* pArgs[])

Chapter 28: Standardizing on the Standard Template Library 373

{

//add a few of students to the students collection -

//a map actually stores objects as “pairs” with the

//left member being the key and the right the actual

object Student* pS;

pS = new Student(“Sean Yours”, 3456); Pair* ptr = new Pair(pS->getKey(), pS); students.insert(*ptr);

//a map overloads the index operator to create the Pair

//and insert it into the map for us

students[1234] = new Student(“Fresch Man”, 1234); students[5678] = new Student(“Student, Jr.”, 5678);

//iterate through the collection of students;

//a map is always retained in the sorted order

//determined by the SC class

cout << “Sorted list of students:” << endl; MapIterator iter = students.begin(); while(iter != students.end())

{

Pair p = *iter; Student* s = p.second;

cout << s->display() << endl; iter++;

}

//the increment and decrement operator can also be used

//to find the successor and predecessor

cout << “\nLook up student 3456” << endl; MapIterator p = students.find(3456);

cout << “Found student “ << p->second->display() << endl;

MapIterator p1 = p;

MapIterator prior = --p1; // <- predecessor cout << “Predecessor = “

<< prior->second->display() << endl;

MapIterator p2 = p;

MapIterator successor = ++p2; // <-successor cout << “Successor = “

<<successor->second->display() << endl;

//find() returns the end iterator when it can’t find the

//object in question; operator[] returns a NULL

if (students.find(0123) == students.end())

{

cout << “The call students.find(0123) returns “

<<“students.end() since student 0123 doesn’t exist”

<<endl;

}

374 Part V: Optional Features

// output using index

cout << “To test index: students[3456] = “ << students[3456]->display() << endl;

if (students[0123] == NULL)

{

cout << “but students[0123] returns a NULL” << endl;

}

system(“PAUSE”); return 0;

}

The key to the program (if you can pardon the pun) is found in the initial three typedefs. A map contains a set of Pair objects, each of which contains a first and second element. The first element is the student ID key, and the second is the Student object. The Map class adds an object of class SC. This class con­ tains a single method that compares two Student objects to determine which is larger. (This is slightly more complicated than the global function used with the list collection, but the effect is the same.)

The STLMap program begins by creating three Student Pair objects and adding them to the list. The iteration through the container displays the Student objects in order by student ID. There is no need to invoke a sort() method because map classes already retain objects sorted by key.

The second section of the STLMap program looks up a student by ID using the find() method. The program also demonstrates how easy it is to retrieve the prior and next objects in the list using the decrement and increment operators.

The output from the program appears as follows:

Sorted list of students: 1234 - Fresch Man

3456 - Sean Yours

5678 - Student, Jr.

Look up student 3456

Found student 3456 - Sean Yours

Predecessor = 1234 - Fresch Man

Successor = 5678 - Student, Jr.

The call students.find(0123) returns students.end() since student 0123 doesn’t exist

To test index: students[3456] = 3456 - Sean Yours but students[0123] returns a NULL

Press any key to continue . . .

Part VI

The Part of Tens

In this part . . .

What For Dummies book would be complete without a Part of Tens? In Chapter 29, I cover ten ways to

avoid adding bugs to your C++ program. (Most of these suggestions work for C programs too, at no extra charge.) Chapter 30 lists the ten most important compiler options available in the Dev-C++ compiler, which is available to the reader on the enclosed CD-ROM.