Movatterモバイル変換

• Table of Contents
• Previous Chapter
• Next Chapter

Chapter 22: Class Templates

In this chapter constructing and using class templates is discussed. In asense, class templates compete with object oriented programming (cf. chapter14), that uses a mechanism resembling that oftemplates. Polymorphism allows the programmer to postpone the implementationof algorithms by deriving classes from base classes in which algorithms areonly partially implemented. The actual definition and processing of the dataupon which the algorithms operate may be postponed until derived classes aredefined. Likewise, templates allow the programmer to postpone thespecification of the data upon which the algorithms operate. This is mostclearly seen with abstract containers, which completely specify the algorithmsand at the same time leave the data type on which the algorithms operatecompletely unspecified.

There exists an intriguing correspondence between the kind of polymorphismwe've encountered in chapter14 and certain uses of classtemplates. In their bookC++ Coding Standards (Addison-Wesley, 2005) Sutter and Alexandrescu refer tostatic polymorphism anddynamic polymorphism.Dynamic polymorphism is what we use when overriding virtual members.Usingvtables the function that is actually called depends on the type ofobject a (base) class pointer points at.Static polymorphism isencountered in the context of templates, and is discussed and compared todynamic polymorphism in section22.12.

Generally, class templates are easier to use than polymorphism. It iscertainly easier to writestack<int> istack to create a stack ofintsthan to derive a new classIstack: public stack and to implement allnecessary member functions defining a similar stack ofints using objectoriented programming. On the other hand, for each different type for which anobject of a class template is defined another, possibly complete class must bereinstantiated. This is not required in the context of object orientedprogramming where derived classesuse, rather thancopy, the functionsthat are already available in their base classes (but see also section22.11).

Previously we've already used class templates. Objects likevector<int> viandvector<string> vs are commonly used. The data types for which thesetemplates are defined and instantiated are an inherent part of such containertypes. It is stressed that it is thecombination of a class template typeand its template parameter(s), rather than the mere class template's typethat defines or generates a type. Sovector<int> is a type as isvector<string>. Such types could very well be specified throughusing-declarations:

    using IntVector =  std::vector<int>;    using StringVector = std::vector<std::string>;    IntVector vi;    StringVector vs;

Like function templates, class templates, both the class interface and theimplementations of the class member functions, must be available at theirpoints of instantiation. Therefore the interfaces and implementations of classtemplates are commonly provided in a header file, which is then included bysource files using those classes (see also section21.13).

22.0.1: Template Argument Deduction

So, in case we have a

    template <typename T>    void fun(T const &param);

we can do

    vector<int> vi;    fun(vi)

and the compiler deducesT == vector<int>.

On the other hand, if we have

    template <typename T>    struct Fun    {        T d_data;        Fun();    };

we cannot do

    Fun fun;

sinceFun is not a type, and the compiler cannot deduce what the intendedtype is.

Sometimes the compilercan deduce the intended types. Consider this:

    vector vi{ 1, 2, 3, 4 };

In this case the compiler deducesint from the provided values. Thecompiler is smart enought to select the most general type, as in this example,wheredouble is deduced:

    vector vi{ 1, 2.5 };

The compiler is doing its utmost to deduce types when they're notexplicitly specified, and it will stay on the safe side. So the vector is avector<int> in the first example and avector<double> in the second.

Although it's nice that the compiler is willing and able to deduce types inmany situations it's at the same time a potential source of confusion. In thefirst example only non-negative values are used, so why not define avector<unsigned> or avector<size_t>? In the second example thecompiler deducesvector<double>, butvector<float> could very wellalso have been used.

To avoid confusion, as arule of thumb, it might be a good idea to specifythe types of class templates when defining class type objects. It requireshardly any effort and it completely clarifies what you want and mean. Soprefer

    vector<int>     vi{ 1, 2, 3 };    vector<double>  vd{ 1, 2.5 };

over the definitions implicitly using types.

22.0.1.1: Simple Definitions

Starting point:

    template <class ...Types>           // any set of types    class Deduce    {        public:            Deduce(Types ...params);    // constructors            void fun();                 // a member function    };

Some definitions:

                                    // deduce:     full definition:                                    // --------------------------------    Deduce first{1};                // 1: int   -> Deduce<int> first{1}     Deduce second;                  // no Types -> Deduce<> second;      Deduce &&ref = Deduce<int>{ 1 };// int      -> Deduce<int> &&ref    template <class Type>    Deduce third{ static_cast<Type *>(0) };

The templatethird is a recipe for constructingDeduceobjects from a type that's specified forthird. The pointer's type simply is a pointer to the specified type (so, specifyingthird<int> implies anint *). Now that the type ofthird's argument is available (i.e., anint *) the compiler deduces thatthird{0} is aDeduce<int *>.

ThisDeduce<int *> object could, e.g., be used to initialize a namedDeduce<int *> object:

    auto x = third<int>;        // x's full definition: Deduce<int *> x{0}

Deduce's member functions can be used by anonymous and named objects:

    x.fun();                    // OK: fun called by named object    third<int>.fun();           // OK: fun called by anonymous object

Here are some examples that won't compile:

    extern Deduce object;       // not an object definition    Deduce *pointer = 0;        // any set of types could be intended    Deduce function();          // same.

When defining objects, either using function-type or curly brace definitionstemplate argument deduction is realized as follows:

• First, a list of available constructors is formed. The list containsall available ordinary constructors and constructor templates (i.e,constructors defined as member templates);
• For each element of that list a parallel imaginary functionis formed by the compiler (forming function templates for constructortemplates, and ordinary functions for ordinary constructors);
• The return types of these imaginary functions are the class types ofthe constructors, using the template parameters of the original classtemplate. For example, for theDeduce::Deduce constructor the imaginaryfunction

      template <class ...Types>    Deduce<Types ...> imaginary(Types ...params);

  is formed.

• Next, ordinary argument deduction and overload resolution is appliedto the set of imaginary functions. If this results in a best match for one of these imaginary functions then that function's class type (orspecialization) will be used. Otherwise the program is ill-formed.

Let's apply this process to the classDeduce. The set of imaginaryfunctions matchingDeduce looks like this:

                                        // already encountered: matching    template <class ...Types>           // Deduce(Types ...params)    Deduce<Types ...> imaginary(Types ...params);                                        // the copy constructor: matching    template <class ...Types>           // Deduce(Deduce<Types ...> const &)    Deduce<Types ...> imaginary(Deduce<Types ...> const &other);                                                                            // the move constructor, matching    template <class ...Types>           // Deduce(Deduce<Types ...> &&)    Deduce<Types ...> imaginary(Deduce<Types ...> &&tmp);

For the constructionDeduce first{1} the first imaginary function winsthe overload contest, resulting in the template argument deductionint forclass ...Types, and henceDeduce<int> first{1} is defined.

Note that when a class template is nested under a class template, the nestedclass template's name depends on the outer class type. The outer class thenprovides the name qualifier for the inner class template. In such casestemplate argument deduction is used for the nested class, but (as it is notused for name qualifiers) is not used for the outer class. Here is an example:adding a nested class template toOuter:

    template <class OuterType>    class Outer    {        public:            template <class InnerType>            struct Inner            {                Inner(OuterType);                Inner(OuterType, InnerType);                template <typename ExtraType>                Inner(ExtraType, InnerType);            };    };    // defining:    Outer<int>::Inner inner{2.0, 1};

In this case, the compiler uses these imaginary functions:

    template <typename InnerType>    Outer<int>::Inner<InnerType>            // copy constructor        imaginary(Outer<int>::Inner<InnerType> const &);    template <typename InnerType>           Outer<int>::Inner<InnerType>            // move constructor        imaginary(Outer<int>::Inner<InnerType> &&);    template <typename InnerType>           // first declared constructor    Outer<int>::Inner<InnerType> imaginary(int);    template <typename InnerType>           // second declared constructor    Outer<int>::Inner<InnerType> imaginary(int, InnerType);    template <typename InnerType>           // third declared constructor    template <typename ExtraType>           Outer<int>::Inner<InnerType> imaginary(ExtraType, InnerType);

Template argument deduction for callingimaginary(2.0, 1) results indouble for its first argument andint for its second. Overloadresolution then favors the last imaginary function, and soExtraType:double andInnerType: int. Consequently,

    Outer<int>::Inner inner{ 2.0, 1 };

is defined as:

    Outer<int>::Inner<int> Inner{ 2.0, 1 };

