Chapter 21: 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: 8.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. Consider constructing a class template when a 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, that 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 in combination with a particular data type only the data type needs to be specified when defining or declaring a class template object (as in 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), that uses a mechanism resembling that of templates. Polymorphism allows the programmer to postpone the implementation of algorithms by deriving classes from base classes in which algorithms are only partially implemented. The actual definition and processing of the data upon which the algorithms operate may be postponed until derived classes are defined. Likewise, templates allow the programmer to postpone the specification of the data upon which the algorithms operate. This is most clearly seen with abstract containers, that completely specify the algorithms and that at the same time leave 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. Usingem vtables the function that is actually called depends on the type of object a (base) class pointer points at. Static polymorphism is encountered in the context of templates. 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. All virtual members must be instantiated (whether they are used or not) as the compiler must construct the vtable for each data type for which an object of the class is instantiated.

Generally, class templates are easier to use than polymorphism. 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 defining a similar stack of ints using object oriented programming. On the other hand, for each different type for which an object of a class template is defined another, possibly complete class must be reinstantiated. This is not required in the context of object oriented programming where derived classes use, rather than copy, the functions that are already available in their base classes (but see also section 21.10).

Previously we've already used class templates. Objects like vector<int> vi and vector<string> vs are commonly used. The data types for which these templates are defined and instantiated are an inherent part of such container types. It is stressed that it is the combination of a class template type and its template parameter(s), rather than the mere class template's type that defines or generates a type. So vector<int> is a type as is vector<string>. Such types could very well be represented by typedefs: 

    typedef std::vector<int>         IntVector;
    typedef std::vector<std::string> StringVector;

    IntVector vi;
    StringVector vs;

21.1: Defining class templates

Having covered the construction of function templates, we're now ready for the next step: constructing class templates. Many useful class templates already exist. Rather than illustrating the construction of a class template by looking at an already existing class template the construction of another potentially useful new class template will be undertaken.

The new class implements a circular queue. a circular queue has a fixed number of max_size elements. New elements are inserted at its back and only its head and tail elements can be accessed. Only the head element can be removed from a circular queue. Once n elements have been appended the next element will again be inserted at the queue's (physical) first position. The circular queue allows insertions until it holds max_size elements. As long as a circular queue contains at least one element elements may be removed from it. Trying to remove an element from an empty circular queue or to add another element to a full circular queue results in exceptions being thrown. In addition to other constructors a circular queue must offer a constructor initializing its objects for max_size elements. This constructor must make available the memory for the max_size elements but must not call those elements default constructors (hinting at the use of the placement new operator). A circular queue should offer value semantics as well as a move constructor.

Please note that in the above description the actual data type that is used for the circular queue is nowhere mentioned. This is a clear indication that our class could very well be defined as a class template. Alternatively, the class could be defined for some concrete data type which is then abstracted when converting the class to a class template.

In this section the class template CirQue (circular queue) is constructed, having one template type parameter Data representing the data type that is stored in the circular queue. The outline of the interface of this class template looks like this: 

    template<typename Data>
    class CirQue
    {
        // member declarations
    };
A class template's definition starts like a function template's definition: Once the CirQue class template has been defined it can be used to create all kinds of circular queues. As one of its constructors expects a size_t argument defining the maximum number of elements that can be stored in the circular queue circular queues could be defined like this: 
    CirQue<int> cqi(10);            // max 10 ints
    CirQue<std::string> cqstr(30);  // max 30 strings
As noted in the introductory section of this chapter the combination of name of the class template and the data type for which it is instantiated defines a data type. Also note the similarity between defining a std::vector (of some data type) and a CirQue (of some data type).

Like std::map containers class templates may be defined with multiple template type parameters.

Back to CirQue. A CirQue must be capable of storing max_size Data elements. These elements are eventually stored in memory pointed at by a pointer Data *d_data, initially pointing to raw memory. New elements are added at the backside of the CirQue. A pointer Data *d_back is used to point to the location where the next element will be stored. Likewise, Data *d_front points to the location of the CirQue's first element. Two size_t data members are used to monitor the filling state of the CirQue: d_size represents the number of elements currently stored in the CirQue, d_maxSize represents the maximum number of elements that the CirQue can contain. Thus, the CirQue's data members are: 

    size_t d_size;
    size_t d_maxSize;
    Data *d_data;
    Data *d_front;
    Data *d_back;

The class CirQue offers various member functions. Normal design principles should be adhered to when constructing class template members. 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. Member function definitions should preferably not be provided in-class but below the class interface. Since class template member functions are function templates their definitions should be provided in the header file offering the class interface. They may be given the inline attribute.

CirQue declares the following (public) members (their definitions are provided as well; all definitions are provided below the class interface):

The remaining public members all consist of one-liners and are implemented as inline functiontemplates:

Finally, the class has one private member, inc, returning a cyclically incremented pointer into CirQue's raw memory: 

    template<typename Data>
    Data *CirQue<Data>::inc(Data *ptr)
    {
        ++ptr;
        return ptr == d_data + d_maxSize ? d_data : ptr;
    }

When objects of a class template are instantiated, only the definitions of all the template's member functions that are used must have been seen by the compiler. That characteristic of templates could be refined to the point where each definition is stored in a separate function template definition file. In that case only the definitions of the function templates that are actually needed would have to be included. However, it is hardly ever done that way. Instead, the usual way to define class templates is to define the interface and to define the remaining function templates immediately below the class template's interface (defining some functions inline).

Now that the class CirQue has been defined, it can be used. To use the class its object must be instantiated for a particular data type. In the following example it is initialized for data type std::string: 

#include "cirque.h"
#include <iostream>
#include <string>
using namespace std;

int main()
{
    CirQue<string> ci(4);
    ci.push_back("1");
    ci.push_back("2");
    cout << ci.size() << ' ' << ci.front() << ' ' << ci.back() << '\n';

    ci.push_back("3");
    ci.pop_front();
    ci.push_back("4");
    ci.pop_front();
    ci.push_back("5");
    cout << ci.size() << ' ' << ci.front() << ' ' << ci.back() << '\n';

    CirQue<string> copy(ci);
    copy.pop_front();
    cout << copy.size() << ' ' << copy.front() << ' ' << copy.back() << '\n';

    int arr[] = {1, 3, 5, 7, 9};
    CirQue<int> ca(arr);
    cout << ca.size() << ' ' << ca.front() << ' ' << ca.back() << '\n';

//    int *ap = arr;
//    CirQue<int> cap(ap);
}

21.1.1: Default class template parameters

Different from function templates, template parameters of template classes may be given default argument values. This holds true for both template type- and template non-type parameters. If default template arguments were defined and if a class template object is instantiated without specifying arguments for its template parameters then the template parameter's defaults are used.

When defining defaults keep in mind that they should be suitable for the majority of instantiations of the class. E.g., for the class template CirQue 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. When instantiating class template objects using default template arguments the type specifications may be omitted but the angle brackets must be retained. Assuming a default type for the CirQue class, an object of that class may be defined as: 

    CirQue<> intCirQue(10);

