Chapter 25. Standard Template Library
Goodness and evil never share the same road, just as ice and charcoal never share the same container.
As people began to develop code, they noticed that they were coding the same things over and over again. For example, in every large C program, you’ll probably find an implementation of a linked list. Since it’s better to reuse than to rewrite, the designers of C++ have added a library of common containers (lists, arrays, and others) to the language. This library is known as the Standard Template Library or STL.
These containers are designed as templates so that they can hold almost anything. The library provides not only the containers but also iterators that make access to the contents of a container easier.
Finally, there are the algorithms that perform common functions on a container, such as sorting, merging two containers, locating elements, and other such functions.
STL Basics
In this section we take a look at the basic concepts that went into the design of the STL and how all these design elements come together to provide a very robust and flexible way of handling items.
Containers
The core of the STL is the container. We’re already familiar with a couple of STL container types, the vector (a single-dimension array) and the stack.
The STL divides containers into sequences, which store their elements in order, and associative containers, in which elements are accessed using a key value.
The basic STL containers are:
vectorA random-access sequential container. This looks pretty much like a C++ array, but you can expand it by inserting elements into it. You can also delete elements from a vector.
dequeSimilar to a vector, but it’s faster at inserting and deleting elements in the middle of the container.
listA doubly linked list. Does not allow for random access.
setA set of items. Items in the set are ordered and unique.
multisetA set that permits multiple items with the same value to be stored in it.
mapAlso known as associative array. This is a container whose values can be looked up by a key. Because this is a template, the key and value can be almost anything. Only one value is stored for each key.
multimapA map that allows multiple values to be stored for each key.
These containers give you a way of storing most data in almost any way you want to. Now that we’ve got our data stored, we need access to it.
Iterators
Iterators allow you to go through a container and access the data inside. One form of this is the forward iterator, which allows you to access each element from first to last. There is a reverse iterator that allows you to go the other way and a bidirectional iterator, which goes both ways. Finally, there is the random access iterator, which allows you to access any element randomly.
Not all containers support all iterator types. For example,
the vector supports random access
iterators, while the list
container does not.
We’ll see how to use iterators in the class program described later in this chapter.
Algorithms
We have containers to hold the data and iterators so we can access it. For
example, the sort algorithm can
be used to sort an ordered container such as a vector. Some of the
other algorithms include:
findFinds an item in a container
countCounts the number of items in a container
equalTests to see if containers are equal
for_eachRuns each element of a container through a given function
copyCopies a container
reverseReverses the elements of an ordered container
These three elements—containers, iterators, and algorithms—make up the STL. Now that we know the basics, let’s see how to use this library in the real world.
Class List—A Set of Students
Suppose we are working on a school scheduling program. We need to keep track of the number
of students in each class. In STL terms, we need a container to hold
the students. The type of container we need is a set.
A set is a container that
holds an ordered list of items. In this case our items are student
names (which are represented by strings). To define our class list, we
use the following declarations:
#include <set> #include <string> std::set<std::string> class_set; // A list of students in the class
The statement #include
<set> is used to get the definition of the set template. We then use this template to
define a set of strings named class_set. (The term “set” is used instead
of the more common “list” to avoid confusion with the STL type
list, which is discussed later in
this chapter.)
We can now add names to our set of students:
while (! in_file.eof( )) {
std::string student;
in_file >> student;
class_set.insert(student);
}This code uses the member function insert to add new students to our
set.
Iterating Through a Set
Now we need to print out the class roster. To do so, we need to write some code to go through the set of students and print out each student’s name. The STL has a concept called an iterator to help us do just that. You can think of an iterator as a pointer to an item in a set (or any other STL container). Actually, an iterator is much more complex than a pointer, but the STL tries to hide that complexity from you and make an iterator look as much like a pointer as possible.
Our iterator for the printing of students is declared as follows:
std::set<std::string>::const_iterator cur_student;
We are using const_iterator
because we will not be changing the values of the items as we go
through them.
Now for the actual stepping through the set. The first element
of the set is called class_set.begin(
); the empty space past the last element is called
class_set.end( ). To step through
all the elements of the set, we use the following code:
for (cur_student = class_set.begin( );
cur_student != class_set.end( );
++cur_student)
{
std::cout << (*cur_student) << '
';
}Notice that to end the loop we used the condition:
cur_student != class_set.end( );
instead of:
cur_student < class_set.end( ); // Wrong!
That’s because the elements of a set are unordered, which means that you
cannot compare two iterators for anything except equality. They
either point to the same element or they don’t. It’s meaningless to
say that one element comes before another.
Using std::foreach to Write Out the Set
Iterating through an entire container is a common operation.
In fact, there’s an STL library function to do just that. Rather
than write our own code, we can use the STL foreach algorithm to output our list:
#include <algorithm>;
//......
static void write_student(set<string>::const_iterator& cur_student) {
std::cout << *cur_student << '
';
}
//......
foreach(class_set.begin(), class_set.end( ), write_student);The include file algorithm brings in the STL algorithm
functions. In this case, the algorithm we are interested in is
foreach. The function, write_student, merely writes out a
student’s name.
The heart of the code is the foreach function call. The first argument
is the place to start; the second argument is one after the place to
stop. (Note that this one-past-stopping is a key concept used in
many STL functions.)
Finally, we have a
function to be called for each student.
Multisets
One of the problems[1] with setsis that each item in a set must be unique. So
what happens if two students named John Smith enroll in the same
class? When we try to do our insert, the set code will see that we’ve
already got John Smith in the set and refuse to add another
one.
A set of objects that can contain duplicates is called a
std::multiset . Except for the way in which it handles duplicates, a
std::multiset is just like a
set. So we really need to declare
our class using this new container:
std::multiset<string> class_set; // A list of students in the class
Creating a Waiting List with the STL List
Suppose we have more students who want to take a class than we have places to put them. In that case we’ll have to start a waiting list for those people who want to get in if space opens up.
We can’t use a set as a waiting list, because a set stores the
elements in order. For that we need the STL container std::list. A std::list is an ordered list of elements
that allows us to add students on the back end and remove them from
the front end.
Our waiting list declaration is:
#include <list> std::list<std::string> waiting_list; // Waiting list for the class
When we want to add a student to the back of the list, we use the code:
waiting_list.push_back(student);
To remove a student from the front, we need two statements:
student = waiting_list.top( );
waiting_list.pop_front( );Iterating through a list is just like iterating through a
set. That’s because they are both
containers, and the STL is designed so that all
containers act the same whenever possible.
Storing Grades in a STL Map
Let’s change our class roster so that we record not only the name of each student, but also the
student’s grade as well. We do this using something called a map. To define our class map, we use the
following declaration:
#include <map> // Map key=name(string), value = grade(char) template map<string, char> student_roster;
Inserting an item into a map
is a little trickier than inserting one into a set because we are inserting a pair of
items. The STL handles this nicely by providing a pair class that takes two elements and turns
them into an item that a map can handle. For example, if John Smith is
in the class and got an A, we would write:
student_roster(pair(string("John Smith"), 'A'));Suppose we want to find out what Mr. Smith’s grade is. We can
search for his record using the find function call. It takes three
parameters: a place to start the search, a place to end the search,
and something to look for. It returns an iterator pointing to the item
found or, if nothing is found, the value returned by the end function. To look for Mr. Smith’s grade,
we use the code:
map<string, char>::const_iterator record_loc;
record_loc = find(student_roster.begin(), student_roster.end( );
string("John Smith"));Now let’s check to see if we found the student:
if (record_loc == student_roster.end( ))
std::cerr << "John Smith not found in the class
";The iterator points to a pair
consisting of the student’s name and grade. The fields of a pair are named first and second. To print John’s record, we use the
statement:
std::cout << "Student: " << record_loc->first << " Grade:" <<
record_loc->second << '
';Putting It All Together
Now let’s use our knowledge of the STL to create a class to handle a simple class roster and waiting
list. The class class_stuff will
contain member functions to perform the following tasks:
Add a student to a class. If the class is full, the student will be added to the waiting list.
Remove a student from a class. If the waiting list has a student in it, the first student on the waiting list gets put in the class.
Record a grade for each assignment.
Print a class roster including grades.
Let’s start by defining the class. We’ll record information
about students in the class in a map. The key is the student’s name, and the
value is a vector containing the
grades.
A vector is very similar to a
list. However, it allows indexed
access to its elements much the same way an array does. We will use
the function size to determine the
number of elements in the vector
and resize to increase the size if
needed.
The start of our class_stuff
definition looks like this:
class class_stuff {
public:
typedef std::vector<int> grades; // A set of grades
std::map<std::string, grades> roster; // Roster of current class
std::list<std::string> waiting_list; // People waiting on the listNow we need to define the member functions. The first one adds a student to a class:
void class_stuff::add_student(
const string& name // Name of the student to add
)
{We first check to see if the student is already in the class; if she is, we don’t add her again:
if (roster.find(name) != roster.end( ))
return; // Already in the class, don't reuseNext we check to see if the number of students currently in the
class has reached the limit. If there is room, we add the student to
the class using the new_student
function described below. If there is not room in the class, the
student goes on the end of the waiting list:
if (roster.size( ) < MAX_STUDENTS) {
// Class has room, add to class
new_student(name);
} else {
// No room, put on waiting list
waiting_list.push_back(name);
}
}The new_student function is
responsible for adding a student to the roster. It creates an empty
set of grades, then inserts the student into the class:
// Insert a student into the class
void class_stuff::new_student(
const string& name // Student to add to the class
)
{
grades no_grades; // Empty grade vector
roster.insert(pair<string, grades>(name, no_grades));
}
};The code to drop a student first checks to see if the student is actually in the class; he can’t be dropped if he’s not enrolled:
void class_stuff::drop_student(
const string& name // Name of the student to drop
)
{
// The student we are probably going to drop
map<string, grades>::iterator the_student =
roster.find(name);
if (the_student == roster.end( ))
return; // Student is not in the classNext we remove the student from the class. The erase member function eliminates an element
from the map:
roster.erase(name);
Finally we check the waiting list and add one student from it if there’s someone available:
// Add a person from the waiting_list if
// there's anyone waiting
if (waiting_list.size( ) > 0) {
string wait_name = waiting_list.front( );
waiting_list.pop_front( );
new_student(wait_name);
}
}To record a grade, we first find the student’s record:
void class_stuff::record_grade(
const string& name, // Name of the student
const int grade, // Grade of this assignment
// Assignment number
const unsigned int assignment_number
)
{
map<string, grades>::iterator the_student =
roster.find(name);
if (the_student == roster.end( ))
{
std::cerr << "ERROR: No such student " << name << '
';
return;
}Then we adjust the size of the grade vector so that it has enough entries to contain the assignment:
// Resize the grade list if there's not enough room
if (the_student->second.size( ) <= assignment_number)
the_student->second.resize(assignment_number+1);Finally, we store the value of the grade:
the_student->second[assignment_number] = grade; }
Our last function prints the grades for all the students in a
class. To do this we need a sorted list of names. We start by copying
the names from the roster into a
container (storted_names) that can
be sorted:
void class_stuff::print_grades( )
{
std::vector<std::string> sorted_names; // Student names sorted
// The student we are inserting into the storted_names list
map<string, grades>::iterator cur_student;
for (cur_student = roster.begin( );
cur_student != roster.end( );
++cur_student)
{
sorted_names.push_back(cur_student->first);
}The std::sort function is one
of the algorithms supplied by the STL. You give it a range of items to
sort and it sorts them. In this case, we want to sort the entire
std::vector from beginning to
end:
sort(sorted_names.begin( ), sorted_names.end( ));
Now it’s simply a matter of stepping through the sorted name
list and printing the data. About the only new thing in this section
of code is the use of [] to access elements of the roster. Remember that roster is a mapping of key to value. One way
to find out the value associated with a particular key is to use the
[] as follows:
value=a_map[key];
The rest of the code for printing the grades is pretty straightforward:
// The current student to print
std::vector<std::string>::const_iterator cur_print;
for (cur_print = sorted_names.begin( );
cur_print != sorted_names.end( );
++cur_print)
{
std::cout << *cur_print << ' ';
// The grade we are printing now
grades::const_iterator cur_grade;
for (cur_grade = roster[*cur_print].begin( );
cur_grade != roster[*cur_print].end( );
++cur_grade)
{
std::cout << *cur_grade << ' ';
}
std::cout << '
';
}
}Example 25-1 shows the
full code for our class_stuff
object, as well as some test code.
/********************************************************
* class_stuff -- A simple class to handle students *
* and grades. *
********************************************************/
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <algorithm>
const unsigned int MAX_STUDENTS = 5; // Max number of students per class
// Set low for testing
class class_stuff {
public:
typedef std::vector<int> grades;// A set of grades
std::map<std::string, grades> roster; // Roster of current class
std::list<std::string> waiting_list; // People waiting on the list
public:
// Constructor defaults
// Destructor defaults
// Copy constructor defaults
// Assignment operator
public:
void add_student(const std::string& name);
void drop_student(const std::string& name);
void record_grade(const std::string& name,
const int grade,
const unsigned int assignment_number
);
void print_grades( );
private:
// Insert a student into the class
void new_student(
const std::string& name // Student to add to the class
)
{
grades no_grades; // Empty grade vector
roster.insert(
std::pair<std::string, grades>(name, no_grades));
}
};
/********************************************************
* class_stuff::add_student -- Add a student to a class *
* If the class if full, add him to the waiting *
* list. *
*********************************************************/
void class_stuff::add_student(
const std::string& name // Name of the student to add
)
{
if (roster.find(name) != roster.end( ))
return; // Already in the class, don't reuse
if (roster.size( ) < MAX_STUDENTS) {
// Class has room, add to class
new_student(name);
} else {
// No room, put on waiting list
waiting_list.push_back(name);
}
}
/********************************************************
* class_stuff::drop_student -- Remove student from *
* a class. If there's a waiting list his place is *
* filled by the first student on the list. *
********************************************************/
void class_stuff::drop_student(
const std::string& name // Name of the student to drop
)
{
// The student we are probably going to drop
std::map<std::string, grades>::iterator the_student =
roster.find(name);
if (the_student == roster.end( ))
return; // Student is not in the class
roster.erase(name);
// Add a person from the waiting_list if
// there's anyone waiting
if (waiting_list.size( ) > 0) {
std::string wait_name = waiting_list.front( );
waiting_list.pop_front( );
new_student(wait_name);
}
}
/********************************************************
* class_stuff::record_grade -- Record a grade for *
* a student. *
********************************************************/
void class_stuff::record_grade(
const std::string& name, // Name of the student
const int grade, // Grade of this assignment
// Assignment number
const unsigned int assignment_number
)
{
std::map<std::string, grades>::iterator the_student =
roster.find(name);
if (the_student == roster.end( ))
{
std::cerr << "ERROR: No such student " << name << '
';
return;
}
// Resize the grade list if there's not enough room
if (the_student->second.size( ) <= assignment_number)
the_student->second.resize(assignment_number+1);
the_student->second[assignment_number] = grade;
}
/********************************************************
* class_stuff::print_grades -- Print the students *
* and their grades. *
********************************************************/
void class_stuff::print_grades( )
{
std::vector<std::string> sorted_names; // Student names sorted
// The student we are inserting into the storted_names list
std::map<std::string, grades>::iterator cur_student;
for (cur_student = roster.begin( );
cur_student != roster.end( );
++cur_student)
{
sorted_names.push_back(cur_student->first);
}
std::sort(sorted_names.begin( ), sorted_names.end( ));
// The current student to print
std::vector<std::string>::const_iterator cur_print;
for (cur_print = sorted_names.begin( );
cur_print != sorted_names.end( );
++cur_print)
{
std::cout << *cur_print << ' ';
// The grade we are printing now
grades::const_iterator cur_grade;
for (cur_grade = roster[*cur_print].begin( );
cur_grade != roster[*cur_print].end( );
++cur_grade)
{
std::cout << *cur_grade << ' ';
}
std::cout << '
';
}
}
int main( )
{
// A class for testing
class_stuff test_class;
test_class.add_student("Able, Sam");
test_class.add_student("Baker, Mary");
test_class.add_student("Johnson, Robin");
test_class.add_student("Smith, Joe");
test_class.add_student("Mouse, Micky");
test_class.add_student("Gadot, Waiting");
test_class.add_student("Congreve, William");
std::cout << "Before drop " << std::endl;
test_class.print_grades( );
std::cout << "
";
test_class.drop_student("Johnson, Robin");
std::cout << "After drop " << std::endl;
test_class.print_grades( );
std::cout << "
";
int i;
for (i = 0; i < 5; ++i)
{
test_class.record_grade("Able, Sam", i*10+50, i);
test_class.record_grade("Baker, Mary", i*10+50, i);
test_class.record_grade("Smith, Joe", i*10+50, i);
test_class.record_grade("Mouse, Micky", i*10+50, i);
test_class.record_grade("Gadot, Waiting", i*10+50, i);
}
std::cout << "Final " << std::endl;
test_class.print_grades( );
std::cout << "
";
return (0);
}Practical Considerations When Using the STL
The containers and related functions of the STL do a good job of making your life easier. However, because the STL is so flexible and powerful, it can sometimes be difficult to get things right. In this section we’ll explore a few techniques that can make your life much easier.
Getting the Types Right
One of the big problems with using STL containers is remembering the types of the variables and parameters being used. It’s very easy to use the wrong type. You’ll encounter this problem with the STL more than with most other code in part due to the flexibility of the system coupled with the large number types used in the definition of containers and the functions that work on them.
One way to make things clearer is through the use of typedef statements. For example:
typedef std::map<std::string, grades> class_roster;
Definitions like this tend to cut down on the clutter because
class_roster is much clearer (and
a little shorter) than map<string,
grades>. It also makes maintenance easier because the
definition of your type is in one place.
Error Messages
One of the problems with templates is that compiler parser technology is not yet up to speed when it comes to issuing error messages. The following example is one line of a multiline error message coming out of a broken program:
classx.cpp:78: no matching function for call to `map< basic_string< char, string_ char_traits< char>, __default_alloc_template< true, 0> >, vector< int, _ _default_ alloc_template< true, 0> >, less< basic_string< char, string_char_traits< char>, _ _ default_alloc_template< true, 0> > >, __default_alloc_template< true, 0> >::find (_ _ rb_tree_iterator< pair< const basic_string< char, string_char_traits< char>, _ _ default_alloc_template< true, 0> >, vector< int, _ _default_alloc_template< true, 0> > >, pair< const basic_string< char, string_char_traits< char>, _ _default_alloc_ template< true, 0> >, vector< int, _ _default_alloc_template< true, 0> > > &, pair< const basic_string< char, string_char_traits< char>, _ _default_alloc_template< true, 0> >, vector< int, __default_alloc_template< true, 0> > > *>, _ _rb_tree_iterator< pair< const basic_string< char, string_char_traits< char>, _ _default_alloc_template< true, 0> >, vector< int, _ _default_alloc_template< true, 0> > >, pair< const basic_ string< char, string_char_traits< char>, _ _default_alloc_template< true, 0> >, vector< int, _ _default_alloc_template< true, 0> > > &, pair< const basic_string< char, string_char_traits< char>, _ _default_alloc_template< true, 0> >, vector< int, __ default_alloc_template< true, 0> > > *>, map< basic_string< char, string_char_ traits< char>, __default_alloc_template< true, 0> >, vector< int, _ _default_alloc_ template< true, 0> >, less< basic_string< char, string_char_traits< char>, _ _default_ alloc_template< true, 0> > >, _ _default_alloc_template< true, 0> > &)'
From this we can see that something went wrong on line 78, but it’s difficult to tell what. (Turns out that this is a type-related problem.) Unfortunately, because of the clutter, it’s next to impossible to tell what’s wrong other than it’s near line 78 and it has something to do with the STL.
The STL pushes the limits of C++ technology, and sometimes the limits push back.
Getting More Information
There is a good reference for the STL at http://www.sgi.com/tech/stl/index.html. Please note that this reference is for a slightly more advanced version of the STL than the one used in the C++ standard.Another STL reference can be found at http://www.cs.rpi.edu/projects/STL/htdocs/stl.html.
Exercises
Exercise 25-1: In Chapter 1 we defined a histogram program that used our home-grown infinite array. Rewrite the program to use the STL.
Exercise 25-2: Write a program that produces an index for a book. The input file is a set of page numbers and index information of the form:
<page-number> <index entry>
There may be more than one record for each index entry. The output should be a sorted list of index entries such as:
alpha 10, 20, 30 beta 5, 6, 18 .....
Exercise 25-3: Change the cross-reference program you wrote for Exercise 20-1 to use the STL.
Exercise 25-4: Write a program that does a frequency count of each word in a document.