C++ For Dummies (2014)

Part V

Security

Chapter 27

Standardizing on the Standard Template Library

In This Chapter

Using the string class

Maintaining entries in a Standard Template Library list

Accessing container elements from an iterator

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 or removing 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 string Container

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 stringobjects:

string concat(const string& s1, const string& s2)
{
return s1 + s2;
}

Table 27-1 Major Methods of the string Class

The C++ '11 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 forunsigned 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;

cout << "Press Enter to continue..." << endl;
cin.ignore(10, '\n');
cin.get();
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. This is used for the “not found position” just like ‘\0' is the “non-character.”

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 Enter to continue...

At its core, a string is still an array. The operations provided by the STL make it easier to manipulate string objects but not that much faster. Inserting into the middle of a string still involves moving the contents of arrays around.

The string class is actually an instantiation of the class template 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++ '11 definition addsu16string 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.

Iterating through Lists

The Standard Template Library provides a large number of containers — many more than I can describe in a single chapter. 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 and 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

The constructor for list<T> creates an empty list. Objects can be added either to the front or end of the list using push_front() or push_back(). For example, the following code snippet creates an empty list of Student objects and adds two students to the list:

list<Student> students;
students.push_back(Student("Dewie Cheatum"));
students.push_back(Student("Marion Haste"));

Making your way through a list

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 iterator returns an indication when it reaches the end of the list.

· 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 of a 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 '11 standard:

for(auto iter = students.begin(); 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>::begin(), avoiding the tortured declarations shown in the earlier code snippet. How cool is that!

Operations on an entire list

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<(const T&, const 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;
}

Can you show me an example?

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();
auto 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 << "\nThe sorted list:" << endl;
displayStudents(students);

cout << "Press Enter to continue..." << endl;
cin.ignore(10, '\n');
cin.get();
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 Enter to continue...

The iterator iter is declared twice in this program. Use the auto version if your compiler is compliant with the 2011 standard. Comment out that line and uncomment the more complicated declaration before it, if not.