Default template arguments cannot be specified when defining template members. So, the definition of, e.g., the push_back member must always begin with the same template specification: 

    template <typename Data>

When a class template uses multiple template parameters, all may be given default values. Like default function arguments, once a default value is used all remaining template 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.

21.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): 
    template <typename Data>
    class CirQue;
Default template arguments may also be specified when declaring class templates. However, default template arguments cannot be specified for both the declaration and the definition of a class template. As a rule of thumb default template arguments should be omitted from declarations, as class template declarations are never used when instantiating objects but are only occasionally used as forward references. Note that this differs from default parameter value specifications for member functions in ordinary classes. Such defaults are always specified when declaring the member functions in the class interface.

21.1.3: Preventing template instantiations (C++0x)

In C++ templates are instantiated when the address of a function template or class template object is taken or when a function template or class template is used. As described in section 21.1.2 it is possible to (forward) declare a class template to allow the definition of a pointer or reference to that template class or to allow it being used as a return type.

In other situations templates are instantiated when they are being used. If this happens many times (i.e., in many different source files) then this may slow down the compilation process considerably. The C++0x standard allows programmers to prevent templates from being instantiated. For this the C++0x standard introduces the extern template syntax. Example: 

    extern template class std::vector<int>;
Having declared the class template it can be used in its translation unit. E.g., the following function will properly compile: 
#include <vector>
#include <iostream>
using namespace std;

extern template class vector<int>;

void vectorUser()
{
    vector<int> vi;
    cout << vi.size() << '\n';
}
But be careful:

21.1.4: Non-type parameters

Function template parameters are either template type parameters or template non-type parameters (actually, a third type of template parameter exists, the template template parameter, which is discussed in chapter 22 (section 22.3)).

Class templates may also define non-type parameters. Like the function template non-type parameters they must be (integral) constants whose values must be known at object instantiation time.

Different from function template non-type parameters the values of class template non-type parameters are not deduced by the compiler using arguments passed to class template members. Assume we modify the class template CirQue 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 parameter of Size elements of type Data. Only showing the relevant constructors (section 21.1.5 provides the rationale for using the type Data2);

Now two template type parameters are required, e.g., when specifying the type of the copy constructor's parameter. The new CirQue class template becomes (showing only the relevant constructors): 

    template <typename Data, size_t Size>
    class CirQue
    {
        // ... data members
        public:
            CirQue(CirQue<Data, Size> &other);
            CirQue(Data *data);
            CirQue(Data const (&arr)[Size]);
            ...
    };

    template <typename Data, size_t Size>
    CirQue<Data, Size>::CirQue(Data const (&arr)[Size])
    :
        d_maxSize(Size),
        d_size(0),
        d_data(operator new(Size * sizeof(Data))),
        d_front(d_data),
        d_back(d_data),
    {
        std::copy(arr, arr + Size, back_inserter(*this));
    }
Unfortunately, this 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];

        CirQue<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 CirQue'
    */
Defining Size as a non-type parameter having a default value doesn't work either. The compiler always uses the default unless its value is explicitly specified. Reasoning that Size can be 0 unless we need another value, we might be tempted to specify size_t Size = 0 in the template's parameter type list. Doing so we create 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 `CirQue<int, 0>':
    ...
    error: creating array with size zero (`0')
So, although class templates may use non-type parameters they must always be specified like type parameters when an object of that class is defined. Default values can be specified for those non-type parameters causing the compiler to use the default when the non-type parameter is left unspecified.

Default template parameter values (either type or non-type template parameters) may not be specified when defining template member functions. In general: function template definitions (and thus: class template member functions) may not be given default template (non) type arguments. If default template arguments are to be used for class template members, they have to be specified by the class interface.

Similar to non-type parameters of function templates default argument values for non-type class template parameters may only be specified as constants:

Although our attempts to define a constructor of the class CirQue accepting an array as its argument has failed so far, we're not yet out of options. In the next section a method is described that does allowing us to reach our goal.

21.1.5: Member templates

Our previous attempt to define a template non-type parameter that 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. Instead, they must explicitly be specified when an object of the class template is defined. As the template arguments are specified just before the template's constructor is called the compiler doens't have to deduce anything and it can simply use the explicitly specified template arguments.

In contrast, when function templates are used, the actual template parameters are deduced from the arguments used when calling the function. This opens up an alley leading to the solution of our problem. If the constructor itself is turned into a function template (having its own template header), then the compiler will be able to deduce the non-type parameter's value and there is no need anymore to specify it explicitly using a class template non-type parameter.

Members (functions or nested classes) of class templates that are themselves templates are called member templates.

Member templates are defined as any other template, including its own template header.

When converting our earlier CirQue(Data const (&array)[Size]) constructor into a member template the class template's Data type parameter can still be used, but we must provide the member template with a non-type parameter of its own. Its declaration in the (partially shown) class interface looks like this: 

    template <typename Data>
    class CirQue
    {
        public:
            template <size_t Size>
            explicit CirQue(Data const (&arr)[Size]);
    };
Its implementation becomes: 
    template <typename Data>
    template <size_t Size>
    CirQue<Data>::CirQue(Data const (&arr)[Size])
    :
        d_size(0),
        d_maxSize(Size),
        d_data(static_cast<Data *>(operator new(Size * sizeof(Data)))),
        d_front(d_data),
        d_back(d_data)
    {
        std::copy(arr, arr + Size, back_inserter(*this));
    }

The implementation uses the STL's copy algorithm and a back_inserter adapter to insert the array's elements into the CirQue. To use the back_inserter CirQue must define two (public) typedefs (cf. section 18.2.1): 

    typedef Data value_type;
    typedef value_type const &const_reference;

Member templates have the following characteristics:

A potentially occurring problem remains. Assume that in addition to the above member template a CirQue<Data>::CirQue(Data const *data) has been defined. Some (here not further elaborated) protocol may be defined allowing the constructor to determine the number of elements that should be stored in the CirQue object. When we now define 

    CirQue<int> object(array);
it is this latter constructor, rather than the member template, that is used by the compiler. The compiler selects this latter constructor as it is a more specialized version of a constructor of the class CirQue than the member template (cf. section 20.9). Problems like these can be solved by defining the constructor CirQue(Data const *data) into a member template as well. It could receive a template type parameter Data2. Data cannot be used as template parameters of a member template may not shadow template parameters of its class. Using Data2 instead of Data takes care of this subtlety. Here is the declaration of the constructor CirQue(Data2 const *) as it could appear in the CirQue header file: 
    template <typename Data>
    class CirQue
    {
        template <typename Data2>
        explicit CirQue(Data2 const *data);
    }
Here is how the two constructors are selected in code defining two CirQue objects: 
    int main()
    {
        int array[30];
        int *iPtr = array;

        CirQue<int> ac(array);      // calls CirQue(Data const (&arr)[Size])
        CirQue<int> acPtr(iPtr);    // calls CirQue(Data2 const *)
    }

21.2: Static data members

