Chapter 19: Class templates

Don't hesitate to send in feedback: send an e-mail if you like the C++ Annotations; if you think that important material was omitted; if you find errors or typos in the text or the code examples; or if you just feel like e-mailing. Send your e-mail to Frank B. Brokken.

Please state the document version you're referring to, as found in the title (in this document: 7.2.0) and please state chapter and paragraph name or number you're referring to.

All received mail is processed conscientiously, and received suggestions for improvements will usually have been processed by the time a new version of the Annotations is released. Except for the incidental case I will normally not acknowledge the receipt of suggestions for improvements. Please don't interpret this as me not appreciating your efforts.

Templates can not only be constructed for functions but also for complete classes. Constructing a class template can be considered when the class should be able to handle different types of data. Class templates are frequently used in C++: chapter 12 discusses data structures like vector, stack and queue, which are implemented as class templates. With class templates, the algorithms and the data on which the algorithms operate are completely separated from each other. To use a particular data structure, operating on a particular data type, only the data type needs to be specified when the class template object is defined or declared, e.g., stack<int> iStack.

In this chapter constructing and using class templates is discussed. In a sense, class templates compete with object oriented programming (cf. chapter 14), where a mechanism somewhat similar to templates is seen. Polymorphism allows the programmer to postpone the definitions of algorithms, by deriving classes from a base class in which the algorithm is only partially implemented, while the data upon which the algorithms operate may first be defined in derived classes, together with member functions that were defined as pure virtual functions in the base class to handle the data. On the other hand, templates allow the programmer to postpone the specification of the data upon which the algorithms operate. This is most clearly seen with the abstract containers, completely specifying the algorithms but at the same time leaving the data type on which the algorithms operate completely unspecified.

The correspondence between class templates and polymorphic classes is well-known. In their book C++ Coding Standards (Addison-Wesley, 2005) Sutter and Alexandrescu (2005) refer to static polymorphism and dynamic polymorphism. Dynamic polymorphism is what we use when overriding virtual members: Using the vtable construction the function that's actually called depends on the type of object a (base) class pointer points to. Static polymorphism is used when templates are used: depending on the actual types, the compiler creates the code, compile time, that's appropriate for those particular types. There's no need to consider static and dynamic polymorphism as mutually exlusive variants of polymorphism. Rather, both can be used together, combining their strengths. A warning is in place, though. When a class template defines virtual members all virtual members are instantiated for every instantiated type. This has to happen, since the compiler must be able to construct the class's vtable.

Generally, class templates are easier to use. It is certainly easier to write stack<int> istack to create a stack of ints than to derive a new class Istack: public stack and to implement all necessary member functions to be able to create a similar stack of ints using object oriented programming. On the other hand, for each different type that is used with a class template the complete class is reinstantiated, whereas in the context of object oriented programming the derived classes use, rather than copy, the functions that are already available in the base class (but see also section 19.9).

19.1: Defining class templates

Now that we've covered the construction of function templates, we're ready for the next step: constructing class templates. Many useful class templates already exist. Instead of illustrating how an existing class template was constructed, let's discuss the construction of a useful new class template.

In chapter 17 we've encountered the auto_ptr class (section 17.3). The auto_ptr, also called smart pointer, allows us to define an object, acting like a pointer. Using auto_ptrs rather than plain pointers we not only ensure proper memory management, but we may also prevent memory leaks when objects of classes using pointer data-members cannot completely be constructed.

The one disadvantage of auto_ptrs is that they can only be used for single objects and not for pointers to arrays of objects. Here we'll construct the class template FBB::auto_ptr, behaving like auto_ptr, but managing a pointer to an array of objects.

Using an existing class as our point of departure also shows an important design principle: it's often easier to construct a template (function or class) from an existing template than to construct the template completely from scratch. In this case the existing std::auto_ptr acts as our model. Therefore, we want to provide the class with the following members:

Now that we have decided which members we need, the class interface can be constructed. Like function templates, a class template definition begins with the keyword template, which is also followed by a non-empty list of template type and/or non-type parameters, surrounded by angle brackets. The template keyword followed by the template parameter list enclosed in angle brackets is called a template announcement in the C++ Annotations. In some cases the template announcement's parameter list may be empty, leaving only the angle brackets.

Following the template announcement the class interface is provided, in which the formal template type parameter names may be used to represent types and constants. The class interface is constructed as usual. It starts with the keyword class and ends with a semicolon.

Normal design considerations should be followed when constructing class template member functions or class template constructors: class template type parameters should preferably be defined as Type const &, rather than Type, to prevent unnecessary copying of large data structures. Template class constructors should use member initializers rather than member assignment within the body of the constructors, again to prevent double assignment of composed objects: once by the default constructor of the object, once by the assignment itself.

Here is our initial version of the class FBB::auto_ptr showing all its members:

    namespace FBB
    {
        template <typename Data>
        class auto_ptr
        {
            Data *d_data;

            public:
                auto_ptr();
                auto_ptr(auto_ptr<Data> &other);
                auto_ptr(Data *data);
                ~auto_ptr();
                auto_ptr<Data> &operator=(auto_ptr<Data> &rvalue);
                Data &operator[](size_t index);
                Data const &operator[](size_t index) const;
                Data *get();
                Data const *get() const;
                Data *release();
                void reset(Data *p = 0);
            private:
                void destroy();
                void copy(auto_ptr<Data> &other);
                Data &element(size_t idx) const;
        };

        template <typename Data>
        inline auto_ptr<Data>::auto_ptr()
        :
            d_data(0)
        {}

        template <typename Data>
        inline auto_ptr<Data>::auto_ptr(auto_ptr<Data> &other)
        {
            copy(other);
        }

        template <typename Data>
        inline auto_ptr<Data>::auto_ptr(Data *data)
        :
            d_data(data)
        {}

        template <typename Data>
        inline auto_ptr<Data>::~auto_ptr()
        {
            destroy();
        }

        template <typename Data>
        inline Data &auto_ptr<Data>::operator[](size_t index)
        {
            return d_data[index];
        }

        template <typename Data>
        inline Data const &auto_ptr<Data>::operator[](size_t index) const
        {
            return d_data[index];
        }

        template <typename Data>
        inline Data *auto_ptr<Data>::get()
        {
            return d_data;
        }

        template <typename Data>
        inline Data const *auto_ptr<Data>::get() const
        {
            return d_data;
        }

        template <typename Data>
        inline void auto_ptr<Data>::destroy()
        {
            delete[] d_data;
        }

        template <typename Data>
        inline void auto_ptr<Data>::copy(auto_ptr<Data> &other)
        {
            d_data = other.release();
        }

        template <typename Data>
        auto_ptr<Data> &auto_ptr<Data>::operator=(auto_ptr<Data> &rvalue)
        {
            if (this != &rvalue)
            {
                destroy();
                copy(rvalue);
            }
            return *this;
        }

        template <typename Data>
        Data *auto_ptr<Data>::release()
        {
            Data *ret = d_data;
            d_data = 0;
            return ret;
        }

        template <typename Data>
        void auto_ptr<Data>::reset(Data *ptr)
        {
            destroy();
            d_data = ptr;
        }

    } // FBB
