- Table of Contents
- Previous Chapter
- Next Chapter

# Chapter 22: Class Templates

Templates can not only be constructed for functions but also for complete classes. Consider constructing a class template when a class should be able to handle different types of data. Class templates are frequently used in C++: chapter 12 discusses data structures like `vector, stack` and `queue`, that are implemented as class templates. With class templates, the algorithms and the data on which the algorithms operate are completely separated from each other. To use a particular data structure in combination with a particular data type only the data type needs to be specified when defining or declaring a class template object (as in `stack<int> iStack`).

In this chapter constructing and using class templates is discussed. In a sense, class templates compete with object oriented programming (cf. chapter 14), that uses a mechanism resembling that of templates. Polymorphism allows the programmer to postpone the implementation of algorithms by deriving classes from base classes in which algorithms are only partially implemented. The actual definition and processing of the data upon which the algorithms operate may be postponed until derived classes are defined. Likewise, templates allow the programmer to postpone the specification of the data upon which the algorithms operate. This is most clearly seen with abstract containers, which completely specify the algorithms and at the same time leave the data type on which the algorithms operate completely unspecified.

There exists an intriguing correspondence between the kind of polymorphism we've encountered in chapter 14 and certain uses of class templates. In their book C++ Coding Standards (Addison-Wesley, 2005) Sutter and Alexandrescu refer to static polymorphism and dynamic polymorphism. Dynamic polymorphism is what we use when overriding virtual members. Using vtables the function that is actually called depends on the type of object a (base) class pointer points at. Static polymorphism is encountered in the context of templates, and is discussed and compared to dynamic polymorphism in section 22.12.

Generally, class templates are easier to use than polymorphism. It is certainly easier to write `stack<int> istack` to create a stack of `ints` than to derive a new class `Istack: public stack` and to implement all necessary member functions defining a similar stack of `ints` using object oriented programming. On the other hand, for each different type for which an object of a class template is defined another, possibly complete class must be reinstantiated. This is not required in the context of object oriented programming where derived classes use, rather than copy, the functions that are already available in their base classes (but see also section 22.11).

Previously we've already used class templates. Objects like `vector<int> vi` and `vector<string> vs` are commonly used. The data types for which these templates are defined and instantiated are an inherent part of such container types. It is stressed that it is the combination of a class template type and its template parameter(s), rather than the mere class template's type that defines or generates a type. So `vector<int>` is a type as is `vector<string>`. Such types could very well be specified through using-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 the implementations of the class member functions, must be available at their points of instantiation. Therefore the interfaces and implementations of class templates are commonly provided in a header file, which is then included by source files using those classes (see also section 21.13).

### 22.0.1: Template Argument Deduction

One important difference between function templates and class templates is that the template arguments of function templates can normally be deduced by the compiler, whereas template arguments of class templates may have to be specified by the user. That's not always required, but since the template types of class templates are an inherent part of the class template's type it must be completely clear to the compiler what the class template's types are.

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 deduces `T == vector<int>`.

On the other hand, if we have

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

we cannot do

        Fun fun;

since `Fun` is not a type, and the compiler cannot deduce what the intended type is.

Sometimes the compiler can deduce the intended types. Consider this:

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

In this case the compiler deduces `int` from the provided values. The compiler is smart enought to select the most general type, as in this example, where `double` is deduced:

        vector vi{ 1, 2.5 };

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

Although it's nice that the compiler is willing and able to deduce types in many situations it's at the same time a potential source of confusion. In the first example only non-negative values are used, so why not define a `vector<unsigned>` or a `vector<size_t>`? In the second example the compiler deduces `vector<double>`, but `vector<float>` could very well also have been used.

To avoid confusion, as a rule of thumb, it might be a good idea to specify the types of class templates when defining class type objects. It requires hardly any effort and it completely clarifies what you want and mean. So prefer

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

over the definitions implicitly using types.

#### 22.0.1.1: Simple Definitions

Here are some examples of how simple definitions where the compiler deduces template arguments can (and cannot) be specified.

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 template `third` is a recipe for constructing `Deduce` objects from a type that's specified for `third`. The pointer's type simply is a pointer to the specified type (so, specifying `third<int>` implies an `int *`). Now that the type of `third`'s argument is available (i.e., an `int *`) the compiler deduces that `third{0}` is a `Deduce<int *>`.

This `Deduce<int *>` object could, e.g., be used to initialize a named `Deduce<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 definitions template argument deduction is realized as follows:

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

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

  is formed.

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

Let's apply this process to the class `Deduce`. The set of imaginary functions matching `Deduce` 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 construction `Deduce first{1}` the first imaginary function wins the overload contest, resulting in the template argument deduction `int` for `class ...Types`, and hence `Deduce<int> first{1}` is defined.

Note that when a class template is nested under a class template, the nested class template's name depends on the outer class type. The outer class then provides the name qualifier for the inner class template. In such cases template argument deduction is used for the nested class, but (as it is not used for name qualifiers) is not used for the outer class. Here is an example: adding a nested class template to `Outer`:

        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 calling `imaginary(2.0, 1)` results in `double` for its first argument and `int` for its second. Overload resolution then favors the last imaginary function, and so `ExtraType: double` and `InnerType: 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

Have a look at the following class interface:

        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 the `Class` constructor expecting two `Class::Iterator` arguments would probably be somewhat similar to the following:

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

where `d_data` is some container storing `T` values. A `Class` object can now constructed from a pair of `Class::Iterators`:

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

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

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

When attempting to instantiate a `Class` object by passing it `Class::Iterators` the compiler cannot directly deduce from the provided arguments that a `Class<Class::Iterator::type>` is to be used: `type` isn't directly available. Compare this to `Class'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 case `Type` clearly is an `int`, and so a `Class<int>` object is constructed.

When we try to do this for `Class(Iterator, Iterator)` we get

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

and here `Class's` template argument isn't directly related to `Iterator`: the compiler cannot deduce its type and consequently compilation fails.

A similar argument applies to the fourth constructor, which receives two `Tp` arguments, which are both independent from `Class's` template type.

In cases like these simple type template argument deduction procedure fails. Still, not everything is lost: explicit conversions, defined as explicitly specified deduction rules which are added (below) to the class's interface can be used.

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

        class template constructor signature -> resulting class type ;

Let's apply this to `Class(Iterator begin, Iterator end)`. Its signature is

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

Requiring that `Iterator` defines a typename `type`, we can now formulate a resulting class type:

        Class<typename Iterator::type>

Now we can combine both in an explicitly specified deduction rule (which is added as a separate line below `Class's` interface):

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

After adding this deduction rule to `Class's` interface the following constructor 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 merely referring to the class name: when referring to `Class` in the class `Class`, the compiler considers `Class` to be `Class<T>`. So the headers of the declaration and definition of `Class's` copy constructor look like this:

        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 required type must explicitly be specified. Consider what happens if add a member `dup` to `Class`:

        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 inside `Class` the compiler deduces that `Class<T>` must be returned. But in the previous section we decided that, when initializing `Class` from iterators, `Class<typename Tp::type>` should be constructed and returned. To accomplish that, the required type is explicitly 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 not have to be used: they can be used in many standard situations where explicitly specifying the class's template arguments appears to be superfluous. Template argument deduction was added to the language to simplify object construction when using class templates. But in the end you don't have to use these deduction rules: it's always still possible to explicitly specify template arguments.

## 22.1: Defining class templates

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

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

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

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

### 22.1.1: Constructing the circular queue: CirQue

The construction of a class template is illustrated in this section. Here, we'll develop the class template `CirQue` (circular queue). This class template has one template type parameter, `Data`, representing the data type that is stored in the circular queue. The outline of the interface of this class template looks like this:

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

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

- The keyword `template`, starting a template definition or declaration.
- The angle bracket enclosed list following `template`: a list containing one or more comma-separated elements is called the template parameter list. Template parameter lists may have multiple elements, like this:

          typename Type1, typename Type2, typename Type3

  When a class template defines multiple template type parameters they are matched in sequence with the list of template type arguments provided when defining 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 the formal type name (`Data` for `CirQue`). It is a formal (type) name, like the formal types used in function template parameter lists.
- Following the template header the class interface is defined. It may use the formal type names defined in the template header as type names.

Once the `CirQue` class template has been defined it can be used to create all kinds of circular queues. As one of its constructors expects a `size_t` argument defining the maximum number of elements that can be stored in the circular queue, circular queues could be defined like this:

        CirQue<int> cqi(10);            // max 10 ints
        CirQue<std::string> cqstr(30);  // max 30 strings

As noted in the introductory section of this chapter the combination of name of the class template and the data type for which it is instantiated defines a data type. Also note the similarity between defining a `std::vector` (of some data type) and a `CirQue` (of some data type).

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

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

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

### 22.1.2: Non-type parameters

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

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

Different from function template non-type parameters the values of class template non-type parameters are not deduced by the compiler using arguments passed to class template members.

Assume we extend our design of the class template `CirQue` so that it defines a second (non-type) parameter `size_t Size`. Our intent is to use this `Size` parameter in the constructor defining an array parameter of `Size` elements of type `Data`.

The `CirQue` class template now becomes (only showing the relevant constructor):

        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 of template non-type parameters are not deduced by the compiler. When the compiler is asked to compile the following `main` function it reports a mismatch between the required and actual number of template parameters:

        int main()
        {
            int arr[30];

            CirQue<int> ap{ arr };
        }
        /*
            Error reported by the compiler:

            In function `int main()':
                error: wrong number of template arguments (1, should be 2)
                error: provided for `template<class Data, size_t Size>
                       class CirQue'
        */

Defining `Size` as a non-type parameter having a default value doesn't work either. The compiler always uses the default unless its value is explicitly specified. Reasoning that `Size` can be 0 unless we need another value, we might be tempted to specify `size_t Size = 0` in the template's parameter type list. Doing so we create a mismatch between the default value 0 and the actual size of the array `arr` as defined in the above `main` function. The compiler, using the default value, reports:

        In instantiation of `CirQue<int, 0>':
        ...
        error: creating array with size zero (`0')

So, although class templates may use non-type parameters they must always be specified like type parameters when an object of that class is defined. Default values can be specified for those non-type parameters causing the compiler to use the default when the non-type parameter is left unspecified.

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

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

- Global variables have constant addresses, which can be used as arguments for non-type parameters.
- Local and dynamically allocated variables have addresses that are not known by the compiler when the source file is compiled. These addresses can therefore not be used as arguments for non-type parameters.
- Lvalue transformations are allowed: if a pointer is defined as a non-type parameter, an array name may be specified.
- Qualification conversions are allowed: a pointer to a non-const object may be used with a non-type parameter defined as a `const` pointer.
- Promotions are allowed: a constant of a `narrower' data type may be used when specifying a default argument for a non-type parameter of a `wider' type (e.g., a `short` can be used when an `int` is called for, a `long` when a `double` is called for).
- Integral conversions are allowed: if a `size_t` parameter is specified, an `int` may be used as well.
- Variables cannot be used to specify template non-type parameters as their values are not constant expressions. Variables defined using the `const` modifier, however, may be used as their values never change.

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

### 22.1.3: Member templates

Our previous attempt to define a template non-type parameter that is initialized by the compiler to the number of elements of an array failed because the template's parameters are not implicitly deduced when a constructor is called. Instead, they must explicitly be specified when an object of the class template is defined. As the template arguments are specified just before the template's constructor is called the compiler doesn't have to deduce anything and it can simply use the explicitly specified template arguments.

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

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

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

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

        template <typename Data>
        class CirQue
        {
            public:
                template <size_t Size>
                explicit CirQue(Data const (&arr)[Size]);
        };

Its implementation becomes:

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

The implementation uses the STL's `copy` algorithm and a `back_inserter` adapter to insert the array's elements into the `CirQue`. To use the `back_inserter` `CirQue` must provide two (public) using-declarations (cf. section 18.2.2):

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

Member templates have the following characteristics:

- Two `template` headers must be used: the class template's `template` header is specified first followed by the member template's template header;
- Normal access rules apply: the member template can be used by programs to construct an `CirQue` object of a given data type. As usual for class templates, the data type must be specified when the object is constructed. To construct a `CirQue` object from the array `int array[30]` we define:

      CirQue<int> object(array);