When static members are defined in class templates, they are defined for every new type for which the class template is instantiated. As they are static members, there will only be one member per type for which the class template is instantiated. 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 object definitions result in the instantiation of just one single static variable, shared among the two objects: 
    TheClass<int> theClassOne;
    TheClass<int> theClassTwo;
Mentioning static members in interfaces does not mean these members are actually defined. They are only declared and must be defined separately. With static members of class templates this is no different. The definition of static members is usually provided immediately following (i.e., below) the template class interface. The static member s_objectCounter will usually be defined as follows, just below its class interface: 
    template <typename Type>                    // definition, following
    int TheClass<Type>::s_objectCounter = 0;    // the interface
Here s_objectCounter is an int and thus independent of the template type parameter Type.

In list-like constructions, where a pointer to objects of the class itself is required, the template type parameter Type must be used when defining the static variable. 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>.

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

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

21.2.1: Extended use of the keyword `typename'

Until now the keyword typename has been used to indicate a template type parameter. However, it is also used to disambiguate code inside templates. Consider the following function template: 
    template <typename Type>
    Type function(Type t)
    {
        Type::Ambiguous *ptr;

        return t + *ptr;
    }
When this code is processed by the compiler, it will complain with an -at first sight puzzling- error message like: 
    4: error: 'ptr' was not declared in this scope
The error message is puzzling as it was the programmer's intention to declare a pointer to a type Ambiguous defined within the class template Type. But the compiler, confronted with Type::Ambiguous may interpret the statement in various ways. Clearly it cannot inspect Type itself trying to uncover Type's true nature as Type is a template type. Because of this Type's actual definition isn't available yet.

The compiler is confronted with two possibilities: either Type::Ambiguous is a static member of the as yet mysterious template Type, or it is a subtype of Type. As the standard specifies that the compiler must assume the former, the statement 

    Type::Ambiguous *ptr;
is interpreted as a multiplication of the static member Type::Ambiguous and the (now undeclared) entity ptr. The reason for the error message should now be clear: in this context ptr is unknown.

To disambiguate code in which an identifier refers to a subtype of a template type parameter the keyword typename must be used. Accordingly, the above code is altered into: 

    template <typename Type>
    Type function(Type t)
    {
        typename Type::Ambiguous *ptr;

        return t + *ptr;
    }
Classes fairly often define subtypes. When such subtypes appear inside template definitions as subtypes of template type parameters the template keyword must be used to identify them as subtypes. Example: a class template Handler defines a typename Container as its template type parameter. It also defines a data member storing the iterator returned by the container's begin member. In addition Handler offers a constructor accepting any container supporting a begin member. Handler's class interface could then look like this: 
    template <typename Container>
    class Handler
    {
        Container::const_iterator d_it;

        public:
            Handler(Container const &container)
            :
                d_it(container.begin())
            {}
    };
What did we have in mind when designing this class? The final consideration is an indication that typename is required. If this is omitted and a Handler is instantiated the compiler produces a peculiar compilation error: 
    #include "handler.h"
    #include <vector>
    using namespace std;

    int main()
    {
        vector<int> vi;
        Handler<vector<int> > ph(vi);
    }
    /*
        Reported error:

    handler.h:4: error: syntax error before `;' token
    */
Clearly the line 
    Container::const_iterator d_it;
in the class Handler causes a problem. It is interpreted by the compiler as a static member instead of a subtype. The problem is solved using typename: 
    template <typename Container>
    class Handler
    {
        typename Container::const_iterator d_it;
        ...
    };
An interesting illustration that the compiler indeed assumes X::a to be a member a of the class X is provided by the error message we get when we try to compile main using the following implementation of Handler's constructor: 
    Handler(Container const &container)
    :
        d_it(container.begin())
    {
        size_t x = Container::ios_end;
    }
    /*
        Reported error:

        error: `ios_end' is not a member of type `std::vector<int,
                std::allocator<int> >'
    */

Now consider what happens if the function template introduced at the beginning of this section doesn't return a Type value, but a Type::Ambiguous value. Again, a subtype of a template type is referred to, and typename must be used: 

    template <typename Type>
    typename Type::Ambiguous function(Type t)
    {
        return t.ambiguous();
    }
Using typename in the specification of a return type is further discussed in section 22.1.1.

Typenames can be embedded in typedefs. As is often the case, this reduces the complexities of declarations and definitions appearing elsewhere. In the next example the type Iterator is defined as a subtype of the template type Container. Iterator may now be used without requiring the use of the keyword typedef: 

    template <typename Container>
    class Handler
    {
        typedef typename Container::const_iterator Iterator;

        Iterator d_it;
        ...
    };

21.3: Specializing class templates for deviating types

The class CirQue can be used for many different types. Their common characteristic is that they can simply be pointed at by class's d_data member. But this is not always as simple as it looks. What if Data turns out to be a vector<int>? For such data types the vanilla CirQue implementation will not properly work and a specialization could be considered. When considering a specialization one should also consider inheritance. Often a class derived from the class template accepting the incompatible data structure as its argument but otherwise equal to the original class template can easily be designed. The developmental advantage of inheritance over specialization is clear: the inherited class inherits the members of its base class while the specialization inherits nothing. All members defined by the original class template must be implemented again by the class template's specialization.

The specialization considered here is a true specialization in that the data members and representation used by the specialization greatly differ from the original CirQue class template. Therefore all members defined by the orginal class template must be modified to fit the specialization's data organization.

