In This Chapter
Using the string class
Maintaining entries in a Standard Template Library list
Accessing container elements from an iterator
Using a map container
Some programs can deal with data as it arrives and dispense with it. Most programs, however, must store data for later processing. A structure that is used to store data is known generically as a container or a collection. (I use the terms interchangeably.) This book has relied heavily on the array for data storage so far. The array container has a couple of nice properties: It stores and retrieves things quickly. In addition, the array can be declared to hold any type of object in a type-safe way. Weighed against these advantages, however, are two large negatives.
First, you must know the size of the array at the time it is created. This requirement is generally not achievable, although you will sometimes know that the number of elements cannot exceed some "large value." Viruses, however, commonly exploit this type of "it can't be larger than this" assumption, which turns out to be incorrect. There is no real way to "grow" an array except to declare a new array and copy the contents of the old array into the newer, larger version.
Second, inserting elements anywhere within the array involves copying elements within the array. This is costly in terms of both memory and computing time. Sorting the elements within an array is even more expensive.
C++ now comes with the Standard Template Library, or STL, which includes many different types of containers, each with its own set of advantages (and disadvantages).
The C++ Standard Template Library is a very large library of sometimes-complex containers. This session is considered just an overview of the power of the STL.
The most common form of array is the null-terminated character string used to display text, which clearly shows both the advantages and disadvantages of the array. Consider how easy the following appears:
cout << "This is a string";
But things go sour quickly when you try to perform an operation even as simple as concatenating two of these null-terminated strings:
char* concatCharString(const char* s1, const char* s2) { int length = strlen(s1) + strlen(s2) + 1; char* s = new char[length]; strcpy(s, s1); strcat(s, s2); return s; }
The STL provides a string
container to handle display strings. The string
class provides a number of operations (including overloaded operators) to simplify the manipulation of character strings (see Table 27-1). The same concat()
operation can be performed as follows using string
objects:
string concat(const string& s1, const string& s2) { return s1 + s2; }
Table 27.1. Major Methods of the string
Class
Method | Meaning |
---|---|
| Creates an empty string object. |
| Creates a string object from a null-terminated character array. |
| Creates a new |
| Destructor returns internal memory to the heap. |
| Overwrites the current object with a copy of the string |
| Extracts a string from the input file. Stops when after |
| Inserts string to the output file. |
string operator+(const string& s1, const string& s2) string operator+(const sring& s1, const char* pszS2) | Creates a new string that is the concatenation of two existing strings. |
string& operator+=( const string& s); string& Operator+=( const char* pszS) | Appends a string to the end of the current string. |
| Returns the |
bool operator==(const string& s1, const string& s2) | Returns true if the two strings are lexographically equivalent. |
bool operator<(const string& s1, const string& s2) | Returns true if |
bool operator>(const string& s1, const string& s2) | Returns true if |
string& append(const string& s) string& append(const char* pszS) | Appends a string to the end of the current string. |
| Returns a reference to the |
| Returns the number of characters the current string object can accommodate without allocating more space from the heap. |
| Returns < 0 if the current object is lexicographically less than |
const char* c_str() const char* data() | Returns a pointer to the null-terminated character array string within the current object. |
| Returns true if the current object is empty. |
size_t find(const string& s, size_t index = 0); | Searches for the substring |
string& insert(size_t index, const string& s) string& insert(size_t index, const char* pszS) | Inserts a string into the current string starting at offset |
| Returns the maximum number of objects that a string object can hold, ever. |
string& replace(size_t index, size_t num, const string& s) string& replace(size_t index, size_t num, const char* pszS) | Replaces |
| Resizes the internal buffer to the specified length. |
size_t size() size_t length() | Returns the length of the current string. |
string substr(size_t index, size_t length) | Returns a string consisting of the current string starting at offset index and continuing for length characters. |
The C++ '09 standard says that functions such as max_size()
return a number of type size_type
. I have listed the argument types in Table 27-1 as size_t
because that's the way they are declared in the gcc compiler that comes with this book. Currently they are both synonyms for unsigned long int
. Be forewarned that at some future date these two types might diverge and the argument types in Table 27-1 might change from size_t
to size_type
.
The following STLString program demonstrates just a few of the capabilities of the string
class:
// STLString - demonstrates just a few of the features // of the string class which is part of the // Standard Template Library #include <cstdlib> #include <cstdio> #include <iostream> using namespace std; // removeSpaces - remove any spaces within a string string removeSpaces(const string& source) { // make a copy of the source string so that we don't // modify it string s = source; // find the offset of the first space; // search the string until no more spaces found size_t offset; while((offset = s.find(" ")) != string::npos) { // remove the space just discovered s.erase(offset, 1); } return s; } // insertPhrase - insert a phrase in the position of // <ip> for insertion point string insertPhrase(const string& source) { string s = source; size_t offset = s.find("<ip>"); if (offset != string::npos) { s.erase(offset, 4); s.insert(offset, "Randall"); } return s;
} int main(int argc, char* pArgs[]) { // create a string that is the sum of two strings cout << "string1 + string2 = " << (string("string 1") + string("string 2")) << endl; // create a test string and then remove all spaces // from it using simple string methods string s2("This is a test string"); cout << "<" << s2 << "> minus spaces = <" << removeSpaces(s2) << ">" << endl; // insert a phrase within the middle of an existing // sentence (at the location of "<ip>") string s3 = "Stephen <ip> Davis"; cout << s3 + " -> " + insertPhrase(s3) << endl; system("PAUSE"); return 0; }
The main()
function begins by using operator+()
to append two strings together. main()
then calls the removeSpaces()
method to remove any spaces found in the string provided. It does this by using the string.find()
operation to return the offset of the first " " that it finds. Once found, removeSpaces()
uses the erase()
method to remove the space. The function picks up where it left off, searching for spaces and erasing them until find()
returns npos
, indicating that it didn't find what it was looking for.
The constant npos
is a constant of type size_t
that is the largest unsigned value possible. It is numerically equal to −1.
The insertPhrase()
method uses the find()
method to find the insertion point flagged by the substring "<ip>"
. The function then calls erase
to remove the "<ip>"
flag and string.insert()
to insert a new string in the middle of an existing string.
The resulting output is as follows:
string1 + string2 = string1string2 <this is a test string> minus spaces = <thisisateststring> Stephen <ip> Davis -> Stephen Randall Davis Press any key to continue ...
The string
class is actually an instantiation of the template class basic_class<T>
with T
set to char
. The wstring
class is another name for basic_class<wchar_t>
. This class provides the same character manipulations shown here for wide strings. The C++ '09 definition adds u16string
and u32string
, which extends the string manipulation methods to UTF-16 and UTF-32 character strings. All comparisons between two string objects are performed lexicographically — that is, which of the two strings would appear first in the dictionary of the current language.
The Standard Template Library provides a large number of containers — many more than I can describe in a single session. However, I provide here a description of one of the more useful families of containers.
The STL list
container retains objects by linking them like Lego blocks. (Chapter 13 shows a simplistic implementation of a linked list.) Objects can be snapped apart and snapped back together in any order. This makes the list
ideal for inserting objects, sorting, merging, and otherwise rearranging objects. Table 27-2 shows some of the methods of the list
containers.
Table 27.2. Major Methods of the list
Template Class
Method | Meaning |
---|---|
| Creates an empty list of objects of class |
| Destructs the list, including invoking the destructor on any |
| Replaces the contents of the current list with copies of the objects in list |
bool operator==(const list<T>& l1, const list<T>& l2) | Performs a lexicographic comparison between each element in the two lists. |
| Returns an iterator that points to the first element in the current list. |
| Removes and destructs every object in the current list. |
| Returns true if the current list is empty. |
| Returns an iterator that points to the next entry beyond the end of the current list. |
list<T>::iterator insert( list<T>::iterator loc, const T& object) | Adds |
| Removes the last or first object from the current list. |
void push_back(const T& object) void push_front(const T& object) | Adds an object to the end or front of the current list. |
| Returns an iterator that points to the last entry in the list (useful when iterating backward through the list, starting at the end and working toward the beginning). |
| Returns an iterator that points to the entry before the first entry in the list (useful when iterating backwards through the list). |
| Removes all objects from the current list that are the same as |
| Returns the number of entries in the current list. |
| Sorts the current list such that each object in the list is less than the next object as determined by |
void splice(list<T>::iterator pos, list<T>& source) | Removes the objects from the |
| Removes any subsequent equal objects (as determined by |
The constructor for list<T>
creates an empty list. Objects can be added either to the front or end of the list using the push_front()
or push_back()
. For example, the following code snippet creates an empty list of Student
objects and adds two to the list:
list<Student> students; students.push_back(Student("Dewie Cheatum")); students.push_back(Student("Marion Haste"));
The programmer iterates through an array by providing the index of each element. However, this technique doesn't work for containers like list
that don't allow for random access. One could imagine a solution based in methods such as getFirst()
and getNext()
; however, the designers of the Standard Template Library wanted to provide a common method for traversing any type of container. For this, the Standard Template Library 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.
The Standard Template Library also provides reverse iterators for moving backward through lists. Everything I say about iterators applies equally for reverse iterators.
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 method begin()
returns an iterator that points to the first element in the list. The indirection operator*()
retrieves a reference to the object pointed at by the iterator. The ++
operator moves the iterator to the next element in the list. A program continues to increment its way through the list until the iterator is equal to the value returned by end()
. The following code snippet starts at the beginning of a list of students and displays each of their names:
void displayStudents(list<Student>& students) { // allocate an iterator that points to the first // element in the list list<Student>::iterator iter = students.begin(); // continue to loop through the list until the // iterator hits the end of the list while(iter != students.end()) { // retrieve the Student the iterator points at Student& s = *iter; cout << s.sName << endl; // now move the iterator over to the next element // in the list iter++; } }
Declarations for iterators can get very complex. This is probably the best justification for the auto
declaration introduced with the '09 standard:
for(auto iter = students.end(); iter != students.end(); iter++) { cout << iter->sName << endl; }
This declares iter
to be an iterator of whatever type is returned by the method list<Student>::end()
, avoiding the tortured declarations shown in the earlier code snippet. How cool is that!
The STL library defines certain operations on the entire list. For example, the list<T&>::sort()
method says "I'll sort the list for you if you'll just tell me which objects go first." You do this by defining operator<(T&, T&)
. This operator is already defined for the intrinsic types and many library classes such as string
. For example, you don't have to do anything to sort a list of integers:
list<int> scores; scores.push_back(10); scores.push_back(1); scores.push_back(5); scores.sort();
The programmer must define her own comparison operator for her own classes if she wants C++ to sort them. For example, the following comparison sorts Student
objects by their student ID:
bool operator<(const Student& s1, const Student& s2) { return s1.ssID < s2.ssID; }
The following STLListStudents program demonstrates several functions you've seen in this section. It creates a list of user-defined Student
objects, iterates the list, and sorts the list.
The program appears as follows:
// STLListStudents - use a list to contain and sort a // user defined class #include <cstdio> #include <cstdlib> #include <iostream> #include <list> using namespace std; // Student - some example user defined class class Student { public: Student(const char* pszS, int id) : sName(pszS), ssID(id) {} string sName; int ssID; }; // the following function is required to support the // sort operation bool operator<(const Student& s1, const Student& s2) { return s1.ssID < s2.ssID; } // displayStudents - iterate through the list displaying // each element void displayStudents(list<Student>& students) { // allocate an iterator that points to the first // element in the list list<Student>::iterator iter = students.begin(); // continue to loop through the list until the // iterator hits the end of the list while(iter != students.end()) {
// retrieve the Student the iterator points at Student& s = *iter; cout << s.ssID << " - " << s.sName << endl; // now move the iterator over to the next element // in the list iter++; } } int main(int argc, char* pArgs[]) { // define a collection of students list<Student> students; // add three student objects to the list students.push_back(Student("Marion Haste", 10)); students.push_back(Student("Dewie Cheatum", 5)); students.push_back(Student("Stew Dent", 15)); // display the list cout << "The original list:" << endl; displayStudents(students); // now sort the list and redisplay students.sort(); cout << " The sorted list:" << endl; displayStudents(students); system("PAUSE"); return 0; }
This program defines a list of user-defined Student
objects. Three calls to push_back()
add elements to the list (hard-coding these calls keeps the program smaller). The program then calls displayStudents()
to display the contents of the list both before and after the list has been sorted using the template library sort()
function.
The output of this program appears as follows:
The original list: 10 - Marion Haste 5 - Dewie Cheatum 15 - Stew Dent The sorted list: 5 - Dewie Cheatum 10 - Marion Haste 15 - Stew Dent Press any key to continue ...
3.145.173.199