- Any member can be defined as a member template, not just a constructor;
- When a template member is implemented below its class interface, the template class header must precede the function template header of the member template;
- The implementation of the member template must specify its proper scope. The member template is defined as a member of the class `CirQue`, instantiated for the formal template parameter type `Data`;
- The template parameter names in the declaration and implementation must be identical;
- The member template should be defined inside its proper namespace environment. The organization of files defining class templates within a namespace 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 the above member template a `CirQue<Data>::CirQue(Data const *data)` has been defined. Some (here not further elaborated) protocol could be defined allowing the constructor to determine the number of elements that should be stored in the `CirQue` object. When we now define

        CirQue<int> object{ array };

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

The compiler selects this latter constructor as it is a more specialized version of a constructor of the class `CirQue` than the member template (cf. section 21.14). Problems like these can be solved by defining the constructor `CirQue(Data const *data)` into a member template as well or by defining a constructor using two parameters, the second parameter defining the number of elements to copy.

When using the former constructor (i.e., the member template) it must define a template type parameter `Data2`. Here ``Data`' cannot be used as template parameters of a member template may not shadow template parameters of its class. Using `Data2` instead of `Data` takes care of this subtlety. The following declaration of the constructor `CirQue(Data2 const *)` could appear in `CirQue`'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 two `CirQue` objects:

        int main()
        {
            int array[30];
            int *iPtr = array;

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

### 22.1.4: CirQue's constructors and member functions

It's time to return to `Cirque`'s design and construction again.

The class `CirQue` offers various member functions. Normal design principles should be adhered to when constructing class template members. Class template type parameters should preferably be defined as `Type const &`, rather than `Type`, to prevent unnecessary copying of large data structures. Template class constructors should use member initializers rather than member assignment within the body of the constructors. Member function definitions should preferably not be provided in-class but below the class interface. Since class template member functions are function templates their definitions should be provided in the header file offering the class interface. They may be given the `inline` attribute.

`CirQue` declares several constructors and (public) members (their definitions are provided as well; all definitions are provided below the class interface).

Here are the constructors and the destructor:

- `explicit CirQue(size_t maxSize = 0)`:
  Constructor initializing a `CirQue` capable of storing `max_size Data` elements. As the constructor's parameter is given a default argument value this constructor can also be used as a default constructor, allowing us to define, e.g., vectors of `CirQue`s. The constructor initializes the `Cirque` object's `d_data` member to a block of raw memory and `d_front` and `d_back` are initialized to `d_data`. As class template member functions are themselves function templates their implementations outside of the class template's interface must start with the class template's template header. Here is the implementation of the `CirQue(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 no special features. It uses a private support member `inc` to increment `d_back` (see below) and placement new to copy the other's `Data` elements to the current object. The implementation of the copy constructor is straightforward:

          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 merely initializes the current object's `d_data` pointer to 0 and swaps (see the member `swap`, below) the temporary object with the current object. `CirQue`'s destructor inspects `d_data` and immediately returns 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 declared as a member template, providing the `Size` non-type parameter. It allocates room for `Size` data elements and copies `arr`'s content to the newly allocated 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 acts very much like the previous one, but is provided with a pointer to the first `Data` element and with a `size_t` providing the number of elements to copy. In our current design the member template variant of this constructor is left out of the design. As the implementation of this constructor is very similar to that of the previous constructor, it is left as an exercise to the reader.

- `~CirQue()`:
  The destructor inspects the `d_data` member. If it is zero then nothing has been allocated and the destructor immediately returns. This may occur in two situations: the circular queue contains no elements or the information was grabbed from a temporary object by some move operation, setting the temporary's `d_data` member to zero. Otherwise `d_size` elements are destroyed by explicitly calling their destructors followed by returning the element's raw memory to the common pool. 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 are `Cirque`'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 calls `swap` 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 by `d_front` from the `CirQue`. Throws an exception if the `CirQue` is empty. The exception is thrown as a `CirQue<Data>::EMPTY` value, defined by the `enum CirQue<Data>::Exception` (see `push_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 the `CirQue`. Throws a `CirQue<Data>::FULL` exception if the `CirQue` is full. The exceptions that can be thrown by a `CirQue` are defined in its `Exception` enum:

          enum Exception
          {
              EMPTY,
              FULL
          };

  A copy of `object` is installed in the `CirQue`'s raw memory using placement `new` and its `d_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 current `CirQue` object with another `CirQue<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);
          }

The remaining public members all consist of one-liners and were implemented as inline function templates:

- `Data &back()`:
  returns a reference to the element pointed at by `d_back` (undefined result if the `CirQue` 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 by `d_front` (undefined result if the `CirQue` is empty);

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

- `bool empty() const`:
  returns `true` if the `CirQue` is empty;

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

- `bool full() const`:
  returns `true` if the `CirQue` 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 the `CirQue`;

          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 the `CirQue`;

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

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

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

### 22.1.5: Using CirQue objects

When objects of a class template are instantiated, only the definitions of all the template's member functions that are actually used must have been seen by the compiler.

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

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

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

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

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

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

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

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

This program produces the following output:

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

### 22.1.6: Default class template parameters

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

When defining defaults keep in mind that they should be suitable for the majority of instantiations of the class. E.g., for the class template `CirQue` the template's type parameter list could have been altered by specifying `int` as its default type:

        template <typename Data = int>

Even though default arguments can be specified, the compiler must still be informed that object definitions refer to templates. When instantiating class template objects using default template arguments the type specifications may be omitted but the angle brackets must be retained. Assuming a default type for the `CirQue` class, an object of that class may be defined as:

        CirQue<> intCirQue(10);

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

        template <typename Data>

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

### 22.1.7: Declaring class templates

Class templates may also be declared. This may be useful in situations where forward class declarations are required. To declare a class template, simply remove its interface (the part between the curly braces):

        template <typename Data>
        class CirQue;

Default template arguments may also be specified when declaring class templates. However, default template arguments cannot be specified for both the declaration and the definition of a class template. As a rule of thumb default template arguments should be omitted from declarations, as class template declarations are never used when instantiating objects but are only occasionally used as forward references. Note that this differs from default parameter value specifications for member functions in ordinary classes. Such defaults are always specified when declaring the member functions in the class interface.

### 22.1.8: Preventing template instantiations

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

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

        extern template class std::vector<int>;

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

    #include <vector>
    #include <iostream>
    using namespace std;

    extern template class vector<int>;

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

But be careful:

- The declaration by itself does not make the class definition available. The `vector` header file still needs to be included to make the features of the class vector known to the compiler. But due to the `extern template` declaration none of the used members will be instantiated for the current compilation unit;
- The compiler assumes (as it always does) that what is declared has been implemented elsewhere. In this case the compiler encounters an implicit declaration: the features of the vector class that are actually used by the above program are not individually declared but they are declared as a group, using the `extern template` declaration. This not only holds true for explicitly used members but hidden members (copy constructors, move constructors, conversion operators, constructors called during promotions, to name a few): all are assumed by the compiler to have been instantiated elsewhere;
- Although the above source file compiles, the instantiations of the templates must be available before the linker can build the final program. To accomplish this one or more source files may be constructed in which all required instantiations are made available.

  In a stand-alone program one might postpone defining the required members and wait for the linker to complain about unresolved external references. These may then be used to create a series of instantiation declarations which are then linked to the program to satisfy the linker. Not a very simple task, though, as the declarations must strictly match the way the members are declared in the class interface. An easier approach is to define an instantiation source file in which all facilities that are used by the program are actually instantiated in a function that is never called by the program. By adding this instantiation function to the source file containing `main` we can be sure that all required members are instantiated 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 matching instantiation declaration of a class template (e.g., for `std::vector<int>`) looks like this:

      template class std::vector<int>;

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

- On the other hand, if it is known that the required template members have already been instantiated elsewhere, then an extern template declaration can be used to prevent member instantiations in the current compilation unit, which may speed up compilation. E.g.,

              // the compiler assumes that required members of
              // vector<int> have already been instantiated elsewhere
      extern template class std::vector<int>;

      int main()
      {
          std::vector<int> vi(5);     // constructor and operator[]
          ++vi[0];                    // are NOT instantiated
      }

### 22.1.9: Template parameter initialization

Class templates commonly specify their parameter types, which types are then used to define, e.g., the parameters of their members. But template parameter types can also, somewhat comparable to the way template function parameter types are determined, be derived from the actually used template arguments, which is called template parameter initialization. Template parameter types which are derived from the actually used template argument values start with `auto` as illustrated in the following example (the examples in this section use in-class implementations for brevity and assume `#include <iostream>` and `using namespace std`):

        template <auto val> struct Demo
        {
            Demo()
            {
                cout << val << '\n';
            }
        };

        int main()
        {
            Demo<12> d1;
            Demo<'a'> d2;
        }

This program shows, respectively, `12` (an `int`) and `a` (a `char`). Those types are determined from the actually used template parameter arguments, and the argument name(s) can be used by the template class's members.

Those members are available inside the class template as `constexpr` data members. Since they are `constexpr` data members the compiler must be able to construct those arguments compile-time. Consequently, when specifying a template argument using a class object only the object's `const` members can be used, and that object's class cannot declare `mutable` data members, illustrated by the next example:

        struct Accepted
        {
            int d_val = 10;
            void unchanged() const
            {
                cout << d_val << '\n';
            }
            void changed()              // OK: not used by Demo below
            {
                cout << ++d_val << '\n';
            }
        };

        struct Rejected
        {
            mutable int d_val = 10;     // 'Rejected' can't be used by
                                        // Demo because of 'mutable'
            void unchanged() const
            {
                cout << d_val << '\n';
            }
            void changed()              // OK: not used by Demo below
            {
                cout << ++d_val << '\n';
            }
        };

        template <auto val> struct Demo
        {
            Demo()
            {
                val.unchanged();
            }
        };

        int main()
        {
            Demo<Accepted{}> sa;
            // Demo<Rejected{}> sr;     // won't compile
        }

Assuming the class's template parameter is defined as used above as `auto val` then `val's` type can be obtained with a `using` declaration. E.g.,

        template <auto val> struct Demo
        {
            using Type = decltype(val);
            ...
        }

and `Type` can be used to define such data members or to refer to such types when specifying member function parameters. Such `Type` variables are not by default immutable:

        template <auto val> struct Demo
        {
            using Type = decltype(val);
            Type d_val = val;
            Demo()
            {
                cout << ++d_val << '\n';
            }
        }

Initialized template parameters become (immutable) data members which can be used in the class template's members. In the next example the class template's `Adder` defines an initialized template parameter `auto add` whose value is added to the elements of a `std::vector`. Also, all the initial elements of the vector are summed, which value is then retrieved by the member `total`:

        #include <vector>
        #include <string>

        template <auto val> class Adder
        {
            using Type = decltype(val);

            Type d_sum = Type();            // initialize d_sum

            public:
                Adder()
                {
                    cout << "adding " << val << "\n\n";
                }
                                            // append 'val' to vect's elements
                void append(std::vector<Type> &vect)
                {
                    for (auto &elem: vect)
                    {
                        d_sum += elem;
                        elem += val;
                    }
                }
                                            // show vect's elements
                void show(std::vector<Type> const &vect) const
                {
                    for (auto &elem: vect)
                        cout << elem << '\n';
                    cout.put('\n');
                }

                Type const &total() const   // show vect elements' original sum
                {
                    return d_sum;
                }
        };

        template <auto val>
        void process(vector<decltype(val)> &vect)
        {
            Adder<val> adder;
            adder.show(vect);
            adder.append(vect);
            adder.show(vect);
            cout << "original sum: " << adder.total() << "\n\n";
        }

        int main()
        {
            vector<int> vi{1, 2, 3, 4};
            process<3>(vi);                     // add 3 to the vi's elements

            vector<double> vd{1.1, 2.2, 3.3, 4.4};
            process<3.5>(vd);                   // add 3.5 to the vd's elements
        }

### 22.1.10: Generic lambda expressions

Like template parameter initializations generic lambda expressions may use `auto` to define their parameters. When used, a lambda expression is instantiated by looking at the actual types of arguments. Since `auto` is generic, different parameters defined using `auto` can be instantiated to different types. Here is an example (assuming all required headers and namespace declaration were specified):

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

The generic lambda function is defined in lines 3 through 6, and is assigned to the `lambda` identifier. Then, `lambda` is passed to `accumulate` in lines 12 and 13. In line 12 it is instantiated to add `int` values, in line 13 to add `std::string` values: the same `lambda` is instantiated to two completely different functors, which are only locally available in `main`.

Generic lambda expressions are in fact class templates. To illustrate: the above example of a generic lambda expression could also have been implemented using 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 using `auto` in the lambda expression's parameter list obeys the rules of template argument deduction (cf. section 21.4), which are somewhat different from the way `auto` normally operates.

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

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

This lambda function (of course) returns 1: the declared capture deduces the type from the initializer expression as if `auto` had been used.

To use move-initialization `std::move` should be used. E.g., a unique_ptr only supports move-assignment. Here it is used to return one of its 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 keyword `auto` indicates that the compiler determines which types to use when the lambda function is instantiated. A generic lambda expression therefore is a class template, even though it doesn't look like one. As an example, the following lambda expression defines a 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 define `lambda` this way then you should be prepared for complex error messages if the types of the derefenced iterators and lambda's (silently assumed) `str` type don't match.

Here is a little program illustrating how generic lambda expressions can be used in other generic lambda expressions: class templates could also have been used. In lines 1 through 9 a generic lambda expression `accumulate` is defined, defining a second paramater which is used as a function: its argument therefore should be usable as a function. A functor definitely is, an the second generic lambda expression `lambda`, defined in lines 11 through 14 provides it. In line 21 `accumulate` and `lambda` are instantiated so that they operate on (a vector of) `ints`, in line 22 they are instantiated for processing (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 verbose implementations which are not required by templates in general. Consider a generic lambda that specifies an `auto &it` parameter, but in addition it should specify a parameter `value` of type `ValueType` that should be defined by `it's` class. Such a parameter requires the use of a `decltype` (and maybe also the use of `std::decay_t`) to retrieve `it's` actual type. Inside the lambda's body a `using` declaration can be specified to make the type available, but that again requires a verbose specification using `std::decay_t` and `decltype`. 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 defined like ordinary templates, in which case the template header immediately follows the lambda-introducer. Using this alternative form the definition of the `generic` 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

When static members are defined in class templates, they are defined for every new type for which the class template is instantiated. As they are static members, there will only be one member per type for which the class template is instantiated. For example, in a class like:

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

There will be one `TheClass<Type>::objectCounter` for each different `Type` specification. The following object definitions result in the instantiation of just one single static variable, shared among the two objects:

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

Mentioning static members in interfaces does not mean these members are actually defined. They are only declared and must be defined separately. With static members of class templates this is no different. The definitions of static members are usually provided immediately following (i.e., below) the template class interface. For example, the static member `s_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

Here `s_objectCounter` is an `int` and is thus independent of the template type parameter `Type`. Multiple instantiations of `s_objectCounter` for identical `Type`s cause no problem, as the linker will remove all but one instantiation from the final executable (cf. section 21.5).

In list-like constructions, where a pointer to objects of the class itself is required, the template type parameter `Type` must be used when defining the static variable. Example:

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

        template <typename Type>
        TheClass<Type> *TheClass<Type>::s_objectPtr = 0;

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

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

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

### 22.2.1: Extended use of the keyword `typename'

Until now the keyword `typename` has been used to indicate a template type parameter. However, it is also used to disambiguate code inside templates. Consider the following function template:

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

            return t + *ptr;
        }