Like function template specializations class template specializations start with a template header that may or may not have an empty template parameter list. If the template parameters are directly specialized by the specialization it remains empty (e.g., CirQue's template type parameter Data is specialized for char * data). But the template parameter list may show typename Data when specializing for a vector<Data>, i.e., a vector storing any type of data. This leads to the following principle:

A template specialization is recognized by the template argument list following a function or class template's name and not by an empty template parameter list. Class template specializations may have non-empty template parameter lists. If so, a partial class template specialization is defined.

A completely specialized class has the following characteristics:

Here is an example of a completely specialized CirQue class, specialized for a vector<int>. All members of the specialized class are declared, but only non-trivial implementations of its members are provided. The specialized class uses a copy of the vector passed to the constructor and implements a circular queue using its vector data member: 

#ifndef INCLUDED_CIRQUEVECTOR_H_
#define INCLUDED_CIRQUEVECTOR_H_

#include <vector>
#include "cirque.h"

template<>
class CirQue<std::vector<int>>
{
    typedef std::vector<int> IntVect;

    IntVect d_data;
    size_t d_size;

    typedef IntVect::iterator iterator;
    iterator d_front;
    iterator d_back;

    public:
        typedef int value_type;
        typedef value_type const &const_reference;

        enum Exception
        {
            EMPTY,
            FULL
        };

        CirQue();
        CirQue(IntVect const &iv);
        CirQue(CirQue<IntVect> const &other);

        CirQue &operator=(CirQue<IntVect> const &other);

        int &back();
        int &front();
        bool empty() const;
        bool full() const;
        size_t maxSize() const;
        size_t size() const;
        void pop_front();
        void push_back(int const &object);
        void swap(CirQue<IntVect> &other);

    private:
        iterator inc(iterator const &iter);
};

CirQue<std::vector<int>>::CirQue()
:
    d_size(0)
{}
CirQue<std::vector<int>>::CirQue(IntVect const &iv)
:
    d_data(iv),
    d_size(iv.size()),
    d_front(d_data.begin()),
    d_back(d_data.begin())
{}
CirQue<std::vector<int>>::CirQue(CirQue<IntVect> const &other)
:
    d_data(other.d_data),
    d_size(other.d_size),
    d_front(d_data.begin() + (other.d_front - other.d_data.begin())),
    d_back(d_data.begin() + (other.d_back - other.d_data.begin()))
{}
CirQue<std::vector<int>> &CirQue<std::vector<int>>::operator=(
                                        CirQue<IntVect> const &rhs)
{
    CirQue<IntVect> tmp(rhs);
    swap(tmp);
}
void CirQue<std::vector<int>>::swap(CirQue<IntVect> &other)
{
    char tmp[sizeof(CirQue<IntVect>)];
    memcpy(tmp, &other, sizeof(CirQue<IntVect>));
    memcpy(&other, this, sizeof(CirQue<IntVect>));
    memcpy(this, tmp, sizeof(CirQue<IntVect>));
}
void CirQue<std::vector<int>>::pop_front()
{
    if (d_size == 0)
        throw EMPTY;

    d_front = inc(d_front);
    --d_size;
}
void CirQue<std::vector<int>>::push_back(int const &object)
{
    if (d_size == d_data.size())
        throw FULL;

    *d_back = object;
    d_back = inc(d_back);
    ++d_size;
}
inline int &CirQue<std::vector<int>>::back()
{
    return d_back == d_data.begin() ? d_data.back() : d_back[-1];
}
inline int &CirQue<std::vector<int>>::front()
{
    return *d_front;
}
CirQue<std::vector<int>>::iterator CirQue<std::vector<int>>::inc(
    CirQue<std::vector<int>>::iterator const &iter)
{
    iterator tmp(iter + 1);
    tmp =  tmp == d_data.end() ? d_data.begin() : tmp;
    return tmp;
}

#endif
Here is an example showing the use of the specialized CirQue class: 
static int iv[] = {1, 2, 3, 4, 5};

int main()
{
    vector<int> vi(iv, iv + 5);
    CirQue<vector<int>> ci(vi);

    cout << ci.size() << ' ' << ci.front() << ' ' << ci.back() << '\n';
    ci.pop_front();
    ci.pop_front();

    CirQue<vector<int>> cp;

    cp = ci;
    cout << cp.size() << ' ' << cp.front() << ' ' << cp.back() << '\n';
    cp.push_back(6);
    cout << cp.size() << ' ' << cp.front() << ' ' << cp.back() << '\n';
}

21.4: Partial specializations

In the previous section class template specializations were introduced. In this section we'll introduce a variant of this specialization, both in number and type of template parameters that are specialized. Partial specializations may be defined for class templates having multiple template parameters. Function templates cannot be partially specialized.

With partial specializations a subset (any subset) of template type parameters are given specific values. It is also possible to use a class template partial specialization when the intent is to specialize the class template, but to parameterize the data type that is processed by the specialization.

To start our discussion with an example of the latter use of a partial class template specialization consider the class CirQue<vector<int>> developed in the previous section. When designing CirQue<vector<int>> you may have asked yourself how many specializations you'd have to implement. One for vector<int>, one for vector<string>, one for vector<double>? As long as the data types handled by the vector used by the class CirQue<vector<...>> behaves like an int (i.e., is a value-type of class) the answer is: zero. Instead of defining full specializations for each new data type the data type itself can be parameterized, resulting in a partial specialization: 

    template <typename Data>
    class CirQue<std::vector<Data>>
    {
        ...
    };
The above class is a specialization as a template argument list is appended to the CirQue class name. But as the class template itself has a non-empty template parameter list it is in fact recognized as a partial specialization. There is one characteristic that distinguishes the implementation (subsequent to the class template's interface) of a class template member function of a partial specialization from the implementation of a member function of a full specialization. Implementations of partially specialized class template member functions receives a template header. No template headers are used when implementing fully specialized class template members.

Implementing the partial specialization for CirQue is not difficult and is left as an exercise for the reader (hints: simply change int into Data in the CirQue<vector<int>> specialization of the previous section). Remember to prefix the type iterator by typename (as in typedef typename DataVect::iterator iterator) (as discussed in section 21.2.1).

The remainder of this section concentrates on specializing class template non-type template parameters. These partial specializations will be illustrated using some simple concepts defined in matrix algebra, a branch of linear algebra.

A matrix is commonly thought of as a table of some 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. Our class template is therefore provided with a DataType template type parameter. It is 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 well defined numbers of rows and columns (the dimensions of the matrix), that normally do not change when matrices are used, 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 argument. Since it's a sensible default, the DataType template type parameter is used last in the template type parameter list.

Our template class Matrix begins its life as: 

    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. Here we will not focus on these operations. Rather, we concentrate on some simple operations: computing marginals and sums: The following example shows a matrix, its marginals, and the sum of its values: 
                matrix:         row
                                marginals:

                1   2   3        6
                4   5   6       15

    column      5   7   9       21  (sum)
    marginals

What do we want our class template to offer?

Class template partial specializations can 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 a row of a generic Matrix, mainly (but not only) used for the construction of column marginals. Here is how such a partial specialization is designed:

Now that we have defined the generic Matrix class and 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 SourceForge) 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 next 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] << '\n';

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

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

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

21.5: Variadic templates (C++0x)

Up to this point we've only encountered templates having a fixed number of template parameters. The C++0x standard extends this with variadic templates.

Variadic templates are defined for function templates and for class templates. Variadic templates allow us to specify an arbitrary number of template arguments of any type.

Variadic templates were added to the language to prevent us from having to define many overloaded templates and to be able to create type safe variadic functions.

Although C (and C++) support variadic functions, their use has always been deprecated in C++ as those functions are notoriously type-unsafe. Variadic function templates can be used to process objects that until now couldn't be processed properly by C-style variadic functions.

Template header of variadic templates show the phrase typename ... Params in their template headers (Params being a formal name). A variadic class template Variadic could be declared as follows: 

    template<typename ... Params> class Variadic;
Assuming the class template's definition is available then this template can be instantiated using any number of template arguments. Example: 
    class Variadic<
            int,
            std::vector<int>,
            std::map<std::string, std::vector<int>>
    > v1;
The template argument list of a variadic template can be empty. Example: 
    class Variadic<> empty;
If this is considered undesirable an empty template argument list can be prevented by providing one or more fixed parameters. Example: 
    template<typename First, typename ... Rest>
    class tuple;

C's function printf is a well-known example of a type-unsafe function. It is turned into a type-safe function when it is implemented as a variadic function template. Not only does this turn the function into a type-safe function but it is also automatically extended to accept any type that can be defined by C++. Here is a possible declaration of a variadic function template printcpp: 

    template<typename ... Params>
    void printcpp(std::string const &strFormat, Params ... parameters);
