C++ Primer Plus

The STL uses the term concept to denote a set of requirements. For example, the concept of forward iterators includes the requirements that a forward iterator object can be dereferenced for reading and writing and that it can be incremented. Actual implementations of the concept are said to model the concept. For example, the forward iterator concept could be modeled by an ordinary pointer or by an object designed to navigate a linked list. Concepts based on other concepts are termed refinements. For example, the bidirectional iterator is a refinement of the forward iterator concept.

Container classes, such as vector and set, are models of container concepts, such as containers, sequences, and associative containers. The STL defines several container class templates: vector, deque, list, set, multiset, map, multimap, and bitset. It also defines the adapter class templates queue, priority_queue, and stack; these classes adapt an underlying container class to give it the characteristic interface suggested by the adapter class template name. Thus, stack, although based, by default, on vector, allows insertion and removal only at the top of the stack. C++11 adds forward_list, unordered_set, unordered_multiset, unordered_map, and unordered_multimap.

Some algorithms are expressed as container class methods, but the bulk are expressed as general, nonmember functions. This is made possible by using iterators as the interface between containers and algorithms. One advantage to this approach is that there needs to be just one for_each() or copy() function, and so on, instead of a separate version for each container. A second advantage is that STL algorithms can be used with non-STL containers, such as ordinary arrays, string objects, array objects, and any classes you design consistent with the STL iterator and container idiom.

Both containers and algorithms are characterized by the type of iterator they provide or need. You should check that a container features an iterator concept that supports the algorithm’s needs. For example, the for_each() algorithm uses an input iterator, whose minimal requirements are met by all the STL container class types. But sort() requires random access iterators, which not all container classes support. A container class may offer a specialized method as an option if it doesn’t meet the requirements for a particular algorithm. For example, the list class has a sort() method that is based on bidirectional iterators, so it can use that method instead of the general function.

The STL also provides function objects, or functors, that are classes for which the () operator is overloaded—that is, for which the operator()() method is defined. Objects of such classes can be invoked by using function notation but can carry additional information. Adaptable functors, for example, have typedef statements that identify the argument types and the return value type for the functor. This information can be used by other components, such as function adapters.

By representing common container types and providing a variety of common operations implemented with efficient algorithms, all done in a generic manner, the STL provides an excellent source of reusable code. You may be able to solve a programming problem directly with the STL tools, or you may be able to use them as building blocks to construct the solution you need.

The complex and valarray template classes support numeric operations for complex numbers and arrays.

Chapter Review

1. Consider the following class declaration:

class RQ1

{

private:

    char * st;       // points to C-style string

public:

    RQ1() { st = new char [1]; strcpy(st,""); }

    RQ1(const char * s)

    {st = new char [strlen(s) + 1]; strcpy(st, s); }

    RQ1(const RQ1 & rq)

    {st = new char [strlen(rq.st) + 1]; strcpy(st, rq.st); }

    ~RQ1() {delete [] st};

    RQ & operator=(const RQ & rq);

    // more stuff

};

Convert this to a declaration that uses a string object instead. What methods no longer need explicit definitions?

2. Name at least two advantages string objects have over C-style strings in terms of ease-of-use.

3. Write a function that takes a reference to a string object as an argument and that converts the string object to all uppercase.

4. Which of the following are not examples of correct usage (conceptually or syntactically) of auto_ptr? (Assume that the needed header files have been included.)

auto_ptr pia(new int[20]);

auto_ptr (new string);

int rigue = 7;

auto_ptrpr(&rigue);

auto_ptr dbl (new double);

5. If you could make the mechanical equivalent of a stack that held golf clubs instead of numbers, why would it (conceptually) be a bad golf bag?

6. Why would a set container be a poor choice for storing a hole-by-hole record of your golf scores?

7. Because a pointer is an iterator, why didn’t the STL designers simply use pointers instead of iterators?