When this code is processed by the compiler, it complains with an -at first sight puzzling- error message like:

        4: error: 'ptr' was not declared in this scope

The error message is puzzling as it was the programmer's intention to declare a pointer to a type `Ambiguous` defined within the class template `Type`. But the compiler, confronted with `Type::Ambiguous` may interpret the statement in various ways. Clearly it cannot inspect `Type` itself trying to uncover `Type`'s true nature as `Type` is a template type. Because of this `Type`'s actual definition isn't available yet.

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

        Type::Ambiguous *ptr;

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

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

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

            return t + *ptr;
        }

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

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

            public:
                Handler(Container const &container)
                :
                    d_it(container.begin())
                {}
        };

What did we have in mind when designing this class?

- The typename `Container` represents any container supporting iterators.
- The container presumably supports a member `begin`. The initialization `d_it(container.begin())` clearly depends on the template's type parameter, so it's only checked for basic syntactic correctness.
- Likewise, the container presumably supports a subtype `const_iterator`, defined in the class `Container`.

The final consideration is an indication that `typename` is required. If this is omitted and a `Handler` is instantiated the compiler produces a peculiar compilation error:

        #include "handler.h"
        #include <vector>
        using namespace std;

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

        handler.h:4: error: syntax error before `;' token
        */

Clearly the line

        Container::const_iterator d_it;

in the class `Handler` causes a problem. It is interpreted by the compiler as a static member instead of a subtype. The problem is solved using `typename`:

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

An interesting illustration that the compiler indeed assumes `X::a` to be a member `a` of the class `X` is provided by the error message we get when we try to compile `main` using the following implementation of `Handler`'s constructor:

        Handler(Container const &container)
        :
            d_it(container.begin())
        {
            size_t x = Container::ios_end;
        }
        /*
            Reported error:

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

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

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

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

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

            Iterator d_it;
            ...
        };

## 22.3: Specializing class templates for deviating types

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

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

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

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

A completely specialized class has the following characteristics:

- The class template specialization must be provided after the generic class template definition. As it is a specialization the compiler must first have seen the original class template;
- The completely specialized class template's template parameter list is empty;
- All of the class's template parameters are given explicit type names or (for the non-type parameters) explicit values. These explicitations are provided in a template parameter specification list (surrounded by angle brackets) that is inserted immediately after the specialized template's class name;
- All members of the specialized class template use specialized types and values where original template parameters are used in the original template definition;
- All original template's members (maybe with the exception of some constructors) should be redefined by the specialization. If a member is left out of the specialization, it cannot be used for a specialized class template object;
- The specialization may define additional members (but maybe shouldn't as it breaks the one-to-one correspondence between the original and specialized class template);
- Member functions of specialized class templates may be declared by the specializing class and implemented below their class interface. If their implementations follow the class interface they may not begin with a `template <>` header, but must immediately start with the member function's header.

### 22.3.1: Example of a class specialization

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

    #ifndef INCLUDED_CIRQUEVECTOR_H_
    #define INCLUDED_CIRQUEVECTOR_H_

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

    template<>
    class CirQue<std::vector<int>>
    {
        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 specialized `CirQue` class:

    static int iv[] = {1, 2, 3, 4, 5};

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

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

        CirQue<vector<int>> cp;

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

    /*
        Displays:
            5 1 5
            3 3 5
            4 3 6
    */

## 22.4: Partial specializations

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

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

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

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

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

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

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

In the next subsections we'll concentrate on specializing class template non-type template parameters. These partial specializations are now illustrated using some simple concepts defined in matrix algebra, a branch of linear algebra.

### 22.4.1: Intermezzo: some simple matrix algebraic concepts

In this section some simple matrix algebraic terms are introduced. These terms are used in the next sections to illustrate and discuss partial specializations of class templates. Readers proficient in matrix algebra may skip this section without loss of continuity.

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

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

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

        1   2   4   8       A matrix of one row
                            (a 1 x 4 matrix), also known as a
                            `row vector' of 4 elements.
                            (column vectors are analogously defined)

Various operations are defined on matrices. They may, for example be added, subtracted or multiplied. Here we will not focus on these operations. Rather, we concentrate on some simple operations: computing marginals and sums.

Marginals are the sums of row elements or the sums of column elements of a matrix. These two kinds of marginals are also known as, respectively, row marginals and column marginals.

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

The following example shows a matrix, its marginals, and the sum of its values:

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

We'll start out by introducing a class template defining a matrix. Having defined this class template we'll continue with defining several specializations.

Since matrices consist of well defined numbers of rows and columns (the dimensions of the matrix), that normally do not change when matrices are used, we might consider specifying their values as template non-type parameters. The `DataType = double` will be used in the majority of cases. Therefore, `double` can be selected as the template's default type argument. Since it's a sensible default, the `DataType` template type parameter is used last in the template type parameter list.

Our template class `Matrix` begins its life as:

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

What do we want our class template to offer?

- It needs a place to store its matrix elements. This can be defined as an array of ``Rows`' rows each containing ``Columns`' elements of type `DataType`. It can be an array, rather than a pointer, since the matrix' dimensions are known a priori. Since a vector of `Columns` elements (a row of the matrix), as well as a vector of `Row` elements (a column of the matrix) is often used, the class could specify using-declarations to represent 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.,) a constructor initializing the matrix from a stream. A copy or move constructor is not required as the class does not use pointers. Likewise, no overloaded assignment 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's `operator[]` member (and its `const` variant) only handles the first index, returning a reference to a complete `MatrixRow`. How elements in a `MatrixRow` can be retrieved is shortly covered. To keep the example simple, no array bound check has been implemented:

          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 sum of all elements in a `Matrix`. We'll define the type `MatrixColumn` as the type containing the row marginals of a matrix, and the type `MatrixRow` as the type containing the column marginals of a matrix.

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

  Marginals can be considered as special forms of matrices. To represent these marginals we can construct partial specializations defining the class templates `MatrixRow` and `MatrixColumn` objects; and we construct a partial specialization handling `1 x 1` matrices. These partial specializations are used to compute marginals and the sum of all the elements of a matrix.

  Before concentrating on these partial specializations themselves we'll use them here to implement the members computing the marginals and the sum of all elements 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

Class template partial specializations can be defined for any (subset) of template parameters. They can be defined for template type parameters and for template non-type parameters alike. Our first partial specialization defines a row of a generic `Matrix`, mainly (but not only) used for the construction of column marginals. Here is how such a partial specialization is designed:

- The partial specialization starts with a template header defining all template parameters that are not specialized in the partial specialization. This template header cannot specify any defaults (like `DataType = double`) since defaults were already specified by the generic class template definition. The specialization must follow the definition of the generic class template's definition, or the compiler complains that it doesn't know what class is being specialized. Following the template header, the class's interface starts. It's a class template (partial) specialization so the class name must be followed by a template argument list specifying the template arguments used by the partial specialization. The arguments specify explicit types or values for some of the template's parameters. Remaining types are simply copied from the class template partial specialization's template parameter list. E.g., the `MatrixRow` specialization specifies 1 for the generic class template's `Rows` non-type parameter (as we're talking here about a single row). Both `Columns` and `DataType` remain to be specified. The `MatrixRow` partial specialization therefore starts as follows:

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

- A `MatrixRow` holds the data of a single row. So it needs a data member storing `Columns` values of type `DataType`. Since `Columns` is a constant value, the `d_row` data member can be defined as an array:

              DataType d_column[Columns];

- The class template partial specialization's constructors require some attention. The default constructor is simple. It merely initializes the `MatrixRow`'s data elements using `DataType`'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 a `MatrixRow` object with the column marginals of a generic `Matrix` object. This requires us to provide the constructor with a non-specialized `Matrix` parameter.

  The rule of thumb here is to define a member template that allows us to keep the general nature of the parameter. The generic `Matrix` template requires three template parameters. Two of these were already provided by the template specialization. The third parameter is mentioned in the member template's template header. Since this parameter refers to the number of rows of the generic matrix it is simply called `Rows`.

  Here then is the implementation of the second constructor, initializing the `MatrixRow`'s data with the column marginals of a generic `Matrix` 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 a `Matrix` template using the additional `Row` template parameter as well as the template parameters of the partial specialization.
- We don't really require additional members to satisfy our current needs. To access the data elements of the `MatrixRow` an overloaded `operator[]()` is of course useful. Again, the `const` variant can be implemented 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];
          }

Now that we have defined the generic `Matrix` class and the partial specialization defining a single row the compiler selects the row's specialization whenever a `Matrix` is defined using `Row = 1`. For example:

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

### 22.4.4: The MatrixColumn partial specialization

The partial specialization for a `MatrixColumn` is constructed similarly. Let's present its highlights (the full `Matrix` class template definition as well as all its specializations are provided in the `cplusplus.yo.zip` archive (that can be obtained from the C++ Annotations' Gitlab website) in the file `yo/classtemplates/examples/matrix.h`):

- The class template partial specialization once again starts with a template header. Now the class interface specifies a fixed value for the second template parameter of the generic class template. This illustrates that we 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 way the `MatrixRow` constructors were implemented. Their implementations are left as an exercise to the reader (and they can be found in `matrix.h`).
- An additional member `sum` is defined to compute the sum of the elements of a `MatrixColumn` vector. It's simply implemented using the `accumulate` 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

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

        Matrix<1, 1> cell;

Is this a `MatrixRow` or a `MatrixColumn` specialization? The answer is: neither.

It's ambiguous, precisely because both the columns and the rows could be used with a (different) template partial specialization. If such a `Matrix` is actually required, yet another specialized template must be designed.

Since this template specialization can be useful to obtain the sum of the elements of a `Matrix`, it's covered here as well.