The ellipsis ( ...) used in the declaration serves two purposes: C++ offers no syntax to determine the individual template arguments. However, the arguments can be determined recursively. An example is provided in the next section. The number of arguments can be determined using a new invocation of the sizeof operator: 
    template<typename ... Params>
    struct StructName
    {
        static size_t const s_size = sizeof ... (Params);
    };

    // StructName<int, char>::s_size          -- initialized to 2

21.5.1: Defining and using variadic templates (C++0x)

The arguments associated with a variadic template parameter are not directly available to the implementation of a function or class template. resort to other means to obtain them.

By defining an partial specialization of a variadic template explicitly defining an additional template type parameter we can associate the first template argument of a parameter pack with the additional tyoe parameter. The setup of such a variadic function template (e.g., printcpp, see the previous section) is as follows:

The overloaded non-template function prints the remainder of the format string, en passant checking for any left-over format specifications: 

    void printcpp(string const &format)
    {
        size_t left = 0;
        size_t right = 0;

        while (true)
        {
            if ((right = format.find('%', right)) == string::npos)
                break;
            if (format.find("%%", right) != right)
                throw std::runtime_error(
                            "printcpp: missing arguments");
            ++right;
            cout << format.substr(left, right - left);
            left = ++right;
        }
        cout << format.substr(left);
    }

Here is the variadic function template's implementation: 

    template<typename First, typename ... Params>
    void printcpp(std::string const &format, First value, Params ... params)
    {
        size_t left = 0;
        size_t right = 0;
        while (true)
        {
            if ((right = format.find('%', right)) == string::npos)      // 1
                throw std::logic_error("printcpp: too many arguments");

            if (format.find("%%", right) != right)                      // 2
                break;

            ++right;
            cout << format.substr(left, right - left);
            left = ++right;
        }
        cout << format.substr(left, right - left) << value;
        printcpp(format.substr(right + 1), params ...);
   }
Make sure that the overloaded function is at least declared before the compiler processes the function template's definition or it won't call the overloaded function printcpp when compiling the function template.

Different from C's printf function printcpp only recognizes % and %% as format specifiers. The above implementation does not recognize, e.g., field widths. Type specifiers like %c and %x are of course not needed as ostream's insertion operator is aware of the types of the arguments that are inserted into the ostream. Extending the format specifiers so that field widths etc. are recognized by this printcpp implementation is left as an exercise to the reader. Here is an example showing how printcpp can be called: 

    printcpp("Hello % with %%main%% called with % args"
                                            " and a string showing %\n",
        "world", argc, string("A String"));

21.5.2: Perfect forwarding (C++0x)

Consider string's member insert. String::insert has several overloaded implementations. It can be used to insert text (completely or partially) provided in a string or in a char const * argument; to insert single characters a specified number of times; iterators can be used to specify the range of characters to be inserted; etc., etc.. All in, string offers five overloaded insert members.

Assume the existence of a class Inserter that is used to insert information into all kinds of objects. Such a class could have a string data member into which information can be inserted. Inserter's interface only partially has to copy string's interface to realize this: only string::insert's interfaces must be duplicated. These duplicating interfaces often contain one statement (calling the appropriate member function of the object's data member) and are for this reason often implemented in-line. These wrapper functions merely forward their parameters to the appropriate member function of the object's data member.

Factory functions also frequently forward their parameters to the constructors of objects that they return.

Before the C++0x standard the interfaces of overloaded functions needed to be duplicated by the forwarding entity: Inserter needed to duplicate the interfaces of all five string::insert members; a factory function needed to duplicate the interfaces of the constructors of the class of the objects it returned.

The C++0x standard simplifies and generalizes forwarding of parameters by offering perfect forwarding, implemented through rvalue references and variadic templates. With perfect forwarding the arguments passed to functions are `perfectly forwarded' to nested functions. Forwarding is called perfect as the arguments are forwarded in a type-safe way. To use perfect forwarding nested functions must define parameter lists matching the forwarding parameters both in types and number.

Perfect forwarding is easily implemented:

In the following example perfect forwarding is used to implement Inserter::insert. The insert function that's actually called now depends on the types and number of arguments that are passed to Inserter::insert: 

    class Inserter
    {
        std::string d_str;  // somehow initialized
        public:
                            // constructors not implemented,
                            // but see below
            Inserter();
            Inserter(std::string const &str);
            Inserter(Inserter const &other);
            Inserter(Inserter const &&other);

            template<typename ... Params>
            void insert(Params && ... params)
            {
                d_str.insert(std::forward<Params>(params) ...);
            }
    };

A factory function returning a Inserter can also easily be implemented using perfect forwarding. Rather than defining four overloaded factory functions a single one now suffices. By providing the factory function with an additional template type parameter specifying the class of the object to construct the factory function is turned into a completely general factory function: 

    template <typename Class, typename ... Params>
    Class factory(Params && ... params)
    {
        return Class(std::forward<Params>(params) ...);
    }
Here are some examples showing its use: 
    Inserter inserter(factory<Inserter>("hello"));
    string delimiter(factory<string>(10, '='));
    Inserter copy(factory<Inserter>(inserter));

The function std::forward is provided by the standard library. It performs no magic, but merely returns params as an nameless object. That way it acts like std::move that also removes the name from an object, returning it as a nameless object. The unpack operator has nothing to do with the use of forward but merely tells the compiler to apply forward to each of the arguments in turn. Thus it behaves similarly to C's ellipsis operator used by variadic functions.

Perfect forwarding was introduced in section 20.3.5: a template function defining a Type &&param, with Type being a template type parameter will convert Type && to Tp & if the function is called with an argument of type Tp &. Otherwise it will bind Type to Tp, with param being defined as Tp &&param. As a result an lvalue argument will bind to an lvalue-type (Tp &), while an rvalue argument will bind to an rvalue-type (Tp &&).

The function std::forward merely passes the argument (and its type) on to the called function or object. Here is its simplified implementation: 

    typedef <type T>
    T &&forward(T &&a)
    {
        return a;
    }
Since T && turns into an lvalue reference when forward is called with an lvalue (or lvalue reference) and remains an rvalue reference if forward is called with an rvalue reference and since forward (like std::move) anonymizes the variable passed as argument to forward the argument value is forwarded while keeping its type from the function's parameter to the called function's argument. This is called perfect forwarding as the called function will only be called if the types of the arguments used when calling the `outer' function (e.g., factory) exactly match the types of the parameters of the called function (e.g., Class's constructor). Perfect forwarding therefore is a tool to uphold type safety.

A cosmetic improvement to forward forces users of forward to specify the type to use rather than to have the compiler deduct the type as a result of the function template parameter type deduction's process. This is realized by a small support struct template: 

    template <typename T>
    struct identity
    {
        typedef T type;
    };
This struct merely defines identity::type as T, but as it is a struct it must be specified explicitly. It cannot be determined from the function's argument itself. The subtle modification to the above implementation of forward thus becomes (cf. section 21.2.1 for an explanation of the use of typename): 
    typedef <type T>
    T &&forward(typename identity<T>::type&& a)
    {
        return a;
    }