22.0.1.2: Explicit Conversions

    template <class T>    struct Class    {        std::vector<T> d_data;        struct Iterator        {            using type = T;            bool operator!=(Iterator const &rhs);            Iterator operator++(int);            type const &operator*() const;            // ...         };            Class();        Class(T t);        Class(Iterator begin, Iterator end);            template <class Tp>        Class(Tp first, Tp second)        {}        Iterator begin();        Iterator end();    };

The implementation of theClass constructor expecting twoClass::Iterator arguments would probably be somewhat similar to thefollowing:

    template <class T>    Class<T>::Class(Iterator begin, Iterator end)    {        while (begin != end)            d_data.push_back(*begin++);    }

whered_data is some container storingT values. AClass object can now constructed from a pair ofClass::Iterators:

    Class<int> source;          ...    Class<int> dest{source.begin(), source.end()};

Here, the simple template argument deduction procedure fails to deduce theint template argument. This fails:

    Class dest{source.begin(), source.end()};

When attempting to instantiate aClass object by passing itClass::Iterators the compiler cannot directly deduce from the providedarguments that aClass<Class::Iterator::type> is to be used:typeisn't directly available. Compare this toClass's third constructor,where

    Class intObject{12};

allows the compiler to create an imaginary function

    template <class Type>    Class <Type> imaginary(Type param)

in which caseType clearly is anint, and so aClass<int>object is constructed.

When we try to do this forClass(Iterator, Iterator) we get

    template <class Iterator>    Class<???> imaginary(Iterator, Iterator);

and hereClass's template argument isn't directly related toIterator: the compiler cannot deduce its type and consequently compilationfails.

A similar argument applies to the fourth constructor, which receives twoTparguments, which are both independent fromClass's template type.

In cases like these simple type template argument deduction procedurefails. Still, not everything is lost:explicit conversions, defined asexplicitly specifieddeduction rules which are added (below) to theclass's interface can be used.

An explicitly specified deduction rule connects a class template constructorsignature to a class template type. It specifies the template arguments forthe class template object that is constructed using the constructor whosesignature is specified. The generic syntactical form of an explicitlyspecified deduction rule looks like this:

    class template constructor signature -> resulting class type ;

Let's apply this toClass(Iterator begin, Iterator end). Its signature is

    template <class Iterator>    Class(Iterator begin, Iterator end)

Requiring thatIterator defines a typenametype, we can now formulatea resulting class type:

    Class<typename Iterator::type>

Now we can combine both in an explicitly specified deduction rule (which isadded as a separate line belowClass's interface):

    template <class Iterator>    Class(Iterator begin, Iterator end) -> Class<typename Iterator::type>;

After adding this deduction rule toClass's interface the followingconstructor calls successfully compile:

    Class src{12};      // already OK    Class dest1{src.begin(), src.end()};                        // begin() and end() return Class<int>::Iterator                        // objects. Typename Class<int>::Iterator::type                        // is defined as int, so Class<int> dest1 is                        // defined.    struct Double       // used at the next construction    {        using type = double;        // ... members ...    };    Class dest2{Double{}, Double{}};                        // Here the struct Double defines                         // typename double type, so                        // Class<double> dest2 is defined.

Within classes the compiler uses (as before) the class itself when merelyreferring to the class name: when referring toClass in the classClass, the compiler considersClass to beClass<T>. So the headersof the declaration and definition ofClass's copy constructor look likethis:

    Class(Class const &other);      // declaration    template <class T>              // definition    Class<T>::Class(Class const &other)    {         // ...     }

Sometimes the default type is not what you want, in which case the requiredtype must explicitly be specified. Consider what happens if add amemberdup toClass:

    template <typename T>    template <typename Tp>    auto Class<T>::dup(Tp first, Tp second)    {        return Class{ first, second };  // probably not what you want    }                                   // (see the following text)

Here, because we're insideClass the compiler deduces thatClass<T> must be returned. But in the previous section we decided that,when initializingClass from iterators,Class<typename Tp::type>should be constructed and returned. To accomplish that, the required type isexplicitly specified:

    template <typename T>    template <typename Tp>    auto Class<T>::dup(Tp first, Tp second)    {                               // OK: explicitly specified Class tyoe.        return Class<typename Tp::type>{ first, second };    }

As shown in this example, simple (implicit) or explicit deduction rules do nothave to be used: theycan be used in many standard situations whereexplicitly specifying the class's template arguments appears to besuperfluous. Template argument deduction was added to the language to simplifyobject construction when using class templates. But in the end you don'thave to use these deduction rules: it's always still possible toexplicitly specify template arguments.

22.1: Defining class templates

The new class implements acircular queue. A circular queue has a fixednumber ofmax_size elements. New elements are inserted at its back andonly its head and tail elements can be accessed. Only the head element can beremoved from a circular queue. Oncen elements have been appended the nextelement is inserted again at the queue's (physical) first position. Thecircular queue allows insertions until it holdsmax_size elements. As longas a circular queue contains at least one element elements may be removed fromit. Trying to remove an element from an empty circular queue or to add anotherelement to a full circular queue results in exceptions being thrown. Inaddition to other constructors a circular queue must offer a constructorinitializing its objects formax_size elements. This constructor must makeavailable the memory for themax_size elements but must not call thoseelements default constructors (hinting at the use of the placementnewoperator). A circular queue should offer value semantics as well as a moveconstructor.

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

The actual construction of a class template is provided in the next section,where the class templateCirQue (circular queue) is developed.

22.1.1: Constructing the circular queue: CirQue

    template<typename Data>    class CirQue    {        // member declarations    };

A class template's definition starts like a function template'sdefinition:

• The keywordtemplate, starting a template definition ordeclaration.
• The angle bracket enclosed list followingtemplate: alist containing one or more comma-separated elements is called thetemplate parameter list. Template parameter lists may have multipleelements, like this:

      typename Type1, typename Type2, typename Type3

  When a class template defines multiple template type parameters they arematched in sequence with the list of template type arguments provided whendefining objects of such a class template. Example:

  template <typename Type1, typename Type2, typename Type3>class MultiTypes{    ...};MultiTypes<int, double, std::string> multiType;    // Type1 is int, Type2 is double, Type3 is std::string

• Inside the template parameter list we find theformal type name(Data forCirQue). It is a formal (type) name, like the formal typesused in function template parameter lists.
• Following the template header the class interface is defined. It mayuse the formal type names defined in the template header as type names.

    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 ofname of the class template and the data type for which it is instantiateddefines a data type. Also note the similarity between defining astd::vector (of some data type) and aCirQue (of some data type).

Likestd::map containers class templates may be defined with multipletemplate type parameters.

Back toCirQue. ACirQue must be capable of storingmax_sizeData elements. These elements are eventually stored in memory pointed atby a pointerData *d_data, initially pointing to raw memory. New elementsare added at the backside of theCirQue. A pointerData *d_back isused to point to the location where the next element is going to bestored. Likewise,Data *d_front points to the location of theCirQue'sfirst element. Twosize_t data members are used to monitor the fillingstate of theCirQue:d_size represents the number of elementscurrently stored in theCirQue,d_maxSize represents the maximumnumber of elements that theCirQue can contain. Thus, theCirQue'sdata members are:

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

22.1.2: Non-type parameters

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

Different from function template non-type parameters the values of classtemplate non-type parameters arenot deduced by the compiler usingarguments passed to class template members.

Assume we extend our design of the class templateCirQue so that itdefines a second (non-type) parametersize_t Size. Our intent is to usethisSize parameter in the constructor defining an array parameter ofSize elements of typeData.

TheCirQue class template now becomes (only showing the relevantconstructor):

    template <typename Data, size_t Size>    class CirQue    {        // ... data members        public:            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 oftemplate non-type parameters are not deduced by the compiler. When thecompiler is asked to compile the followingmain function it reports amismatch 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'    */

DefiningSize as a non-type parameter having a default value doesn'twork either. The compiler always uses the default unless its value isexplicitly specified. Reasoning thatSize can be 0 unless we need anothervalue, we might be tempted to specifysize_t Size = 0 in the template'sparameter type list. Doing so we create a mismatch between the defaultvalue 0 and the actual size of the arrayarr as defined in the abovemain 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 alwaysbe specified like type parameters when an object of that class isdefined. Default values can be specified for those non-type parameters causingthe compiler to use the default when the non-type parameter is leftunspecified.

Default template parameter values(either type or non-type template parameters) maynot be specified whendefining 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 classtemplate members, theyhave to be specified by the class interface.

Similar to non-type parameters of function templates default argumentvalues for non-type class template parameters may only be specified asconstants:

• Global variables have constant addresses, whichcan be used as arguments for non-type parameters.
• Local anddynamically allocated variables haveaddresses that arenot known by the compiler when the source file iscompiled. These addresses can thereforenot be used as arguments fornon-type parameters.
• Lvalue transformations are allowed: if apointer is defined as a non-type parameter, an array name may be specified.
• Qualificationconversions are allowed: a pointer to a non-const object may be used with anon-type parameter defined as aconst pointer.
• Promotions are allowed: a constant of a `narrower'data type may be used when specifying a default argument for a non-typeparameter of a `wider' type (e.g., ashort can be used when anint iscalled for, along when adouble is called for).
• Integral conversions are allowed: if asize_t parameter is specified, anint may be used as well.
• Variables cannot be used to specify template non-type parameters astheir values are not constant expressions. Variables defined using theconst modifier, however, may be used as their values never change.

Although our attempts to define a constructor of the classCirQueaccepting an array as its argument has failed so far, we're not yet out ofoptions. In the next section a method is described thatdoes allow usto reach our goal.

22.1.3: Member templates

In contrast, whenfunction templates are used, the actual templateparameters are deduced from the arguments used when calling the function. Thisopens up an alley leading to the solution of our problem. If the constructoritself is turned into a function template (having its own template header),then the compilerwill be able to deduce the non-type parameter's valueand there is no need anymore to specify it explicitly using a class templatenon-type parameter.

Members (functions or nested classes) of class templates that are themselvestemplates are calledmember templates.

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

When converting our earlierCirQue(Data const (&array)[Size]) constructorinto a member template the class template'sData type parameter can stillbe used, but we must provide the member template with a non-type parameter ofits own. Its declaration in the (partially shown) class interface looks likethis:

    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(sizeof(arr)))),        d_front(d_data),        d_back(d_data)    {        std::copy(arr, arr + Size, std::back_inserter(*this));    }

    using value_type = Data;    using const_reference = value_type const &;

Member templates have the following characteristics:

• Twotemplate headers must be used: the class template'stemplateheader is specified first followed by the member template's template header;
• Normal access rules apply: the member template can beused by programs to construct anCirQue object of a given datatype. As usual for class templates, the data type must be specified when theobject is constructed. To construct aCirQue object from the arrayint array[30] we define:

  CirQue<int> object(array);

• Any member can be defined as a member template, not just aconstructor;
• When a template member is implemented below its class interface, thetemplate class header must precede the function template header of the membertemplate;
• The implementation of the member template must specify its properscope. The member template is defined as a member of the classCirQue,instantiated for the formal template parameter typeData;
• The template parameter names in the declaration andimplementation must be identical;
• The member template should be defined inside its proper namespaceenvironment. The organization of files defining class templates within anamespace should therefore be:

  namespace SomeName{    template <typename Type, ...>   // class template definition    class ClassName    {        ...    };    template <typename Type, ...>   // non-inline member definition(s)    ClassName<Type, ...>::member(...)    {        ...    }}                                   // namespace closes

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

    CirQue<int> object{ array };

it is this latter constructor, rather than the member template, that thecompiler will use.

The compiler selects this latter constructor as it is a more specializedversion of a constructor of the classCirQue than the member template(cf. section21.14). Problems like these can be solved bydefining the constructorCirQue(Data const *data) into a member templateas well or by defining a constructor using two parameters, the secondparameter defining the number of elements to copy.

When using the former constructor (i.e., the member template) it must define atemplate type parameterData2. Here `Data' cannot be used as templateparameters of a member template may not shadow template parameters of itsclass. UsingData2 instead ofData takes care of this subtlety. Thefollowing declaration of the constructorCirQue(Data2 const *) couldappear inCirQue's 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 twoCirQue 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 *)    }

22.1.4: CirQue's constructors and member functions

The classCirQue offers various member functions. Normal designprinciples should be adhered to when constructing class templatemembers. Class template type parameters should preferably be defined asType const &, rather thanType, to prevent unnecessary copying oflarge data structures. Template class constructors should use memberinitializers rather than member assignment within the body of theconstructors. Member function definitions should preferably not be providedin-class but below the class interface. Since class template member functionsare function templates their definitions should be provided in the headerfile offering the class interface. Theymay be given theinlineattribute.

CirQue declares several constructors and (public) members (theirdefinitions are provided as well; all definitions are provided below the classinterface).

Here are the constructors and the destructor:

• explicit CirQue(size_t maxSize = 0):
  Constructor initializing aCirQue capable of storingmax_size Data elements. As theconstructor's parameter is given a default argument value this constructor canalso be used as a default constructor, allowing us to define, e.g., vectors ofCirQues. The constructor initializes theCirque object'sd_datamember to a block of raw memory andd_front andd_back are initializedtod_data. As class template member functions are themselves functiontemplates their implementations outside of the class template's interface muststart with the class template's template header. Here is the implementation oftheCirQue(size_t) constructor:

      template<typename Data>    CirQue<Data>::CirQue(size_t maxSize)    :        d_size(0),        d_maxSize(maxSize),        d_data(            maxSize == 0 ?                0            :                static_cast<Data *>(                            operator new(maxSize * sizeof(Data)))        ),        d_front(d_data),        d_back(d_data)    {}

• CirQue(CirQue<Data> const &other):
  The copy constructor has nospecial features. It uses a private support memberinc to incrementd_back (see below) and placement new to copy the other'sData elementsto the current object. The implementation of the copy constructor isstraightforward:

      template<typename Data>    CirQue<Data>::CirQue(CirQue<Data> const &other)    :        d_size(other.d_size),        d_maxSize(other.d_maxSize),        d_data(            d_maxSize == 0 ?                0            :                static_cast<Data *>(                    operator new(d_maxSize * sizeof(Data)))        ),        d_front(d_data + (other.d_front - other.d_data))    {        Data const *src = other.d_front;        d_back = d_front;        for (size_t count = 0; count != d_size; ++count)        {            new(d_back) Data(*src);            d_back = inc(d_back);            if (++src == other.d_data + d_maxSize)                src = other.d_data;        }    }

• CirQue(CirQue<Data> &&tmp):
  The move constructor merelyinitializes the current object'sd_data pointer to 0 and swaps (see thememberswap, below) the temporary object with the currentobject.CirQue's destructor inspectsd_data and immediatelyreturns when it's zero. Implementation:

      template<typename Data>    CirQue<Data>::CirQue(CirQue<Data> &&tmp)    :        d_data(0)    {        swap(tmp);    }

• CirQue(Data const (&arr)[Size]):
  This constructor is declaredas a member template, providing theSize non-type parameter. It allocatesroom forSize data elements and copiesarr's content to the newlyallocated memory.Implementation:

      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(sizeof(arr)))),        d_front(d_data),        d_back(d_data)    {        std::copy(arr, arr + Size, std::back_inserter(*this));    }

• CirQue(Data const *data, size_t size):
  This constructor actsvery much like the previous one, but is provided with a pointer to the firstData element and with asize_t providing the number of elements tocopy. In our current design the member template variant of this constructor isleft out of the design. As the implementation of this constructor is verysimilar to that of the previous constructor, it is left as an exercise to thereader.

• ~CirQue():
  The destructor inspects thed_data member. If it iszero then nothing has been allocated and the destructor immediatelyreturns. This may occur in two situations: the circular queue contains noelements or the information was grabbed from a temporary object by some moveoperation, setting the temporary'sd_data member to zero. Otherwised_size elements are destroyed by explicitly calling their destructorsfollowed by returning the element's raw memory to the commonpool. Implementation:

      template<typename Data>    CirQue<Data>::~CirQue()    {        if (d_data == 0)            return;        for (; d_size--; )        {            d_front->~Data();            d_front = inc(d_front);        }        operator delete(d_data);    }

Here areCirque's members:

• CirQue &operator=(CirQue<Data> const &other):
  The copy assignment operator has a standard implementation:

      template<typename Data>    CirQue<Data> &CirQue<Data>::operator=(CirQue<Data> const &rhs)    {        CirQue<Data> tmp(rhs);        swap(tmp);        return *this;    }

• CirQue &operator=(CirQue<Data> &&tmp):
  The move assignment operator also has a standard implementation. As its implementation merely callsswap it is defined as an inline function template:

      template<typename Data>    inline CirQue<Data> &CirQue<Data>::operator=(CirQue<Data> &&tmp)    {        swap(tmp);        return *this;    }

• void pop_front():
  removes the element pointed at byd_front from theCirQue. Throws an exception if theCirQue is empty. The exception is thrown as aCirQue<Data>::EMPTY value, defined by theenum CirQue<Data>::Exception (seepush_back). The implementation is straightforward (explicitly calling the destructor of the element that is removed):

      template<typename Data>    void CirQue<Data>::pop_front()    {        if (d_size == 0)            throw EMPTY;        d_front->~Data();        d_front = inc(d_front);        --d_size;    }

• void push_back(Data const &object):
  adds another element to theCirQue. Throws aCirQue<Data>::FULL exception if theCirQue is full. The exceptions that can be thrown by aCirQue are defined in itsException enum:

      enum Exception    {        EMPTY,        FULL    };

  A copy ofobject is installed in theCirQue's raw memory using placementnew and itsd_size is incremented.

      template<typename Data>    void CirQue<Data>::push_back(Data const &object)    {        if (d_size == d_maxSize)            throw FULL;        new (d_back) Data(object);        d_back = inc(d_back);        ++d_size;    }

• void swap(CirQue<Data> &other):
  swaps the currentCirQue object with anotherCirQue<Data> object;

      template<typename Data>    void CirQue<Data>::swap(CirQue<Data> &other)    {        static size_t const size = sizeof(CirQue<Data>);        char tmp[size];        memcpy(tmp, &other, size);        memcpy(reinterpret_cast<char *>(&other), this, size);        memcpy(reinterpret_cast<char *>(this), tmp, size);    }

• Data &back():
  returns a reference to the element pointed at byd_back (undefined result if theCirQue is empty):

      template<typename Data>    inline Data &CirQue<Data>::back()    {        return d_back == d_data ? d_data[d_maxSize - 1] : d_back[-1];    }

• Data &front():
  returns reference to the element pointed at byd_front (undefined result if theCirQue is empty);

      template<typename Data>    inline Data &CirQue<Data>::front()    {        return *d_front;    }

• bool empty() const:
  returnstrue if theCirQue is empty;

      template<typename Data>    inline bool CirQue<Data>::empty() const    {        return d_size == 0;    }

• bool full() const:
  returnstrue if theCirQue is full;

      template<typename Data>    inline bool CirQue<Data>::full() const    {        return d_size == d_maxSize;    }

• size_t size() const:
  returns the number of elements currently stored in theCirQue;

      template<typename Data>    inline size_t CirQue<Data>::size() const    {        return d_size;    }

• size_t maxSize() const:
  returns the maximum number of elements that can be stored in theCirQue;

      template<typename Data>    inline size_t CirQue<Data>::maxSize() const    {        return d_maxSize;    }

Finally, the class has one private member,inc, returning acyclically incremented pointer intoCirQue's raw memory:

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

22.1.5: Using CirQue objects

That characteristic of templates could be refined to the point where eachdefinition is stored in a separate function template definition file. In thatcase only the definitions of the function templates that are actually neededwould 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 todefine the remaining function templates immediately below the class template'sinterface (defining some functions inline).

Now that the classCirQue has been defined, it can be used. To use theclass its object must be instantiated for a particular data type. In thefollowing example it is initialized for data typestd::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);}

    2 1 2    3 3 5    2 4 5    5 1 9

22.1.6: Default class template parameters

When defining defaults keep in mind that they should be suitable for themajority of instantiations of the class. E.g., for the class templateCirQue the template's type parameter list could have been alteredby specifyingint as its default type:

    template <typename Data = int>

Even though default arguments can be specified, the compiler must still beinformed that object definitions refer to templates. When instantiating classtemplate objects using default template arguments the type specifications maybe omitted but the angle brackets must be retained. Assuming a defaulttype for theCirQue class, an object of that class may be definedas:

    CirQue<> intCirQue(10);

Default template arguments cannot be specified when defining templatemembers. So, the definition of, e.g., thepush_back member must alwaysbegin with the sametemplate specification:

    template <typename Data>

When a class template uses multiple template parameters, all may be givendefault values. Like default function arguments, once a default value is usedall remaining template parameters must also use their default values. Atemplate type specification list may not start with a comma, nor may itcontain multiple consecutive commas.

22.1.7: Declaring class templates

    template <typename Data>    class CirQue;

Default template arguments may alsobe specified when declaring class templates. However, default templatearguments cannot be specified for both the declaration and the definition of aclass template. As arule of thumb default template arguments should beomitted fromdeclarations, as class template declarations are never usedwhen instantiating objects but are only occasionally used as forwardreferences. Note that this differs from default parameter value specificationsfor member functions in ordinary classes. Such defaults are always specifiedwhen declaring the member functions in the class interface.

22.1.8: Preventing template instantiations

In other situations templates are instantiated when they are being used. Ifthis happens many times (i.e., in many different source files) then this mayslow down the compilation process considerably. Fortunately,C++ allowsprogrammers toprevent templates from being instantiated, using theextern template syntax. Example:

    extern template class std::vector<int>;

Having declared the class template it can be used in its translationunit. E.g., the following function properly compiles:

#include <vector>#include <iostream>using namespace std;extern template class vector<int>;void vectorUser(){    vector<int> vi;    cout << vi.size() << '\n';}

• The declaration by itself doesnot make the class definitionavailable. Thevector header filestill needs to be included to makethe features of the class vector known to the compiler. But due to theextern template declaration none of the used members will be instantiatedfor the current compilation unit;
• The compilerassumes (as it always does) that what is declaredhas been implemented elsewhere. In this case the compiler encounters animplicit declaration: the features of the vector class that are actuallyused by the above program are not individually declared but they are declaredas a group, using theextern template declaration. This not only holdstrue for explicitly used members but hidden members (copy constructors, moveconstructors, conversion operators, constructors called during promotions, toname a few): all are assumed by the compiler to have been instantiatedelsewhere;
• Although the above source filecompiles, theinstantiationsof the templates must be available before the linker can build the finalprogram. To accomplish this one or more source files may be constructed inwhich all required instantiations are made available.

  In a stand-alone program one might postpone defining the required membersand wait for the linker to complain about unresolved externalreferences. These may then be used to create a series of instantiationdeclarations which are then linked to the program to satisfy the linker. Nota very simple task, though, as the declarations must strictly match the waythe members are declared in the class interface. An easier approach is todefine aninstantiation sourcefile in which all facilities thatare used by the program are actually instantiated in a function that is nevercalled by the program. By adding thisinstantiation function to the sourcefile containingmain we can be sure that all required members areinstantiated as well. Here is an example of how this can be done:

  #include <vector>#include <iostream>extern void vectorUser();int main(){    vectorUser();}// this part is never called. It is added to make sure all required// features of declared templates will also be instantiated.namespace{    void instantiator()    {        std::vector<int> vi;        vi.size();    }}

• Last, but certainly not least: a fully matchinginstantiation declaration of a class template (e.g., forstd::vector<int>) looks like this:

  template class std::vector<int>;

  Adding this to a source file, however, will instantiate thefullclass, i.e., all its members are now instantiated. This may not what youwant, as it might needlessly inflate your final executable.

• On the other hand, if it is known that the required template membershave already been instantiated elsewhere, then anextern templatedeclaration can be used to prevent member instantiations in the currentcompilation unit, which may speed up compilation. E.g.,

          // the compiler assumes that required members of        // vector<int> have already been instantiated elsewhereextern template class std::vector<int>;int main(){    std::vector<int> vi(5);     // constructor and operator[]    ++vi[0];                    // are NOT instantiated}

22.1.9: Generic lambda expressions

     1: int main()     2: {     3:     auto lambda = [](auto lhs, auto rhs)     4:                 {     5:                     return lhs + rhs;     6:                 };     7:      8:     vector<int> values {1, 2, 3, 4, 5};     9:     vector<string> text {"a", "b", "c", "d", "e"};    10:     11:     cout <<    12:         accumulate(values.begin(), values.end(), 0, lambda) << '\n' <<    13:         accumulate(text.begin(), text.end(), string{}, lambda) << '\n';    14: }

Generic lambda expressions are in fact class templates. To illustrate: theabove example of a generic lambda expression could also have been implementedusing the following class template:

    struct Lambda    {        template <typename LHS, typename RHS>        auto operator()(LHS const &lhs, RHS const &rhs) const         {            return lhs + rhs;        }    };    auto lambda = Lambda{};

This identity implies that usingauto in the lambda expression'sparameter list obeys the rules of template argument deduction (cf. section21.4), which are somewhat different from the wayauto normallyoperates.

Another extension is the way generic lambda expressions capture outer scopevariables. Previously variables could only be captured by value or byreference. As a consequence an outer scope variable of a type that onlysupports move construction could not be passed by value to a lambdafunction. This restriction was dropped, allowing variables to be initializedfrom arbitrary expressions. This not only allows move-initialization ofvariables in the lambda introducer, but with generic lambdas variables mayalso be initialized if they do not have a correspondingly named variable inthe lambda expression's outer scope. In this case initializer expressions canbe used as follows:

    auto fun = [value = 1]                {                   return value;               };

This lambda function (of course) returns 1: the declared capture deducesthe type from the initializer expression as ifauto had been used.

To use move-initializationstd::move should be used. E.g., aunique_ptr only supports move-assignment. Here it is used to return one ofits values via a lambda function:

    std::unique_ptr<int> ptr(new int(10));    auto fun = [value = std::move(ptr)]                {                   return *value;               };

In generic lambda expressions the keywordauto indicates that the compilerdetermines which types to use when the lambda function is instantiated. Ageneric lambda expression thereforeis a class template, even though itdoesn't look like one. As an example, the following lambda expression definesa generic class template, which can be used as shown:

    char const *target = "hello";    auto lambda =                [target](auto const &str)       {           return str == target;       };           vector<string> vs{stringVectorFactory()};    find_if(vs.begin(), vs.end(), lambda);

This works fine, but if you definelambda this way then you should beprepared for complex error messages if the types of the derefenced iteratorsand lambda's (silently assumed)str type don't match.

Here is a little program illustrating how generic lambda expressions can beused in other generic lambda expressions: class templates could also have beenused. In lines 1 through 9 a generic lambda expressionaccumulate isdefined, defining a second paramater which is used as a function: its argumenttherefore should be usable as a function. A functor definitely is, an thesecond generic lambda expressionlambda, defined in lines 11 through 14provides it. In line 21accumulate andlambda are instantiated so thatthey operate on (a vector of)ints, in line 22 they are instantiated forprocessing (a vector of)strings:

     1: auto accumulate(auto const &container, auto function)     2: {     3:     auto accu = decltype(container[0]){};     4:      5:     for (auto &value: container)     6:         accu = function(accu, value);     7:      8:     return accu;     9: }    10:     11: auto lambda = [](auto lhs, auto rhs)    12:             {    13:                 return lhs + rhs;    14:             };    15:     16: int main()    17: {    18:     vector<int> values  = {1, 2, 3, 4, 5};    19:     vector<string> text = {"a", "b", "c", "d", "e"};    20:     21:     cout << accumulate(values,  lambda) << '\n' <<    22:             accumulate(text,    lambda) << '\n';    23: }

In some situations generic lambdas are a bit too generic, resulting in verboseimplementations which are not required by templates in general. Consider ageneric lambda that specifies anauto &it parameter, but in addition itshould specify a parametervalue of typeValueType that should bedefined byit's class. Such a parameter requires the use of adecltype(and maybe also the use ofstd::decay_t) to retrieveit's actualtype. Inside the lambda's body ausing declaration can be specified tomake the type available, but that again requires a verbose specification usingstd::decay_t anddecltype. Here is an example:

    auto generic =         [](auto &it,            typename std::decay_t<decltype(it)>::ValueType value)        {            using Type = std::decay_t<decltype(it)>;            typename Type::ValueType val2{ value };            Type::staticMember();        };

To avoid this kind of verbosity generic lambda functions can also be definedlike ordinary templates, in which case the template header immediately followsthe lambda-introducer. Using this alternative form the definition of thegeneric generic lambda simply and straightforwardly becomes:

    auto generic =         []<typename Type>(Type &it, typename Type::ValueType value)        {            typename Type::ValueType val2{ value };            Type::staticMember();        };

22.2: Static data members

    template <typename Type>    class TheClass    {        static int s_objectCounter;    };

There will beoneTheClass<Type>::objectCounter for each differentType specification. The following object definitions result in theinstantiation of just one single static variable, shared among the twoobjects:

    TheClass<int> theClassOne;    TheClass<int> theClassTwo;

Mentioning static members in interfaces does not mean these members areactually defined. They are onlydeclared and must bedefinedseparately. With static members of class templates this is no different. Thedefinitions of static members are usually provided immediately following (i.e., below) the templateclass interface. For example, the static members_objectCounter's definition, positioned just below its class interface,looks like this:

    template <typename Type>                    // definition, following    int TheClass<Type>::s_objectCounter = 0;    // the interface

Heres_objectCounter is anint and is thus independent of thetemplate type parameterType. Multiple instantiations ofs_objectCounter for identicalTypes cause no problem, as the linkerwill remove all but one instantiation from the final executable (cf. section21.5).

In list-like constructions, where a pointer to objects of the classitself is required, the template type parameterType must be used whendefining the static variable. Example:

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

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

22.2.1: Extended use of the keyword `typename'

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

When this code is processed by the compiler, it complains with an -atfirst 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 todeclare a pointer to a typeAmbiguous defined within the class templateType. But the compiler, confronted withType::Ambiguous may interpretthe statement in various ways. Clearly it cannot inspectType itselftrying to uncoverType's true nature asType is a templatetype. Because of thisType's actual definition isn't available yet.

The compiler is confronted with two possibilities: eitherType::Ambiguous is astatic member of the as yet mysterious templateType, or it is asubtype ofType. As the standardspecifies that the compiler must assume the former, the statement

    Type::Ambiguous *ptr;

is interpreted as amultiplication of the static memberType::Ambiguous and the (now undeclared) entityptr. The reason forthe error message should now be clear: in this contextptr is unknown.

To disambiguate code in which an identifier refers to a subtype of a template type parameter the keywordtypename must beused. 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 insidetemplate definitions as subtypes of template type parameters thetypenamekeywordmust be used to identify them as subtypes. Example: a classtemplateHandler defines atypename Container as its template typeparameter. It also defines a data member storing the iterator returned by thecontainer'sbegin member. In additionHandler offers a constructoraccepting any container supporting abegin member.Handler's classinterface 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 typenameContainer represents any container supportingiterators.
• The container presumably supports a memberbegin. Theinitializationd_it(container.begin()) clearly depends on thetemplate's type parameter, so it's only checked for basic syntacticcorrectness.
• Likewise, the container presumably supports asubtypeconst_iterator, defined in the classContainer.

    #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 classHandler causes a problem. It is interpreted by thecompiler as astatic member instead of a subtype. The problem issolved usingtypename:

    template <typename Container>    class Handler    {        typename Container::const_iterator d_it;        ...    };

An interesting illustration that the compiler indeed assumesX::a tobe a membera of the classX is provided by the error message we getwhen we try to compilemain using the following implementation ofHandler'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 thebeginning of this section doesn't return aType value, but aType::Ambiguous value. Again, a subtype of a template type is referred to,andtypename must be used:

    template <typename Type>    typename Type::Ambiguous function(Type t)    {        return t.ambiguous();    }

Typenames can be embedded in using declarations. As is often the case,thisreduces the complexities of declarations and definitions appearingelsewhere. In the next example the typeIterator is defined as a subtypeof the template typeContainer.Iterator may now be used withoutrequiring the use of the keywordtypename:

    template <typename Container>    class Handler    {        using Iterator = Container::const_iterator;        Iterator d_it;        ...    };

22.3: Specializing class templates for deviating types

The specialization considered here is a true specialization in that thedata members and representation used by the specialization greatly differ fromthe originalCirQue class template. Therefore all members defined by theorginal class template must be modified to fit the specialization's dataorganization.

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

A template specialization is recognizedby the template argument list following a function or class template'sname andnot by an empty template parameter list. Class templatespecializations may have non-empty template parameter lists. If so, apartial class template specialization is defined.

A completely specialized class has the following characteristics:

• The class template specialization must be provided after the genericclass template definition. As it is a specialization the compilermust first have seen the original class template;
• The completely specialized class template's template parameter listis empty;
• All of the class's template parameters are given explicit type namesor (for the non-type parameters) explicit values. These explicitations areprovided in a template parameter specification list (surrounded by anglebrackets) that is inserted immediately after the specialized template's classname;
• All members of the specialized class template use specialized typesand values where original template parameters are used in the originaltemplate definition;
• All original template's members (maybe with the exception of someconstructors)should be redefined by the specialization. If a member isleft out of the specialization, it cannot be used for a specialized classtemplate object;
• The specialization may define additional members (but maybe shouldn'tas it breaks the one-to-one correspondence between the original andspecialized class template);
• Member functions of specialized class templates may be declared bythe specializing class and implemented below their class interface. If theirimplementations follow the class interface they maynot begin with atemplate <> header, but must immediately start with the member function'sheader.

22.3.1: Example of a class specialization

#ifndef INCLUDED_CIRQUEVECTOR_H_#define INCLUDED_CIRQUEVECTOR_H_#include <vector>#include "cirque.h"template<>class CirQue<std::vector<int>>{    using IntVect =  std::vector<int>;    IntVect d_data;    size_t d_size;    using iterator = IntVect::iterator;    iterator d_front;    iterator d_back;    public:        using value_type = int;        using const_reference = value_type const &;        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(reinterpret_cast<char *>(&other), this, sizeof(CirQue<IntVect>));    memcpy(reinterpret_cast<char *>(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

The next example shows how to use the specializedCirQue 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';}/*    Displays:        5 1 5        3 3 5        4 3 6*/

22.4: Partial specializations

Function templates cannot be partially specialized: there is no need for that, as a `partially specialized function template' merely is a functiontemplate that is tailored to particular types of some of its parameters. Sincefunction templates can be overloaded, `partially specializing' a functiontemplate simply means that overloads have to be defined for those specializedparameter types.

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

To start our discussion with an example of the latter use of a partial classtemplate specialization consider the classCirQue<vector<int>>developed in the previous section. When designingCirQue<vector<int>>you may have asked yourself how many specializations you'd have toimplement. One forvector<int>, one forvector<string>, one forvector<double>? As long as the data types handled by thevector usedby the classCirQue<vector<...>> behaves like anint (i.e., is avalue-type of class) the answer is: zero. Instead of defining fullspecializations for each new data type the data type itself can beparameterized, resulting in a partial specialization:

    template <typename Data>    class CirQue<std::vector<Data>>    {        ...    };

The above class is a specialization as a template argument list isappended to theCirQue class name. But as the class template itself has anon-empty template parameter list it is in fact recognized as a partialspecialization. There is one characteristic that distinguishes theimplementation (subsequent to the class template's interface) of a classtemplate member function of a partial specialization from the implementationof a member function of a full specialization. Implementations of partiallyspecialized class template member functions receive a template header. Notemplate headers are used when implementing fully specialized class templatemembers.

Implementing the partial specialization forCirQue is not difficult and isleft as an exercise for the reader (hints: simply changeint intoDatain theCirQue<vector<int>> specialization of the previous section).Remember to prefix the typeiterator bytypename (as inusingiterator = DataVect::iterator) (as discussed in section22.2.1).

In the next subsections we'll concentrate on specializing class templatenon-type template parameters. These partial specializations are nowillustrated using some simple concepts defined in matrix algebra, a branch oflinear algebra.

22.4.1: Intermezzo: some simple matrix algebraic concepts

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 plaindouble values, but they could also be complexnumbers, for which our complex container (cf. section12.4) mightprove useful. Our class template is therefore provided with aDataTypetemplate type parameter. It is specified when amatrix is constructed. Some simple matrices usingdouble 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)

Various operations are defined on matrices. They may, for example beadded, subtracted or multiplied. Here we will not focus on theseoperations. Rather, we concentrate on some simple operations: computingmarginals and sums.

Marginals are the sums of row elements or the sums of column elements of amatrix. These two kinds of marginals are also known as, respectively,row marginals andcolumn marginals.

• Row marginals are obtained by adding, for each row,all the row's elements and putting these (Rows) sums in correspondingelements of a (column) vector ofRows elements.
• Column marginals areobtained by adding, for each column, all the column's elements and puttingthese (Columns) sums in corresponding elements of a (row) vector ofColumns elements.
• The sum of all elements of a matrix can of course be computed as thesum of the elements of one of its marginals.

    -------------------------------------                                row                matrix          marginals                ---------                1   2   3        6                4   5   6       15                ---------    column      5   7   9       21  (sum)    marginals    -------------------------------------

22.4.2: The Matrix class template

Since matrices consist of well defined numbers of rows and columns (thedimensions of the matrix), that normally do not change when matrices areused, we might consider specifying their values as template non-typeparameters. TheDataType = double will be used in the majority ofcases. Therefore,double can be selected as the template's default typeargument. Since it's a sensible default, theDataType template typeparameter is used last in the template type parameter list.

Our template classMatrix begins its life as:

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

What do we want our class template to offer?

• It needs a place to store its matrix elements. This can be defined asan array of `Rows' rows each containing `Columns' elements of typeDataType. It can be an array, rather than a pointer, since the matrix'dimensions are knowna priori. Since a vector ofColumns elements (arow of the matrix), as well as a vector ofRow elements (acolumnof the matrix) is often used, the class could specify using-declarations torepresent them. The class interface's initial section thus contains:

          using MatrixRow = Matrix<1, Columns, DataType>;        using MatrixColumn = Matrix<Rows, 1, DataType>;        MatrixRow d_matrix[Rows];

• It should offer constructors: a default constructor and (e.g.,) aconstructor initializing the matrix from a stream. A copy or move constructoris not required as the class does not use pointers. Likewise, no overloadedassignment operator or destructor is required. Implementations:

      template <size_t Rows, size_t Columns, typename DataType>    Matrix<Rows, Columns, DataType>::Matrix()    {        std::fill(d_matrix, d_matrix + Rows, MatrixRow());    }    template <size_t Rows, size_t Columns, typename DataType>    Matrix<Rows, Columns, DataType>::Matrix(std::istream &str)    {        for (size_t row = 0; row < Rows; row++)            for (size_t col = 0; col < Columns; col++)                str >> d_matrix[row][col];    }

• The class'soperator[] member (and itsconst variant) onlyhandles the first index, returning a reference to a completeMatrixRow. How elements in aMatrixRow can be retrieved is shortlycovered. To keep the example simple, no array bound check has beenimplemented:

      template <size_t Rows, size_t Columns, typename DataType>    Matrix<1, Columns, DataType>    &Matrix<Rows, Columns, DataType>::operator[](size_t idx)    {        return d_matrix[idx];    }

• Now we get to the interesting parts: computing marginals and the sumof all elements in aMatrix. We'll define the typeMatrixColumn as thetype containing the row marginals of a matrix, and the typeMatrixRow asthe type containing the column marginals of a matrix.

  There is also the sum of all the elements of a matrix. This sum of all theelements of a matrix is a number that itself can be thought of as a1 x 1matrix.

  Marginals can be considered as special forms of matrices. To represent thesemarginals we can constructpartial specializations defining the classtemplatesMatrixRow andMatrixColumn objects; and we construct apartial specialization handling1 x 1 matrices. These partialspecializations are used to compute marginals and the sum of all the elementsof a matrix.

  Before concentrating on these partial specializations themselves we'll usethem here to implement the members computing the marginals and the sum of allelements of a matrix:

      template <size_t Rows, size_t Columns, typename DataType>    Matrix<1, Columns, DataType>    Matrix<Rows, Columns, DataType>::columnMarginals() const    {        return MatrixRow(*this);    }    template <size_t Rows, size_t Columns, typename DataType>    Matrix<Rows, 1, DataType>    Matrix<Rows, Columns, DataType>::rowMarginals() const    {        return MatrixColumn(*this);    }    template <size_t Rows, size_t Columns, typename DataType>    DataType Matrix<Rows, Columns, DataType>::sum()  const    {        return rowMarginals().sum();    }

22.4.3: The MatrixRow partial specialization

• The partial specialization starts with a template header defining alltemplate parameters that arenot specialized in the partialspecialization. This template header cannot specify any defaults (likeDataType = double) since defaults were already specified by the genericclass template definition. The specializationmust follow the definitionof the generic class template's definition, or the compiler complains that itdoesn't know what class is being specialized. Following the template header,the class's interface starts. It's a class template (partial) specializationso the class name must be followed by a template argument list specifying thetemplate arguments used by the partial specialization. The arguments specifyexplicit types or values for some of the template's parameters. Remainingtypes are simply copied from the class template partial specialization'stemplate parameter list. E.g., theMatrixRow specialization specifies 1for the generic class template'sRows non-type parameter (as we're talkinghere about a single row). BothColumns andDataType remain to bespecified. TheMatrixRow partial specialization therefore starts asfollows:

      template <size_t Columns, typename DataType>  // no default allowed    class Matrix<1, Columns, DataType>

• AMatrixRow holds the data of a single row. So it needs adata member storingColumns values of typeDataType. SinceColumnsis a constant value, thed_row data member can be defined as an array:

          DataType d_column[Columns];

• The class template partial specialization's constructors require someattention. The default constructor is simple. It merely initializes theMatrixRow's data elements usingDataType's default constructor:

      template <size_t Columns, typename DataType>    Matrix<1, Columns, DataType>::Matrix()    {        std::fill(d_column, d_column + Columns, DataType());    }

  Another constructor is needed initializing aMatrixRow objectwith the column marginals of a genericMatrix object. This requires us toprovide the constructor with a non-specializedMatrix parameter.

  Therule of thumb here is to define a member template that allows us tokeep the general nature of the parameter. The genericMatrixtemplate requires three template parameters. Two of these were alreadyprovided by the template specialization. The third parameter is mentioned inthe member template's template header. Since this parameter refers to thenumber of rows of the generic matrix it is simply calledRows.

  Here then is the implementation of the second constructor, initializing theMatrixRow's data with the column marginals of a genericMatrix object:

      template <size_t Columns, typename DataType>    template <size_t Rows>    Matrix<1, Columns, DataType>::Matrix(                            Matrix<Rows, Columns, DataType> const &matrix)    {        std::fill(d_column, d_column + Columns, DataType());        for (size_t col = 0; col < Columns; col++)            for (size_t row = 0; row < Rows; row++)                d_column[col] += matrix[row][col];    }

  The constructor's parameter is a reference to aMatrix template usingthe additionalRow template parameter as well as the template parametersof the partial specialization.
• We don't really require additional members to satisfy our currentneeds. To access the data elements of theMatrixRow an overloadedoperator[]() is of course useful. Again, theconst variant can beimplemented like the non-const variant. Here is its implementation:

      template <size_t Columns, typename DataType>    DataType &Matrix<1, Columns, DataType>::operator[](size_t idx)    {        return d_column[idx];    }

    Matrix<4, 6> matrix;        // generic Matrix template is used    Matrix<1, 6> row;           // partial specialization is used

22.4.4: The MatrixColumn partial specialization

• The class template partial specialization once again starts with atemplate header. Now the class interface specifies a fixed value for thesecond template parameter of the generic class template. This illustrates thatwe can construct partial specializations for every single template parameter;not just for the first or the last:

      template <size_t Rows, typename DataType>    class Matrix<Rows, 1, DataType>

• Its constructors are implemented completely analogously to the waytheMatrixRow constructors were implemented. Their implementations areleft as an exercise to the reader (and they can be found inmatrix.h).
• An additional membersum is defined to compute the sum of theelements of aMatrixColumn vector. It's simply implementedusing theaccumulate generic algorithm:

      template <size_t Rows, typename DataType>    DataType Matrix<Rows, 1, DataType>::sum()    {        return std::accumulate(d_row, d_row + Rows, DataType());    }

22.4.5: The 1x1 matrix: avoid ambiguity

    Matrix<1, 1> cell;

Is this aMatrixRow or aMatrixColumn specialization? The answeris: neither.

It's ambiguous, precisely becauseboth the columnsand the rows couldbe used with a (different) template partial specialization. If such aMatrix is actually required, yet another specialized template must bedesigned.

Since this template specialization can be useful to obtain the sum of theelements of aMatrix, it's covered here as well.

• This class template partial specialization also needs a templateheader, this time only specifyingDataType. The class definition specifiestwo fixed values: 1 for the number of rows and 1 for the number of columns:

      template <typename DataType>    class Matrix<1, 1, DataType>

• The specialization defines the usual batch of constructors.Constructors expecting a more genericMatrix type are again implemented asmember templates. For example:

      template <typename DataType>    template <size_t Rows, size_t Columns>    Matrix<1, 1, DataType>::Matrix(                            Matrix<Rows, Columns, DataType> const &matrix)    :        d_cell(matrix.rowMarginals().sum())    {}    template <typename DataType>    template <size_t Rows>    Matrix<1, 1, DataType>::Matrix(Matrix<Rows, 1, DataType> const &matrix)    :        d_cell(matrix.sum())    {}

• SinceMatrix<1, 1> is basically a wrapper around aDataTypevalue, we need members to access that latter value. A type conversionoperator might be useful, but we also defined aget member to obtainthe value if the conversion operator isn't used by the compiler (whichhappens when the compiler is given a choice, see section11.3). Here are the accessors (leaving out theirconstvariants):

      template <typename DataType>    Matrix<1, 1, DataType>::operator DataType &()    {        return d_cell;    }    template <typename DataType>    DataType &Matrix<1, 1, DataType>::get()    {        return d_cell;    }

Finally, themain function shown below illustrates how theMatrixclass 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';    }    /*        Generated output from input: 1 2 3 4 5 6        Column marginals:        9 12        Row marginals:        3        7        11        Sum total: 21    */

22.5: Variadic templates

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

Variadic templates were added to the language to prevent us from having todefine many overloaded templates and to be able to createtype safevariadic functions.

AlthoughC (andC++) supportvariadic functions, their use hasalways been deprecated inC++ as those functions are notoriouslytype-unsafe. Variadic function templates can be used to process objectsthat until now couldn't be processed properly byC-style variadicfunctions.

Template headers of variadic templates use the phrasetypename ...Params (Params being a formalname). A variadic class templateVariadic could be declared as follows:

    template<typename ...Params> class Variadic;

Assuming the class template's definition is available then this templatecan 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 also beempty. Example:

    class Variadic<> empty;

If this is considered undesirable using an empty template argument listcan be prevented by providing one or more fixed parameters. Example:

    template<typename First, typename ...Rest>    class tuple;

C's functionprintf is a well-known example of a type-unsafefunction. It is turned into a type-safe function when it is implemented as avariadic function template. Not only does this turn the function into atype-safe function but it is also automatically extended to accept any typethat can be defined byC++. Here is a possible declaration of a variadicfunction templateprintcpp:

    template<typename ...Params>    void printcpp(std::string const &strFormat, Params ...parameters);

Theellipsis (...) used in the declaration serves two purposes:

• In the template header it is written to theleft of a template parameter name where it declares aparameter pack. A parameter pack allows us to specify any number of template arguments when instantiating the template. Parameter packs can be used to bind type and non-type template arguments to template parameters.
• In a template implementation it appears to theright of the template pack's parameter name. In that case it represents a series of template arguments that are subsequently matched with a function parameter that in turn is provided to the right of the ellipsis. Here the ellipsis is known as theunpack operator as it `unpacks' a series of arguments in a function's argument list thereby implicitly defining its parameters.

    template<typename ...Params>    struct StructName    {        enum: size_t { s_size = sizeof ...(Params) };    };    // StructName<int, char>::s_size          -- initialized to 2

22.5.1: Defining and using variadic templates

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

• Theprintcpp function receives at least a formatstring. Following the format string any number of additional arguments may bespecified.
• If there are no arguments trailing the format string then there is noneed to use a function template. An overloaded (non-template) functionis defined to handle this situation.
• A variadic function template handles all remaining situations. Inthis case there is always at least one argument trailing the formatstring. That argument's type is matched with the variadic template function'sfirst (ordinary) template type parameterFirst. The types of any remainingarguments are bound to the template function's second template parameter,which is a parameter pack.
• The variadic function template processes the argument trailing theformat string. Then it recursively calls itself passing the format string andthe parameter pack to the recursive call
• If the recursive call merely receives the format string theoverloaded (non-template) function is called (cf. section21.14) ending the recursion. Otherwise the parameter pack'sfirst argument is matched with the recursive call'sFirst parameter. Asthis reduces the size of the recursive call's parameter pack the recursioneventually stops.

The overloaded non-template function prints the remainder of the formatstring,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::runtime_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...);   }

• At 1 the format string is searched for a parameter specification%. If none is found then the function is called with too many argumentsand it throws an exception;
• At 2 it verifies that it has not encountered%%. If only a single% has been seen thewhile-loop ends, the format string is insertedintocout up to the% followed byvalue, and the recursive callreceives the remaing part of the format string as well as the remainingparameter pack;
• If%% was seen the format string is inserted up to the second%, which is ignored, and processing of the format string continues beyondthe%%.

Different fromC'sprintf functionprintcpp only recognizes% and%% as format specifiers. The above implementation does notrecognize, e.g., field widths. Type specifiers like%c and%x are ofcourse not needed asostream's insertion operator is aware of the types ofthe arguments that are inserted into theostream. Extending the formatspecifiers so that field widths etc. are recognized by thisprintcppimplementation is left as an exercise to the reader. Here is an exampleshowing howprintcpp can be called:

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

22.5.2: Perfect forwarding

Assume the existence of a classInserter that is used to insertinformation into all kinds of objects. Such a class could have astringdata member into which information can be inserted.Inserter's interfaceonly partially has to copystring's interface to realize this: onlystring::insert's interfaces must be duplicated. The members duplicatinginterfaces often contain one statement (calling the appropriate memberfunction of the object's data member) and are for this reason oftenimplemented in-line. Suchwrapper functions merelyforward theirparameters to the matching member functions of the object's data member.

Another example is found infactory functions that also frequently forwardtheir parameters to the constructors of objects that they return.

C++ simplifies and generalizes forwarding of parameters byofferingperfect forwarding, implemented through rvalue references andvariadic templates. With perfect forwarding the arguments passed to functionsare `perfectly forwarded' to nested functions. Forwarding is calledperfect as the arguments are forwarded in a type-safe way. To use perfectforwarding nested functions must define parameter lists matching theforwarding parameters both in types and number.

Perfect forwarding is easily implemented:

• The forwarding function is defined as a template
  (usually avariadic template, but single argument forwarding is also possible. To define and forward a single argument omit the ellipsis from the following code);
• The forwarding function's parameter list is anrvalue reference parameter pack (e.g.,Params &&...params);
• std::forward is used to forward the forwarding function's arguments to the nested function, keeping track of their types and number. Beforeforward can be used the<utility> header file must be included.
• The nested function is called using this stanza to specify its arguments:
  std::forward<Params>(params)....

In the next example perfect forwarding is used to implementone memberInserter::insert that can be used to call any of the five overloadedstring::insert members. Theinsert function that's actually called nowsimply depends on the types and number of arguments that are passed toInserter::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 &&other);            template<typename ...Params>            void insert(Params &&...params)            {                d_str.insert(std::forward<Params>(params)...);            }    };

A factory function returning anInserter can also easily be implementedusing perfect forwarding. Rather than defining four overloaded factoryfunctions a single one now suffices. By providing the factory function with anadditional template type parameter specifying the class of the object toconstruct the factory function is turned into a completely general factoryfunction:

    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 functionstd::forward is provided by the standard library. Itperforms no magic, but merely returnsparams as a nameless object. Thatway it acts likestd::move that also removes the name from an object,returning it as a nameless object. The unpack operator has nothing to do withthe use offorward but merely tells the compiler to applyforward toeach of the arguments in turn. Thus it behaves similarly toC's ellipsisoperator used by variadic functions.

Perfect forwarding was introduced in section21.4.5: a templatefunction defining aType &&param, withType being a template typeparameter convertsType && toTp & if the function is called withan argument of typeTp &. Otherwise it bindsType toTp,withparam being defined asTp &&param. As a result anlvalueargument binds to an lvalue-type (Tp &), while anrvalue argumentbinds to an rvalue-type (Tp &&).

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

    typedef <type T>    T &&forward(T &&a)    {        return a;    }

SinceT && turns into an lvalue reference whenforward is calledwith an lvalue (or lvalue reference) and remains an rvalue reference ifforward is called with an rvalue reference, and sinceforward (likestd::move) anonymizes the variable passed as argument toforward, theargument value is forwarded while passing its type from the function'sparameter to the called function's argument.

This is calledperfect forwarding as the nested function can only becalled if the types of the arguments that were used when calling the `outer'function (e.g.,factory) exactly match the types of the parameters of thenested function (e.g.,Class's constructor). Perfect forwarding thereforeis a tool to realize type safety.

A cosmetic improvement toforward requires users offorward tospecify the type to use rather than to have the compiler deduce the type as aresult of the function template parameter type deduction's process. This isrealized by a small support struct template:

    template <typename T>    struct identity    {        using type = T;    };

This struct merely definesidentity::type asT, but as it is astruct it must be specified explicitly. It cannot be determined from thefunction's argument itself. The subtle modification to the aboveimplementation offorward thus becomes (cf. section22.2.1 foran explanation of the use oftypename):

    typedef <type T>    T &&forward(typename identity<T>::type &&arg)    {        return arg;    }

Nowforward must explicitly statearg's type, as in:

    std::forward<Params>(params)

Using thestd::forward function and the rvalue reference specificationis not restricted to the context of parameter packs. Because of the specialway rvalue references to template type parameters are treated (cf. section21.4.5) they can profitably be used to forward individual function parameters as well. Here is an example showing how an argument to a functioncan be forwarded from a template to a function that is itself passed to thetemplate as a pointer to an (unspecified) function:

    template<typename Fun, typename ArgType>    void caller(Fun fun, ArgType &&arg)    {        fun(std::forward<ArgType>(arg));    }

A functiondisplay(ostream &out) andincrement(int &x) may nowboth be called throughcaller. Example:

    caller(display, cout);    int x = 0;    caller(increment, x);

22.5.3: The unpack operator

The unpack operator can also be used to define template classes that arederived 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 numberof other classes. If the classCombi is derived of classesA, B, andC thenCombi is-anA, B, andC. It should of course be given avirtual destructor. ACombi object can be passed to functions expectingpointers or references to any of its base class type objects. Here is anexample definingCombi as a class derived from a vector of complexnumbers, a string and a pair of ints and doubles (using uniform intializers ina sequence matching the sequence of the types specified for the usedCombitype):

    using MultiTypes = Combi<        vector<complex<double>>, string, pair<int, double> >;    MultiTypes mt = { {3.5, 4}, "mt", {1950, 1.72} };

The same construction can also be used to define template data memberssupporting variadic type lists such astuples (cf. section22.6). 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 areessential. The compiler considers their omission an error. In the followingstruct definition it was the intent of the programmer to pass a parameterpack on to a nested object construction but ellipses were omitted whilespecifying the template parameters, resulting in aparameter 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 thecall object the programmershould have used:

    Call<size - 1, List &&...> call(std::forward<List>(list)...);

22.5.4: Non-type variadic templates

    template <int ...Ints>    int forwarder()    {        return computer<Ints ...>::result;  // forwarding the Ints    }    template <>     // specialization if no ints are provided    int forwarder<>()    {        return 0;    }    // use as:    cout << forwarder<1, 2, 3>() << ' ' << forwarder<>() << '\n';

Thesizeof operator can be used for variadic non-type parameters aswell:sizeof...(Ints) would return 3 when used in the first functiontemplate forforwarder<1, 2, 3>().

Variadic non-type parameters are used to define variadic literaloperators, introduced in section23.3.

22.5.5: Folding expressions

Sometimes the arguments must be combined using binary operators (likearg1+ arg2 + ...). In those cases afolding expression can be used insteadof combining the arguments using a traditional variadic template.

All binary operators (including the assignment, compound assignment and commaoperators) can be used in folding expressions.

• Aunary left fold is a fold expression that looks like this:

      (... op expr)

  whereop is the binary operator that is used in the fold expression,andexpr is an expression formulated in terms of the function parameterrepresenting the variadic arguments. Here is an example:

      template <typename ReturnType, typename ...Params>    ReturnType sum(Params ...params)    {        return (... + params);    }

  If a more elaborate expression than just the designator of the variadicarguments is used then the expression must be clearly demarcated, e.g., by surrounding it with parentheses:

      return (... + (2 * params));

  In a unary fold expression all the function's arguments matching the typesof the parameter pack are combined using specified operator. E.g.,

      sum<int>(1, 2, 3);

  returns 6.

• Aunary right fold is a fold expression that results in the sameexpression as its unary left fold alternative, but swaps the ellipses and theparams identifier:

      (expr op ...)

Together, unary left folds and unary right folds are calledunary folds.

• Abinary fold is a fold expression of the following form:

      (expr1 op ... op expr2)

  Here, eitherexpr1 is the identifier representing the variablearguments orexpr2 must be that identifier. The other one can be any othervalid expression (as with unary folds, both expressions must be clearlydemarcated). In addition, both operators must be identical.

If a binary operator has been overloaded, it will be used where applicable. Awell-known example is of courseoperator<< as defined forstd::ostreamobjects. A binary fold defined foroperator<< will not only do shifts, butcan also be used to insert a series of arguments intocout:

    template <class ...Pack>    ostream &out2(ostream &out, Pack &&...args)    {        return (out << ... << args);    };

Here is another interesting example: a fold expression for the comma operator:

    template <class ...Pack>    void call(Pack &&...args)    {        ... , args();    };

This unary fold calls each of its arguments in sequence. Arguments couldbe function addresses, function object or lambda functions. Note the use ofthe rvalue reference when defining the variadic parameter list which preventscopying of function objects that might be passed tocall. Assuming thatstruct Functor defines a functor, and thatvoid function() has beendefined, thencall could be called this way:

    Functor functor;    call(functor, function, functor,         []()        {            // ...            }    );

Finally: don't forget the parentheses surrounding fold expressions: they are required!

22.6: Tuples

Whereasstd::pair containers have limited functionality and only supporttwo members, tuples have slightly more functionality and may contain anunlimited number of different data types. In that respect a tuple can beconsidered the `template's answer toC's struct'.

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

    template <class ...Types>    class tuple;

Here is an example of its use:

    using tuple_idsc = std::tuple<int, double &, std::string, char const *>;    double pi = 3.14;    tuple_idsc idsc(59, pi, "hello", "fixed");    // access a field:    std::get<2>(idsc) = "hello world";

Thestd::get<idx>(tupleObject) function template returns areference to theidx^th (zero based) field of the tupletupleObject. The index is specified as the function template's non-typetemplate argument.

Type-based tuple addressing () can beused for tuple types used once in a tuple definition (if the same type is usedrepeatedly referring to that type introduces an ambiguity). The next exampleshows how to refer to the elements in the above example by type:

    get<int>(idsc)              // 59    get<double &>(idsc)         // 3.14    get<string>(idsc)           // "hello"s    get<char const *>(idsc)     // "fixed"

Tuples may be constructed without specifying initial values. Primitivetypes are initialized to zeroes; class type fields are initialized by theirdefault constructors. Be aware that in some situations the construction of atuple may succeed but its use may fail. Consider:

    tuple<int &> empty;    cout << get<0>(empty);

Here the tupleempty cannot be used as itsint & field is anundefined reference. However,empty's construction succeeds.

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

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

• std::tuple_size<Tuple>::value returns the number oftypes defined for the tuple typeTuple. Example:

  cout << tuple_size<tuple_idsc>::value << '\n';  // displays: 4

• std::tuple_element<idx, Tuple>::type returns the type of elementidx ofTuple. Example:

  tuple_element<2, tuple_idsc>::type text;  // defines std::string text

The unpack operator can also be used to forward the arguments of aconstructor to a tuple data member. Consider a classWrapper that isdefined 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 bythe types and values that are used when initializing an object of the classWrapper using perfectforwarding. Comparable to the way a class may inherit from its template types(cf. section22.5.3) it may forward its types and constructor argumentsto 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)...)            {}    };

22.6.1: Tuples and structured bindings

Structured bindings, however, can also be used in a much more generic way, byassociating them with tuples. By doing so structured bindings don't have to beassociated with data members, but they may hold values returned by classmembers.

The association between structured binding declarations and tuples is verystrong. In fact it is so strong that the standard explicitly allows users todefine tuple specializations, even though tuple specializations live in thestandard namespace, which otherwise is off-limits to programmers (except, ofcourse, when using its features).

In order to allow structured bindings to be associated with class membersthe following steps must be performed:

• The class must be provided with overloadedget member templates, usingint (or another integral type) specializations, where each specialization returns a class element (e.g., a member function).

  The availability ofif constexpr clauses makes it easy to combine all these specializations into a single member template.

  Alternatively, a function template defined outside of the class can be defined, which allows associating structured bindings with class members even if you're not the class's author. In this case the function defines aClassType [cv] &object parameter.

• A specialization ofstd::tuple_size<Type> is provided, definingstatic size_t const value as the number of index values that can be specified with theget<idx> function. Although defining entities in the standard namespace is normallyoff limits to ordinary programs, in this special case such specializations are allowed by theC++ standard.

• A specialization ofstd::tuple_element<idx, Type> is provided, definingtype as the type matching the return type ofget<idx>.

The flexibility that is achieved by being able to use structured bindings thisway is enormous. As long as a class offers members returning values thosemembers can be associated with structured binding variables. The memberfunctions don't even have to return values that are immediately available(e.g, as data members accessors) but their return values could also becomputed on the spot, by simply referring to the corresponding structuredbinding variable.

To illustrate the abovementioned steps for associating structured bindingswith class members we use these classes:

    class Euclid    {        size_t d_x;        size_t d_y;            public:            Euclid(size_t x = 0, size_t y = 0);            double distance() const;        // sqrt(d_x * d_x + d_y * d_y)    };    class Data    {        std::string d_text{ "hello from Data" };        Euclid d_euclid;            public:            void setXY(size_t x, size_t y);                Euclid factory() const;            double distance() const;            std::string const &text() const;    };

The first step towards allowing structured bindings forData consists ofdefining a (member) termplateget. IfData is our own class we canadd a member templateget. Alternatively, if we're only interested inaccessingData's public members we could derive a classDataGet fromData, and provide that class with theget member template. Yet anotherpossibility is to define a freeget function template. Thegetfunction must return whatever we're interested in. To make the appropriateselection we use an integral type (int, size_t, ...) selector value, andthe function template thus only has a non-type template parameter. Rather thandefining several specializations using theif constexpr clause is advised,as it greatly simplifies the function's definition.

Ourget function defines selector 0 forfactory, selector 1 fordistance and selector 2 fortext. Thedistance member simplyreturnsd_euclid.distance(), andEuclid::distance is run-timeevaluated using itsd_x andd_y values. Thus,distance is anexample of a function that will be run-time evaluated when we're referring,later on, to the third structured bindings variable.

Here's the definition of the member templateget:

    template <size_t Nr>    auto get() const    {        if constexpr (Nr == 0)            return factory();            if constexpr (Nr == 1)            return distance();            if constexpr (Nr == 2)            return text();            static_assert(Nr >= 0 and Nr < 3);    }

This function is still suboptimal. Consider its specialization for value 2: itreturnsData::text(). Asauto merely inspects the returned data type,get<2>() returns astd::string, rather than (text's) return type,which is astd::string const &. To use the return types that are actuallyreturned byData's member functions,get's return type should bedefined asdecltype(auto) rather than justauto:

    template <size_t Nr>    decltype(auto) get() const    ...

When definingget as a free function template it must be provided with aparameterData const &data (orData &data if members are used that maymodifydata's data members), returning the parameter's memberfunctions. E.g.,

        // get as a free function template:    template <size_t Nr>    decltype(auto) get(Data const &data)    {        if constexpr (Nr == 0)            return data.factory();            if constexpr (Nr == 1)            return data.distance();            ... // (etc)    }

Now that step 1 has been completed, we turn our attention to thestd::tuple specializations. These specializations are defined inside thestd namespace(usingnamespace std { ... } orstd::tuple...).

The specialization ofstd::tuple_size forData definesstatic size_t const value as the number of index valuesthat can be specified with theget<idx> function:

    template<>    struct std::tuple_size<Data>    {        static size_t const value = 3;    };

The specialization ofstd::tuple_element forData returns the typesmatching the various return types of theget member template. Itsimplementation also provides a nice example wheredeclval is used: thereturn type of theget<Nr> specialization must be determined. But toobtain that return type aData object is required, which isn't availableby just mentioningData intupe_element's specialization. However,declval<Data>() defines an rvalue reference, whichcan be passed toget<Nr>. But the function's returnvalue isn't required, so the objectdoesn't have to be constructed. Only its return type is needed. Hence, bysurrounding theget<Nr> call bydecltype no object is constructed, andmerely its return type is used:

    template<size_t Nr>    struct std::tuple_element<Nr, Data>    {        using type = decltype( declval<Data>().get<Nr>() );        // if get<Nr> is a free function use:        //           decltype( get<Nr>( declval<Data>() ) );        };

Astuple_size andtuple_element are directly associated with the classData their definitions should be provided inData's header file, belowData's class interface.

Here's how this could be used in amain function, showing single objectaccess and access using a range-based for-loop:

    int main()    {        Data data;        auto &[ ef, dist, txt ] = data;        // or maybe:        // auto &&[ ef, dist, txt ] = Data{};            cout << dist << ' ' << txt << '\n';            Data array[5];        for (auto &[ ef, dist, txt]: array)            cout << "for: " << dist << ' ' << txt << '\n';    }

22.7: Computing the return type of function objects

    template <typename Class>    class Filter    {        Class obj;        public:            template <typename Param>            Param operator()(Param const &param) const            {                return obj(param);            }    };

The template classFilter is a wrapper aroundClass, filteringClass's function call operator through its own function call operator. Inthe above example the return value ofClass's function call operator issimply passed on, but any other manipulation is of course also possible.

A type that is specified asFilter's template type argument may ofcourse have multiple function call operators:

    struct Math    {        int operator()(int x);        double operator()(double x);    };

Math objects can now be filtered usingFilter<Math> fm usingMath's first or second function call operator, depending on the actualargument type. Withfm(5) theint-version is used, withfm(12.5)thedouble-version is used.

However, this scheme doesn't work if the function call operators havedifferent return and argument types. Because of this the following classConvert cannot be used withFilter:

    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 templatestd::result_of<Functor(Typelist)>. Before usingstd::result_of theheader file<functional> must be included.

Theresult_of class template offers a using declaration (type),representing the type that is returned byFunctor<TypeList>. It can beused as follows to improve the implementation ofFilter:

    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. Nowfc(5) returns adouble, whilefc(4.5) returns astd::string.

The classConvert must define the relationships between its function calloperators and their return types. Predefined function objects (like those inthe standard template library) already do so, but self-defined functionobjects must do this explicitly.

If a function object class defines only one function call operator it canspecify its return type through a using-declaration. If the above classConvert would only define the first of its two function call operatorsthen the using declaration (in the class'spublic section) should be:

    using type = double;

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

• define a genericstruct result like this:

  template <typename Signature>struct result;

• For each function call signature define aspecialization ofstruct result.Convert's first function call operator gives rise to:

  template <typename Class>struct result<Class(int)>{    using type = double;};

  andConvert's second function call operator to:

  template <typename Class>struct result<Class(double)>{    using type = std::string;};

• In cases where function call operators have multiple arguments thespecifications should again provide for the correct signatures. A functioncall operator called with anint and adouble, returning asize_tgets:

  template <typename Class>struct result<Class(int, double)>{    using type = size_t;};

22.8: Instantiating class templates

Template parameters arealso specified when default template parametervalues are specified albeit that in that case the compiler provides thedefaults (cf. section22.4 wheredouble is used as the defaulttype to use for the template'sDataType parameter). The actual values ortypes of template parameters arenever deduced from arguments as is done with function templateparameters. So to define aMatrix of complex-valued elements, thefollowing syntax is used:

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

Since the class templateMatrix uses a default data typea matrix ofdouble-valued elements can be defined like this:

    Matrix<3, 5> doubleMatrix;

A class template object may bedeclared using the keywordextern. For example, todeclare the matrixcomplexMatrix use:

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

A class template declaration suffices to compile return values orparameters that are of class template types. Example: the following sourcefile may be compiled, although the compiler hasn't seen the definition of theMatrix class template. Generic classes and (partial) specializations mayall be declared. A function expecting or returning a class template object,reference, or parameter automatically becomes a function template itself. Thisis necessary to allow the compiler to tailor the function to the types ofvarious 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 areused the compiler must first have seen theirimplementations. So, template member functions must be known to the compilerwhen the template is instantiated. This does not mean thatall members ofa template class are instantiated or must have been seen when a class templateobject is defined. The compiler only instantiates those members that are actually used. Thisis illustrated by the following simple classDemo that has twoconstructors and two members. When we use one constructor and call one memberinmain note the sizes of the resulting object file and executableprogram. Next the class definition is modified in that the unused constructorand member are commented out. Again we compile and link the program. Nowobserve that these latter sizes are identical to the former sizes. There areother ways to illustrate that only used members are instantiated. Thenmprogram could be used. It shows the symbolic content of object files. Usingnm we'll reach the same conclusion:only template member functions thatare actually used are instantiated. Here is the class templateDemo thatwas used for our little experiment. Inmain only the first constructorand the first member function are called and thus only these members wereinstantiated:

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

22.9: Processing class templates and instantiations

Code not depending on template parameters is verified by the compiler whenthe template is defined. If a member function in a class template uses aqsort function, thenqsort does not depend on a templateparameter. Consequently,qsort must be known to the compiler when itencountersqsort's function call. In practice this implies that the<cstdlib> header file must have been read by the compiler before itis able to compile the class template definition.

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

    Ret member();

then the compiler may encountermember or the class to whichmember belongs in the following locations:

• the location where a class template object is defined. This is calledthepoint of instantiation of the class template object. The compiler must have read the class template's implementation and hasperformed a basic check for syntactic correctness of member functions likemember. It won't accept a definition or declaration likeRet &&*member, becauseC++ does not support functions returning pointers torvalue references. Furthermore, it checks whether the actual type namethat is used for instantiating the object is valid. This type name must beknown to the compiler at the object's point of instantiation.
• the location where the template member function is used. This iscalled the template member function's point of instantiation. HeretheRet parameter must have been specified (or deduced) and at this pointmember'sstatements that depend on theRet template parameter are checked forsyntactic correctness. For example, ifmember contains a statementlike

      Ret tmp(Ret(), 15);

  then this is in principle a syntactically valid statement. However, whenRet = int the statement fails to compile asint does not have aconstructor expecting twoint arguments. Note that this isnot aproblem when the compiler instantiates an object ofmember's class. Atthe point of instantiation of the object its member function `member' isnot instantiated and so the invalidint construction remains undetected.

22.10: Declaring friends

Like ordinary classes, class templates may declare other functions andclasses as their friends. Conversely, ordinary classes may declare templateclasses as their friends. Here too, the friend is constructed as a specialfunction or class augmenting or supporting the functionality of the declaringclass. Although thefriend keyword can be used by any type of class (ordinary or template) when using class templates the following casesshould be distinguished:

• A class template may declare an ordinary function or class as itsfriend. This is a common friend declaration, such as the insertion operatorforostream objects.
• A class template may declare another function template or classtemplate as its friend. In this case, the friend's template parameters mayhave to be specified.

  If the actual values of the friend's template parametersmust be equalto the template parameters of the class declaring the friend, the friend issaid to be abound friend class or function template. Inthis case the template parameters of the template specifying thefrienddeclaration determine (bind) the values of the template parameters of thefriend class or function. Bound friends result in a one-to-one correspondencebetween the template's parameters and the friend's template parameters.

• In the most general case a class template may declare anotherfunction template or class template to be its friend, irrespective of thefriend's actual template arguments.

  In this case anunbound friend class or function template isdeclared. The template parameters of the friend class or function templateremain to be specified and are not related in some predefined way to thetemplate parameters of the class declaring the friend. If a class template hasdata members of various types, specified by its template parameters andanother class should be allowed direct access to these data members we want tospecify any of the current template arguments when specifying such afriend. Rather than specifying multiple bound friends, a single generic(unbound) friend may be declared, specifying the friend's actual templateparameters only when this is required.

• The above cases, in which a template is declared as a friend, mayalso be encountered when ordinary classes are used:
  • The ordinary class declaring ordinary friends has already beencovered (chapter15).
  • The equivalent of bound friends occurs if an ordinary classspecifies specific actual template parameters when declaring its friend.
  • The equivalent of unbound friends occurs if an ordinary classdeclares a generic template as its friend.

22.10.1: Non-templates used as friends in templates

Concrete classes and ordinary functions can be declared as friends, butbefore a single member function of a class can be declared as a friend, thecompiler must have seen theclass interface declaring that member. Let'sconsider the various possibilities:

• A class template may declare an ordinary function to be itsfriend. It is not completely clearwhy we would like to declare anordinary function as a friend. Usually we pass an object of the classdeclaring the friend to such a function. With class templates this requires usto provide the (friend) function with a template parameter without specifyingits types. As the language does not support constructions like

  void function(std::vector<Type> &vector)

  unlessfunction itself is a template, it is not immediately clear howand why such a friend should be constructed. One reason could be to allow thefunction access to the class's private static members. In addition suchfriends could instantiate objects of classes that declare them as theirfriends. This would allow the friend functions direct access to such object'sprivate members. For example:

      template <typename Type>    class Storage    {        friend void basic();        static size_t s_time;        std::vector<Type> d_data;        public:            Storage();    };    template <typename Type>    size_t Storage<Type>::s_time = 0;    template <typename Type>    Storage<Type>::Storage()    {}    void basic()    {        Storage<int>::s_time = time(0);        Storage<double> storage;        std::sort(storage.d_data.begin(), storage.d_data.end());    }

• Declaring an ordinary class to be a class template's friend probablyfinds more applications. Here the ordinary (friend) class may instantiate anykind of object of the class template. The friend class may then access allprivate members of the instantiated class template:

      template <typename Type>    class Composer    {        friend class Friend;        std::vector<Type> d_data;        public:            Composer();    };    class Friend    {        Composer<int> d_ints;        public:            Friend(std::istream &input);    };    inline::Friend::Friend(std::istream &input)    {        std::copy(std::istream_iterator<int>(input),                  std::istream_iterator<int>(),                  back_inserter(d_ints.d_data));    }

• Alternatively, just a single member function of an ordinary class maybe declared as a friend. This requires that the compiler has read the friendclass's interface before declaring the friend. Omitting the requireddestructor and overloaded assignment operators, the following shows an exampleof a class whose membersorter is declared as a friend of the classComposer:

      template <typename Type>    class Composer;    class Friend    {        Composer<int> *d_ints;        public:            Friend(std::istream &input);            void sorter();    };    template <typename Type>    class Composer    {        friend void Friend::sorter();        std::vector<Type> d_data;        public:            Composer(std::istream &input)            {                std::copy(std::istream_iterator<int>(input),                          std::istream_iterator<int>(),                          back_inserter(d_data));            }    };    inline Friend::Friend(std::istream &input)    :        d_ints(new Composer<int>{ input })    {}    inline void Friend::sorter()    {        std::sort(d_ints->d_data.begin(), d_ints->d_data.end());    }

  In this exampleFriend::d_ints is a pointer member. Itcannot be aComposer<int> object as theComposer class interfacehasn't yet been seen by the compiler when it readsFriend's classinterface. Disregarding this and defining a data memberComposer<int>d_ints results in the compiler generating the error

  error: field `d_ints' has incomplete type

  `Incomplete type', as the compiler at this points knows of the existenceof the classComposer, but as it hasn't seenComposer's interface itdoesn't know what size thed_ints data member has.

22.10.2: Templates instantiated for specific types as friends

• A function template is a friend of a class template. In this case wedon't experience the problems we encountered with ordinary functions declaredas friends of class templates. Since the friend function template itself is atemplate it may be provided with the required template arguments allowing itto become the declaring class's friend. The various declarations are organizedlike this:
  • The class template declaring the bound template friend function isdefined;
  • The (friend) function template is defined, now having access to allthe class template's (private) members.
  The bound template friend declaration specifies the required templatearguments immediately following the template's function name. Without thetemplate argument list affixed to the function name it would remain anordinary friend function. Here is an example showing a bound friend to createa subset of the entries of a dictionary. For real life examples, a dedicatedfunction object returning!key1.find(key2) is probably more useful. Forthe current example,operator== is acceptable:

      template <typename Key, typename Value>    class Dictionary    {        friend Dictionary<Key, Value>            subset<Key, Value>(Key const &key,                               Dictionary<Key, Value> const &dict);        std::map<Key, Value> d_dict;        public:            Dictionary();    };    template <typename Key, typename Value>    Dictionary<Key, Value>               subset(Key const &key, Dictionary<Key, Value> const &dict)    {        Dictionary<Key, Value> ret;        std::remove_copy_if(dict.d_dict.begin(), dict.d_dict.end(),                            std::inserter(ret.d_dict, ret.d_dict.begin()),                            std::bind2nd(std::equal_to<Key>(), key));        return ret;    }

• By declaring a full class template as a class template's friend, allmembers of the friend class may access all private members of the classdeclaring the friend. As the friend class only needs to be declared, theorganization of the declaration is much easier than when function templatesare declared as friends. In the following example a classIterator isdeclared as a friend of a classDictionary. Thus, theIterator is ableto accessDictionary's private data. There are some interesting points tonote here:
  • To declare a class template as a friend, that class only needs tobe declared as a class template before it is declared as a friend:

        template <typename Key, typename Value>    class Iterator;    template <typename Key, typename Value>    class Dictionary    {        friend class Iterator<Key, Value>;

  • However, members of the friend class may already be used, eventhough the compiler hasn't seen the friend class's interface yet:

        template <typename Key, typename Value>    template <typename Key2, typename Value2>    Iterator<Key2, Value2> Dictionary<Key, Value>::begin()    {        return Iterator<Key, Value>(*this);    }    template <typename Key, typename Value>    template <typename Key2, typename Value2>    Iterator<Key2, Value2> Dictionary<Key, Value>::subset(Key const &key)    {        return Iterator<Key, Value>(*this).subset(key);    }

  • Of course, the friend class's interface must eventually be seenby the compiler. Since it's a support class forDictionary it can safelydefine astd::map data member that is initialized by the friend class'sconstructor. The constructor may then access theDictionary's private datamemberd_dict:

        template <typename Key, typename Value>    class Iterator    {        std::map<Key, Value> &d_dict;        public:            Iterator(Dictionary<Key, Value> &dict)            :                d_dict(dict.d_dict)            {}

  • TheIterator memberbegin may return amapiterator. Since the compiler does not know what the instantiation of the maplooks like, amap<Key, Value>::iterator is a template subtype. So itcannot be used as-is, but it must be prefixed bytypename (see the functionbegin's return type in the next example):

        template <typename Key, typename Value>    typename std::map<Key, Value>::iterator Iterator<Key, Value>::begin()    {        return d_dict.begin();    }

• In the previous example we might decide that only aDictionaryshould be able to construct anIterator (maybe because we conceptuallyconsiderIterator to be a sub-type ofDictionary). This is easilyaccomplished by definingIterator's constructor in its private section,and by declaringDictionary to be a friend ofIterator. Consequently,only aDictionary can create anIterator. By declaring the constructorof aspecificDictionary type as a friend ofIterator's we declareabound friend. This ensures that only that particular type ofDictionary can createIterators using template parameters identical toits own. Here is how it's done:

      template <typename Key, typename Value>    class Iterator    {        friend Dictionary<Key, Value>::Dictionary();        std::map<Key, Value> &d_dict;        Iterator(Dictionary<Key, Value> &dict);        public:

  In this example,Dictionary's constructor isIterator'sfriend. The friend is a template member. Other members can be declared asa class's friend as well. In those cases their prototypes must be used, alsospecifying the types of their return values. Assuming that

  std::vector<Value> sortValues()

  is a member ofDictionary then the matching bound friend declarationis:

  friend std::vector<Value> Dictionary<Key, Value>::sortValues();

• A class template may define free members, which should have access tothe data of instantiations of the class template, but only for matchingtypes. An example is a class template for which the free memberoperator==must be available. If this is required for a templateClassTemplate,requiring atypename Type template type argument, thena free member

      template<typename Type>    bool operator==(ClassTemplate<Type> const &lhs,                     ClassTemplate<Type> const &rhs);

  must have been declared prior toClassTemplate's interfaceitself. Within the class interfaceoperator== may then be declared as afriend, specifyingoperator== as a specialized function template (note the<> following the function name) like this:

      template <typename Type>    class ClassTemplate    {        friend  bool operator==<>(ClassTemplate<Type> const &lhs,                                 ClassTemplate<Type> const &rhs);        ...    };

  Now that the class has been declared,operator=='s implementation mayfollow.

Finally, the following example can be used as a prototype forsituations where bound friends are useful:

    template <typename T>   // a function template    void fun(T *t)    {        t->not_public();    };    template<typename X>    // a free member function template    bool operator==(A<X> const &lhs, A<X> const &rhs);    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> *);                            // operator== is a friend for A<X> only        friend  bool operator==<>(A<X> const &lhs, A<X> const &rhs);        int d_data = 10;        public:            A();        private:            void not_public();    };    template <typename X>    A<X>::A()    {        fun(this);    }    template <typename X>    void A<X>::not_public()    {}    template<typename X>    // may access lhs/rhs's private data    bool operator==(A<X> const &lhs, A<X> const &rhs)    {        return lhs.d_data == rhs.d_data;    }    int main()    {        A<int> a;        fun(&a);            // fun instantiated for A<int>.    }

22.10.2.1: Free operators as friends of nested classes

It is possible to define the freeoperator== as friend in the nestedclass, which then automatically becomes a bound friend. E.g.,

    #include <string>    template <typename Type>    struct String    {        struct iterator        {            std::string::iterator d_iter;            friend bool operator==(iterator const &lhs, iterator const &rhs)            {                return lhs.d_iter == rhs.d_iter;            }        };        iterator begin()        {            return iterator{};        }    };    int main()    {        String<int> str;        return  str.begin() == str.begin();    }

But when moving the implementation out of the interface we run into theproblem thatoperator== is a function template, which must be declared assuch in the class interface. The compiler suggests tomake sure thefunction template has already been declared and add '<>' after the functionname. But declaring

    template <typename Type>    bool operator==(Type const &lhs, Type const &rhs);

    template <typename Type>    inline bool operator==(String<Type>::iterator const &lhs,                           String<Type>::iterator const &rhs)    {        return lhs.d_iter == rhs.d_iter;    }

So how to solve this issue? There are two known ways to solve thisproblem. One was suggested by Radu Cosma (teaching assistant of ourC++course in the 2021-2022 academic year), the other solution is provided in section23.13.7.2.

Radu proposed using an application ofSFINAE: by defining a free operatorprovided with a type uniquely defined by the nested class, which is thenprovided with a default value in the free function's implementation, thecompiler automatically selects the appropriate overloaded function. This worksfor multiple classes declaring nested classes and for classes definingmultiple nested classes alike. Here is an example of two classes eachdeclaring a nested classiterator:

    template <typename Type>    struct String    {        struct iterator        {            using StringType_iterator = int;            friend bool operator==<>(iterator const &lhs, iterator const &rhs);                std::string::iterator d_iter;        };        iterator begin()        {            return iterator{};        }    };        template <typename Type>    struct Container    {        struct iterator        {            using ContainerType_iterator = int;            friend bool operator==<>(iterator const &lhs, iterator const &rhs);                int *d_ptr;        };        iterator begin()        {            return iterator{};        }    };

Then, for each nested class an implementation of the free operator isprovided. These implementations are function templates provided with a template typeType and a second type which is the uniquelynamedint type of the nested class for which the free operator isimplemented:

    template <typename Type, Type::StringType_iterator = 0>    inline bool operator==(Type const &lhs, Type const &rhs)    {        return lhs.d_iter == rhs.d_iter;    }        template <typename Type, Type::ContainerType_iterator = 0>    inline bool operator==(Type const &lhs, Type const &rhs)    {        return lhs.d_ptr == rhs.d_ptr;    }

    int main()    {        String<int> str;        Container<int> cnt;        return str.begin() == str.begin() and cnt.begin() == cnt.begin();    }

22.10.3: Unbound templates as friends

Here are the syntactic conventions declaring unbound friends:

• Declaring a function template as an unbound friend: anyinstantiation of the function template may instantiate objects of the templateclass and may access its private members. Assume the followingfunction template has been defined

  template <typename Iterator, typename Class, typename Data>Class &ForEach(Iterator begin, Iterator end, Class &object,                    void (Class::*member)(Data &));

  This function template can be declared as an unbound friend in thefollowing class templateVector2:

  template <typename Type>class Vector2: public std::vector<std::vector<Type> >{    template <typename Iterator, typename Class, typename Data>    friend Class &ForEach(Iterator begin, Iterator end, Class &object,                void (Class::*member)(Data &));    ...};

  If the function template is defined inside some namespace this namespacemust be mentioned as well. Assuming thatForEach is defined in thenamespaceFBB its friend declaration becomes:

  template <typename Iterator, typename Class, typename Data>friend Class &FBB::ForEach(Iterator begin, Iterator end, Class &object,                void (Class::*member)(Data &));

  The following example illustrates the use of an unbound friend. The classVector2 stores vectors of elements of template type parameterType. Itsprocess member allowsForEach to call its privaterows member. Therows member, in turn, uses anotherForEach tocall its privatecolumns member. Consequently,Vector2 uses twoinstantiations ofForEach which is a clear hint for using an unboundfriend. It is assumed thatType class objects can be inserted intoostream objects (the definition of theForEach function template canbe found in thecplusplus.yo.zip archive that can be retrieved fromhttps://fbb-git.gitlab.io/cppannotations/). Here is the program:

      template <typename Type>    class Vector2: public std::vector<std::vector<Type> >    {        using iterator = typename Vector2<Type>::iterator;        template <typename Iterator, typename Class, typename Data>        friend Class &ForEach(Iterator begin, Iterator end, Class &object,                    void (Class::*member)(Data &));        public:            void process();        private:            void rows(std::vector<Type> &row);            void columns(Type &str);    };    template <typename Type>    void Vector2<Type>::process()    {        ForEach<iterator, Vector2<Type>, std::vector<Type> >                (this->begin(), this->end(), *this, &Vector2<Type>::rows);    }    template <typename Type>    void Vector2<Type>::rows(std::vector<Type> &row)    {        ForEach(row.begin(), row.end(), *this,                                        &Vector2<Type>::columns);        std::cout << '\n';    }    template <typename Type>    void Vector2<Type>::columns(Type &str)    {        std::cout << str << " ";    }    using namespace std;    int main()    {        Vector2<string> c;        c.push_back(vector<string>(3, "Hello"));        c.push_back(vector<string>(2, "World"));        c.process();    }    /*        Generated output:        Hello Hello Hello        World World    */

• Analogously, a full class template may be declared as friend. Thisallows all instantiations of the friend's member functions to instantiateobjects of the class template declaring the friend class. In this case, theclass declaring the friend should offer functionality that is useful todifferent instantiations of its friend class (i.e., instantiations usingdifferent template arguments). The syntactic convention is comparable to theconvention used when declaring an unbound friend function template:

  template <typename Type>class PtrVector{    template <typename Iterator, typename Class>    friend class Wrapper;      // unbound friend class};

  All members of the class templateWrapper may now instantiatePtrVectors using any actual type for itsType parameter. This allowstheWrapper instantiation to access all ofPtrVector's privatemembers.

• When only some members of a class template need access to privatemembers of another class template (e.g., the other class template has privateconstructors and only some members of the first class template need toinstantiate objects of the second class template), then the latter classtemplate may declare only those members of the former class template requiringaccess to its private members as its friends. Again, the friend class'sinterface may be left unspecified. However, the compiler must be informed thatthe friend member's class is indeed a class. A forward declaration of thatclass must therefore be provided. In the next examplePtrVectordeclaresWrapper::begin as its friend. Note the forward declaration ofthe classWrapper:

  template <typename Iterator>class Wrapper;template <typename Type>class PtrVector{    template <typename Iterator> friend        PtrVector<Type> Wrapper<Iterator>::begin(Iterator const &t1);    ...};

22.10.4: Extended friend declarations

Consider the following class template, declaringFriend as a friend:

    template <typename Friend>    class Class    {        friend Friend;        void msg();             // private, displays some message    };

Now, an actualFriend class may access all ofClass's members

    class Concrete    {        Class<Concrete> d_class;        Class<std::string> d_string;       public:            void msg()            {                d_class.msg();    // OK: calls private Class<Concrete>::msg()                //d_string.msg(); // fails to compile: msg() is private            }    };

A declaration likeClass<int> intClass is also OK, but here the frienddeclaration is simply ignored. After all, there are no `int members' to accessClass<int>'s private members.

22.11: Class template derivation

• An existing class template is used as base class when deriving aordinary class. The derived class itself will partially be a class template,but this is somewhat hidden from view when an object of the derived class isdefined.
• An existing class template is used as the base class when derivinganother class template. Here the class template characteristics remain clearlyvisible.
• An ordinary class is used as the base class when deriving a templateclass. This interesting hybrid allows us to construct class templates thatarepartially compiled.

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 forthe following derived class templateDerived:

    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 instantiatedby specifying template arguments, turning the derived class into an ordinaryclass (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 aderived class template.

Class template derivation pretty much follows the same rules as ordinaryclass derivation, not involving class templates. Some subtleties that arespecific for class template derivation may easily cause confusion like the useofthis when members of a template base class are called from a derivedclass. The reasons for usingthis are discussed in section23.1. Inthe upcoming sections the focus will be on the class derivation proper.

22.11.1: Deriving ordinary classes from class templates

Example: a program executing commands entered at the keyboard might accept allunique initial abbreviations of the commands it defines. E.g., the commandlist might be entered asl, li, lis orlist. By deriving a classHandler from

    map<string, void (Handler::*)(string const &cmd)>

and by defining a member functionprocess(string const &cmd) to do theactual command processing a program might simply execute the followingmain() function:

    int main()    {        string line;        Handler cmd;        while (getline(cin, line))            cmd.process(line);    }

• The class is derived from astd::map, expecting the commandassociated with each command-processing member as its keys. SinceHandler uses the map merely to define associations between the commands and the processingmember functions and to makemap's types available, private derivation isused:

      class Handler: private std::map<std::string,                            void (Handler::*)(std::string const &cmd)>

• The actual association can be defined using static private datamembers:s_cmds is an array ofHandler::value_type values, ands_cmds_end is a constant pointer pointing beyond the array's last element:

          static value_type s_cmds[];        static value_type *const s_cmds_end;

• The constructor simply initializes the map from these two static datamembers. It could be implemented inline:

      inline Handler::Handler()    :        std::map<std::string,                    void (Handler::*)(std::string const &cmd)>        (s_cmds, s_cmds_end)    {}

• The memberprocess iterates along the map's elements. Once thefirst word on the command line matches the initial characters of the command,the corresponding command is executed. If no such command is found, an errormessage is issued:

      void Handler::process(std::string const &line)    {        istringstream istr(line);        string cmd;        istr >> cmd;        for (iterator it = begin(); it != end(); it++)        {            if (it->first.find(cmd) == 0)            {                (this->*it->second)(line);                return;            }        }        cout << "Unknown command: " << line << '\n';    }

22.11.2: Deriving class templates from class templates

The class templateSortVector presented below is derived from theexisting class templatestd::vector. It allows us to perform ahierarchic sort of its elements using any ordering of any data membersits data elements may contain. To accomplish this there is but onerequirement.SortVector's data type must offer dedicated memberfunctions comparing its members.

For example, ifSortVector's data type is an object of classMultiData, thenMultiData should implement member functions having thefollowing prototypes for each of its data members which can be compared:

    bool (MultiData::*)(MultiData const &rhv)

So, ifMultiData has two data members,int d_value andstd::string d_text and both may be used by a hierarchic sort, thenMultiData 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 thatoperator<< andoperator>> have been defined forMultiData objects.

The class templateSortVector is directly derived from the templateclassstd::vector. Our implementation inherits all members from that baseclass. 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 memberhierarchicSort is the trueraison d'être for theclass. It defines the hierarchic sort criteria. It expects a pointer to a series of pointers to member functions of the classType as well as asize_t representing the size of the array.

The array's first element indicatesType's most significant sortcriterion, the array's last element indicates the class's least significantsort criterion. Since thestable_sort generic algorithm was designedexplicitly to support hierarchic sorting, the member uses this genericalgorithm to sortSortVector's elements. With hierarchic sorting, theleast significant criterion should be sorted first.hierarchicSort'simplementation is therefore easy. It requires a support classSortWithwhose objects are initialized by the addresses of the member functions passedto thehierarchicSort() 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 classSortWith is a simple wrapper class around a pointer toa predicate function. Since it depends onSortVector's actual datatype the classSortWith 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 andinitializes the class'sd_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 returntrue if itsfirst 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 examples, which can be embedded in amainfunction, provides an illustration:

• First, ASortVector object is created forMultiData objects.It uses thecopy generic algorithm to fill theSortVector object frominformation appearing at the program's standard input stream. Havinginitialized the object its elements are displayed to the standard outputstream:

          SortVector<MultiData> sv;        copy(istream_iterator<MultiData>(cin),                istream_iterator<MultiData>(),                back_inserter(sv));

• An array of pointers to members is initialized with the addresses oftwo member functions. The text comparison is the most significant sortcriterion:

          bool (MultiData::*arr[])(MultiData const &rhv) const =        {            &MultiData::textCmp,            &MultiData::intCmp,        };

• Next, the array's elements are sorted and displayed to the standardoutput stream:

          sv.hierarchicSort(arr, 2);

• Then the two elements of the array of pointers toMultiData'smember functions are swapped, and the previous step is repeated:

          swap(arr[0], arr[1]);        sv.hierarchicSort(arr, 2);

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

22.11.3: Deriving class templates from ordinary classes

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

As an illustration of this approach we'll develop such a class templatebelow. We'll develop a classTable derived from an ordinary classTableType. The classTable displays elements of some type in atable having a configurable number of columns. The elements are eitherdisplayed horizontally (the firstk elements occupy the first row) orvertically (the firstr elements occupy a first column).

When displaying the table's elements they are inserted into a stream. Thetable is handled by a separate class (TableType), implementing the table'spresentation. Since the table's elements are inserted into a stream, theconversion to text (orstring) is implemented inTable, but thehandling of the strings themselves is left toTableType. We'll cover somecharacteristics ofTableType shortly, concentrating onTable'sinterface first:

• The classTable is a class template, requiring only one templatetype parameter:Iterator referring to an iterator to some data type:

  template <typename Iterator>class Table: public TableType{

• Table doesn't need any data members. All data manipulations areperformed byTableType.
• Table has two constructors. The constructor's first twoparameters areIterators used to iterate over the elements that must beentered into the table. The constructors require us to specify the number ofcolumns we would like our table to have as well as aFillDirection.FillDirection is anenum, defined byTableType,having valuesHORIZONTAL andVERTICAL. To allowTable's users toexercise control over headers, footers, captions, horizontal and verticalseparators, one constructor has aTableSupport reference parameter. TheclassTableSupport is developed at a later stage as a virtual classallowing clients to exercise this control. Here are the class's constructors:

          Table(Iterator const &begin, Iterator const &end,                size_t nColumns, FillDirection direction);        Table(Iterator const &begin, Iterator const &end,                TableSupport &tableSupport,                size_t nColumns, FillDirection direction);

• The constructors areTable's only two public members. Bothconstructors use a base class initializer to initialize theirTableTypebase class and then call the class's private memberfill to insert datainto theTableType base class object. Here are the constructor'simplementations:

  template <typename Iterator>Table<Iterator>::Table(Iterator const &begin, Iterator const &end,                TableSupport &tableSupport,                size_t nColumns, FillDirection direction):    TableType(tableSupport, nColumns, direction){    fill(begin, end);}template <typename Iterator>Table<Iterator>::Table(Iterator const &begin, Iterator const &end,                size_t nColumns, FillDirection direction):    TableType(nColumns, direction){    fill(begin, end);}

• The class'sfill member iterates over the range of elements[begin, end), as defined by the constructor's first two parameters.As we will see shortly,TableType defines a protected data memberstd::vector<std::string> d_string. One of the requirements of the datatype to which the iterators point is that this data type can be inserted intostreams. So,fill uses anostringstream object to obtain the textualrepresentation of the data, which is then appended tod_string:

  template <typename Iterator>void Table<Iterator>::fill(Iterator it, Iterator const &end){    while (it != end)    {        std::ostringstream str;        str << *it++;        d_string.push_back(str.str());    }    init();}

This completes the implementation of the classTable. Note that thisclass template only has three members, two of them beingconstructors. Therefore, in most cases only two function templates must beinstantiated: a constructor and the class'sfill member. For example, thefollowing defines a table having four columns, vertically filled bystrings 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 asTableType::VERTICAL. It could also have been specified usingTable,but sinceTable is a class template its specification would have beenslightly more complex:Table<istream_iterator<string> >::VERTICAL.

Now that theTable derived class has been designed, let's turn ourattention to the classTableType. Here are its essential characteristics:

• It is an ordinary class, designed to operate asTable's baseclass.
• It uses various private data members, among whichd_colWidth, avector storing the width of the widest element per column andd_indexFun,pointing to the class's member function returning the element intable[row][column], conditional to the table's filldirection.TableType also uses aTableSupport pointer and areference. The constructor not requiring aTableSupport object uses theTableSupport * to allocate a (default)TableSupport object and thenuses theTableSupport & as the object's alias. The other constructorinitializes the pointer to 0 and uses the reference data member to refer totheTableSupport object provided by its parameter. Alternatively, a staticTableSupport object could have been used to initialize the reference datamember in the former constructor. The remaining private data members areprobably self-explanatory:

          TableSupport           *d_tableSupportPtr;        TableSupport           &d_tableSupport;        size_t                d_maxWidth;        size_t                d_nRows;        size_t                d_nColumns;        WidthType               d_widthType;        std::vector<size_t>   d_colWidth;        size_t               (TableType::*d_widthFun)                                        (size_t col) const;        std::string const     &(TableType::*d_indexFun)                                        (size_t row, size_t col) const;

• The actualstring objects populating the table are stored in aprotected data member:

          std::vector<std::string> d_string;

• The (protected) constructors perform basic tasks: they initialize theobject's data members. Here is the constructor expecting a reference to aTableSupport object:

  #include "tabletype.ih"TableType::TableType(TableSupport &tableSupport, size_t nColumns,                        FillDirection direction):    d_tableSupportPtr(0),    d_tableSupport(tableSupport),    d_maxWidth(0),    d_nRows(0),    d_nColumns(nColumns),    d_widthType(COLUMNWIDTH),    d_colWidth(nColumns),    d_widthFun(&TableType::columnWidth),    d_indexFun(direction == HORIZONTAL ?                    &TableType::hIndex                :                    &TableType::vIndex){}

• Onced_string has been filled, the table is initialized byTable::fill. Theinit protected member resizesd_string sothat its size is exactlyrows x columns, and it determines the maximumwidth of the elements per column. Its implementation is straightforward:

  #include "tabletype.ih"void TableType::init(){    if (!d_string.size())                   // no elements        return;                             // then do nothing    d_nRows = (d_string.size() + d_nColumns - 1) / d_nColumns;    d_string.resize(d_nRows * d_nColumns);  // enforce complete table                                            // determine max width per column,                                            // and max column width    for (size_t col = 0; col < d_nColumns; col++)    {        size_t width = 0;        for (size_t row = 0; row < d_nRows; row++)        {            size_t len = stringAt(row, col).length();            if (width < len)                width = len;        }        d_colWidth[col] = width;        if (d_maxWidth < width)             // max. width so far.            d_maxWidth = width;    }}

• The public memberinsert is used by the insertion operator(operator<<) to insert aTable into a stream. First it informs theTableSupport object about the table's dimensions. Next it displays thetable, allowing theTableSupport object to write headers, footers andseparators:

  #include "tabletype.ih"ostream &TableType::insert(ostream &ostr) const{    if (!d_nRows)        return ostr;    d_tableSupport.setParam(ostr, d_nRows, d_colWidth,                            d_widthType == EQUALWIDTH ? d_maxWidth : 0);    for (size_t row = 0; row < d_nRows; row++)    {        d_tableSupport.hline(row);        for (size_t col = 0; col < d_nColumns; col++)        {            size_t colwidth = width(col);            d_tableSupport.vline(col);            ostr << setw(colwidth) << stringAt(row, col);        }        d_tableSupport.vline();    }    d_tableSupport.hline();    return ostr;}

• Thecplusplus.yo.zip archive containsTableSupport's fullimplementation. This implementation is found in the directoryyo/classtemplates/examples/table. Most of its remaining members areprivate. Among those, these two members return table element[row][column] for, respectively, a horizontally filled table and avertically filled table:

      inline std::string const &TableType::hIndex(size_t row, size_t col) const    {        return d_string[row * d_nColumns + col];    }    inline std::string const &TableType::vIndex(size_t row, size_t col) const    {        return d_string[col * d_nRows + row];    }

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

• hline(size_t rowIndex): called just before displayingthe elements in rowrowIndex.
• hline(): called immediately after displaying the final row.
• vline(size_t colIndex): called just before displaying the element incolumncolIndex.
• vline(): called immediately after displaying all elements in a row.

    /*                                  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';    }    /*        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    */

22.12: Static Polymorphism

In many cases, however, dynamic polymorphism isn't really required. Usuallythe derived class objects that are passed to functions expecting base classreferences are invariants: at fixed locations in programs fixed class typesare used to create objects. The polymorphic nature of these objects is usedinside the functions that receive these objects, expecting references to theirbase classes. As an example consider reading information from a networksocket. A classSocketBuffer is derived fromstd::streambuf, and thestd::stream receiving a pointer to theSocketBuffer merely usesstd::streambuf's interface. However, the implementation, by usingpolymorphism, in fact communicates with functions defined inSocketBuffer.

The disadvantages of this scheme are that, firstly, inside the functionsexpecting references to polymorphic base classes execution is somewhat sloweddown precisely because of late-binding. Member functions aren'tdirectly called, but are called indirectly via the object'svpointer andtheir derived class'sVtable. Secondly, programs using dynamicpolymorphism tend to become somewhat bloated compared to programs using staticbinding. Thecode bloat is caused by the requirement to satisfy atlink-time all the references that are mentioned in all the object filescomprising the final program. This requirement forces the linker to link allthe functions whose addresses are stored in theVtables of all polymorphicclasses, even if these functions are never actually called.

Static polymorphism allows us to avoid thesedisadvantages. It can be used instead of dynamic polymorphism in cases wherethe abovementioned invariant holds. Static polymorphism, also called thecuriously recurring template pattern (CRTP), is an example oftemplate meta programming (see also chapter23 foradditional examples of template meta programming).

Whereas dynamic polymorphism is based on the concepts ofvpointers,Vtables, andfunction overriding, static polymorphism capitalizes on thefact that function templates (c.q., member templates) are only compiled intoexecutable code when they are actually called. This allows us to write code inwhich functions are called which are completely non-existent at the time wewrite our code. This, however, shouldn't worry us too much. After all, we usea comparable approach when calling a purely virtual function of an abstractbase class. The function is really called, but which function is eventuallycalled is determined later in time. With dynamic polymorphism it is determinedrun-time, with static polymorphism it is determined compile-time.

There's no need to consider static and dynamic polymorphism as mutuallyexclusive variants of polymorphism. Rather, both can be used together,combining their strengths.

This section contains several subsections.

• First, the syntax used with static polymorphism is introduced and illustrated;
• Next, it is shown how classes that use dynamic polymorphism can be converted to classes that use static polymorphism;
• Finally it is illustrated how static polymorphism can be used to reduce implementation effort. Static polymorphism allows us to implement only once what would have to be implemented repeatedly when only dynamic polymorphism is used.

22.12.1: An example of static polymorphism

In the context of dynamic polymorphism these overridable members are the baseclass's virtual members. In the context of static polymorphism there are novirtual members. Instead, the statically polymorphic base class (referred toas the `base class' below) declares atemplate type parameter (referred toas the `derived class type' below). Next, the base class's interfacing memberscall members of the derived class type.

Here is a simple example: a class template acting as a base class. Its publicinterface consists of one member. But different from dynamic polymorphismthere's no reference in the class's interface to any member showingpolymorphic behavior (i.e, no `virtual' members are declared):

    template <class Derived>    struct Base    {        void interface();    }

Let's have a closer look at the member `interface'. This member is calledby functions receiving a reference or pointer to the base class, but it maycall members that must be available in the derived class type at the pointwhereinterface is called. Before we can call members of the derived classtype an object of the derived class type must be available. This object isobtained through inheritance. The derived class type is going to be derivedfrom the base class. ThusBase's this pointer is alsoDerived's thispointer.

Forget about polymorphism for a second: when we have aclass Derived:public Base then (because of inheritance) astatic_cast<Derived *> can beused to cast aBase * to aDerived object. Adynamic_cast ofcourse doesn't apply, as we don't use dynamic polymorphism. But astatic_cast is appropriate since ourBase *does in fact point toaDerived class object.

So, to call aDerived class member from insideinterface wecan use the following implementation (remember thatBase is a base classofDerived):

    template<class Derived>    void Base<Derived>::interface()    {        static_cast<Derived *>(this)->polymorphic();    }

It's remarkable that, when the compiler is given this implementation itcannot determine whetherDerived isreally derived fromBase. Neither can it determine whether the classDerived indeed offersa memberpolymorphic. The compiler simplyassumes this to be true. Ifso, then the provided implementation is syntactically correct. One of thekey characteristics of using templates is that the implementation's viabilityis eventually determined at the function's point of instantiation (cf. section21.6). At that point the compiler will verify that, e.g., thefunctionpolymorphic really is available.

Thus, in order to use the above scheme we must ensure that

• derived class type is actually derived from the base class and
• that the derived class type defines a member `polymorphic'.

    class First: public Base<First>

In this curious pattern the classFirst is derived fromBase,which itself is instantiated forFirst. This is acceptable, as thecompiler already has determined that the typeFirst exists. At this pointthat is all it needs.

The second requirement is simply satisfied by defining the memberpolymorphic. In chapter14 we saw that virtual andoverriding members belong to the class's private interface. We can apply thesame philosophy here, by placingpolymorphic inFirst's privateinterface, allowing it to be accessed from the base class by declaring

    friend void Base<First>::interface();

First's complete class interface can now be designed, followed bypolymorphic's implementation:

    class First: public Base<First>    {        friend void Base<First>::interface();        private:            void polymorphic();    };    void First::polymorphic()    {        std::cout << "polymorphic from First\n";    }

Note that the classFirst itself is not a class template: its memberscan be separately compiled and stored in, e.g., a library. Also, as is thecase with dynamic polymorphism, the memberpolymorphic has full access toall ofFirst's data members and member functions.

Multiple classes can now be designed likeFirst, each offering theirown implementation ofpolymorphic. E.g., the memberSecond::polymorphic of the classSecond, designed likeFirst,could be implemented like this:

    void Second::polymorphic()    {        std::cout << "polymorphic from Second\n";    }

The polymorphic nature ofBase becomes apparent once a functiontemplate is defined in whichBase::interface is called. Again, thecompiler simply assumes a memberinterface exists when it reads thedefinition of the following function template:

    template <class Class>    void fun(Class &object)    {        object.interface();    }

Only where this function is actually called will the compiler verify theviability of the generated code. In the followingmain function aFirst object is passed tofun:First declaresinterfacethrough its base class, andFirst::polymorphic is called byinterface. The compiler will at this point (i.e., wherefun is called)check whetherfirst indeed has a memberpolymorphic. Next aSecondobject is passed tofun, and here again the compiler checks whetherSecond has a memberSecond::polymorphic:

    int main()    {        First first;        fun(first);        Second second;        fun(second);    }

There are also downsides to using static polymorphism:

• First, the sentence `aSecond object is passed tofun'formally isn't correct, sincefun is a function template the functionsfun called asfun(first) andfun(second) aredifferent functions, not just calls of one function with differentarguments. With static polymorphism every instantiation using its own templateparameters results in completely new code which is generated when the template(e.g.,fun) is instantiated. This is something to consider when creatingstatically polymorphic base classes. If the base class defines data membersand member functions, and if these additional members are used by derivedclass types, then each member has its own instantiation for each derived classtype. This also results incode bloat, albeit of a different kind thanobserved with dynamic polymorphism. This kind of code bloat can often besomewhat reduced by deriving the base class from its own (ordinary,non-template) base class, encapsulating all elements of the staticallypolymorphic base class that do not depend on its template type parameters.
• Second, if different types of statically polymorphic objects aredynamically created (using thenew operator) then the types of thereturned pointers are all different. In addition, the types of the pointers totheir statically polymorphic base classes differ from each other. Theselatter pointers are different because they are pointers toBase<Derived>,representing different types for differentDerived types. Consequently,and different from dynamic polymorphism, these pointers cannot be collectedin, e.g., a vector of shared pointers to base class pointers. There simplyisn't one base class pointer type. Thus, because of the different base classtypes, there's no direct statically polymorphic equivalent to virtualdestructors.
• Third, as illustrated in the next section, designing staticpolymorphic classes using multiple levels of inheritance is not a trivialtask.

22.12.2: Converting dynamic polymorphic classes to static polymorphic classes

In chapter14 the base classVehicle and some derivedclasses were introduced.Vehicle, Car andTruck's interfaces look likethis (regarding the members that are involved in their polymorphic behaviors):

    class Vehicle    {        public:            int mass() const;        private:            virtual int vmass() const;    };    class Car: public Vehicle    {        private:            int vmass() const override;    };            class Truck: public Car    {        private:            int vmass() const override;    };

When converting dynamically polymorphic classes to statically polymorphicclasses we must realize that polymorphic classes show two importantcharacteristics:

• they define facilities (data members, member functions) that areinherited by derived classes (e.g.,Vecicle::mass) (i.e., the inheritableinterface), and
• derived classes implement the redefinable interface in a way thatsuits their purpose (e.g.,Truck::vmass).

With statically polymorphic classes these two characteristics shouldcompletely be separated. As we've seen in the previous section, astatically polymorphic derived class derives from its base class by using itsown class type as argument to the base class's type parameter. This works fineif there's only one level of inheritance (i.e., one base class, and one ormore classes that are directly derived from that base class).

With multiple levels of inheritance (e.g.,Truck -> Car -> Vehicle)Truck's inheritance specification becomes a problem. Here's an intialattempt to use static polymorphism and multiple levels of inheritance:

    template <class Derived>    class Vehicle    {        public:            void mass()             {                static_cast<Derived *>(this)->vmass();            }    };        class Car: public Vehicle<Car>    {        friend void Vehicle<Car>::mass();        void vmass();    };    class Truck: public Car    {        void vmass();    };

• IfTruck inherits fromCar, thenTruck implicitlyderives fromVehicle<Car>, asCar derives fromVehicle<Car>. Consequently, whenTruck{}.mass() is called it is notTruck::vmass that's activated, butCar'svmass function. ButTruckmust derive fromCar in order to useCar's protectedfeatures and to addCar's public features to its own publicinterface.
• Multiple inheritance also doesn't solve the issue: wheninheritingTruck fromVehicle<Truck>and fromCar results in a classTruck thatalso inherits fromVehicle<Car> (throughTruck's Car base class), and compilation failsas the compiler encounters an ambiguity when instantiatingVehicle::mass:should it callClass::vmass or should it callTruck::vmass?

In derived classes the protected and public interfaces of (direct or indirect)base classes are made available using standard inheritance. This is shown inthe left-hand side of figure29.

The left-hand side classes are used as base classes for the next level ofinheritance (except forTruckBase, butTruckBase could be used as baseclass for yet another level of class inheritance). This line of inheritancedeclares the inheritable interface of the classes.

Each of the classes to the left is a base class of a single class to theright:VehicleBase is a base class forVehicle,TruckBase forTruck. The classes to the left contain all members that are completelyindependent of the elements that are involved in realizing the staticpolymorphism. As that's a mere design principle to realize multiple levels ofstatic polymorphism the common data hiding principles are relaxed, and theleft-hand side classes declare their matching right-hand side derived classtemplates as friend, to allow full access to all members of a left-hand sideclass, including the private members, from the matching derived class templateto the right. E.g.,VehicleBase declaresVechicle as its friend:

    class VehicleBase    {        template <class Derived>        friend class Vehicle;        // all members originally in Vehicle, but not involved         // in realizing static polymorphism are declared here. E.g.,        size_t d_massFactor = 1;    };

The top level class to the left (VehicleBase) lays the foundation ofstatic polymorphism, by defining that part of the interface that uses thestatically redefinable functions. E.g, using the curiously recurring templatepattern it defines a class membermass that calls the functionvmassof its derived class (in addition it can use all members of its non-classtemplate base class). E.g,:

    template <class Derived>    class Vehicle: public VehicleBase    {        public:            int mass() const            {                return d_massFactor *                        static_cast<Derived const *>(this)->vmass();            }    };

Which function actually is called whenvmass is called depends on theimplementation in the classDerived, which is handled by the remainingclasses, shown belowVehicle, which are all derived fromVehicle (aswell as from their own...Base class). These classes use the curiouslyrecurring template pattern. E.g.,

    class Car: public CarBase, public Vehicle<Car>

So, ifCar now implements its ownvmass function, which can useany of its own (i.e.,CarBase's members), thenthat function is calledwhen calling aVehicle's mass function. E.g.,

    template <class Vehicle>    void fun(Vehicle &vehicle)    {        cout << vehicle.mass() << '\n';    }        int main()    {        Car car;        fun(car);       // Car's vmass is called            Truck truck;        fun(truck);     // Truck's vmass is called    }

Now that we've analyzed the design of statically polymorphic classes usingmultiple levels of inheritance let's summarize the steps we took toimplement static polymorphism

• First, starting at the base class,the classVehicle.Vehicle's non-redefinable interface is movedto a classVehicleBase, andVehicle itself is turned into a staticallypolymorphic base class. In general all members of the original polymorphic base class that do not use or implement virtual members should bemoved to theXBase class.

• VehicleBase declaresVehicle to be afriend, to allowVehicle full access to its former members, that are now inVehicleBase.

• Vehicle's members refer to the redefinable interface. I.e., itsmembers call members of itsDerived template type parameter. In thisimplementationVehicle does not implement its ownvmass member. Wecannot defineVehicle<Vehicle>, and with static polymorphism the baseclass is essentially comparable to an abstract base class. If this isinconvenient then a default class can be specified forVehicle's Derivedclass, implementing the redefinable interface of the original polymorphic base class (allowing for definitions likeVehicle<> vehicle).

• Likewise the remaining classes have their members not involved instatic polymorphism moved to a base class. E.g., classCar moves these members toCarBase andTruck moves those members toTruckBase.

• A standard linear line of inheritance is used fromVehicleBase toCarBase and from there toTruckBase.

• Each of the remaining classes (here:Car andTruck) is aclass template that derives from its base classes, and also, using thecuriously recurrent template pattern, fromVehicle.

• Each of these remaining classes can now implement its own version ofthe redefinable interface, as used by the members ofVehicle.

This design pattern can be extended to any level of inheritance: for eachnew level a base class is constructed, deriving from the most deeply nestedXXXBase class so far, and deriving fromVehicle<XXX>, implementing itsown ideas about the redefinable interface.

Functions that are used in combination with statically polymorphic classesthemselves must be function templates. E.g.,

    template <class Vehicle>    void fun(Vehicle &vehicle)    {        cout << vehicle.mass() << '\n';    }

Here,Vehicle is just a formal name. When an object is passed tofun it must offer a membermass, or compilation will fail. If theobject is in fact aCar orTruck, then theirVehicle<Type> staticbase class membermass is called, which in turn uses static polymorphismto call the membervmass as implemented by the actually passed classtype. The followingmain function displays, respectively, 1000 and 15000:

    int main()    {        Car car;        fun(car);            Truck truck;        fun(truck);    }

Note that this program implementsfun twice, rather than once in thecase of dynamic polymorphism. The same holds true for theVehicle classtemplate: two implementations, one for theCar type, and one for theTruck type. The statically polymorphic program will be slightly faster,though.

(A compilable example using static polymorphism is found in theC++ Annotations's source distribution's fileyo/classtemplates/examples/staticpolymorphism/polymorph.cc.)

22.12.3: Using static polymorphism to avoid reimplementations

Consider the situation where we have a class containing a container ofpointers to some polymorphic base class type (like the classVehicle fromchapter14). How to copy such a container to another container?We're not hinting at using shared pointers here, but would like to make a fullcopy. Clearly, we'll need to duplicate the objects the pointers point at, andassign these new pointers to the copied object's container.

The prototype design patttern is commonly used to create copies of objects ofpolymorphic classes, given pointers to their base classes.

To apply the prototype design pattern we have to implementnewCopy in allderived classes. Not by itself a big deal, but static polymorphism can nicelybe used here to avoid having to reimplement this function for each derivedclass.

We start off with an abstract base classVehicleBase declaring a purevirtual membernewCopy:

    struct VehicleBase    {        virtual ~VehicleBase();        VehicleBase *clone() const; // calls newCopy        // declare any additional members defining the         // public user interface here        private:            VehicleBase *newCopy() const = 0;       };

Next we define a static polymorphic classCloningVehicle which is derivedfromVehicleBase (note that we thus combine dynamic and staticpolymorphism). This class provides the generic implementation ofnewCopy. This is possible because all derived classes can use thisimplementation. Also,CloningVehicle will be re-implemented for eachconcrete type of vehicle that is eventually used: aCar, aTruck, anAmphibiousVehicle, etc, etc.CloningVehicle thus isn't shared (likeVehicleBase), but instantiated for each new type of vehicle.

The core characteristic of a statically polymorphic class is that it can useits class template type parameter via astatic_cast of its own type. Amember function likenewCopy is implemented always the same way, viz.,by using the derived class's copy constructor. Here is the classCloningVehicle:

    template <class Derived>    class CloningVehicle: public VehicleBase    {        VehicleBase *newCopy() const        {            return new Derived(*static_cast<Derived const *>(this));        }    };

And we're done. All types of vehicles should now be derived fromCloningVehicle, which automatically provides them with their ownimplementation ofnewCopy. E.g., a classCar looks like this:

    class Car: public CloningVehicle<Car>    {        // Car's interface, no need to either        // declare or implement newCopy,        // but a copy constructor is required.    };

Having defined astd::vector<VehicleBase *> original we could create acopy oforiginal like this:

    for(auto pointer: original)        duplicate.push_back(pointer->clone());

Irrespective of the actual type of vehicle to which the pointers point,theirclone members will return pointers to newly allocated copies ofobjects of their own types.

22.13: Class templates and nesting

    template <typename Type>    class PtrVector: public std::vector<Type *>

The nested class defines its constructor as a private member, and allowsPtrVector<Type> objects access to its private members. Therefore onlyobjects of the surroundingPtrVector<Type> class type are allowed toconstruct theiriterator objects. However,PtrVector<Type>'s clientsmay constructcopies of thePtrVector<Type>::iterator objects theyuse.

Here is the nested classiterator, using a (required)frienddeclaration. Note the use of thetypename keyword: sincestd::vector<Type *>::iterator depends on a template parameter, it is notyet an instantiated class. Thereforeiterator becomes an implicittypename. The compiler issues a warning iftypename has beenomitted. 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*();            };

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

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

    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 and using declarations can also be definedby class templates. The classTable, mentioned before (section22.11.3) inherited the enumerationTableType::FillDirection. HadTable been implemented as a full class template, then this enumerationwould have been defined inTable 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 bespecified when referring to aFillDirection value or to its type. Forexample (assumingiter andnCols are defined as in section22.11.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);

22.14: Constructing iterators

To ensure that an object of a class is interpreted as a particular type ofiterator, the class must be designed so that it satisfies the requirements ofthat type of iterator. The interface of a class implementing an iterator usesiterator_tags, which are available when including the<iterator> header file.

Iterator classes should provide the followingusing declarations:

• iterator_category, specifying the iterator's tag, as in

     using iterator_category = std::random_access_iterator_tag;

• differenct_type, defining the type representing differences between pointers, commonly:

     using difference_type = std::ptrdiff_t;

• value_type, defining the data type of a dereferenced iterator. E.g.,

     using value_type = std::string;

• pointer, defining the iterator's pointer type which can also be defined as aconst pointer. E.g.,

     using pointer = value_type *; // or maybe:    using pointer = value_type const *;

• reference, defining the iterator's pointer type which can also be defined as aconst pointer. E.g.,

     using reference = value_type &; // or maybe:    using reference = value_type const &;

Theseusing declarations are commonly encountered in the publicsections of iterators, which therefore might be defined as structs. Here's anexample of how an iterator's interface could be designed:

    struct Iterator    {        using iterator_category = std::random_access_iterator_tag;        using difference_type   = std::ptrdiff_t;        using value_type        = std::string;        using pointer           = value_type *;        using reference         = value_type &;         friend bool operator==(iterator const &lhs, iterator const &rhs);        friend auto operator<=>(Iterator const &lhs, Iterator const &rhs);        friend int operator-(Iterator const &lhs, Iterator const &rhs);        friend Iterator operator+(Iterator const &lhs, int step);        friend Iterator operator-(Iterator const &lhs, int step);     private:        // private data members     public:        // public members    private:        // private support members    }

• a prefix increment operator (Iterator &operator++());
• a dereference operator (Type &operator*());
• a 'pointer to' operator (Type *operator->());
• comparison operators testing the (in)equality of two iterator objects(preferably free operators, likebool operator==(Iterator const &lhs, Iterator const &rhs),bool operator!=((Iterator const &lhs, Iterator const &rhs))). Instead ofoperator!= the `spaceship operator (operator<=>) can also be used, allowing ordering of the iterators.

When iterators are used in the context of generic algorithms they must meetadditional requirements. These are required because generic algorithms performchecks on the types of the iterators they receive. Simple pointers are usuallyaccepted, but if an iterator-object is used the generic algorithm mightrequire the iterator to specify what type of iterator it represents.

The type of iterator that is implemented is indicated by the class'siterator_category. The six standard iterator categories are:

• std::input_iterator_tag. This tag is used whenthe iterator class defines anInputIterator. Iterators of this type allowreading operations, iterating from the first to the last element of the seriesto which the iterator refers.

  The InputIterator dereference operator could be declared as follows:

      value_type const &operator*() const;

  or, in a concrete implementation the data type specified atusingvalue_type = ... could be used instead tovalue_type. Except for thestandard operators there are no further requirements for InputIterators.

• std::output_iterator_tag. This tag is used whenthe iterator class defines anOutputIterator. Iterators of this type allowassignments to their dereferenced iterators. Therefore, the OutputIteratordereference operator is usually declared as:

      value_type &operator*();

  Except for the standard operators there are no further requirements forOutputIterators.

• std::forward_iterator_tag. This tag is usedwhen the iterator class defines aForwardIterator. Iterators of this typeallow readingand assignment operations, iterating from the first to thelast element of the series to which the iterator refers. Therefore, theForwardIterator dereference operator should be declared as follows:

      value_type &operator*();

  and it could also declare an overloadedoperator*() const:

      value_type const &operator*() const;

  Except for the standard operators there are no further requirements forForwardIterators.

• std::bidirectional_iterator_tag. Thistag is used when the iterator class defines aBidirectionalIterator. Iterators of this type allow readingandassignment operations, iterating step by step, possibly in either direction,over all elements of the series to which the iterator refers.

  The Bidirectional dereference operator should allow assignment to the dataits dereference operator refers to and it should allow steppingbackward. BidirectionalIterator should therefore, in addition to the standardoperators required for iterators, offer the following operators:

      value_type &operator*(); // any maybe its const-overload    Iterator &operator--();

• std::random_access_iterator_tag. This tag isused when the iterator class defines aRandomAccessIterator. Theseiterators are like Bidirectional iterators, but in addition allow stepping tothe next iterator usingint step sizes (the resulting iterator may pointto a location outside of the valid iterator range. Like other iterators,RandomAccessIterators do not check the validity of the obtained iterator).

  In addition to the members offered by the BidirectionalIterator, RandomAccessIterators provide the following operators:

  • Type operator-(Iterator const &rhs) const, returning the number ofdata elements between the current andrhs iterator (returning a negativevalue ifrhs refers to a data element beyond the data elementthisiterator refers to);
  • Iterator operator+(int step) const, returning an iterator referringto a data elementstep data elements beyond the data elementthisiterator refers to;
  • Iterator operator-(int step) const, returning an iterator referringto a data elementstep data elements before the data elementthisiterator refers to;
  • bool operator<(Iterator const &rhs) const, returningtrue ifthe data elementthis iterator refers to is located before the dataelement therhs iterator refers to.
• std::contiguous_iterator_tag. This tag isused when the iterator class defines aContiguousIterator. These iteratorsoffer the same facilities as the RandomAccessIterators, but it is theresponsibility of the software engineer to ensure that the elements to whichthe iterators refer are stored contiguously in memory.

Each iterator tag assumes that a certain set of operators isavailable. TheRandomAccessIterators antContiguousIterators are themost complex, as other iterators only offer subsets of their facilities.

Note that iterators are always defined over a certain range([begin, end)). Increment and decrement operations may result inundefined behavior of the iterator if the resulting iterator value would referto a location outside of this range.

Normally iterators of classes merely accesses the data elements of thoseclasses. Internally, an iterator might use an ordinary pointer but it ishardly ever necessary for the iterator to allocate memory. Therefore,iterators normally don't need to define copy constructors and assignmentoperators. For the same reason iterators usually don't require destructors.

Most classes offering members returning iterators do so by having membersconstruct the required iterators that are thereupon returned as objects. Asthecaller of these member functions only has touse or sometimescopy the returned iterator objects, there is usually no need to providepublicly available constructors, except for the copy constructor (which isavailable by default). Therefore additional constructors are usually defined asprivate orprotected members. To allow an outer class to createiterator objects, the iterator class usually declares the outer class as itsfriend.

In the following sections aRandomAccessIterator, and areverseRandomAccessIterator is covered. The container class for which a randomaccess iterator must be developed may actually store its data elements in manydifferent ways (e.g., using containers or pointers to pointers). Section26.5 contains an example of a self-made template iterator class.

The random access iterator developed in the next sections reaches dataelements that are only accessible through pointers. The iterator class isdesigned as an inner class of a class derived from a vector of stringpointers.

22.14.1: Implementing a `RandomAccessIterator'

    #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

Assume that we want to use thesort generic algorithm withStringPtr objects. This algorithm (see section19.1.54) requires twoRandomAccessIterators. Although these iterators are available (viastd::vector'sbegin andend members), they return iterators tostd::string *s. When comparingstring * values the pointer valuesinstead of the content of the strings are compared, which is not what we want.

To remedy this, an internal typeStringPtr::iterator is defined,not returning iterators to pointers, but iterators to theobjects thesepointers point to. Once thisiterator type is available, we can add thefollowing members to ourStringPtr class interface, hiding the identicallynamed, 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 aStringPtr object can easily be sorted:

    int main()    {        StringPtr sp;               // assume sp is somehow filled        sort(sp.begin(), sp.end()); // sp is now sorted    }

To make this work, a typeStringPtr::iterator is defined. As suggested byits type name,iterator is a nested type ofStringPtr. To use aStringPtr::iterator in combination with thesort generic algorithm itmust be aRandomAccessIterator, whosevalue_type is astd::string. Therefore, the iterator specifies:

    using iterator_category = std::random_access_iterator_tag;    using difference_type   = std::ptrdiff_t;    using value_type        = std::string;    using pointer           = value_type *;    using reference         = value_type &;

Now we're ready to redesignStringPtr's class interface. It offersmembers returning (reverse) iterators, and a nestediterator class. Hereis its interface:

struct StringPtr: public std::vector<std::string *>{    class iterator;    using reverse_iterator = std::reverse_iterator<iterator>;    iterator begin();    iterator end();    reverse_iterator rbegin();    reverse_iterator rend();};struct StringPtr::iterator{//USING    using iterator_category = std::random_access_iterator_tag;    using difference_type   = std::ptrdiff_t;    using value_type        = std::string;    using pointer           = value_type *;    using reference         = value_type &;

Next we have a look atStringPtr::iterator's characteristics:

• iterator definesStringPtr as its friend, soiterator'sconstructor can be private. Only theStringPtr class itself should be ableto construct iterators. Copy construction and iterator-assignment should bepossible, but that's possible by default and needs no specific declaration orimplementation. Furthermore, since an iterator is already provided byStringPtr's base class, we can use that iterator to access the informationstored in theStringPtr object.

• StringPtr::begin andStringPtr::end may simply returniterator objects. They are implemented like this:

  inline StringPtr::iterator StringPtr::begin(){    return iterator(std::vector<std::string *>::begin());}inline StringPtr::iterator StringPtr::end(){    return iterator(std::vector<std::string *>::end());}

• All ofiterator's remaining members are public. It's very easy toimplement them, mainly manipulating and dereferencing the available iteratord_current. ARandomAccessIterator requires a series of operators. Theyusually have very simple implementations, and can often very well beimplemented inline:
  • iterator &operator++(); the pre-increment operator:

    inline StringPtr::iterator &StringPtr::iterator::operator++(){    ++d_current;    return *this;}

  • iterator operator++(int); the post-increment operator:

    inline StringPtr::iterator StringPtr::iterator::operator++(int){    return iterator(d_current++);}

  • iterator &operator--(); the pre-decrement operator:

    inline StringPtr::iterator &StringPtr::iterator::operator--(){    --d_current;    return *this;}

  • iterator operator--(int); the post-decrement operator:

    inline StringPtr::iterator StringPtr::iterator::operator--(int){    return iterator(d_current--);}

  • iterator &operator=(iterator const &other); the overloaded assignment operator. Sinceiterator objects do not allocate any memory themselves, the default assignment operator can be used.
  • bool operator==(iterator const &rhv) const; testing the equality of twoiterator objects:

    inline bool operator==(StringPtr::iterator const &lhs,                       StringPtr::iterator const &rhs){    return lhs.d_current == rhs.d_current;}

  • auto operator<=>(iterator const &rhv) const; testing the ordering of twoiterator objects:

    inline auto operator<=>(StringPtr::iterator const &lhs,                        StringPtr::iterator const &rhs){    return lhs.d_current <=> rhs.d_current;}

  • int operator-(iterator const &rhv) const; returning the number of elements between the element pointed to by the left-hand side iterator and the right-hand side iterator (i.e., the value to add to the left-hand side iterator to make it equal to the value of the right-hand side iterator):

    inline int operator-(StringPtr::iterator const &lhs,                     StringPtr::iterator const &rhs){    return lhs.d_current - rhs.d_current;}

  • Type &operator*() const; returning a reference to the object to which the current iterator points. With anInputIterator and with allconst_iterators, the return type of this overloaded operator should beType const &. This operator returns a reference to a string. This string is obtained by dereferencing the dereferencedd_current value. Asd_current is an iterator tostring * elements, two dereference operations are required to reach the string itself:

    inline std::string &StringPtr::iterator::operator*() const{    return **d_current;}

  • iterator operator+(int stepsize) const; this operator advances the current iterator bystepsize:

    inline StringPtr::iterator operator+(StringPtr::iterator const &lhs,                                                                int step){    StringPtr::iterator ret{ lhs };    ret.d_current += step;          // avoids ambiguity    return ret;}

  • iterator operator-(int stepsize) const; this operator decreases the current iterator bystepsize:

    inline StringPtr::iterator operator-(StringPtr::iterator const &lhs,                                                                int step){    StringPtr::iterator ret{ lhs };    ret.d_current -= step;          // avoids ambiguity    return ret;}

  • std::string *operator->() const is an additionally added operator. Here only one dereference operation is required, returning a pointer to the string, allowing us to access the members of a string via its pointer.

    inline std::string *StringPtr::iterator::operator->() const{    return *d_current;}

  • Two more additionally added operators areoperator+= andoperator-=. They are not formally required byRandomAccessIterators, but they come in handy anyway:

    inline StringPtr::iterator &StringPtr::iterator::operator+=(int step){    d_current += step;    return *this;}inline StringPtr::iterator &StringPtr::iterator::operator-=(int step){    d_current -= step;    return *this;}

22.14.2: Implementing a `reverse_iterator'

To implement a reverse iterator forStringPtr we only need to definethereverse_iterator type in its interface. This requires us to specifyonly one line of code, which must be inserted after the interface of the classiterator:

    using reverse_iterator = std::reverse_iterator<iterator>;

Also, the well-known membersrbegin andrend are added toStringPtr'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());}

The following program illustrates the use ofStringPtr'sRandomAccessIterator:

    #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    */

Assume we would like to process all lines stored invector<string>lines up to any trailing empty lines (or lines only containing blanks) itmight contain. How should we proceed? One approach is to start the processingfrom the first line in the vector, continuing until the first of the trailingempty lines. However, once we encounter an empty line it does of course nothave to be the first line of the set of trailing empty lines. In that case,we'd better use the following algorithm:

• First, use

      rit = find_if(lines.rbegin(), lines.rend(), NonEmpty());

  to obtain areverse_iterator rit pointing to the last non-empty line.

• Next, use

      for_each(lines.begin(), --rit, Process());

  to process all lines up to the first empty line.

    for_each(lines.begin(), &*--rit, Process());

When defining aconst_reverse_iterator (e.g., matching aconst_iterator class), then theconst_iterator's operator* membershould be a member returning a non-modifiable value or object. Since aconst_reverse_iterator uses the iterator'soperator-- member,we're running against a small conceptual conflict. On the one hand, astd::input_iterator_tag is inappropriate, since we must allow decrementingthe iterator. On the other hand, astd::bidirectional_iterator isinappropriate, since we don't allow modification of the data.

Iterator tags are primarily conceptual. Ifconst_iterators andconst_reverse_iterators only allow increment operations, then aninput_iterator_tag is the best match for the iterator's intendeduse. Hence this tag is used below.

Furthermore, in line with the nature of ainput_iterator_tag ourconst_iterator should not offer anoperator--. This, of course,causes problems: a reverse iterator must be able to use the iterator'soperator-- member. This can easily be solved by stashing the iterator'soperator-- in the iterator's private section, and declaringstd::reverse_iterator<(const_)iterator> its friend (note that declaring a(const_)reverse_iterator that is derived fromstd::reverse_iteratordoesn't solve the issue: it isstd::reverse_iterator that calls theiterator'soperator--, not a class that is derived from it).

To keep the const-ness of dereferencingconst_iterator iteratorsusing specification can added to theconst_iterator class. Theusing specifications provided byData::iterator are inherited byData::const_iterator, butData::const_iterator may also specify:

    using const_pointer   = value_type const *;    using const_reference = value_type const &;

The elements involved in defining aniterator, const_iterator,reverse_iterator andconst_reverse_iterator for a classData isillustrated in the following example, which only requires the definitions oftheiterator andconst_iterator classes, as these types can be passedto thereverse_iterator template to obtain the correspondingreverse-iterators:

    // compile only: members only declared, not implemented#include <string>#include <iterator>#include <iostream>struct Data{    class iterator;    class const_iterator;    using reverse_iterator = std::reverse_iterator<iterator>;    using const_reverse_iterator = std::reverse_iterator<const_iterator>;    private:        std::string *d_data;        size_t d_n;    public:        // ...};struct Data::iterator{    using iterator_category = std::bidirectional_iterator_tag;    using difference_type   = std::ptrdiff_t;    using value_type        = std::string;    using pointer           = value_type *;    using reference         = value_type &;    friend class Data;    private:        pointer d_current;    public:        iterator() = default;        iterator &operator++();        iterator &operator--();        std::string &operator*();    private:        iterator(std::string *data, size_t idx);        friend class std::reverse_iterator<iterator>;};bool operator==(Data::iterator const &lhs, Data::iterator const &rhs);struct Data::const_iterator: public Data::iterator{    using const_pointer   = value_type const *;    using const_reference = value_type const &;    friend class Data;    friend class std::reverse_iterator<const_iterator>;    const_iterator() = default;    const_iterator &operator++();    const_iterator &operator--();    const_reference operator*() const;    // or, in this case: std::string const &operator*() const;    private:        const_iterator(std::string const *data, size_t idx);};bool operator==(Data::const_iterator const &lhs,                Data::const_iterator const &rhs);void demo(){    Data::iterator iter;    Data::reverse_iterator riter(iter);    std::cout << *riter << '\n';    Data::const_iterator citer;    Data::const_reverse_iterator criter(citer);    std::cout << *criter << '\n';};

• Table of Contents
• Previous Chapter
• Next Chapter