- This class template partial specialization also needs a template header, this time only specifying `DataType`. The class definition specifies two 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 generic `Matrix` type are again implemented as member 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())
          {}

- Since `Matrix<1, 1>` is basically a wrapper around a `DataType` value, we need members to access that latter value. A type conversion operator might be useful, but we also defined a `get` member to obtain the value if the conversion operator isn't used by the compiler (which happens when the compiler is given a choice, see section 11.3). Here are the accessors (leaving out their `const` variants):

          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, the `main` function shown below illustrates how the `Matrix` class template and its partial specializations can be used:

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

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

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

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

            cout << "Sum total: " << Matrix<1, 1>(matrix) << '\n';
        }
        /*
            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

Up to this point we've encountered templates defining a fixed number of template parameters. However, templates may also defined as variadic templates, allowing any number of arguments to be passed to their instantiations.

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

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

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

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

        template<typename ...Params> class Variadic;

Assuming the class template's definition is available then this template can be instantiated using any number of template arguments. Example:

        class Variadic<
                int,
                std::vector<int>,
                std::map<std::string, std::vector<int>>
        > v1;

The template argument list of a variadic template can also be empty. Example:

        class Variadic<> empty;

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

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

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

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

The ellipsis (...) used in the declaration serves two purposes:

- In the template header it is written to the left of a template parameter name where it declares a parameter 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 the right 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 the unpack operator as it `unpacks' a series of arguments in a function's argument list thereby implicitly defining its parameters.

C++ offers no syntax to access the individual template arguments directly. However, the arguments can be visited recursively. An example is provided in the next section. The number of arguments is determined using a new invocation of the `sizeof` operator:

        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

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

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

- The `printcpp` function receives at least a format string. Following the format string any number of additional arguments may be specified.
- If there are no arguments trailing the format string then there is no need to use a function template. An overloaded (non-template) function is defined to handle this situation.
- A variadic function template handles all remaining situations. In this case there is always at least one argument trailing the format string. That argument's type is matched with the variadic template function's first (ordinary) template type parameter `First`. The types of any remaining arguments are bound to the template function's second template parameter, which is a parameter pack.
- The variadic function template processes the argument trailing the format string. Then it recursively calls itself passing the format string and the parameter pack to the recursive call
- If the recursive call merely receives the format string the overloaded (non-template) function is called (cf. section 21.14) ending the recursion. Otherwise the parameter pack's first argument is matched with the recursive call's `First` parameter. As this reduces the size of the recursive call's parameter pack the recursion eventually stops.

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

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

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

Here is the variadic function template's implementation:

        template<typename First, typename ...Params>
        void printcpp(std::string const &format, First value, Params ...params)
        {
            size_t left = 0;
            size_t right = 0;
            while (true)
            {
                if ((right = format.find('%', right)) == string::npos)      // 1
                    throw std::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 arguments and it throws an exception;
- At 2 it verifies that it has not encountered `%%`. If only a single `%` has been seen the `while`-loop ends, the format string is inserted into `cout` up to the `%` followed by `value`, and the recursive call receives the remaing part of the format string as well as the remaining parameter pack;
- If `%%` was seen the format string is inserted up to the second `%`, which is ignored, and processing of the format string continues beyond the `%%`.

Make sure that the overloaded function is at least declared before the compiler processes the function template's definition or it won't call the overloaded function `printcpp` when compiling the function template.

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

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

### 22.5.2: Perfect forwarding

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

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

Another example is found in factory functions that also frequently forward their parameters to the constructors of objects that they return.

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

Perfect forwarding is easily implemented:

- The forwarding function is defined as a template
  (usually a variadic 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 an rvalue 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. Before `forward` 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 implement one member `Inserter::insert` that can be used to call any of the five overloaded `string::insert` members. The `insert` function that's actually called now simply depends on the types and number of arguments that are passed to `Inserter::insert`:

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

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

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

        template <typename Class, typename ...Params>
        Class factory(Params &&...params)
        {
            return Class(std::forward<Params>(params)...);
        }

Here are some examples showing its use:

        Inserter inserter(factory<Inserter>("hello"));
        string delimiter(factory<string>(10, '='));
        Inserter copy(factory<Inserter>(inserter));

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

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

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

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

Since `T &&` turns into an lvalue reference when `forward` is called with an lvalue (or lvalue reference) and remains an rvalue reference if `forward` is called with an rvalue reference, and since `forward` (like `std::move`) anonymizes the variable passed as argument to `forward`, the argument value is forwarded while passing its type from the function's parameter to the called function's argument.

This is called perfect forwarding as the nested function can only be called 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 the nested function (e.g., `Class`'s constructor). Perfect forwarding therefore is a tool to realize type safety.

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

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

This struct merely defines `identity::type` as `T`, but as it is a struct it must be specified explicitly. It cannot be determined from the function's argument itself. The subtle modification to the above implementation of `forward` thus becomes (cf. section 22.2.1 for an explanation of the use of `typename`):

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

Now `forward` must explicitly state `arg`'s type, as in:

        std::forward<Params>(params)

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

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

A function `display(ostream &out)` and `increment(int &x)` may now both be called through `caller`. Example:

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

### 22.5.3: The unpack operator

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

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

        template <typename ...BaseClasses>
        class Combi: public BaseClasses...          // derive from base classes
        {
            public:
                                                    // specify base class objects
                                                    // to its constructor using
                                                    // perfect forwarding
                Combi(BaseClasses &&...baseClasses)
                :
                    BaseClasses(baseClasses)...     // use base class initializers
                {}                                  // for each of the base
        };                                          // classes

This allows us to define classes that combine the features of any number of other classes. If the class `Combi` is derived of classes `A, B,` and `C` then `Combi` is-an `A, B,` and `C`. It should of course be given a virtual destructor. A `Combi` object can be passed to functions expecting pointers or references to any of its base class type objects. Here is an example defining `Combi` as a class derived from a vector of complex numbers, a string and a pair of ints and doubles (using uniform intializers in a sequence matching the sequence of the types specified for the used `Combi` type):

        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 members supporting variadic type lists such as `tuples` (cf. section 22.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 are essential. The compiler considers their omission an error. In the following `struct` definition it was the intent of the programmer to pass a parameter pack on to a nested object construction but ellipses were omitted while specifying the template parameters, resulting in a parameter packs not expanded with `...' error message:

        template <int size, typename ...List>
        struct Call
        {
            Call(List &&...list)
            {
                Call<size - 1, List &&> call(std::forward<List>(list)...);
            }
        };

Instead of the above definition of the `call` object the programmer should have used:

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

### 22.5.4: Non-type variadic templates

Variadic templates not necessarily define template types. Non-types can also be used with variadic templates. The following function template accepts any series of `int` values, forwarding these values to a class template. The class template defines an `enum` value `result` which is returned by the function, unless no int values were specified, in which case 0 is returned.

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

The `sizeof` operator can be used for variadic non-type parameters as well: `sizeof...(Ints)` would return 3 when used in the first function template for `forwarder<1, 2, 3>()`.

Variadic non-type parameters are used to define variadic literal operators, introduced in section 23.3.

### 22.5.5: Folding expressions

Functions accepting variable numbers of arguments (of possibly varying types) are commonly handled using variadic templates. Implementations usually process the first argument, passing the remaining arguments to an overloaded function, which is defined by the compiler for these remaining argument types. One of the overloaded versions, accepting zero or one argument, ends the compiler's recursive implementations.

Sometimes the arguments must be combined using binary operators (like `arg1 + arg2 + ...`). In those cases a folding expression can be used instead of combining the arguments using a traditional variadic template.

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

- A unary left fold is a fold expression that looks like this:

          (... op expr)

  where op is the binary operator that is used in the fold expression, and expr is an expression formulated in terms of the function parameter representing 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 variadic arguments 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 types of the parameter pack are combined using specified operator. E.g.,

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

  returns 6.

There are no special restrictions that apply to function templates using fold expressions. Directly returning the result of the fold expression is OK, but the result could also be used in another expression (maybe inserting its value into an `ostream`), or when initializing a variable or object. Also, the types of the arguments do not have to be identical: the only requirement is that the fully expanded expression (in the example: `1 + 2 + 3` is a valid expression).

- A unary right fold is a fold expression that results in the same expression as its unary left fold alternative, but swaps the ellipses and the `params` identifier:

          (expr op ...)

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

- A binary fold is a fold expression of the following form:

          (expr1 op ... op expr2)

  Here, either `expr1` is the identifier representing the variable arguments or `expr2` must be that identifier. The other one can be any other valid expression (as with unary folds, both expressions must be clearly demarcated). In addition, both operators must be identical.

If a binary operator has been overloaded, it will be used where applicable. A well-known example is of course `operator<<` as defined for `std::ostream` objects. A binary fold defined for `operator<<` will not only do shifts, but can also be used to insert a series of arguments into `cout`:

        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 could be function addresses, function object or lambda functions. Note the use of the rvalue reference when defining the variadic parameter list which prevents copying of function objects that might be passed to `call`. Assuming that `struct Functor` defines a functor, and that `void function()` has been defined, then `call` 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

C++ offers a generalized pair container: the tuple, covered in this section. Before tuples can be used the header file `<tuple>` must be included.

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

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

        template <class ...Types>
        class tuple;

Here is an example of its use:

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

The `std::get<idx>(tupleObject)` function template returns a reference to the `idx`th (zero based) field of the tuple `tupleObject`. The index is specified as the function template's non-type template argument.

Type-based tuple addressing () can be used for tuple types used once in a tuple definition (if the same type is used repeatedly referring to that type introduces an ambiguity). The next example shows 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. Primitive types are initialized to zeroes; class type fields are initialized by their default constructors. Be aware that in some situations the construction of a tuple may succeed but its use may fail. Consider:

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

Here the tuple `empty` cannot be used as its `int &` field is an undefined reference. However, `empty`'s construction succeeds.

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

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

- `std::tuple_size<Tuple>::value` returns the number of types defined for the tuple type `Tuple`. Example:

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

- `std::tuple_element<idx, Tuple>::type` returns the type of element `idx` of `Tuple`. Example:

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

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

        template <typename ...Params>
        class Wrapper
        {
            ...
            public:
                Wrapper(Params &&...params);
        };

This class may be given a tuple data member which should be initialized by the types and values that are used when initializing an object of the class `Wrapper` using perfect forwarding. Comparable to the way a class may inherit from its template types (cf. section 22.5.3) it may forward its types and constructor arguments to its tuple data member:

        template <typename ...Params>
        class Wrapper
        {
            std::tuple<Params...> d_tuple;     // same types as used for
                                                // Wrapper itself
            public:
                Wrapper(Params &&...params)
                :                               // initialize d_tuple with
                                                // Wrapper's arguments
                    d_tuple(std::forward<Params>(params)...)
                {}
        };

### 22.6.1: Tuples and structured bindings

Structured bindings were introduced in section 3.3.7.1. That section concentrated on associating structured binding declarations with data members of structs, returned as POD values.

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

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

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

- The class must be provided with overloaded `get` member templates, using `int` (or another integral type) specializations, where each specialization returns a class element (e.g., a member function).

  The availability of `if 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 a `ClassType [cv] &object` parameter.

- A specialization of `std::tuple_size<Type>` is provided, defining `static size_t const value` as the number of index values that can be specified with the `get<idx>` function. Although defining entities in the standard namespace is normally off limits to ordinary programs, in this special case such specializations are allowed by the C++ standard.

- A specialization of `std::tuple_element<idx, Type>` is provided, defining `type` as the type matching the return type of `get<idx>`.

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

To illustrate the abovementioned steps for associating structured bindings with 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 for `Data` consists of defining a (member) termplate `get`. If `Data` is our own class we can add a member template `get`. Alternatively, if we're only interested in accessing `Data's` public members we could derive a class `DataGet` from `Data`, and provide that class with the `get` member template. Yet another possibility is to define a free `get` function template. The `get` function must return whatever we're interested in. To make the appropriate selection we use an integral type (`int, size_t, ...`) selector value, and the function template thus only has a non-type template parameter. Rather than defining several specializations using the `if constexpr` clause is advised, as it greatly simplifies the function's definition.

Our `get` function defines selector 0 for `factory`, selector 1 for `distance` and selector 2 for `text`. The `distance` member simply returns `d_euclid.distance()`, and `Euclid::distance` is run-time evaluated using its `d_x` and `d_y` values. Thus, `distance` is an example 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 template `get`:

        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: it returns `Data::text()`. As `auto` merely inspects the returned data type, `get<2>()` returns a `std::string`, rather than (text's) return type, which is a `std::string const &`. To use the return types that are actually returned by `Data's` member functions, `get's` return type should be defined as `decltype(auto)` rather than just `auto`:

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

When defining `get` as a free function template it must be provided with a parameter `Data const &data` (or `Data &data` if members are used that may modify `data's` data members), returning the parameter's member functions. 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 the `std::tuple` specializations. These specializations are defined inside the `std` namespace (using `namespace std { ... }` or `std::tuple...`).

The specialization of `std::tuple_size` for `Data` defines `static size_t const value` as the number of index values that can be specified with the `get<idx>` function:

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

The specialization of `std::tuple_element` for `Data` returns the types matching the various return types of the `get` member template. Its implementation also provides a nice example where `declval` is used: the return type of the `get<Nr>` specialization must be determined. But to obtain that return type a `Data` object is required, which isn't available by just mentioning `Data` in `tupe_element's` specialization. However, `declval<Data>()` defines an rvalue reference, which can be passed to `get<Nr>`. But the function's return value isn't required, so the object doesn't have to be constructed. Only its return type is needed. Hence, by surrounding the `get<Nr>` call by `decltype` no object is constructed, and merely 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>() ) );

        };

As `tuple_size` and `tuple_element` are directly associated with the class `Data` their definitions should be provided in `Data's` header file, below `Data's` class interface.

Here's how this could be used in a `main` function, showing single object access 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

As amply illustrated in chapter 19 function objects play an important role with generic algorithms. Like generic algorithms themselves, function objects can be generically defined as members of class templates. If the function call operators (`operator()`) of such classes define parameters then the types of those parameters may also be abstracted by defining the function call operators themselves as member templates. Example:

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

The template class `Filter` is a wrapper around `Class`, filtering `Class`'s function call operator through its own function call operator. In the above example the return value of `Class`'s function call operator is simply passed on, but any other manipulation is of course also possible.

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

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

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

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

        struct Convert
        {
            double operator()(int x);           // int-to-double
            std::string operator()(double x);   // double-to-string
        };

This problem can be tackled successfully by the class template `std::result_of<Functor(Typelist)>`. Before using `std::result_of` the header file `<functional>` must be included.

The `result_of` class template offers a using declaration (`type`), representing the type that is returned by `Functor<TypeList>`. It can be used as follows to improve the implementation of `Filter`:

        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. Now `fc(5)` returns a `double`, while `fc(4.5)` returns a `std::string`.

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

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

        using type = double;

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

- define a generic `struct result` like this:

      template <typename Signature>
      struct result;

- For each function call signature define a specialization of `struct result`. `Convert`'s first function call operator gives rise to:

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

  and `Convert`'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 the specifications should again provide for the correct signatures. A function call operator called with an `int` and a `double`, returning a `size_t` gets:

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

## 22.8: Instantiating class templates

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

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

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

Since the class template `Matrix` uses a default data type a matrix of `double`-valued elements can be defined like this:

        Matrix<3, 5> doubleMatrix;

A class template object may be declared using the keyword `extern`. For example, to declare the matrix `complexMatrix` use:

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

A class template declaration suffices to compile return values or parameters that are of class template types. Example: the following source file may be compiled, although the compiler hasn't seen the definition of the `Matrix` class template. Generic classes and (partial) specializations may all be declared. A function expecting or returning a class template object, reference, or parameter automatically becomes a function template itself. This is necessary to allow the compiler to tailor the function to the types of various actual arguments that may be passed to the function:

        #include <cstddef>

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

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

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

When class templates are used the compiler must first have seen their implementations. So, template member functions must be known to the compiler when the template is instantiated. This does not mean that all members of a template class are instantiated or must have been seen when a class template object is defined. The compiler only instantiates those members that are actually used. This is illustrated by the following simple class `Demo` that has two constructors and two members. When we use one constructor and call one member in `main` note the sizes of the resulting object file and executable program. Next the class definition is modified in that the unused constructor and member are commented out. Again we compile and link the program. Now observe that these latter sizes are identical to the former sizes. There are other ways to illustrate that only used members are instantiated. The `nm` program could be used. It shows the symbolic content of object files. Using `nm` we'll reach the same conclusion: only template member functions that are actually used are instantiated. Here is the class template `Demo` that was used for our little experiment. In `main` only the first constructor and the first member function are called and thus only these members were instantiated:

        #include <iostream>

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

        // the following members should be commented out before
        // compiling for the 2nd time:

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

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

## 22.9: Processing class templates and instantiations

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

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

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

        Ret member();

then the compiler may encounter `member` or the class to which `member` belongs in the following locations:

- the location where a class template object is defined. This is called the point of instantiation of the class template object. The compiler must have read the class template's implementation and has performed a basic check for syntactic correctness of member functions like `member`. It won't accept a definition or declaration like `Ret && *member`, because C++ does not support functions returning pointers to rvalue references. Furthermore, it checks whether the actual type name that is used for instantiating the object is valid. This type name must be known to the compiler at the object's point of instantiation.
- the location where the template member function is used. This is called the template member function's point of instantiation. Here the `Ret` parameter must have been specified (or deduced) and at this point `member`'s statements that depend on the `Ret` template parameter are checked for syntactic correctness. For example, if `member` contains a statement like

          Ret tmp(Ret(), 15);

  then this is in principle a syntactically valid statement. However, when `Ret = int` the statement fails to compile as `int` does not have a constructor expecting two `int` arguments. Note that this is not a problem when the compiler instantiates an object of `member`'s class. At the point of instantiation of the object its member function ``member`' is not instantiated and so the invalid `int` construction remains undetected.

## 22.10: Declaring friends

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

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

- A class template may declare an ordinary function or class as its friend. This is a common friend declaration, such as the insertion operator for `ostream` objects.
- A class template may declare another function template or class template as its friend. In this case, the friend's template parameters may have to be specified.

  If the actual values of the friend's template parameters must be equal to the template parameters of the class declaring the friend, the friend is said to be a bound friend class or function template. In this case the template parameters of the template specifying the `friend` declaration determine (bind) the values of the template parameters of the friend class or function. Bound friends result in a one-to-one correspondence between the template's parameters and the friend's template parameters.

- In the most general case a class template may declare another function template or class template to be its friend, irrespective of the friend's actual template arguments.

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

- The above cases, in which a template is declared as a friend, may also be encountered when ordinary classes are used:
  - The ordinary class declaring ordinary friends has already been covered (chapter 15).
  - The equivalent of bound friends occurs if an ordinary class specifies specific actual template parameters when declaring its friend.
  - The equivalent of unbound friends occurs if an ordinary class declares a generic template as its friend.

### 22.10.1: Non-templates used as friends in templates

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

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

- A class template may declare an ordinary function to be its friend. It is not completely clear why we would like to declare an ordinary function as a friend. Usually we pass an object of the class declaring the friend to such a function. With class templates this requires us to provide the (friend) function with a template parameter without specifying its types. As the language does not support constructions like

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

  unless `function` itself is a template, it is not immediately clear how and why such a friend should be constructed. One reason could be to allow the function access to the class's private static members. In addition such friends could instantiate objects of classes that declare them as their friends. This would allow the friend functions direct access to such object's private 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 probably finds more applications. Here the ordinary (friend) class may instantiate any kind of object of the class template. The friend class may then access all private 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 may be declared as a friend. This requires that the compiler has read the friend class's interface before declaring the friend. Omitting the required destructor and overloaded assignment operators, the following shows an example of a class whose member `sorter` is declared as a friend of the class `Composer`:

          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 example `Friend::d_ints` is a pointer member. It cannot be a `Composer<int>` object as the `Composer` class interface hasn't yet been seen by the compiler when it reads `Friend`'s class interface. Disregarding this and defining a data member `Composer<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 existence of the class `Composer`, but as it hasn't seen `Composer`'s interface it doesn't know what size the `d_ints` data member has.

### 22.10.2: Templates instantiated for specific types as friends

With bound friend class or function templates there is a one-to-one mapping between the template arguments of the friend templates and the template arguments of the class templates declaring them as friends. In this case, the friends themselves are templates too. Here are the various possibilities:

- A function template is a friend of a class template. In this case we don't experience the problems we encountered with ordinary functions declared as friends of class templates. Since the friend function template itself is a template it may be provided with the required template arguments allowing it to become the declaring class's friend. The various declarations are organized like this:
  - The class template declaring the bound template friend function is defined;
  - The (friend) function template is defined, now having access to all the class template's (private) members.
  The bound template friend declaration specifies the required template arguments immediately following the template's function name. Without the template argument list affixed to the function name it would remain an ordinary friend function. Here is an example showing a bound friend to create a subset of the entries of a dictionary. For real life examples, a dedicated function object returning `!key1.find(key2)` is probably more useful. For the 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, all members of the friend class may access all private members of the class declaring the friend. As the friend class only needs to be declared, the organization of the declaration is much easier than when function templates are declared as friends. In the following example a class `Iterator` is declared as a friend of a class `Dictionary`. Thus, the `Iterator` is able to access `Dictionary`'s private data. There are some interesting points to note here:
  - To declare a class template as a friend, that class only needs to be 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, even though 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 seen by the compiler. Since it's a support class for `Dictionary` it can safely define a `std::map` data member that is initialized by the friend class's constructor. The constructor may then access the `Dictionary`'s private data member `d_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)
                    {}

  - The `Iterator` member `begin` may return a `map` iterator. Since the compiler does not know what the instantiation of the map looks like, a `map<Key, Value>::iterator` is a template subtype. So it cannot be used as-is, but it must be prefixed by `typename` (see the function `begin`'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 a `Dictionary` should be able to construct an `Iterator` (maybe because we conceptually consider `Iterator` to be a sub-type of `Dictionary`). This is easily accomplished by defining `Iterator`'s constructor in its private section, and by declaring `Dictionary` to be a friend of `Iterator`. Consequently, only a `Dictionary` can create an `Iterator`. By declaring the constructor of a specific `Dictionary` type as a friend of `Iterator`'s we declare a bound friend. This ensures that only that particular type of `Dictionary` can create `Iterator`s using template parameters identical to its 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 is `Iterator`'s friend. The friend is a template member. Other members can be declared as a class's friend as well. In those cases their prototypes must be used, also specifying the types of their return values. Assuming that

      std::vector<Value> sortValues()

  is a member of `Dictionary` then the matching bound friend declaration is:

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

- A class template may define free members, which should have access to the data of instantiations of the class template, but only for matching types. An example is a class template for which the free member `operator==` must be available. If this is required for a template `ClassTemplate`, requiring a `typename Type` template type argument, then a free member

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

  must have been declared prior to `ClassTemplate`'s interface itself. Within the class interface `operator==` may then be declared as a friend, specifying `operator==` 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 may follow.

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

        template <typename T>   // a function template
        void fun(T *t)
        {
            t->not_public();
        };
        template<typename X>    // a 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

When nesting a class under a class template it may be desirable to provide that nested class with free operators, which are bound to the surrounding class. This situation is encountered when defining a nested iterator for which a free `operator==(iterator const &lhs, iterator const &rhs)` operator is preferred over a member `operator==(iterator const &rhs) const`, as the member does not allow promotions of the lhs operand.

It is possible to define the free `operator==` as friend in the nested class, 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();
        }

However, this requires an in-class implementation, which should be avoided as it combines interfaces and implementations which reduces clarity.

But when moving the implementation out of the interface we run into the problem that `operator==` is a function template, which must be declared as such in the class interface. The compiler suggests to make sure the function template has already been declared and add '<>' after the function name. But declaring

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

before the `struct String` class template, and then implementing `operator==` as

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

the compiler still complains, reporting declaration of 'operator==' as non-function.

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

Radu proposed using an application of SFINAE: by defining a free operator provided with a type uniquely defined by the nested class, which is then provided with a default value in the free function's implementation, the compiler automatically selects the appropriate overloaded function. This works for multiple classes declaring nested classes and for classes defining multiple nested classes alike. Here is an example of two classes each declaring a nested class `iterator`:

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

Note that the nested classes declare the free functions as function template specializations.

Then, for each nested class an implementation of the free operator is provided. These implementations are function templates provided with a template type `Type` and a second type which is the uniquely named `int` type of the nested class for which the free operator is implemented:

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

The `main` function illustrates the use of both free operators:

        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

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

Here are the syntactic conventions declaring unbound friends:

- Declaring a function template as an unbound friend: any instantiation of the function template may instantiate objects of the template class and may access its private members. Assume the following function 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 the following class template `Vector2`:

      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 namespace must be mentioned as well. Assuming that `ForEach` is defined in the namespace `FBB` 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 class `Vector2` stores vectors of elements of template type parameter `Type`. Its `process` member allows `ForEach` to call its private `rows` member. The `rows` member, in turn, uses another `ForEach` to call its private `columns` member. Consequently, `Vector2` uses two instantiations of `ForEach` which is a clear hint for using an unbound friend. It is assumed that `Type` class objects can be inserted into `ostream` objects (the definition of the `ForEach` function template can be found in the `cplusplus.yo.zip` archive that can be retrieved from https://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. This allows all instantiations of the friend's member functions to instantiate objects of the class template declaring the friend class. In this case, the class declaring the friend should offer functionality that is useful to different instantiations of its friend class (i.e., instantiations using different template arguments). The syntactic convention is comparable to the convention 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 template `Wrapper` may now instantiate `PtrVector`s using any actual type for its `Type` parameter. This allows the `Wrapper` instantiation to access all of `PtrVector`'s private members.

- When only some members of a class template need access to private members of another class template (e.g., the other class template has private constructors and only some members of the first class template need to instantiate objects of the second class template), then the latter class template may declare only those members of the former class template requiring access to its private members as its friends. Again, the friend class's interface may be left unspecified. However, the compiler must be informed that the friend member's class is indeed a class. A forward declaration of that class must therefore be provided. In the next example `PtrVector` declares `Wrapper::begin` as its friend. Note the forward declaration of the class `Wrapper`:

      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

Through extended friend declarations, which are also available for class templates, template type parameters can be declared as friends. A template type argument, however, does not necessarily have to be a type for which the keyword `friend` makes sense, like `int`. In those cases the friend declaration is simply ignored.

Consider the following class template, declaring `Friend` as a friend:

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

Now, an actual `Friend` class may access all of `Class`'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 like `Class<int> intClass` is also OK, but here the friend declaration is simply ignored. After all, there are no `int members' to access `Class<int>`'s private members.

## 22.11: Class template derivation

Class templates can be used for inheritance purposes as well. When a class template is used in class derivation, the following situations should be distinguished:

- An existing class template is used as base class when deriving a ordinary 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 is defined.
- An existing class template is used as the base class when deriving another class template. Here the class template characteristics remain clearly visible.
- An ordinary class is used as the base class when deriving a template class. This interesting hybrid allows us to construct class templates that are partially compiled.

These three variants of class template derivation are elaborated in this and the upcoming sections.

Consider the following base class:

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

            public:
                Base(T const &t);
        };

The above class is a class template that can be used as a base class for the following derived class template `Derived`:

        template<typename T>
        class Derived: public Base<T>
        {
            public:
                Derived(T const &t);
        };
        template<typename T>
        Derived<T>::Derived(T const &t)
        :
            Base(t)
        {}

Other combinations are also possible. The base class may be instantiated by specifying template arguments, turning the derived class into an ordinary class (showing a class object's definition as well):

        class Ordinary: public Base<int>
        {
            public:
                Ordinary(int x);
        };
        inline Ordinary::Ordinary(int x)
        :
            Base(x)
        {}

        Ordinary ordinary{ 5 };

This approach allows us to add functionality to a class template, without the need for constructing a derived class template.

Class template derivation pretty much follows the same rules as ordinary class derivation, not involving class templates. Some subtleties that are specific for class template derivation may easily cause confusion like the use of `this` when members of a template base class are called from a derived class. The reasons for using `this` are discussed in section 23.1. In the upcoming sections the focus will be on the class derivation proper.

### 22.11.1: Deriving ordinary classes from class templates

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

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

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

and by defining a member function `process(string const &cmd)` to do the actual command processing a program might simply execute the following `main()` function:

        int main()
        {
            string line;
            Handler cmd;

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

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

- The class is derived from a `std::map`, expecting the command associated with each command-processing member as its keys. Since `Handler` uses the map merely to define associations between the commands and the processing member functions and to make `map`'s types available, private derivation is used:

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

- The actual association can be defined using static private data members: `s_cmds` is an array of `Handler::value_type` values, and `s_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 data members. It could be implemented inline:

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

- The member `process` iterates along the map's elements. Once the first word on the command line matches the initial characters of the command, the corresponding command is executed. If no such command is found, an error message 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

Although it's perfectly acceptable to derive an ordinary class from a class template, the resulting class of course has limited generality compared to its template base class. If generality is important, it's probably a better idea to derive a class template from a class template. This allows us to extend an existing class template with new functionality or to override the functionality of the existing class template.

The class template `SortVector` presented below is derived from the existing class template `std::vector`. It allows us to perform a hierarchic sort of its elements using any ordering of any data members its data elements may contain. To accomplish this there is but one requirement. `SortVector`'s data type must offer dedicated member functions comparing its members.

For example, if `SortVector`'s data type is an object of class `MultiData`, then `MultiData` should implement member functions having the following prototypes for each of its data members which can be compared:

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

So, if `MultiData` has two data members, `int d_value` and `std::string d_text` and both may be used by a hierarchic sort, then `MultiData` should offer the following two members:

        bool intCmp(MultiData const &rhv);  // returns d_value < rhv.d_value
        bool textCmp(MultiData const &rhv); // returns d_text  < rhv.d_text

Furthermore, as a convenience it is assumed that `operator`<< and `operator`>> have been defined for `MultiData` objects.

The class template `SortVector` is directly derived from the template class `std::vector`. Our implementation inherits all members from that base class. It also offers two simple constructors:

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

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

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

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

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

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

`SortWith`'s constructor receives a pointer to a predicate function and initializes the class's `d_ptr` data member:

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

Its binary predicate member (`operator()`) must return `true` if its first argument should eventually be placed ahead of its second argument:

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

The following examples, which can be embedded in a `main` function, provides an illustration:

- First, A `SortVector` object is created for `MultiData` objects. It uses the `copy` generic algorithm to fill the `SortVector` object from information appearing at the program's standard input stream. Having initialized the object its elements are displayed to the standard output stream:

              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 of two member functions. The text comparison is the most significant sort criterion:

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

- Next, the array's elements are sorted and displayed to the standard output stream:

              sv.hierarchicSort(arr, 2);

- Then the two elements of the array of pointers to `MultiData`'s member functions are swapped, and the previous step is repeated:

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

After compiling the program the following command can be given:

        echo a 1 b 2 a 2 b 1 | a.out

This results in the following output:

        a 1 b 2 a 2 b 1
        ====
        a 1 a 2 b 1 b 2
        ====
        a 1 b 1 a 2 b 2
        ====

### 22.11.3: Deriving class templates from ordinary classes

An ordinary class may be used as the base class for deriving a template class. The advantage of such an inheritance tree is that the base class's members may all be compiled beforehand. When objects of the class template are now instantiated only the actually used members of the derived class template must be instantiated.

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

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

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

- The class `Table` is a class template, requiring only one template type 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 are performed by `TableType`.
- `Table` has two constructors. The constructor's first two parameters are `Iterator`s used to iterate over the elements that must be entered into the table. The constructors require us to specify the number of columns we would like our table to have as well as a FillDirection. `FillDirection` is an `enum`, defined by `TableType`, having values `HORIZONTAL` and `VERTICAL`. To allow `Table`'s users to exercise control over headers, footers, captions, horizontal and vertical separators, one constructor has a `TableSupport` reference parameter. The class `TableSupport` is developed at a later stage as a virtual class allowing 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 are `Table`'s only two public members. Both constructors use a base class initializer to initialize their `TableType` base class and then call the class's private member `fill` to insert data into the `TableType` base class object. Here are the constructor's implementations:

      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's `fill` 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 member `std::vector<std::string> d_string`. One of the requirements of the data type to which the iterators point is that this data type can be inserted into streams. So, `fill` uses an `ostringstream` object to obtain the textual representation of the data, which is then appended to `d_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 class `Table`. Note that this class template only has three members, two of them being constructors. Therefore, in most cases only two function templates must be instantiated: a constructor and the class's `fill` member. For example, the following defines a table having four columns, vertically filled by `string`s extracted from the standard input stream:

        Table<istream_iterator<string> >
            table(istream_iterator<string>(cin), istream_iterator<string>(),
                  4, TableType::VERTICAL);

The fill-direction is specified as `TableType::VERTICAL`. It could also have been specified using `Table`, but since `Table` is a class template its specification would have been slightly more complex: `Table<istream_iterator<string> >::VERTICAL`.

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

- It is an ordinary class, designed to operate as `Table`'s base class.
- It uses various private data members, among which `d_colWidth`, a vector storing the width of the widest element per column and `d_indexFun`, pointing to the class's member function returning the element in `table[row][column]`, conditional to the table's fill direction. `TableType` also uses a `TableSupport` pointer and a reference. The constructor not requiring a `TableSupport` object uses the `TableSupport *` to allocate a (default) `TableSupport` object and then uses the `TableSupport &` as the object's alias. The other constructor initializes the pointer to 0 and uses the reference data member to refer to the `TableSupport` object provided by its parameter. Alternatively, a static `TableSupport` object could have been used to initialize the reference data member in the former constructor. The remaining private data members are probably 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 actual `string` objects populating the table are stored in a protected data member:

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

- The (protected) constructors perform basic tasks: they initialize the object's data members. Here is the constructor expecting a reference to a `TableSupport` 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)
      {}

- Once `d_string` has been filled, the table is initialized by `Table::fill`. The `init` protected member resizes `d_string` so that its size is exactly `rows x columns`, and it determines the maximum width 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 member `insert` is used by the insertion operator (`operator`<<) to insert a `Table` into a stream. First it informs the `TableSupport` object about the table's dimensions. Next it displays the table, allowing the `TableSupport` object to write headers, footers and separators:

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

- The `cplusplus.yo.zip` archive contains `TableSupport`'s full implementation. This implementation is found in the directory `yo/classtemplates/examples/table`. Most of its remaining members are private. Among those, these two members return table element `[row][column]` for, respectively, a horizontally filled table and a vertically 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 class `TableSupport` is used to display headers, footers, captions and separators. It has four virtual members to perform those tasks (and, of course, a virtual constructor):

- `hline(size_t rowIndex)`: called just before displaying the elements in row `rowIndex`.
- `hline()`: called immediately after displaying the final row.
- `vline(size_t colIndex)`: called just before displaying the element in column `colIndex`.
- `vline()`: called immediately after displaying all elements in a row.

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

        /*
                                      table.cc
        */

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

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

        using namespace std;
        using namespace FBB;

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

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

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

            cout << table << '\n';
        }
        /*
            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

Chapter 14 introduced polymorphism. Polymorphism allows us to use a base class's interface to call implementations which are defined in derived classes. Traditionally this involves defining Vtables for polymorphic classes, containing pointers to functions that can be overridden in derived classes. Objects of polymorphic classes harbor hidden pointers, pointing to their class's Vtables. This type of polymorphism is called dynamic polymorphism, and it uses late binding as the function to call is determined run-time, rather than compile-time.

In many cases, however, dynamic polymorphism isn't really required. Usually the derived class objects that are passed to functions expecting base class references are invariants: at fixed locations in programs fixed class types are used to create objects. The polymorphic nature of these objects is used inside the functions that receive these objects, expecting references to their base classes. As an example consider reading information from a network socket. A class `SocketBuffer` is derived from `std::streambuf`, and the `std::stream` receiving a pointer to the `SocketBuffer` merely uses `std::streambuf's` interface. However, the implementation, by using polymorphism, in fact communicates with functions defined in `SocketBuffer`.

The disadvantages of this scheme are that, firstly, inside the functions expecting references to polymorphic base classes execution is somewhat slowed down precisely because of late-binding. Member functions aren't directly called, but are called indirectly via the object's vpointer and their derived class's Vtable. Secondly, programs using dynamic polymorphism tend to become somewhat bloated compared to programs using static binding. The code bloat is caused by the requirement to satisfy at link-time all the references that are mentioned in all the object files comprising the final program. This requirement forces the linker to link all the functions whose addresses are stored in the Vtables of all polymorphic classes, even if these functions are never actually called.

Static polymorphism allows us to avoid these disadvantages. It can be used instead of dynamic polymorphism in cases where the abovementioned invariant holds. Static polymorphism, also called the curiously recurring template pattern (CRTP), is an example of template meta programming (see also chapter 23 for additional examples of template meta programming).

Whereas dynamic polymorphism is based on the concepts of vpointers, Vtables, and function overriding, static polymorphism capitalizes on the fact that function templates (c.q., member templates) are only compiled into executable code when they are actually called. This allows us to write code in which functions are called which are completely non-existent at the time we write our code. This, however, shouldn't worry us too much. After all, we use a comparable approach when calling a purely virtual function of an abstract base class. The function is really called, but which function is eventually called is determined later in time. With dynamic polymorphism it is determined run-time, with static polymorphism it is determined compile-time.

There's no need to consider static and dynamic polymorphism as mutually exclusive 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

With static polymorphism a class template takes the role of a base class in dynamic polymorphism. This class template declares several members, which are comparable to members of a polymorphic base class: they are either support members or they call members that are overridden in derived classes.

In the context of dynamic polymorphism these overridable members are the base class's virtual members. In the context of static polymorphism there are no virtual members. Instead, the statically polymorphic base class (referred to as the `base class' below) declares a template type parameter (referred to as the `derived class type' below). Next, the base class's interfacing members call members of the derived class type.

Here is a simple example: a class template acting as a base class. Its public interface consists of one member. But different from dynamic polymorphism there's no reference in the class's interface to any member showing polymorphic 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 called by functions receiving a reference or pointer to the base class, but it may call members that must be available in the derived class type at the point where `interface` is called. Before we can call members of the derived class type an object of the derived class type must be available. This object is obtained through inheritance. The derived class type is going to be derived from the base class. Thus `Base's this` pointer is also `Derived's this` pointer.

Forget about polymorphism for a second: when we have a `class Derived: public Base` then (because of inheritance) a `static_cast<Derived *>` can be used to cast a `Base *` to a `Derived` object. A `dynamic_cast` of course doesn't apply, as we don't use dynamic polymorphism. But a `static_cast` is appropriate since our `Base *` does in fact point to a `Derived` class object.

So, to call a `Derived` class member from inside `interface` we can use the following implementation (remember that `Base` is a base class of `Derived`):

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

It's remarkable that, when the compiler is given this implementation it cannot determine whether `Derived` is really derived from `Base`. Neither can it determine whether the class `Derived` indeed offers a member `polymorphic`. The compiler simply assumes this to be true. If so, then the provided implementation is syntactically correct. One of the key characteristics of using templates is that the implementation's viability is eventually determined at the function's point of instantiation (cf. section 21.6). At that point the compiler will verify that, e.g., the function `polymorphic` 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`'.

The first requirement is satisfied by using the curiously recurring template pattern:

        class First: public Base<First>

In this curious pattern the class `First` is derived from `Base`, which itself is instantiated for `First`. This is acceptable, as the compiler already has determined that the type `First` exists. At this point that is all it needs.

The second requirement is simply satisfied by defining the member `polymorphic`. In chapter 14 we saw that virtual and overriding members belong to the class's private interface. We can apply the same philosophy here, by placing `polymorphic` in `First's` private interface, 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 by `polymorphic'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 class `First` itself is not a class template: its members can be separately compiled and stored in, e.g., a library. Also, as is the case with dynamic polymorphism, the member `polymorphic` has full access to all of `First`'s data members and member functions.

Multiple classes can now be designed like `First`, each offering their own implementation of `polymorphic`. E.g., the member `Second::polymorphic` of the class `Second`, designed like `First`, could be implemented like this:

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

The polymorphic nature of `Base` becomes apparent once a function template is defined in which `Base::interface` is called. Again, the compiler simply assumes a member `interface` exists when it reads the definition 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 the viability of the generated code. In the following `main` function a `First` object is passed to `fun`: `First` declares `interface` through its base class, and `First::polymorphic` is called by `interface`. The compiler will at this point (i.e., where `fun` is called) check whether `first` indeed has a member `polymorphic`. Next a `Second` object is passed to `fun`, and here again the compiler checks whether `Second` has a member `Second::polymorphic`:

        int main()
        {
            First first;
            fun(first);

            Second second;
            fun(second);
        }

There are also downsides to using static polymorphism:

- First, the sentence `a `Second` object is passed to `fun`' formally isn't correct, since `fun` is a function template the functions `fun` called as `fun(first)` and `fun(second)` are different functions, not just calls of one function with different arguments. With static polymorphism every instantiation using its own template parameters results in completely new code which is generated when the template (e.g., `fun`) is instantiated. This is something to consider when creating statically polymorphic base classes. If the base class defines data members and member functions, and if these additional members are used by derived class types, then each member has its own instantiation for each derived class type. This also results in code bloat, albeit of a different kind than observed with dynamic polymorphism. This kind of code bloat can often be somewhat reduced by deriving the base class from its own (ordinary, non-template) base class, encapsulating all elements of the statically polymorphic base class that do not depend on its template type parameters.
- Second, if different types of statically polymorphic objects are dynamically created (using the `new` operator) then the types of the returned pointers are all different. In addition, the types of the pointers to their statically polymorphic base classes differ from each other. These latter pointers are different because they are pointers to `Base<Derived>`, representing different types for different `Derived` types. Consequently, and different from dynamic polymorphism, these pointers cannot be collected in, e.g., a vector of shared pointers to base class pointers. There simply isn't one base class pointer type. Thus, because of the different base class types, there's no direct statically polymorphic equivalent to virtual destructors.
- Third, as illustrated in the next section, designing static polymorphic classes using multiple levels of inheritance is not a trivial task.

Summarizing, static polymorphism is best used in situations where a small number of different derived class types are used, where a fixed number of derived class objects are used, and where the statically polymorphic base classes themselves are lean (possibly encapsulating some of their code in ordinary base classes of their own).

### 22.12.2: Converting dynamic polymorphic classes to static polymorphic classes

So you've decided that you want to convert some of your dynamically polymorphic classes into statically polymorphic classes. Now what?

In chapter 14 the base class `Vehicle` and some derived classes were introduced. `Vehicle, Car` and `Truck`'s interfaces look like this (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 polymorphic classes we must realize that polymorphic classes show two important characteristics:

- they define facilities (data members, member functions) that are inherited by derived classes (e.g., `Vecicle::mass`) (i.e., the inheritable interface), and
- derived classes implement the redefinable interface in a way that suits their purpose (e.g., `Truck::vmass`).

With statically polymorphic classes these two characteristics should completely be separated. As we've seen in the previous section, a statically polymorphic derived class derives from its base class by using its own class type as argument to the base class's type parameter. This works fine if there's only one level of inheritance (i.e., one base class, and one or more 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 intial attempt 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();
        };

- If `Truck` inherits from `Car`, then `Truck` implicitly derives from `Vehicle<Car>`, as `Car` derives from `Vehicle<Car>`. Consequently, when `Truck{}.mass()` is called it is not `Truck::vmass` that's activated, but Car's `vmass` function. But `Truck` must derive from `Car` in order to use `Car's` protected features and to add `Car's` public features to its own public interface.
- Multiple inheritance also doesn't solve the issue: when inheriting `Truck` from `Vehicle<Truck>` and from `Car` results in a class `Truck` that also inherits from `Vehicle<Car>` (through `Truck's Car` base class), and compilation fails as the compiler encounters an ambiguity when instantiating `Vehicle::mass`: should it call `Class::vmass` or should it call `Truck::vmass`?

To solve this problem (i.e., to ensure that `Truck{}.mass()` calls `Truck::vmass`) the redefinable interface must be separated from the inheritable interface.

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

Figure 29: Vehicle Static Polymorphic Class Design

The left-hand side classes are used as base classes for the next level of inheritance (except for `TruckBase`, but `TruckBase` could be used as base class for yet another level of class inheritance). This line of inheritance declares the inheritable interface of the classes.

Each of the classes to the left is a base class of a single class to the right: `VehicleBase` is a base class for `Vehicle`, `TruckBase` for `Truck`. The classes to the left contain all members that are completely independent of the elements that are involved in realizing the static polymorphism. As that's a mere design principle to realize multiple levels of static polymorphism the common data hiding principles are relaxed, and the left-hand side classes declare their matching right-hand side derived class templates as friend, to allow full access to all members of a left-hand side class, including the private members, from the matching derived class template to the right. E.g., `VehicleBase` declares `Vechicle` 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 of static polymorphism, by defining that part of the interface that uses the statically redefinable functions. E.g, using the curiously recurring template pattern it defines a class member `mass` that calls the function `vmass` of its derived class (in addition it can use all members of its non-class template 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 when `vmass` is called depends on the implementation in the class `Derived`, which is handled by the remaining classes, shown below `Vehicle`, which are all derived from `Vehicle` (as well as from their own `...Base` class). These classes use the curiously recurring template pattern. E.g.,

        class Car: public CarBase, public Vehicle<Car>

So, if `Car` now implements its own `vmass` function, which can use any of its own (i.e., `CarBase's` members), then that function is called when calling a `Vehicle'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 using multiple levels of inheritance let's summarize the steps we took to implement static polymorphism

- First, starting at the base class, the class `Vehicle`. `Vehicle's` non-redefinable interface is moved to a class `VehicleBase`, and `Vehicle` itself is turned into a statically polymorphic base class. In general all members of the original polymorphic base class that do not use or implement virtual members should be moved to the `XBase` class.

- `VehicleBase` declares `Vehicle` to be a `friend`, to allow `Vehicle` full access to its former members, that are now in `VehicleBase`.

- `Vehicle's` members refer to the redefinable interface. I.e., its members call members of its `Derived` template type parameter. In this implementation `Vehicle` does not implement its own `vmass` member. We cannot define `Vehicle<Vehicle>`, and with static polymorphism the base class is essentially comparable to an abstract base class. If this is inconvenient then a default class can be specified for `Vehicle's Derived` class, implementing the redefinable interface of the original polymorphic base class (allowing for definitions like `Vehicle<> vehicle`).

- Likewise the remaining classes have their members not involved in static polymorphism moved to a base class. E.g., class `Car` moves these members to `CarBase` and `Truck` moves those members to `TruckBase`.

- A standard linear line of inheritance is used from `VehicleBase` to `CarBase` and from there to `TruckBase`.

- Each of the remaining classes (here: `Car` and `Truck`) is a class template that derives from its base classes, and also, using the curiously recurrent template pattern, from `Vehicle`.

- Each of these remaining classes can now implement its own version of the redefinable interface, as used by the members of `Vehicle`.

This design pattern can be extended to any level of inheritance: for each new level a base class is constructed, deriving from the most deeply nested `XXXBase` class so far, and deriving from `Vehicle<XXX>`, implementing its own ideas about the redefinable interface.

Functions that are used in combination with statically polymorphic classes themselves 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 to `fun` it must offer a member `mass`, or compilation will fail. If the object is in fact a `Car` or `Truck`, then their `Vehicle<Type>` static base class member `mass` is called, which in turn uses static polymorphism to call the member `vmass` as implemented by the actually passed class type. The following `main` function displays, respectively, 1000 and 15000:

        int main()
        {
            Car car;
            fun(car);

            Truck truck;
            fun(truck);
        }

Note that this program implements `fun` twice, rather than once in the case of dynamic polymorphism. The same holds true for the `Vehicle` class template: two implementations, one for the `Car` type, and one for the `Truck` type. The statically polymorphic program will be slightly faster, though.

(A compilable example using static polymorphism is found in the C++ Annotations's source distribution's file `yo/classtemplates/examples/staticpolymorphism/polymorph.cc`.)

### 22.12.3: Using static polymorphism to avoid reimplementations

Static polymorphism may profitably be used to avoid reimplementing code in an otherwise dynamic polymorphic environment.

Consider the situation where we have a class containing a container of pointers to some polymorphic base class type (like the class `Vehicle` from chapter 14). How to copy such a container to another container? We're not hinting at using shared pointers here, but would like to make a full copy. Clearly, we'll need to duplicate the objects the pointers point at, and assign these new pointers to the copied object's container.

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

To apply the prototype design pattern we have to implement `newCopy` in all derived classes. Not by itself a big deal, but static polymorphism can nicely be used here to avoid having to reimplement this function for each derived class.

We start off with an abstract base class `VehicleBase` declaring a pure virtual member `newCopy`:

        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 class `CloningVehicle` which is derived from `VehicleBase` (note that we thus combine dynamic and static polymorphism). This class provides the generic implementation of `newCopy`. This is possible because all derived classes can use this implementation. Also, `CloningVehicle` will be re-implemented for each concrete type of vehicle that is eventually used: a `Car`, a `Truck`, an `AmphibiousVehicle`, etc, etc. `CloningVehicle` thus isn't shared (like `VehicleBase`), but instantiated for each new type of vehicle.

The core characteristic of a statically polymorphic class is that it can use its class template type parameter via a `static_cast` of its own type. A member function like `newCopy` is implemented always the same way, viz., by using the derived class's copy constructor. Here is the class `CloningVehicle`:

        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 from `CloningVehicle`, which automatically provides them with their own implementation of `newCopy`. E.g., a class `Car` 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 a `std::vector<VehicleBase *> original` we could create a copy of `original` like this:

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

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

## 22.13: Class templates and nesting

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

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

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

The nested class defines its constructor as a private member, and allows `PtrVector<Type>` objects access to its private members. Therefore only objects of the surrounding `PtrVector<Type>` class type are allowed to construct their `iterator` objects. However, `PtrVector<Type>`'s clients may construct copies of the `PtrVector<Type>::iterator` objects they use.

Here is the nested class `iterator`, using a (required) `friend` declaration. Note the use of the `typename` keyword: since `std::vector<Type *>::iterator` depends on a template parameter, it is not yet an instantiated class. Therefore `iterator` becomes an implicit typename. The compiler issues a warning if `typename` has been omitted. Here is the class interface:

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

                    iterator(PtrVector<Type> &vector);

                    public:
                        Type &operator*();
                };

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

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

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

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

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

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

        int main()
        {
            PtrVector<int> vi;

            vi.push_back(new int(1234));

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

            std::cout << *begin << '\n';
        }

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

        template <typename Iterator>
        class Table: public TableType
        {
            public:
                enum FillDirection
                {
                    HORIZONTAL,
                    VERTICAL
                };
            ...
        };

In this case, the actual value of the template type parameter must be specified when referring to a `FillDirection` value or to its type. For example (assuming `iter` and `nCols` are defined as in section 22.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

Section 18.2 iterators as used by generic algorithms were introduced. We've seen that several types of iterators were distinguished: InputIterators, ForwardIterators, OutputIterators, BidirectionalIterators, RandomAccessIterators, and ContiguousIterators.

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

Iterator classes should provide the following `using` 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 a `const` 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 a `const` pointer. E.g.,

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

These using declarations are commonly encountered in the public sections of iterators, which therefore might be defined as structs. Here's an example 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
        }

In section 18.2 the characteristics of iterators were discussed. All iterators should support (using `Iterator` as the generic name of the designed iterator class and `Type` to represent the (possibly `const`, in which case the associated operator should be a `const` member as well) data type to which `Iterator` objects refer):

- 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, like `bool operator==(Iterator const &lhs, Iterator const &rhs)`, `bool operator!=((Iterator const &lhs, Iterator const &rhs))`). Instead of `operator!=` 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 meet additional requirements. These are required because generic algorithms perform checks on the types of the iterators they receive. Simple pointers are usually accepted, but if an iterator-object is used the generic algorithm might require the iterator to specify what type of iterator it represents.

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

- `std::input_iterator_tag`. This tag is used when the iterator class defines an InputIterator. Iterators of this type allow reading operations, iterating from the first to the last element of the series to 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 at `using value_type = ...` could be used instead to `value_type`. Except for the standard operators there are no further requirements for InputIterators.

- `std::output_iterator_tag`. This tag is used when the iterator class defines an OutputIterator. Iterators of this type allow assignments to their dereferenced iterators. Therefore, the OutputIterator dereference operator is usually declared as:

          value_type &operator*();

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

- `std::forward_iterator_tag`. This tag is used when the iterator class defines a ForwardIterator. Iterators of this type allow reading and assignment operations, iterating from the first to the last element of the series to which the iterator refers. Therefore, the ForwardIterator dereference operator should be declared as follows:

          value_type &operator*();

  and it could also declare an overloaded `operator*() const`:

          value_type const &operator*() const;

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

- `std::bidirectional_iterator_tag`. This tag is used when the iterator class defines a BidirectionalIterator. Iterators of this type allow reading and assignment 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 data its dereference operator refers to and it should allow stepping backward. BidirectionalIterator should therefore, in addition to the standard operators required for iterators, offer the following operators:

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

- `std::random_access_iterator_tag`. This tag is used when the iterator class defines a RandomAccessIterator. These iterators are like Bidirectional iterators, but in addition allow stepping to the next iterator using `int` step sizes (the resulting iterator may point to 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 of data elements between the current and `rhs` iterator (returning a negative value if `rhs` refers to a data element beyond the data element `this` iterator refers to);
  - `Iterator operator+(int step) const`, returning an iterator referring to a data element `step` data elements beyond the data element `this` iterator refers to;
  - `Iterator operator-(int step) const`, returning an iterator referring to a data element `step` data elements before the data element `this` iterator refers to;
  - `bool operator<(Iterator const &rhs) const`, returning `true` if the data element `this` iterator refers to is located before the data element the `rhs` iterator refers to.
- `std::contiguous_iterator_tag`. This tag is used when the iterator class defines a ContiguousIterator. These iterators offer the same facilities as the RandomAccessIterators, but it is the responsibility of the software engineer to ensure that the elements to which the iterators refer are stored contiguously in memory.

Each iterator tag assumes that a certain set of operators is available. The RandomAccessIterators ant `ContiguousIterators` are the most 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 in undefined behavior of the iterator if the resulting iterator value would refer to a location outside of this range.

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

Most classes offering members returning iterators do so by having members construct the required iterators that are thereupon returned as objects. As the caller of these member functions only has to use or sometimes copy the returned iterator objects, there is usually no need to provide publicly available constructors, except for the copy constructor (which is available by default). Therefore additional constructors are usually defined as private or protected members. To allow an outer class to create iterator objects, the iterator class usually declares the outer class as its friend.

In the following sections a RandomAccessIterator, and a reverse RandomAccessIterator is covered. The container class for which a random access iterator must be developed may actually store its data elements in many different ways (e.g., using containers or pointers to pointers). Section 26.5 contains an example of a self-made template iterator class.

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

### 22.14.1: Implementing a `RandomAccessIterator'

In the chapter about containers (chapter 12) it was noted that containers own the information they contain. If they contain objects, then those objects are destroyed once the containers are destroyed. As pointers are not objects their use in containers is discouraged (STL's `unique_ptr` and `shared_ptr` type objects may be used, though). Although discouraged, we might be able to use pointer data types in specific contexts. In the following class `StringPtr`, an ordinary class is derived from the `std::vector` container that uses `std::string *` as its data type:

        #ifndef INCLUDED_STRINGPTR_H_
        #define INCLUDED_STRINGPTR_H_

        #include <string>
        #include <vector>

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

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

        #endif

This class needs a destructor: as the object stores string pointers, a destructor is required to destroy the strings once the `StringPtr` object itself is destroyed. Similarly, a copy constructor and an overloaded assignment operator are required. Other members (in particular: constructors) are not explicitly declared here as they are not relevant to this section's topic.

Assume that we want to use the `sort` generic algorithm with `StringPtr` objects. This algorithm (see section 19.1.54) requires two RandomAccessIterators. Although these iterators are available (via `std::vector`'s `begin` and `end` members), they return iterators to `std::string *`s. When comparing `string *` values the pointer values instead of the content of the strings are compared, which is not what we want.

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

        StringPtr::iterator begin();    // returns iterator to the first element
        StringPtr::iterator end();      // returns iterator beyond the last
                                        // element

Since these two members return the (proper) iterators, the elements in a `StringPtr` object can easily be sorted:

        int main()
        {
            StringPtr sp;               // assume sp is somehow filled

            sort(sp.begin(), sp.end()); // sp is now sorted
        }

To make this work, a type `StringPtr::iterator` is defined. As suggested by its type name, `iterator` is a nested type of `StringPtr`. To use a `StringPtr::iterator` in combination with the `sort` generic algorithm it must be a `RandomAccessIterator`, whose `value_type` is a `std::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 redesign `StringPtr`'s class interface. It offers members returning (reverse) iterators, and a nested `iterator` class. Here is 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 at `StringPtr::iterator`'s characteristics:

- `iterator` defines `StringPtr` as its friend, so `iterator`'s constructor can be private. Only the `StringPtr` class itself should be able to construct iterators. Copy construction and iterator-assignment should be possible, but that's possible by default and needs no specific declaration or implementation. Furthermore, since an iterator is already provided by `StringPtr`'s base class, we can use that iterator to access the information stored in the `StringPtr` object.

- `StringPtr::begin` and `StringPtr::end` may simply return `iterator` 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 of `iterator`'s remaining members are public. It's very easy to implement them, mainly manipulating and dereferencing the available iterator `d_current`. A `RandomAccessIterator` requires a series of operators. They usually have very simple implementations, and can often very well be implemented 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. Since `iterator` objects do not allocate any memory themselves, the default assignment operator can be used.
  - `bool operator==(iterator const &rhv) const`; testing the equality of two `iterator` 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 two `iterator` 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 an `InputIterator` and with all `const_iterators`, the return type of this overloaded operator should be `Type const &`. This operator returns a reference to a string. This string is obtained by dereferencing the dereferenced `d_current` value. As `d_current` is an iterator to `string *` 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 by `stepsize`:

        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 by `stepsize`:

        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 are `operator+=` and `operator-=`. They are not formally required by `RandomAccessIterators`, 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;
        }

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

### 22.14.2: Implementing a `reverse_iterator'

Once we've implemented an iterator, the matching reverse iterator can be implemented in a jiffy. To implement a reverse_iterator `std::reverse_iterator` is used, which nicely implements the reverse iterator once we have defined an iterator. Its constructor merely requires an object of the iterator type for which we want to construct a reverse iterator.

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

        using reverse_iterator = std::reverse_iterator<iterator>;

Also, the well-known members `rbegin` and `rend` are added to `StringPtr`'s interface. Again, they can easily be implemented inline:

    inline StringPtr::reverse_iterator StringPtr::rbegin()
    {
        return reverse_iterator(end());
    }
    inline StringPtr::reverse_iterator StringPtr::rend()
    {
        return reverse_iterator(begin());
    }

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

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

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

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

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

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

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

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

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

                generated output:
            a.out bravo charlie mike quebec zulu
            ======
            zulu quebec mike charlie bravo a.out
        */