Now forward must explicitly state the a's plain type, as in: 
    std::forward<Params>(params)

Using the std::forward function and the rvalue reference specification is not restricted to the context of parameter packs. Because of the special way rvalue references to template type parameters are treated (cf. section 20.3.5) they can profitably be used to forward individual function parameters as well. Here is an example showing how an argument to a function can be forwarded from a template to a function that is itself passed to the template as a pointer to a (unspecified) function: 

    template<typename Fun, typename ArgType>
    void caller(Fun fun, ArgType &&arg)
    {
        fun(std::forward<ArgType>(arg));
    }
A function display(ostream &out) and increment(int &x) may now both be called through caller. Example: 
    caller(display, cout);
    int x = 0;
    caller(increment, x);

21.5.3: The unpack operator (C++0x)

The unpack operator is used to obtain template arguments in many situations. No mechanism other than recursion (as shown in section 21.5.1) is available to obtain the individual types and values of a variadic template.

The unpack operator can also be used to define template classes that are derived from any number of base classes. Here is how it's done: 

    template <typename... BaseClasses>
    class Combi: public BaseClasses ...         // derive from base classes
    {
        public:
                                                // specify base class objects
                                                // to its constructor using
                                                // perfect forwarding
            Combi(BaseClasses && ... baseClasses)
            :
                BaseClasses(baseClasses) ...    // use base class initializers
            {}                                  // for each of the base
    };                                          // classes
This allows us to define classes that combine the features of any number of other classes. If the class Combi is derived of classes A, B, and C then Combi is-a A, B, and C. It should of course be given a virtual destructor. A Combi object can be passed to functions expecting pointers or references to any of its base class type objects. Here is an example defining Combi as a class derived from a vector of complex numbers, a string and a pair of ints and doubles (using uniform intializers in a sequence matching the sequence of the types specified for the used Combi type): 
    typedef Combi<vector<double>>, string, pair<int, double>> MultiTypes;
    MultiTypes mt = {{3.5, 4}, "mt", {1950, 1.72}};

The same construction can also be used to define template data members that support variadic type lists such as tuples (cf. section ref TUPLES). Such a class could be designed along these lines: 

    template <typename ... Types>
    struct Multi
    {
        std::tuple<Types ...> d_tup;        // define tuple for Types types

        Multi(Types ... types)
        :                                   // initialize d_tup from Multi's
            d_tup(std::forward<Types>(types) ...)   //             arguments
        {}
    };

The ellipses that are used when forwarding parameter packs are essential. The compiler considers their omission an error. In the following struct definition it was the intent of the programmer to pass a parameter pack on to a nested object construction but ellipses were omitted while specifying the template parameters, resulting in a parameter packs not expanded with `...' error message: 

    template <int size, typename ... List>
    struct Call
    {
        Call(List && ... list)
        {
            Call<size - 1, List &&> call(std::forward<List>(list) ...);
        }
    };
Instead of the above definition of the call object the programmer should have used: 
    Call<size - 1, List && ...> call(std::forward<List>(list) ...);

21.5.4: Computing the return type of function objects (C++0x)

As amply illustrated in chapter 19 function objects play an important role with generic algorithms. Like generic algorithms themselves, function objects can be generically defined as members of class templates. When the function call operator (operator()) of such classes themselves have arguments then the types of those arguments may also be abstracted by defining the function call operator itself as a member template. Example: 
    template <typename Class>
    class Filter
    {
        Class obj;
        public:
            template <typename Param>
            Param operator()(Param const &param) const
            {
                return obj(param);
            }
    };
The template class Filter is a wrapper around Class, filtering Class's function call operator through its own function call operator. In the above example the return value of Class's function call operator is simply passed on, but any other manipulation is of course also possible.

A type that is specified as Filter's template type argument may of course have multiple function call operators: 

    struct Math
    {
        int operator()(int x);
        double operator()(double x);
    };
Math objects can now be filtered using Filter<Math> fm using Math's first or second function call operator, depending on the actual argument type. With fm(5) the int-version is used, with fm(12.5) the double-version is used.

Unfortunately this scheme doesn't work if the function call operators have different return and argument types. Because of this the following class Convert cannot be used with Filter: 

    struct Convert
    {
        double operator()(int x);           // int-to-double
        std::string operator()(double x);   // double-to-string
    };
This problem can be tackled successfully by the class template std::result_of<Functor(Typelist)> that is defined by the C++0x standard. Before using std::result_of the header file <functional> must have been included.

The result_of class template offers a tyedef, type, representing the type that is returned by Functor<TypeList>. It can be used to improve Filter as follows: 

    template <typename Class>
    class Filter
    {
        Class obj;
        public:
            template <typename Arg>
                typename std::result_of<Class(Arg)>::type
                operator()(Arg const &arg) const
                {
                    return obj(arg);
                }
    };
Using this definition, Filter<Convert> fc can be constructed and fc(5) will return a double, while fc(4.5) returns a std::string.

The class Convert must define the relationships between its function call operators and their return types. Predefined function objects (like those in the standard template libary) already do so, but self-defined function objects must to this explicitly.

If a function object class defines only one function call operator it can define its return type by a typedef. If the above class Convert would only define the first of its two function call operators then the typedef (in the class's public section) should be: 

    typedef double type;

If multiple function call operators are defined, each with its own signature and return type, then the association between signature and return type is set up as follows (all in the class's public section):

21.5.5: Tuples (C++0x)

The C++0x standard offers a generalized pair container: the tuple, covered in this section. Before tuples can be used the header file <tuple> must have been included.

Whereas std::pair containers have limited functionality and only support two members, tuples have slightly more functionality and may contain an unlimited number of different data types. In that respect a tuple can be thought of the `template's answer to C's struct'.

A tuple's generic declaration (and definition) uses the variadic template notation: 

    template <class ...Types>
    class tuple;
Here is an example of its use: 
    typedef std::tuple<int, double &, std::string, char const *> tuple_idsc;

    double pi = 3.14;
    tuple_idsc idsc(59, pi, "hello", "fixed");

    // access a field:
    std::get<2>(idsc) = "hello world";
The std::get<idx>(tupleObject) function template returns a reference to the idx+sup(th) field of the tuple tupleObject. Index 0 returns a reference to its first value. The index is specified as the function template's non-type template argument.

Tuples may be constructed without specifying initial values. Primitive types are initialized to zeroes; class type fields are initialized by their default constructors. Be aware that in some situations the construction of a tuple may succeed but its use may fail. Consider: 

    tuple<int &> empty;
    cout << get<0>(empty);
Here the tuple empty cannot be used as its int & field is an undefined reference. Empty's construction, however, succeeds.

Tuples may be assigned to each other if their type lists are identical; if supported by their constituent types copy constructors are available as well. Copy construction and assignment is also available if a right-hand type can be converted to its matching left-hand type or if the left-hand type can be constructed from the matching right-hand type. Tuples (matching in number and (convertible) types) can be compared using relational operators as long as their constituent types support comparisons. In this respect tuples are like pairs.

Tuples offer the following static elements (using compile-time initialization):