The class interface shows the following features: Let's have a look at some of the member functions defined beyond the class interface. Note in particular: Some remarks about specific members: Now that the class has been defined, it can be used. To use the class, its object must be instantiated for a particular data type. The example defines a new std::string array, storing all command-line arguments. Then, the first command-line argument is printed. Next, the auto_ptr object is used to initialize another auto_ptr of the same type. It is shown that the original auto_ptr now holds a 0-pointer, and that the second auto_ptr object now holds the command-line arguments:
    #include <iostream>
    #include <algorithm>
    #include <string>
    #include "autoptr.h"
    using namespace std;

    int main(int argc, char **argv)
    {
        FBB::auto_ptr<string> sp(new string[argc]);
        copy(argv, argv + argc, sp.get());

        cout << "First auto_ptr, program name: " << sp[0] << endl;

        FBB::auto_ptr<string> second(sp);

        cout << "First auto_ptr, pointer now: " << sp.get() << endl;
        cout  << "Second auto_ptr, program name: " << second[0] << endl;

        return 0;
    }
    /*
        Generated output:

        First auto_ptr, program name: a.out
        First auto_ptr, pointer now: 0
        Second auto_ptr, program name: a.out
    */

19.1.1: Default class template parameters

Different from function templates, template parameters of template classes may be given default values. This holds true both for template type- and template non-type parameters. If a class template is instantiated without specifying arguments for its template parameters, and if default template parameter values were defined, then the defaults are used. When defining such defaults keep in mind that the defaults should be suitable for the majority of instantiations of the class. E.g., for the class template FBB::auto_ptr the template's type parameter list could have been altered by specifying int as its default type:
        template <typename Data = int>
Even though default arguments can be specified, the compiler must still be informed that object definitions refer to templates. So, when instantiating class template objects for which default parameter values have been defined the type specifications may be omitted, but the angle brackets must remain. So, assuming a default type for the FBB::auto_ptr class, an object of that class may be defined as:
        FBB::auto_ptr<> intAutoPtr;
No defaults must be specified for template members defined outside of their class interface. Function templates, even member function templates, cannot specify default parameter values. So, the definition of, e.g., the release() member will always begin with the same template specification:
        template <typename Data>

When a class template uses multiple template parameters, all may be given default values. However, like default function arguments, once a default value is used, all remaining parameters must also use their default values. A template type specification list may not start with a comma, nor may it contain multiple consecutive commas.

19.1.2: Declaring class templates

Class templates may also be declared. This may be useful in situations where forward class declarations are required. To declare a class template, simply remove its interface (the part between the curly braces):
    namespace FBB
    {
        template <typename Type>
        class auto_ptr;
    }
Here default types may also be specified. However, default type values cannot be specified in both the declaration and the definition of a template class. As a rule of thumb default values should be omitted from declarations, as class template declarations are never used when instantiating objects, but only for the occasional forward reference. Note that this differs from default parameter value specifications for member functions in ordinary classes. Such defaults should be specified in the member functions' declarations and not in their definitions.

19.1.3: Non-type parameters

As we've seen with function templates, template parameters are either template type parameters or template non-type parameters (actually, a third kind of template parameter exists, the template template parameter, which is discussed in chapter 20 (section 20.3)).

Class templates also may define non-type parameters. Like the non-const parameters used with function templates they must be constants whose values are known by the time an object is instantiated.