Although it is thus possible to construct a reverse iterator from a normal iterator, the opposite does not hold true: it is not possible to initialize a normal iterator from a reverse iterator.

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

- First, use

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

  to obtain a `reverse_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.

However, we can't mix iterators and reverse iterators when using generic algorithms. So how can we initialize the second iterator using the available `reverse_iterator`? The solution is not very difficult, as an iterator may be initialized from a pointer. Although the reverse iterator `rit` is not a pointer, `&*(rit - 1)` or `&*--rit` is. So we use

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

to process all the lines up to the first of the set of trailing empty lines. In general, if `rit` is a `reverse_iterator` pointing to some element and we need an `iterator` to point to that element, we may use `&*rit` to initialize the iterator. Here, the dereference operator is applied to reach the element the reverse iterator refers to. Then the address operator is applied to obtain its address with which we can initialize the iterator.

When defining a `const_reverse_iterator` (e.g., matching a `const_iterator` class), then the `const_iterator's operator*` member should be a member returning a non-modifiable value or object. Since a `const_reverse_iterator` uses the iterator's `operator--` member, we're running against a small conceptual conflict. On the one hand, a `std::input_iterator_tag` is inappropriate, since we must allow decrementing the iterator. On the other hand, a `std::bidirectional_iterator` is inappropriate, since we don't allow modification of the data.