The unpack operator can also be used to forward the arguments of a constructor to a tuple data member. Consider a class Wrapper that is defined as a variadic template: 

    template <typename ... Params>
    class Wrapper
    {
        ...
        public:
            Wrapper(Params && ... params);
    };
This class may be given a tuple data member which should be initialized by the types and values that are used when initializing an object of the class Wrapper using perfect forwarding. Comparable to the way a class may inherit from its template types (cf. section 21.5.3) it may forward its types and constructor arguments to its tuple data member: 
    template <typename ... Params>
    class Wrapper
    {
        std::tuple<Params ...> d_tuple;     // same types as used for
                                            // Wrapper itself
        public:
            Wrapper(Params && ... params)
            :                               // initialize d_tuple with
                                            // Wrapper's arguments
                d_tuple(std::forward<Params>(params) ...)
            {}
    };

21.5.6: User-defined literals (C++0x, ?)

The C++0x standard offers extensible literals, also known as user defined literals. Standard C++ defines various kinds of literals, like numerical constants (with or without suffixes), character constants and string (textual) literals.

Under the C++0x standard a literal, e.g., 1013, can be looked at in two ways: as a raw literal in which the literal as ASCII string or series of characters is passed to a processing function or as a cooked literal in which case the compiler already performs some conversion.

To extend a literal either a processing function or a variadic function template must be defined. Both functions must start with an underscore and all user defined literals are suffixes.

Using Type to represent the resulting type of the literal a a (raw) literal can be declared using the following syntax (the initial underscore in _functionName is required): 

    Type operator "" _functionName(char const *text [, size_t len]);
Here, `, size_t len' is an optional parameter receiving text's length (as returned by C's strlen function)

The function _functionName is implemented by the software engineer and must return a value of type Type. Here is an example of the definition and use of an user defined literal _kmh returning a double: 

    double _kmh(char const *speed)
    {
        std::istringstream in(speed);
        double ret;
        in >> ret;
        return ret;
    }
    double operator "" _kmh(char const *speed);

    double value = "120"_kmh;

21.6: Template typedefs and `using' declarations (C++0x, ?)