However, their values are not deduced by the compiler using arguments passed to constructors. Assume we modify the class template FBB::auto_ptr so that it has an additional non-type parameter size_t Size. Next we use this Size parameter in a new constructor defining an array of Size elements of type Data as its parameter. The new FBB::auto_ptr template class becomes (showing only the relevant constructors; note the two template type parameters that are now required, e.g., when specifying the type of the copy constructor's parameter):

    namespace FBB
    {
        template <typename Data, size_t Size>
        class auto_ptr
        {
            Data *d_data;
            size_t d_n;

            public:
                auto_ptr(auto_ptr<Data, Size> &other);
                auto_ptr(Data2 *data);
                auto_ptr(Data const (&arr)[Size]);
                ...
        };

        template <typename Data, size_t Size>
        inline auto_ptr<Data, Size>::auto_ptr(Data const (&arr)[Size])
        :
            d_data(new Data2[Size]),
            d_n(Size)
        {
            std::copy(arr, arr + Size, d_data);
        }
    }
Unfortunately, this new setup doesn't satisfy our needs, as the values of template non-type parameters are not deduced by the compiler. When the compiler is asked to compile the following main() function it reports a mismatch between the required and actual number of template parameters:
    int main()
    {
        int arr[30];

        FBB::auto_ptr<int> ap(arr);
    }
    /*
        Error reported by the compiler:

        In function `int main()':
            error: wrong number of template arguments (1, should be 2)
            error: provided for `template<class Data, size_t Size>
                   class FBB::auto_ptr'
    */
Defining Size as a non-type parameter having a default value doesn't work either. The compiler will use the default, unless explicitly specified otherwise. So, reasoning that Size can be 0 unless we need another value, we might specify size_t Size = 0 in the templates parameter type list. However, this causes a mismatch between the default value 0 and the actual size of the array arr as defined in the above main() function. The compiler using the default value, reports:
    In instantiation of `FBB::auto_ptr<int, 0>':
    ...
    error: creating array with size zero (`0')
So, although class templates may use non-type parameters, they must be specified like the type parameters when an object of the class is defined. Default values can be specified for those non-type parameters, but then the default will be used when the non-type parameter is left unspecified.

Note that default template parameter values (either type or non-type template parameters) may not be used when template member functions are defined outside the class interface. Function template definitions (and thus: class template member functions) may not be given default template (non) type parameter values. If default template parameter values are to be used for class template members, they have to be specified in the class interface.

Similar to non-type parameters of function templates, non-type parameters of class templates may only be specified as constants:

Although our attempts to define a constructor of the class FBB::auto_ptr accepting an array as its argument, allowing us to use the array's size within the constructor's code has failed so far, we're not yet out of options. In the next section an approach will be described allowing us to reach our goal, after all.

19.2: Member templates

Our previous attempt to define a template non-type parameter which is initialized by the compiler to the number of elements of an array failed because the template's parameters are not implicitly deduced when a constructor is called, but they are explicitly specified, when an object of the class template is defined. As the parameters are specified just before the template's constructor is called, there's nothing to deduce anymore, and the compiler will simply use the explicitly specified template arguments.

On the other hand, when template functions are used, the actual template parameters are deduced from the arguments used when calling the function. This opens an approach route to the solution of our problem. If the constructor itself is made into a member which itself is a function template (containing a template announcement of its own), then the compiler will be able to deduce the non-type parameter's value, without us having to specify it explicitly as a class template non-type parameter.

Member functions (or classes) of class templates which themselves are templates are called member templates. Member templates are defined in the same way as any other template, including the template <typename ...> header.

When converting our earlier FBB::auto_ptr(Data const (&array)[Size]) constructor into a member template we may use the class template's Data type parameter, but must provide the member template with a non-type parameter of its own. The class interface is given the following additional member declaration:

    template <typename Data>
    class auto_ptr
    {
        ...
        public:
            template <size_t Size>
            auto_ptr(Data const (&arr)[Size]);
        ...
    };
and the constructor's implementation becomes:
    template <typename Data>
    template <size_t Size>
    inline auto_ptr<Data>::auto_ptr(Data const (&arr)[Size])
    :
        d_data(new Data[Size]),
        d_n(Size)
    {
        std::copy(arr, arr + Size, d_data);
    }

Member templates have the following characteristics:

One small problem remains. When we're constructing an FBB::auto_ptr object from a fixed-size array the above constructor is not used. Instead, the constructor FBB::auto_ptr<Data>::auto_ptr(Data *data) is activated. As the latter constructor is not a member template, it is considered a more specialized version of a constructor of the class FBB::auto_ptr than the former constructor. Since both constructors accept an array the compiler will call auto_ptr(Data *) rather than auto_ptr(Data const (&array)[Size]). This problem can be solved by simply changing the constructor auto_ptr(Data *data) into a member template as well, in which case its template type parameter should be changed into `Data'. The only remaining subtlety is that template parameters of member templates may not shadow the template parameters of their class. Renaming Data into Data2 takes care of this subtlety. Here is the (inline) definition of the auto_ptr(Data *) constructor, followed by an example in which both constructors are actually used:
    template <typename Data>
    template <typename Data2>           // data: dynamically allocated
    inline auto_ptr<Data>::auto_ptr(Data2 *data)
    :
        d_data(data),
        d_n(0)
    {}
Calling both constructors in main():
    int main()
    {
        int array[30];

        FBB::auto_ptr<int> ap(array);
        FBB::auto_ptr<int> ap2(new int[30]);

        return 0;
    }

19.3: Static data members

When static members are defined in class templates, they are instantiated for every new instantiation. As they are static members, there will be only one member when multiple objects of the same template type(s) are defined. For example, in a class like:
    template <typename Type>
    class TheClass
    {
        static int s_objectCounter;
    };
There will be one TheClass<Type>::objectCounter for each different Type specification. The following instantiates just one single static variable, shared among the different objects:
    TheClass<int> theClassOne;
    TheClass<int> theClassTwo;
Mentioning static members in interfaces does not mean these members are actually defined: they are only declared by their classes and must be defined separately. With static members of class templates this is not different. The definitions of static members are usually provided immediately following (i.e., below) the template class interface. The static member s_objectCounter will thus be defined as follows, just below its class interface:
    template <typename Type>                    // definition, following
    int TheClass<Type>::s_objectCounter = 0;    // the interface
In the above case, s_objectCounter is an int and thus independent of the template type parameter Type.

In a list-like construction, where a pointer to objects of the class itself is required, the template type parameter Type must be used to define the static variable, as shown in the following example:

    template <typename Type>
    class TheClass
    {
        static TheClass *s_objectPtr;
    };

    template <typename Type>
    TheClass<Type> *TheClass<Type>::s_objectPtr = 0;
As usual, the definition can be read from the variable name back to the beginning of the definition: s_objectPtr of the class TheClass<Type> is a pointer to an object of TheClass<Type>.

Finally, when a static variable of a template's type parameter is defined, it should of course not be given the initial value 0. The default constructor (e.g., Type() will usually be more appropriate):

    template <typename Type>                    // s_type's definition
    Type TheClass<Type>::s_type = Type();

19.4: Specializing class templates for deviating types

Our earlier class FBB::auto_ptr can be used for many different types. Their common characteristic is that they can simply be assigned to the class's d_data member, e.g., using auto_ptr(Data *data). However, this is not always as simple as it looks. What if Data's actual type is char *? Examples of a char **, data's resulting type, are well-known: main()'s argv parameter and and environ, for example are char ** varables, both having a final element equal to 0. The specialization developed here assumes that there is indeed such a final 0-pointer element.

It this special case we might not be interested in the mere reassignment of the constructor's parameter to the class's d_data member, but we might be interested in copying the complete char ** structure. To implement this, class template specializations may be used.

Class template specializations are used in cases where member function templates cannot (or should not) be used for a particular actual template parameter type. In those cases specialized template members can be constructed, fitting the special needs of the actual type.

Class template member specializations are specializations of existing class members. Since the class members already exist, the specializations will not be part of the class interface. Rather, they are defined below the interface as members, redefining the more generic members using explicit types. Furthermore, as they are specializations of existing class members, their function prototypes must exactly match the prototypes of the member functions for which they are specializations. For our Data = char * specialization the following definition could be designed:

    template <>
    auto_ptr<char *>::auto_ptr(char **argv)
    :
        d_n(0)
    {
        char **tmp = argv;
        while (*tmp++)
            d_n++;
        d_data = new char *[d_n];

        for (size_t idx = 0; idx < d_n; idx++)
        {
            std::string str(argv[idx]);
            d_data[idx] =
                strcpy(new char[str.length() + 1], str.c_str());
        }
    }
Now, the above specialization will be used to construct the following FBB::auto_ptr object:
    int main(int argc, char **argv)
    {
        FBB::auto_ptr<char *> ap3(argv);
        return 0;
    }

Although defining a template member specialization may allow us to use the occasional exceptional type, it is also quite possible that a single template member specialization is not enough. Actually, this is the case when designing the char * specialization, since the template's destroy() implementation is not correct for the specialized type Data = char *. When multiple members must be specialized for a particular type, then a complete class template specialization might be considered.

A completely specialized class shows the following characteristics:

Below a full specialization of the class template FBB::auto_ptr for the actual type Data = char * is given, illustrating the above characteristics. The specialization should be appended to the file already containing the generic class template. To reduce the size of the example members that are only declared may be assumed to have identical implementations as used in the generic template.

    #include <iostream>
    #include <algorithm>
    #include "autoptr.h"

    namespace FBB
    {
        template<>
        class auto_ptr<char *>
        {
            char **d_data;
            size_t d_n;

            public:
                auto_ptr<char *>();
                auto_ptr<char *>(auto_ptr<char *> &other);
                auto_ptr<char *>(char **argv);

                // template <size_t Size>             NI
                // auto_ptr(char *const (&arr)[Size])

                ~auto_ptr();
                auto_ptr<char *> &operator=(auto_ptr<char *> &rvalue);
                char *&operator[](size_t index);
                char *const &operator[](size_t index) const;
                char **get();
                char *const *get() const;
                char **release();
                void reset(char **argv);
                void additional() const;    // just an additional public
                                            // member
            private:
                void full_copy(char **argv);
                void copy(auto_ptr<char *> &other);
                void destroy();
        };

        inline auto_ptr<char *>::auto_ptr()
        :
            d_data(0),
            d_n(0)
        {}

        inline auto_ptr<char *>::auto_ptr(auto_ptr<char *> &other)
        {
            copy(other);
        }

        inline auto_ptr<char *>::auto_ptr(char **argv)
        {
            full_copy(argv);
        }

        inline auto_ptr<char *>::~auto_ptr()
        {
            destroy();
        }

        inline void auto_ptr<char *>::reset(char **argv)
        {
            destroy();
            full_copy(argv);
        }

        inline void auto_ptr<char *>::additional() const
        {}

        inline void auto_ptr<char *>::full_copy(char **argv)
        {
            d_n = 0;
            char **tmp = argv;
            while (*tmp++)
                d_n++;
            d_data = new char *[d_n];

            for (size_t idx = 0; idx < d_n; idx++)
            {
                std::string str(argv[idx]);
                d_data[idx] =
                    strcpy(new char[str.length() + 1], str.c_str());
            }
        }

        inline void auto_ptr<char *>::destroy()
        {
            while (d_n--)
                delete d_data[d_n];
            delete[] d_data;
        }
    }

Note that specializations not automatically have empty template parameter lists. Consider the following example of an (grossly incomplete) specialization of FBB::auto_ptr:

    #include <iostream>
    #include <vector>
    #include "autoptr.h"

    namespace FBB
    {
        template<typename T>
        class auto_ptr<std::vector<T> *>
        {
            public:
                auto_ptr<std::vector<T> *>();
        };

        template <typename T>
        inline auto_ptr<std::vector<T> * >::auto_ptr()
        {
            std::cout << "Vector specialization\n";
        }
    }

In this example a specialization is created for the type std::vector>, instantiated with any data type T. Since T is not specified, it must be mentioned in the template paramter list as a template type parameter. E.g., if an FBB::auto_ptr<std::vector<int> *> is constructed, the compiler deducts that T is an int and will use the vector<T> * specialization, in which T could be used as a type specification. The following basic example shows that the compiler will indeed select the vector<T>* specialization:

    #include "autoptr4.h"

    int main(int argc, char **argv)
    {
        FBB::auto_ptr<std::vector<int> *> vspec;
        return 0;
    }

19.5: Partial specializations

In the previous section we've seen that it is possible to design template class specializations. It was shown that both class template members and complete class templates could be specialized. Furthermore, the specializations we've seen were specializing template type parameters.

In this section we'll introduce a variant of these specializations, both in number and types of template parameters that are specialized. Partial specializations may be defined for class templates having multiple template parameters. With partial specializations a subset (any subset) of template type parameters are given specific values.

Having discussed specializations of template type parameters in the previous section, we'll discuss specializations of non-type parameters in the current section. Partial specializations of template non-type parameters will be illustrated using some simple concepts defined in matrix algebra, a branch of linear algebra.

A matrix is commonly thought of as consisting of a table of a certain number of rows and columns, filled with numbers. Immediately we recognize an opening for using templates: the numbers might be plain double values, but they could also be complex numbers, for which our complex container (cf. section 12.4) might prove useful. Consequently, our class template should be given a DataType template type parameter, for which a ordinary class can be specified when a matrix is constructed. Some simple matrices using double values, are:

    1   0   0           An identity matrix,
    0   1   0           a 3 x 3 matrix.
    0   0   1

    1.2  0    0    0    A rectangular matrix,
    0.5  3.5  18  23    a 2 x 4 matrix.

    1   2   4   8       A matrix of one row,
                        a 1 x 4 matrix, also known as a
                        `row vector' of 4 elements.
                        (column vectors are analogously defined)
Since matrices consist of a specific number of rows and columns (the dimensions of the matrix), which normally do not change when using matrices, we might consider specifying their values as template non-type parameters. Since the DataType = double selection will be used in the majority of cases, double can be selected as the template's default type. Since it's having a sensible default, the DataType template type parameter is put last in the template type parameter list. So, our template class Matrix starts off as follows:
    template <size_t Rows, size_t Columns, typename DataType = double>
    class Matrix
    ...

Various operations are defined on matrices. They may, for example be added, subtracted or multiplied. We will not focus on these operations here. Rather, we'll concentrate on a simple operation: computing marginals and sums. The row marginals are obtained by computing, for each row, the sum of all its elements, putting these Rows sum values in corresponding elements of a column vector of Rows elements. Analogously, column marginals are obtained by computing, for each column, the sum of all its elements, putting these Columns sum values in corresponding elements of a row vector of Columns elements. Finally, the sum of the elements of a matrix can be computed. This sum is of course equal to the sum of the elements of its marginals. The following example shows a matrix, its marginals, and its sum:

                matrix:         row
                                marginals:

                1   2   3        6
                4   5   6       15

    column      5   7   9       21  (sum)
    marginals
So, what do we want our class template to offer?

Class template partial specializations may be defined for any (subset) of template parameters. They can be defined for template type parameters and for template non-type parameters alike. Our first partial specialization defines the special case where we construct a row of a generic Matrix, specifically aiming at (but not restricted to) the construction of column marginals. Here is how such a partial specialization is constructed:

Now that we have defined the generic Matrix class as well as the partial specialization defining a single row, the compiler will select the row's specialization whenever a Matrix is defined using Row = 1. For example:
    Matrix<4, 6> matrix;        // generic Matrix template is used
    Matrix<1, 6> row;           // partial specialization is used

The partial specialization for a MatrixColumn is constructed similarly. Let's present its highlights (the full Matrix class template definition as well as all its specializations are provided in the cplusplus.yo.zip archive (at ftp.rug.nl) in the file yo/classtemplates/examples/matrix.h):

The reader might wonder what happens if we specify the following matrix:

        Matrix<1, 1> cell;
Is this a MatrixRow or a MatrixColumn specialization? The answer is: neither. It's ambiguous, precisely because both the columns and the rows could be used with a (different) template partial specialization. If such a Matrix is actually required, yet another specialized template must be designed. Since this template specialization can be useful to obtain the sum of the elements of a Matrix, it's covered here as well: The following main() function shows how the Matrix class template and its partial specializations can be used:
    #include <iostream>
    #include "matrix.h"
    using namespace std;

    int main(int argc, char **argv)
    {
        Matrix<3, 2> matrix(cin);

        Matrix<1, 2> colMargins(matrix);
        cout << "Column marginals:\n";
        cout << colMargins[0] << " " << colMargins[1] << endl;

        Matrix<3, 1> rowMargins(matrix);
        cout << "Row marginals:\n";
        for (size_t idx = 0; idx < 3; idx++)
            cout << rowMargins[idx] << endl;

        cout << "Sum total: " << Matrix<1, 1>(matrix) << endl;
        return 0;
    }
    /*
        Generated output from input: 1 2 3 4 5 6

        Column marginals:
        9 12
        Row marginals:
        3
        7
        11
        Sum total: 21
    */

19.6: Instantiating class templates

Template classes are instantiated when an object of a class template is defined. When a class template object is defined or declared, the template parameters must explicitly be specified.

Template parameters are also specified when a class template defines default template parameter values, albeit that in that case the compiler will provide the defaults (cf. section 19.5 where double is used as the default type to be used with the template's DataType parameter). The actual values or types of template parameters are never deduced, as happens with function templates: to define a Matrix of elements that are complex values, the following construction is used:

        Matrix<3, 5, std::complex> complexMatrix;
while the following construction defines a matrix of elements that are double values, with the compiler providing the (default) type double:
        Matrix<3, 5> doubleMatrix;

A class template object may be declared using the keyword extern. For example, the following construction is used to declare the matrix complexMatrix:

        extern Matrix<3, 5, std::complex> complexMatrix;

A class template declaration is sufficient if the compiler encounters function declarations of functions having return values or parameters which are class template objects, pointers or references. The following little source file may be compiled, although the compiler hasn't seen the definition of the Matrix class template. Note that generic classes as well as (partial) specializations may be declared. Furthermore, note that a function expecting or returning a class template object, reference, or parameter itself automatically becomes a function template. This is necessary to allow the compiler to tailor the function to the types of various actual arguments that may be passed to the function:

    #include <stddef.h>

    template <size_t Rows, size_t Columns, typename DataType = double>
    class Matrix;

    template <size_t Columns, typename DataType>
    class Matrix<1, Columns, DataType>;

    Matrix<1, 12> *function(Matrix<2, 18, size_t> &mat);

When class templates are used they have to be processed by the compiler first. So, template member functions must be known to the compiler when the template is instantiated. This does not mean that all members of a template class are instantiated when a class template object is defined. The compiler will only instantiate those members that are actually used. This is illustrated by the following simple class Demo, having two constructors and two members. When we create a main() function in which one constructor is used and one member is called, we can make a note of the sizes of the resulting object file and executable program. Next the class definition is modified such that the unused constructor and member are commented out. Again we compile and link the main() function and the resulting sizes are identical to the sizes obtained earlier (on my computer, using g++ version 4.1.2) these sizes are 3904 bytes (after stripping). There are other ways to illustrate the point that only members that are used are instantiated, like using the nm program, showing the symbolic contents of object files. Using programs like nm will yield the same conclusion: only template member functions that are actually used are initialized. Here is an example of the class template Demo used for this little experiment. In main() only the first constructor and the first member function are called and thus only these members were instantiated:

    #include <iostream>

    template <typename Type>
    class Demo
    {
        Type d_data;

        public:
            Demo();
            Demo(Type const &value);

            void member1();
            void member2(Type const &value);
    };

    template <typename Type>
    Demo<Type>::Demo()
    :
        d_data(Type())
    {}

    template <typename Type>
    void Demo<Type>::member1()
    {
        d_data += d_data;
    }

    // the following members are commented out before compiling
    // the second program

    template <typename Type>
    Demo<Type>::Demo(Type const &value)
    :
        d_data(value)
    {}

    template <typename Type>
    void Demo<Type>::member2(Type const &value)
    {
        d_data += value;
    }

    int main()
    {
        Demo<int> demo;
        demo.member1();
    }

19.7: Processing class templates and instantiations

In section 18.9 the distinction between code depending on template parameters and code not depending on template parameters was introduced. The same distinction also holds true when class templates are defined and used.

Code that does not depend on template parameters is verified by the compiler when the template is defined. E.g., if a member function in a class template uses a qsort() function, then qsort() does not depend on a template parameter. Consequently, qsort() must be known to the compiler when it encounters the qsort() function call. In practice this implies that cstdlib or stdlib.h must have been processed by the compiler before it will be able to process the class template definition.

On the other hand, if a template defines a <typename Type> template type parameter, which is the return type of some template member function, e.g.,

        Type member() ...
then we distinguish the following situations where the compiler encounters member() or the class to which member() belongs:

19.8: Declaring friends

Friend functions are normally constructed as support functions of a class that cannot be constructed as class members themselves. The well-known insertion operator for output streams is a case in point. Friend classes are most often seen in the context of nested classes, where the inner class declares the outer class as its friend (or the other way around). Here again we see a support mechanism: the inner class is constructed to support the outer class.

Like ordinary classes, class templates may declare other functions and classes as their friends. Conversely, ordinary classes may declare template classes as their friends. Here too, the friend is constructed as a special function or class augmenting or supporting the functionality of the declaring class. Although the friend keyword can thus be used in any type of class (ordinary or template) to declare any type of function or class as a friend, when using class templates the following cases should be distinguished:

19.8.1: Non-function templates or classes as friends

A class template may declare a ordinary function, ordinary member function or complete ordinary class as its friend. Such a friend may access the class template's private members.

Concrete classes and ordinary functions can be declared as friends, but before a single class member function can be declared as a friend, the compiler must have seen the class interface declaring that member. Let's consider the various possibilities:

19.8.2: Templates instantiated for specific types as friends

With bound friend class templates or functions there is a one-to-one mapping between the actual values of the template-friends' template parameters and the class template's template parameters declaring them as friends. In this case, the friends themselves are templates too. Here are the various possibilities: Finally, the following basic example can be used as a prototype for situations where bound friends are useful:
    template <typename T>           // a function
    void fun(T *t)                  // template
    {
        t->not_public();
    };

    template <typename X>           // a class template
    class A
    {                               // fun() is used as
                                    // friend bound to A,
                                    // instantiated for X,
                                    // whatever X may be
        friend void fun<A<X> >(A<X> *);

        public:
            A();

        private:
            void not_public();
    };

    template <typename X>
    A<X>::A()
    {
        fun(this);
    }

    template <typename X>
    void A<X>::not_public()
    {}

    int main()
    {
        A<int> a;

        fun(&a);                    // fun instantiated for
                                    // A<int>.
    }

19.8.3: Unbound templates as friends

When a friend is declared as an unbound friend, it merely declares an existing template to be its friend, no matter how it is instantiated. This may be useful in situations where the friend should be able to instantiate objects of class templates declaring the friend, allowing the friend to access the instantiated object's private members. Again, functions, classes and member functions may be declared as unbound friends.

Here are the syntactic conventions declaring unbound friends:

19.9: Class template derivation

Class templates can be used in class derivation as well. When a class template is used in class derivation, the following situations should be distinguished: These three variants of class template derivation will now be elaborated.

Consider the following base class:

    template<typename T>
    class Base
    {
        T const &t;

        public:
            Base(T const &t);
    };
The above class is a class template, which can be used as a base class for the following derived class template Derived:
    template<typename T>
    class Derived: public Base<T>
    {
        public:
            Derived(T const &t);
    };

    template<typename T>
    Derived<T>::Derived(T const &t)
    :
        Base(t)
    {}
Other combinations are possible as well: by specifying ordinary template type parameters of the base class, the base class is instantiated and the derived class becomes an ordinary class:
    class Ordinary: public Base<int>
    {
        public:
            Ordinary(int x);
    };

    inline Ordinary::Ordinary(int x)
    :
        Base(x)
    {}

    // With the following object definition:
    Ordinary
        o(5);
This construction allows us in a specific situation to add functionality to a class template, without the need for constructing a derived class template.

Class template derivation pretty much follows the same rules as ordinary class derivation, not involving class templates. However, some subtleties associated with class template derivation may easily cause confusion. In the following sections class derivation involving class templates will be discussed. Some of the examples shown in these sections may contain unexpected statements and expressions, like the use of this when members of a template base class are called from a derived class. The `chicken and egg' problem I encountered here was solved by first discussing the principles of class template derivation; next the subtleties that are part of class template derivation are covered by section 20.1.

19.9.1: Deriving ordinary classes from class templates

When an existing class template is used as a base class for deriving an ordinary class, the class template parameters are specified when defining the derived class's interface. If in a certain context an existing class template lacks a particular functionality, then it may be useful to derive a ordinary class from a class template. For example, although the class map can easily be used in combination with the find_if() generic algorithm (section 17.4.16) to locate a particular element, it requires the construction of a class and at least two additional function objects of that class. If this is considered too much overhead in a particular context, extending a class template with some tailor-made functionality might be considered.

A program executing commands entered at the keyboard might accept all unique initial abbreviations of the commands it defines. E.g., the command list might be entered as l, li, lis or list. By deriving a class Handler from

        map<string, void (Handler::*)(string const &cmd)>
and defining a process(string const &cmd) to do the actual command processing, the program might simply execute the following main() function:
    int main()
    {
        string line;
        Handler cmd;

        while (getline(cin, line))
            cmd.process(line);
    }

The class Handler itself is derived from a complex map, in which the map's values are pointers to Handler's member functions, expecting the command line entered by the user. Here are Handler's characteristics:

19.9.2: Deriving class templates from class templates

Although it's perfectly acceptable to derive a ordinary class from a class template, the resulting class of course has limited generality compared to its template base class. If generality is important, it's probably a better idea to derive a class template from a class template. This allows us the extend an existing class template with some additional functionality, like allowing hierarchal sorting of its elements.

The following class SortVector is a class template derived from the existing class template Vector. However, it allows us to perform a hierarchal sort of its elements using any order of any members its data elements may contain. To accomplish this there is but one requirement: the SortVector's data type must have dedicated member functions comparing its members. For example, if SortVector's data type is an object of class MultiData, then MultiData should implement member functions having the following prototypes for each of its data members which can be compared:

        bool (MultiData::*)(MultiData const &rhv)
So, if MultiData has two data members, int d_value and std::string d_text, and both may be required for a hierarchal sort, then MultiData should offer members like:
    bool intCmp(MultiData const &rhv);  // returns d_value < rhv.d_value
    bool textCmp(MultiData const &rhv); // returns d_text  < rhv.d_text
Furthermore, as a convenience it is also assumed that operator<<() and operator>>() have been defined for MultiData objects, but that assumption as such is irrelevant to the current discussion.

The class template SortVector is derived directly from the template class std::vector. Our implementation inherits all members from that base class, as well as two simple constructors:

    template <typename Type>
    class SortVector: public std::vector<Type>
    {
        public:
            SortVector()
            {}
            SortVector(Type const *begin, Type const *end)
            :
                std::vector<Type>(begin, end)
            {}

However, its member hierarchalSort() is the actual reason why the class exists. This class defines the hierarchal sort criteria. It expects an array of pointers to member functions of the class indicated by sortVector's template Type parameter as well as a size_t indicating the size of the array. The array's first element indicates the class's most significant or first sort criterion, the array's last element indicates the class's least significant or last sort criterion. Since the stable_sort() generic algorithm was designed explicitly to support hierarchal sorting, the member uses this generic algorithm to sort SortVector's elements. With hierarchal sorting, the least significant criterion should be sorted first. hierarchalSort()'s implementation therefore, is easy, assuming the existence of a support class SortWith whose objects are initialized by the addresses of the member functions passed to the hierarchalSort() member:

    template <typename Type>
    class SortWith
    {
       bool (Type::*d_ptr)(Type const &rhv) const;

The class SortWith is a simple wrapper class around a pointer to a predicate function. Since it's dependent on SortVector's actual data type SortWith itself is also a class template:

    template <typename Type>
    class SortWith
    {
       bool (Type::*d_ptr)(Type const &rhv) const;

It's constructor receives such a pointer and initializes the class's d_ptr data member:

    template <typename Type>
    SortWith<Type>::SortWith(bool (Type::*ptr)(Type const &rhv) const)
    :
        d_ptr(ptr)
    {}

Its binary predicate member operator()() should return true if its first argument should be sorted before its second argument:

    template <typename Type>
    bool SortWith<Type>::operator()(Type const &lhv, Type const &rhv) const
    {
        return (lhv.*d_ptr)(rhv);
    }

Finally, an illustration is provided by the following main() function.

After compilation the program the following command can be given:
        echo a 1 b 2 a 2 b 1 | a.out
This results in the following output:
    a 1 b 2 a 2 b 1
    ====
    a 1 a 2 b 1 b 2
    ====
    a 1 b 1 a 2 b 2
    ====

19.9.3: Deriving class templates from ordinary classes

An existing class may be used as the base class for deriving a template class. The advantage of such an inheritance tree is that the base class's members may all be compiled beforehand, so when objects of the class template are instantiated only the used members of the derived (template) class need to be instantiated.

This approach may be used for all class templates having member functions whose implementations do not depend on template parameters. These members may be defined in a separate class which is then used as a base class of the class template derived from it.

As an illustration of this approach we'll develop such a class template in this section. We'll develop a class Table derived from an ordinary class TableType. The class Table will display elements of some type in a table having a configurable number of columns. The elements are either displayed horizontally (the first k elements occupying the first row) or vertically (the first r elements occupying a first column).

When displaying the table's elements they are inserted into a stream. This allows us to define the handling of the table in a separate class (TableType), implementing the table's presentation. Since the table's elements are inserted into a stream, the conversion to text (or string) can be implemented in Table, but the handling of the strings is left to TableType. We'll cover some characteristics of TableType shortly, concentrating on Table's interface first:

This completes the implementation of the class Table. Note that this class template only has three members, two of them constructors. Therefore, in most cases only two function templates will have to be instantiated: a constructor and the class's fill() member. For example, the following constructs a table having four columns, vertically filled by strings extracted from the standard input stream:
    Table<istream_iterator<string> >
        table(istream_iterator<string>(cin), istream_iterator<string>(),
              4, TableType::Vertical);
Note here that the fill-direction is specified as TableType::Vertical. It could also have been specified using Table, but since Table is a class template, the specification would become somewhat more complex: Table<istream_iterator<string> >::Vertical.

Now that the Table derived class has been designed, let's turn our attention to the class TableType. Here are its essential characteristics:

The support class TableSupport is used to display headers, footers, captions and separators. It has four virtual members to perform those tasks (and, of course, a virtual constructor):

The reader is referrred to the cplusplus.yo.zip archive for the full implementation of the classes Table, TableType and TableSupport. Here is a small program showing their use:
    /*
                                  table.cc
    */

    #include <fstream>
    #include <iostream>
    #include <string>
    #include <iterator>
    #include <sstream>

    #include "tablesupport/tablesupport.h"
    #include "table/table.h"

    using namespace std;
    using namespace FBB;

    int main(int argc, char **argv)
    {
        size_t nCols = 5;
        if (argc > 1)
        {
            istringstream iss(argv[1]);
            iss >> nCols;
        }

        istream_iterator<string>   iter(cin);   // first iterator isn't const

        Table<istream_iterator<string> >
            table(iter, istream_iterator<string>(), nCols,
                  argc == 2 ? TableType::Vertical : TableType::Horizontal);

        cout << table << endl;
        return 0;
    }
    /*
        Example of generated output:
        After: echo a b c d e f g h i j | demo 3
            a e i
            b f j
            c g
            d h
        After: echo a b c d e f g h i j | demo 3 h
            a b c
            d e f
            g h i
            j
    */

19.10: Class templates and nesting

When a class is nested within a class template, it automatically becomes a class template itself. The nested class may use the template parameters of the surrounding class, as shown in the following skeleton program. Within a class PtrVector, a class iterator is defined. The nested class receives its information from its surrounding class, a PtrVector<Type> class. Since this surrounding class should be the only class constructing its iterators, iterator's constructor is made private, and the surrounding class is given access to the private members of iterator using a bound friend declaration. Here is the initial section of PtrVector's class interface:
    template <typename Type>
    class PtrVector: public std::vector<Type *>

This shows that the std::vector base class will store pointers to Type values, rather than the values themselves. Of course, a destructor is needed now, since the (externally allocated) memory for the Type objects must eventually be freed. Alternatively, the allocation might be part of PtrVector's tasks, when storing new elements. Here it is assumed that the PtrVector's clients do the required allocations, and that the destructor will be implemented later on.

The nested class defines its constructor as a private member, and allows PtrVector<Type> objects to access its private members. Therefore only objects of the surrounding PtrVector<Type> class type are allowed to construct their iterator objects. However, PtrVector<Type>'s clients may construct copies of the PtrVector<Type>::iterator objects they use. Here is the nested class iterator, containing the required friend declaration. Note the use of the typename keyword: since std::vector<Type *>::iterator depends on a template parameter, it is not yet an instantiated class, so iterator becomes an implicit typename. The compiler issues a corresponding warning if typename has been omitted. In these cases typename must be used. Here is the class interface:

            class iterator
            {
                friend class PtrVector<Type>;
                typename std::vector<Type *>::iterator d_begin;

                iterator(PtrVector<Type> &vector);

                public:
                    Type &operator*();
            };

The implementation of the members shows that the base class's begin() member is called to initialize d_begin. Also note that the return type of PtrVector<Type>::begin() must again be preceded by typename:

    template <typename Type>
    PtrVector<Type>::iterator::iterator(PtrVector<Type> &vector)
    :
        d_begin(vector.std::vector<Type *>::begin())
    {}

    template <typename Type>
    Type &PtrVector<Type>::iterator::operator*()
    {
        return **d_begin;
    }

The remainder of the class is simple. Omitting all other functions that might be implemented, the function begin() will return a newly constructed PtrVector<Type>::iterator object. It may call the constructor since the class iterator called its surrounding class its friend:

    template <typename Type>
    typename PtrVector<Type>::iterator PtrVector<Type>::begin()
    {
        return iterator(*this);
    }

Here is a simple skeleton program, showing how the nested class iterator might be used:

    int main()
    {
        PtrVector<int> vi;

        vi.push_back(new int(1234));

        PtrVector<int>::iterator begin = vi.begin();

        std::cout << *begin << endl;
    }

Nested enumerations and typedefs can also be defined in class templates. The class Table, mentioned before (section 19.9.3) inherited the enumeration TableType::FillDirection. If Table would have been implemented as a full class template, then this enumeration would have been defined in Table itself as:

    template <typename Iterator>
    class Table: public TableType
    {
        public:
            enum FillDirection
            {
                Horizontal,
                Vertical
            };
        ...
    };
In this case, the actual value of the template type parameter must be specified when referring to a FillDirection value or to its type. For example (assuming iter and nCols are defined as in section 19.9.3):
    Table<istream_iterator<string> >::FillDirection direction =
                argc == 2 ?
                    Table<istream_iterator<string> >::Vertical
                :
                    Table<istream_iterator<string> >::Horizontal;

    Table<istream_iterator<string> >
        table(iter, istream_iterator<string>(), nCols, direction);

19.11: Constructing iterators

In section 17.2 the iterators used with generic algorithms were introduced. We've seen that several types of iterators were distinguished: InputIterators, ForwardIterators, OutputIterators, BidirectionalIterators and RandomAccessIterators.

In section 17.2 the characteristics of iterators were introduced: all iterators should support an increment operation, a dereference operation and a comparison for (in)equality.

However, when iterators must be used in the context of generic algorithms they must meet additional requirements. This is caused by the fact that generic algorithms check the types of the iterators they receive. Simple pointers are usually accepted, but if an iterator-object is used it must be able to specify the kind of iterator it represents.

To ensure that an object of a class is interpreted as a particular type of iterator, the class must be derived from the class iterator. The particular type of iterator is defined by the class template's first parameter, and the particular data type to which the iterator points is defined by the class template's second parameter. Before a class may be inherited from the class iterator, the following header file must have been included:

        #include <iterator>
The particular type of iterator that is implemented by the derived class is specified using a so-called iterator_tag, provided as the first template argument of the class iterator. For the five basic iterator types, these tags are: Each iterator tag assumes that a certain set of operators is available. The RandomAccessIterator is the most complex of iterators, as it implies all other iterators.

Note that iterators are always defined over a certain range, e.g., [begin, end). Increment and decrement operations may result in undefined behavior of the iterator if the resulting iterator value would refer to a location outside of this range.

Often, iterators only access the elements of the series to which they refer. Internally, an iterator may use an ordinary pointer, but it is hardly ever necessary for the iterator to allocate its own memory. Therefore, as the overloaded assignment operator and the copy constructor do not have to allocate any memory, the default implementation of the overloaded assignment operator and of the copy constructor is usually sufficient. I.e., usually these members do not have to be implemented at all. As a consequence there is usually also no destructor.

Most classes offering members returning iterators do so by having members constructing the required iterator, which is thereupon returned as an object by these member functions. As the caller of these member functions only has to use or sometimes copy the returned iterator objects, there is normally no need to provide any publicly available constructors, except for the copy constructor. Therefore these constructors may usually be defined as private or protected members. To allow an outer class to create iterator objects, the iterator class will declare the outer class as its friend.

In the following sections, the construction of a RandomAccessIterator, the most complex of all iterators, and the construction of a reverse RandomAccessIterator is discussed. The container class for which a random access iterator must be developed may actually store its data elements in many different ways, e.g., using various containers or using pointers to pointers. Therefore it is difficult to construct a template iterator class which is suitable for a large variety of ordinary (container) classes.

In the following sections, the available std::iterator class will be used to construct an inner class representing a random access iterator. This approach clearly shows how to construct an iterator class. The reader may either follow this approach when constructing iterator classes in other contexts, or a full template iterator class can be designed. An example of such a template iterator class is provided in section 21.6.

The construction of the random access iterator as shown in the next sections aims at the implementation of an iterator reaching the elements of a series of elements only accessible through pointers. The iterator class is designed as an inner class of a class derived from a vector of string pointers.

19.11.1: Implementing a `RandomAccessIterator'

When discussing containers (chapter 12) it was noted that containers own the information they contain. If they contain objects, then these objects are destroyed once the containers are destroyed. As pointers are no objects, and as auto_ptr objects cannot be stored in containers using pointer data types for containers was discouraged. However, we might be able to use pointer data types in specific contexts. In the following class StringPtr, a ordinary class is derived from the std::vector container using std::string * as its data type:
    #ifndef INCLUDED_STRINGPTR_H_
    #define INCLUDED_STRINGPTR_H_

    #include <string>
    #include <vector>

    class StringPtr: public std::vector<std::string *>
    {
        public:
            StringPtr(StringPtr const &other);
            ~StringPtr();

            StringPtr &operator=(StringPtr const &other);
    };

    #endif
Note the declaration of the destructor: as the object stores string pointers, a destructor is required to destroy the strings when the StringPtr object itself is destroyed. Similarly, a copy constructor and overloaded assignment is required. Other members (in particular: constructors) are not explicitly declared as they are not relevant to this section's topic.

Let's assume that we want to be able to use the sort() generic algorithm with StringPtr objects. This algorithm (see section 17.4.58) requires two RandomAccessIterators. Although these iterators are available (via std::vector's begin() and end() members), they return iterators to std::string *s, which cannot sensibly be compared.

To remedy this, assume that we have defined an internal type StringPtr::iterator, not returning iterators to pointers, but iterators to the objects these pointers point to. Once this iterator type is available, we can add the following members to our StringPtr class interface, hiding the identically named, but useless members of its base class:

    StringPtr::iterator begin();    // returns iterator to the first element
    StringPtr::iterator end();      // returns iterator beyond the last
                                    // element
Since these two members return the (proper) iterators, the elements in a StringPtr object can easily be sorted:
    in main()
    {
        StringPtr sp;               // assume sp is somehow filled

        sort(sp.begin(), sp.end()); // sp is now sorted
        return 0;
    }
To make this all work, the type StringPtr::iterator must be defined. As suggested by its type name, iterator is a nested type of StringPtr, suggesting that we may implement iterator as a nested class of StringPtr. However, to use a StringPtr::iterator in combination with the sort() generic algorithm, it must also be a RandomAccessIterator. Therefore, StringPtr::iterator itself must be derived from the existing class std::iterator, available once the following preprocessor directive has been specified:
        #include <iterator>
To derive a class from std::iterator, both the iterator type and the data type the iterator points to must be specified. Take caution: our iterator will take care of the string * dereferencing; so the required data type will be std::string, and not std::string *. So, the class iterator starts its interface as:
    class iterator:
        public std::iterator<std::random_access_iterator_tag, std::string>
Since its base class specification is quite complex, we could consider associating this type with a shorter name using the following typedef:
    typedef std::iterator<std::random_access_iterator_tag, std::string>
            Iterator;
However, if the defined type (Iterator) is used only once or twice, the typedefinition only adds clutter to the interface, and is better not used.

Now we're ready to redesign StringPtr's class interface. It contains members returning (reverse) iterators, and a nested iterator class. The members will be discussed in some detail next:

class StringPtr: public std::vector<std::string *>
{
    public:
    class iterator: public
            std::iterator<std::random_access_iterator_tag, std::string>
    {
        friend class StringPtr;
        std::vector<std::string *>::iterator d_current;

        iterator(std::vector<std::string *>::iterator const &current);

        public:
            iterator &operator--();
            iterator const operator--(int);
            iterator &operator++();
            bool operator==(iterator const &other) const;
            bool operator!=(iterator const &other) const;
            int operator-(iterator const &rhs) const;
            std::string &operator*() const;
            bool operator<(iterator const &other) const;
            iterator const operator+(int step) const;
            iterator const operator-(int step) const;
            iterator &operator+=(int step); // increment over `n' steps
            iterator &operator-=(int step); // decrement over `n' steps
            std::string *operator->() const;// access the fields of the
                                            // struct an iterator points
                                            // to. E.g., it->length()
    };

    typedef std::reverse_iterator<iterator> reverse_iterator;

    iterator begin();
    iterator end();
    reverse_iterator rbegin();
    reverse_iterator rend();
};

Let's first have a look at StringPtr::iterator's characteristics:

The interfaces required for other iterator types are simpler, requiring only a subset of the interface required by a random access iterator. E.g., the forward iterator is never decremented and never incremented over arbitrary step sizes. Consequently, in that case all decrement operators and operator+(int step) can be omitted from the interface. Of course, the tag to use would then be std::forward_iterator_tag. The tags (and the set of required operators) varies accordingly for the other iterator types.

19.11.2: Implementing a `reverse_iterator'

Once we've implemented an iterator, the matching reverse iterator can be implemented in a jiffy. Comparable to the std::iterator a std::reverse_iterator exists, which will nicely implement the reverse iterator for us, once we have defined an iterator class. Its constructor merely requires an object of the iterator type for which we want to construct a reverse iterator.

To implement a reverse iterator for StringPtr, we only need to define the reverse_iterator type in its interface. This requires us to specify only one line of code, which must be inserted after the interface of the class iterator:

        typedef std::reverse_iterator<iterator> reverse_iterator;
Finally, the well known members rbegin() and rend() are added to StringPtr's interface. Again, they can easily be implemented inline:
inline StringPtr::reverse_iterator StringPtr::rbegin()
{
    return reverse_iterator(end());
}
inline StringPtr::reverse_iterator StringPtr::rend()
{
    return reverse_iterator(begin());
}

Note the arguments the reverse_iterator constructors receive: the begin point of the reversed iterator is obtained by providing reverse_iterator's constructor with end(): the endpoint of the normal iterator range; the endpoint of the reversed iterator is obtained by providing reverse_iterator's constructor with begin(): the begin point of the normal iterator range.

The following little program illustrates the use of StringPtr's RandomAccessIterator:

    #include <iostream>
    #include <algorithm>
    #include "stringptr.h"
    using namespace std;

    int main(int argc, char **argv)
    {
        StringPtr sp;

        while (*argv)
            sp.push_back(new string(*argv++));

        sort(sp.begin(), sp.end());
        copy(sp.begin(), sp.end(), ostream_iterator<string>(cout, " "));

        cout << "\n======\n";

        sort(sp.rbegin(), sp.rend());
        copy(sp.begin(), sp.end(), ostream_iterator<string>(cout, " "));

        cout << endl;
    }
    /*
            when called as:
        a.out bravo mike charlie zulu quebec

            generated output:
        a.out bravo charlie mike quebec zulu
        ======
        zulu quebec mike charlie bravo a.out
    */
Although it is thus possible to construct a reverse iterator from a normal iterator, the opposite does not hold true: it is not possible to initialize a normal iterator from a reverse iterator. Let's assume we would like to process all lines stored in a vector<string> lines up to any trailing empty lines (or lines only containing blanks) it might contain. How would we proceed? One approach is to start the processing from the first line in the vector, continuing until the first of the trailing empty lines. However, once we encounter an empty line it does of course not have to be the first line of the set of trailing empty lines. In that case, we would like to use the following algorithm: However, we can't mix iterators and reverse iterators when using generic algorithms. So how can we initialize the second iterator using the available reverse_iterator? The solution is actually not very difficult, as an iterator may be initialized by a pointer. The reverse iterator rit is not a pointer, but &*(rit - 1) or &*--rit is. Thus, we can use
        for_each(lines.begin(), &*--rit, Process());
to process all the lines up to the first of the set of trailing empty lines. In general, if rit is a reverse_iterator pointing to some element, but we need an iterator to point to that element, we may use &*rit to initialize the iterator. Here, the dereference operator is applied to reach the element the reverse iterator refers to. Then the address operator is applied to obtain its address.