Iterator tags are primarily conceptual. If `const_iterators` and `const_reverse_iterators` only allow increment operations, then an `input_iterator_tag` is the best match for the iterator's intended use. Hence this tag is used below.

Furthermore, in line with the nature of a `input_iterator_tag` our `const_iterator` should not offer an `operator--`. This, of course, causes problems: a reverse iterator must be able to use the iterator's `operator--` member. This can easily be solved by stashing the iterator's `operator--` in the iterator's private section, and declaring `std::reverse_iterator<(const_)iterator>` its friend (note that declaring a `(const_)reverse_iterator` that is derived from `std::reverse_iterator` doesn't solve the issue: it is `std::reverse_iterator` that calls the iterator's `operator--`, not a class that is derived from it).

To keep the const-ness of dereferencing `const_iterator` iterators `using` specification can added to the `const_iterator` class. The `using` specifications provided by `Data::iterator` are inherited by `Data::const_iterator`, but `Data::const_iterator` may also specify:

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

whereafter its `operator *()` can return a `const_reference`.

The elements involved in defining an `iterator, const_iterator, reverse_iterator` and `const_reverse_iterator` for a class `Data` is illustrated in the following example, which only requires the definitions of the `iterator` and `const_iterator` classes, as these types can be passed to the `reverse_iterator` template to obtain the corresponding reverse-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