The typedef keyword is frequently used to define `shorthand' notations for extensive type names. Consider the following example: 
    typedef
       std::map<std::shared_ptr<KeyType>, std::vector<std::set<std::string>>>
            MapKey_VectorStringSet;

    MapKey_VectorStringSet mapObject;
In situations like this the actual type of the key or the data stored in the map's vector might vary. Some may store string objects, other may store double values.

A class may be defined based on the above map allowing the specification of the final key and value types. Example: 

    template <typename DeepKey, typename DeepValue>
    class DeepMap: public std::map<std::shared_ptr<DeepKey>,
                            std::vector<std::set<DeepMap>>>
    {};
This increases the flexibility of the initially defined map as it is now possible to write 
    DeepMap<KeyType, std::string> mapObject;
The C++0x standard adds to this the possibility to pre-specify either of these template type parameters. To preset the key's type to std::string leaving the data type open for later specification the following template using declaration syntax is available: 
    template<typename DeepValue>
    using MapString_DeepValue = DeepMap<std::string, DeepValue>;

    MapString_DeepValue<size_t> specialMap;
The specialMap now uses shared_ptr<string> for its key and vector<set<size_t>> for its data type. A similar shorthand notation can be used to pre-specify the value type leaving the key type open for later specification.

In addition to the above template syntax the using keyword can also be used to separate a typedef name from a complex type definition. Consider constructing a typedef defining a pointer to a function expecting and returning a double. The traditional way to define such a type is as follows: 

    typedef double (*PFD)(double);
In addition the C++0x standard offers the following alternative syntax: 
    using PFD = double (*)(double);

21.7: Instantiating class templates

Class templates are instantiated when an object of a class template is defined. When a class template object is defined or declared its template parameters must explicitly be specified.

Template parameters are also specified when default template parameter values are specified albeit that in that case the compiler provides the defaults (cf. section 21.4 where double is used as the default type to use for the template's DataType parameter). The actual values or types of template parameters are never deduced from arguments as is done with function template parameters. So to define a Matrix of complex-valued elements, the following syntax is used: 

    Matrix<3, 5, std::complex> complexMatrix;
Since the class template Matrix uses a default data type a matrix of double-valued elements can be defined like this: 
    Matrix<3, 5> doubleMatrix;
A class template object may be declared using the keyword extern. For example, to declare the matrix complexMatrix use: 
    extern Matrix<3, 5, std::complex> complexMatrix;
A class template declaration suffices to compile return values or parameters that are of class template types. Example: the following source file may be compiled, although the compiler hasn't seen the definition of the Matrix class template. Generic classes and (partial) specializations may all be declared. A function expecting or returning a class template object, reference, or parameter automatically becomes a function template itself. 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 <cstddef>

    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 the compiler must first have seen their implementations. 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 or must have been seen when a class template object is defined. The compiler only instantiates those members that are actually used. This is illustrated by the following simple class Demo that has two constructors and two members. When we use one constructor and call one member in main note the sizes of the resulting object file and executable program. Next the class definition is modified in that the unused constructor and member are commented out. Again we compile and link the program. Now observe that these latter sizes are identical to the former sizes. There are other ways to illustrate that only used members are instantiated. The nm program could be used. It shows the symbolic contents of object files. Using nm we'll reach the same conclusion: only template member functions that are actually used are instantiated. Here is the class template Demo that was used for our 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 should be commented out before
    // compiling for the 2nd time:

    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();
    }

21.8: Processing class templates and instantiations

In section 20.11 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 not depending on template parameters is verified by the compiler when the template is defined. 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 qsort's function call. In practice this implies that the <cstdlib> header file must have been processed by the compiler before it is able to compile the class template definition.

On the other hand, if a template defines a <typename Ret> template type parameter to parameterize the return type of some template member function as in: 

    Ret member();
then the compiler may encounter member or the class to which member belongs in the following locations:

21.9: Declaring friends

Friend functions are normally constructed as support (free) functions of a class that cannot be implemented and declared as class members. The insertion operator for output streams is a well known example. Friend classes are most often seen in the context of nested classes. Here the inner class declares the outer class as its friend (or the other way around). 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 be used by any type of class (ordinary or template) when using class templates the following cases should be distinguished:

21.9.1: Non-function templates or classes as friends

A class template may declare a ordinary function, ordinary member function or 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 member function of a class can be declared as a friend, the compiler must have seen the class interface declaring that member. Let's consider the various possibilities:

21.9.2: Templates instantiated for specific types as friends

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

21.9.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. Functions, classes, and member functions may all be declared as unbound friends.

Here are the syntactic conventions declaring unbound friends:

21.10: Class template derivation

Class templates can be used for inheritance purposes as well. When a class template is used in class derivation, the following situations should be distinguished: These three variants of class template derivation are elaborated in this and the upcoming sections.

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 that 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 also possible. The base class may be instantiated by specifying template arguments, turning the derived class into an ordinary class (showing a class object's definition as well): 
    class Ordinary: public Base<int>
    {
        public:
            Ordinary(int x);
    };
    inline Ordinary::Ordinary(int x)
    :
        Base(x)
    {}

    Ordinary ordinary(5);
This approach allows us 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. Some subtleties that are specific for class template derivation may easily cause confusion like the use of this when members of a template base class are called from a derived class. The reasons for using this are discussed in section 22.1. In the upcoming sections the focus will be on the class derivation proper.

21.10.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 an 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 19.1.16), it requires the construction of a class and at least two additional function objects of that class. If this is considered too much overhead then extending a class template with tailor-made functionality might be considered.

Example: 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 by defining a member function process(string const &cmd) to do the actual command processing a 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 std::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:

21.10.2: Deriving class templates from class templates

Although it's perfectly acceptable to derive an 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 to extend an existing class template with new functionality or to override the functionality of the existing class template.

The class template SortVector presented below is derived from the existing class template std::vector. It allows us to perform a hierarchic sort of its elements using any ordering of any data members its data elements may contain. To accomplish this there is but one requirement. SortVector's data type must offer 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 used by a hierarchic sort, then MultiData should offer the following two members: 
    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 assumed that operator<< and operator>> have been defined for MultiData objects.

The class template SortVector is directly derived from the template class std::vector. Our implementation inherits all members from that base class. It also offers 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)
            {}

Its member hierarchicSort is the true raison d'être for the class. It defines the hierarchic sort criteria. It expects a pointer to a series of pointers to member functions of the class Type as well as a size_t representing the size of the array.

The array's first element indicates Type's most significant sort criterion, the array's last element indicates the class's least significant sort criterion. Since the stable_sort generic algorithm was designed explicitly to support hierarchic sorting, the member uses this generic algorithm to sort SortVector's elements. With hierarchic sorting, the least significant criterion should be sorted first. hierarchicSort's implementation is therefore easy. It requires a support class SortWith whose objects are initialized by the addresses of the member functions passed to the hierarchicSort() member: 

    template <typename Type>
    void SortVector<Type>::hierarchicSort(
                bool (Type::**arr)(Type const &rhv) const,
                size_t n)
    {
        while (n--)
            stable_sort(this->begin(), this->end(), SortWith<Type>(arr[n]));
    }

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

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

SortWith's constructor receives a pointer to a predicate function 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()) must return true if its first argument should eventually be placed ahead of its second argument: 

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

The following main function provides an illustration:

After compiling 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
    ====

21.10.3: Deriving class templates from ordinary classes

An ordinary 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. When objects of the class template are now instantiated only the actually used members of the derived class template must 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 below. We'll develop a class Table derived from an ordinary class TableType. The class Table displays elements of some type in a table having a configurable number of columns. The elements are either displayed horizontally (the first k elements occupy the first row) or vertically (the first r elements occupy a first column).

When displaying the table's elements they are inserted into a stream. The table is handled by 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) is implemented in Table, but the handling of the strings themselves 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 defines 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);
The fill-direction is specified as TableType::VERTICAL. It could also have been specified using Table, but since Table is a class template its specification would have been slightly 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 little 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 << '\n';
        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
    */

21.11: 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 by 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 stores pointers to Type values, rather than the values themselves. Of course, a destructor is now required as the (externally allocated) memory for the Type objects must eventually be freed. Alternatively, the allocation might be part of PtrVector's tasks, when it stores new elements. Here it is assumed that PtrVector's clients do the required allocations and that the destructor is implemented later on.

The nested class defines its constructor as a private member, and allows PtrVector<Type> objects access to 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, using a (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. Therefore iterator becomes an implicit typename. The compiler issues a warning if typename has been omitted. 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. PtrVector<Type>::begin's return type 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 returns a newly constructed PtrVector<Type>::iterator object. It may call the constructor since the class iterator declared its surrounding class as 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 << '\n';
    }

Nested enumerations and nested typedefs can also be defined by class templates. The class Table, mentioned before (section 21.10.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 21.10.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);

21.12: Constructing iterators

In section 18.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.

To ensure that an object of a class is interpreted as a particular type of iterator, the class must be derived from the class std::iterator. Before a class can be derived from this class the <iterator> header file must have been included.

In section 18.2 the characteristics of iterators were discussed. All iterators should support an increment operation, a dereference operation and a comparison for (in)equality.

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.

The 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 ([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 assignment operator and the copy constructor do not have to allocate any memory, their default implementations usually suffice. For the same reason iterators usually don't require destructors.

Most classes offering members returning iterators do so by having members construct the required iterators that are thereupon returned as objects by those member functions. As the caller of these member functions only has to use or sometimes copy the returned iterator objects, there is usually no need to provide any publicly available constructor, except for the copy constructor. Therefore these constructors are usually defined as private or protected members. To allow an outer class to create iterator objects, the iterator class usually declares 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 containers or pointers to pointers). Therefore it is difficult to construct a template iterator class which is suitable for a large variety of container classes.

In the following sections the available std::iterator class is used to construct an inner class representing a random access iterator. The reader may follow the approach illustrated there to construct iterator classes for other contexts. An example of such a template iterator class is provided in section 23.7.

The random access iterator developed in the next sections reaches data elements that are only accessible through pointers. The iterator class is designed as an inner class of a class derived from a vector of string pointers.

21.12.1: Implementing a `RandomAccessIterator'

In the chapter about containers (chapter 12) it was noted that containers own the information they contain. If they contain objects, then those objects are destroyed once the containers are destroyed. As pointers are not objects their use in containers is discouraged (STL's unique_ptr and shared_ptr type objects may be used, though). Although discouraged, we might be able to use pointer data types in specific contexts. In the following class StringPtr, an ordinary class is derived from the std::vector container that uses 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
This class needs a destructor: as the object stores string pointers, a destructor is required to destroy the strings once the StringPtr object itself is destroyed. Similarly, a copy constructor and overloaded assignment is required. Other members (in particular: constructors) are not explicitly declared here as they are not relevant to this section's topic.

Assume that we want to be able to use the sort generic algorithm with StringPtr objects. This algorithm (see section 19.1.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, we may define 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
    }
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. 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.

To derive a class from std::iterator, both the iterator type and the data type the iterator points to must be specified. Caveat: our iterator will take care of the string * dereferencing; so the required data type will be std::string, and not std::string *. The class iterator therefore 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;
In practical situations, if the type (Iterator) is used only once or twice, the type definition only adds clutter to the interface, and is better not used.

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

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++();
            iterator &operator++(int);
            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();
};

First we 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.

21.12.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, that nicely implements 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;
Also, 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 the value returned by the member end: the endpoint of the normal iterator range; the endpoint of the reversed iterator is obtained by providing reverse_iterator's constructor with the value returned by the member begin: the begin point of the normal iterator range.

The following small 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 << '\n';
    }
    /*
            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.

Assume we would like to process all lines stored in vector<string> lines up to any trailing empty lines (or lines only containing blanks) it might contain. How should 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'd better 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 not very difficult, as an iterator may be initialized from a pointer. Although the reverse iterator rit is not a pointer, &*(rit - 1) or &*--rit is. So we 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 and 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 with which we can initialize the iterator.