C++ Templates: The Complete Guide Class Templates

Class Templates

Templates and Design

Programs are generally constructed using designs that map relatively well on the mechanisms offered by a chosen programming language. Because templates are a whole new language mechanism, it is not surprising to find that they call for new design elements. We explore these elements in this part of the book.

Templates are different from more traditional language constructs in that they allow us to parameterize the types and constants of our code. When combined with (1) partial specialization and (2) recursive instantiation, this leads to a surprising amount of expressive power. In the following chapters, this is illustrated by a large number of design techniques:
  • Generic programming
  • Traits
  • Policy classes
  • Metaprogramming
  • Expression templates
Our presentation aims not only at listing the various known design elements, but also at conveying the principles that inspire such designs so that new techniques may be created.

The Polymorphic Power of Templates

Polymorphism is the ability to associate different specific behaviors with a single generic notation. [1] Polymorphism is also a cornerstone of the object-oriented programming paradigm, which in C++ is supported mainly through class inheritance and virtual functions. Because these mechanism are (at least in part) handled at run time, we talk about dynamic polymorphism. This is usually what is thought of when talking about plain polymorphism in C++. However, templates also allow us to associate different specific behaviors with a single generic notation, but this association is generally handled at compile time, which we refer to as static polymorphism. In this chapter we review the two forms of polymorphism and discuss which form is appropriate in which situations.
[1] Polymorphism literally refers to the condition of having many forms or shapes (from the Greek polumorphos).

Dynamic Polymorphism

Historically, C++ started with supporting polymorphism only through the use of inheritance combined with virtual functions. [2] The art of polymorphic design in this context consists of identifying a common set of capabilities among related object types and declaring them as virtual function interfaces in a common base class.
[2] Strictly speaking, macros can also be thought of as an early form of static polymorphism. However, they are left out of consideration because they are mostly orthogonal to the other language mechanisms.
The poster child for this design approach is an application that manages geometric shapes and allows them to be rendered in some way (for example, on a screen). In such an application we might identify a so-called abstract base class (ABC) GeoObj, which declares the common operations and properties applicable to geometric objects. Each concrete class for specific geometric objects then derives from GeoObj (see Figure 14.1):
Figure 14.1. Polymorphism implemented via inheritance
graphics/14fig01.gif
// poly/dynahier.hpp 

#include "coord.hpp" 

// common abstract base class GeoObj for geometric objects 
class GeoObj { 
  public: 
    // draw geometric object: 
    virtual void draw() const = 0; 
    // return center of gravity of geometric object: 
    virtual Coord center_of_gravity() const = 0; 
    … 
}; 

// concrete geometric object class Circle 
// - derived from GeoObj 
class Circle : public GeoObj { 
  public: 
    virtual void draw() const; 
    virtual Coord center_of_gravity() const; 
    … 
}; 

// concrete geometric object class Line 
// - derived from GeoObj 
class Line : public GeoObj { 
  public: 
    virtual void draw() const; 
    virtual Coord center_of_gravity() const; 
    … 
}; 
…
After creating concrete objects, client code can manipulate these objects through references or pointers to the base class, which enables the virtual function dispatch mechanism. Calling a virtual member function through a pointer or reference to a base class subobject results in an invocation of the appropriate member of the specific concrete object to which was referred.
In our example, the concrete code can be sketched as follows:
// poly/dynapoly.cpp 

#include "dynahier.hpp" 
#include <vector> 

// draw any GeoObj 
void myDraw (GeoObj const& obj) 
{ 
    obj.draw();            // call draw() according to type of object 
} 

// process distance of center of gravity between two GeoObjs 
Coord distance (GeoObj const& x1, GeoObj const& x2) 
{ 
    Coord c = x1.center_of_gravity() - x2.center_of_gravity(); 
    return c.abs();        // return coordinates as absolute values 
} 

// draw inhomogeneous collection of GeoObjs 
void drawElems (std::vector<GeoObj*> const& elems) 
{ 
    for (unsigned i=0; i<elems.size(); ++i) { 
        elems[i]->draw();  // call draw() according to type of element 
    } 
} 
int main() 
{ 
    Line l; 
    Circle c, c1, c2; 

    myDraw(l);            // myDraw(GeoObj&) => Line::draw() 
    myDraw(c);            // myDraw(GeoObj&) => Circle::draw() 

    distance(c1,c2);      // distance(GeoObj&,GeoObj&) 
    distance(l,c);        // distance(GeoObj&,GeoObj&) 

    std::vector<GeoObj*> coll;  // inhomogeneous collection 
    coll.push_back(&l);         // insert line 
    coll.push_back(&c);         // insert circle 
    drawElems(coll);            // draw different kinds of GeoObjs 
}
The key polymorphic interface elements are the functions draw() and center_of_gravity(). Both are virtual member functions. Our example demonstrates their use in the functions mydraw(), distance(),anddrawElems(). The latter functions are expressed using the common base type GeoObj. As a consequence it cannot be determined at compile time which version of draw() or center_of_gravity() has to be used. However, at run time, the complete dynamic type of the objects for which the virtual functions are invoked is accessed to dispatch the function calls. Hence, depending on the actual type of a geometric object, the appropriate operation is done: If mydraw() is called for a Line object, the expression obj.draw() calls Line::draw(), whereas for a Circle object the function Circle::draw() is called. Similarly, with distance() the member functions center_of_gravity() appropriate for the argument objects are called.

Perhaps the most compelling feature of this dynamic polymorphism is the ability to handle heterogeneous collections of objects. drawElems() illustrates this concept: The simple expression

elems[i]->draw()
results in invocations of different member functions, depending on the type of the element being iterated over.

Static Polymorphism

Templates can also be used to implement polymorphism. However, they don't rely on the factoring of common behavior in base classes. Instead, the commonality is implicit in that the different "shapes" of an application must support operations using common syntax (that is, the relevant functions must have the same names). Concrete classes are defined independently from each other (see Figure 14.2). The polymorphic power is then enabled when templates are instantiated with the concrete classes.
Figure 14.2. Polymorphism implemented via templates
graphics/14fig02.gif
For example, the function myDraw() in the previous section
void myDraw (GeoObj const& obj)   // GeoObj is abstract base class 
{ 
    obj.draw(); 
}
could conceivably be rewritten as follows:
template <typename GeoObj> 
void myDraw (GeoObj const& obj)   // GeoObj is template parameter 
{ 
    obj.draw(); 
}
Comparing the two implementations of myDraw(), we may conclude that the main difference is the specification of GeoObj as a template parameter instead of a common base class. There are, however, more fundamental differences under the hood. For example, using dynamic polymorphism we had only one myDraw() function at run time, whereas with the template we have distinct functions, such as myDraw<Line>() and myDraw<Circle>().
We may attempt to recode the complete example of the previous section using static polymorphism. First, instead of a hierarchy of geometric classes, we have several individual geometric classes:
// poly/statichier.hpp 

#include "coord.hpp" 

// concrete geometric object class Circle 
// - not derived from any class 
class Circle { 
  public: 
    void draw() const; 
    Coord center_of_gravity() const; 
    … 
}; 

// concrete geometric object class Line 
// - not derived from any class 
class Line { 
  public: 
    void draw() const; 
    Coord center_of_gravity() const; 
    … 
}; 
…
Now, the application of these classes looks as follows:
// poly/staticpoly.cpp 

#include "statichier.hpp" 
#include <vector> 

// draw any GeoObj 
template <typename GeoObj> 
void myDraw (GeoObj const& obj) 
{ 
    obj.draw();    // call draw() according to type of object 
} 

// process distance of center of gravity between two GeoObjs 
template <typename GeoObj1, typename GeoObj2> 
Coord distance (GeoObj1 const& x1, GeoObj2 const& x2) 
{ 
    Coord c = x1.center_of_gravity() - x2.center_of_gravity(); 
    return c.abs();  // return coordinates as absolute values 
} 

// draw homogeneous collection of GeoObjs 
template <typename GeoObj> 
void drawElems (std::vector<GeoObj> const& elems) 
{ 
    for (unsigned i=0; i<elems.size(); ++i) { 
        elems[i].draw();    // call draw() according to type of element 
    } 
} 

int main() 
{ 
    Line l; 
    Circle c, c1, c2; 

    myDraw(l);        // myDraw<Line>(GeoObj&) => Line::draw() 
    myDraw(c);        // myDraw<Circle>(GeoObj&) => Circle::draw() 

    distance(c1,c2);  // distance<Circle,Circle>(GeoObj1&,GeoObj2&) 
    distance(l,c);    // distance<Line,Circle>(GeoObj1&,GeoObj2&) 

    // std::vector<GeoObj*> coll;    // ERROR: no inhomogeneous 
                                     //        collection possible 
    std::vector<Line> coll;   // OK: homogeneous collection possible 
    coll.push_back(l);        // insert line 
    drawElems(coll);          // draw all lines 
}
As with myDraw(), GeoObj can no longer be used as a concrete parameter type for distance(). Instead, we provide for two template parameters GeoObj1 and GeoObj2. By using two different template parameters, different combinations of geometric object types can be accepted for the distance computation:
distance(l,c);   // distance<Line,Circle>(GeoObj1&,GeoObj2&)
However, heterogeneous collections can no longer be handled transparently. This is where the static part of static polymorphism imposes its constraint: All types must be determined at compile time. Instead, we can easily introduce different collections for different geometric object types. There is no longer a requirement that the collection be limited to pointers, which can have significant advantages in terms of performance and type safety.

Dynamic versus Static Polymorphism

Let's categorize and compare both forms of polymorphisms.

Terminology

Dynamic and static polymorphism provide support for different C++ programming idioms [3]:
[3] For a detailed discussion of polymorphism terminology, see also Sections 6.5 to 6.7 of [CzarneckiEiseneckerGenProg].
  • Polymorphism implemented via inheritance is bounded and dynamic:
    - Bounded means that the interfaces of the types participating in the polymorphic behavior are predetermined by the design of the common base class (other terms for this concept are invasive or intrusive).
    - Dynamic means that the binding of the interfaces is done at run time (dynamically).
  • Polymorphism implemented via templates is unbounded and static:
- Unbounded means that the interfaces of the types participating in the polymorphic behavior are not predetermined (other terms for this concept are noninvasive or nonintrusive).
- Static means that the binding of the interfaces is done at compile time (statically).
So, strictly speaking, in C++ parlance, dynamic polymorphism and static polymorphism are shortcuts for bounded dynamic polymorphism and unbounded static polymorphism. In other languages other combinations exist (for example, Smalltalk provides unbounded dynamic polymorphism). However, in the context of C++, the more concise terms dynamic polymorphism and static polymorphism do not cause confusion.

Strengths and Weaknesses

Dynamic polymorphism in C++ exhibits the following strengths:
  • Heterogeneous collections are handled elegantly.
  • The executable code size is potentially smaller (because only one polymorphic function is needed, whereas distinct template instances must be generated to handle different types).
  • Code can be entirely compiled; hence no implementation source must be published (distributing template libraries usually requires distribution of the source code of the template implementations).
In contrast, the following can be said about static polymorphism in C++:
  • Collections of built-in types are easily implemented. More generally, the interface commonality need not be expressed through a common base class.
  • Generated code is potentially faster (because no indirection through pointers is needed a priori and nonvirtual functions can be inlined much more often).
  • Concrete types that provide only partial interfaces can still be used if only that part ends up being exercised by the application.
Static polymorphism is often regarded as more type safe than dynamic polymorphism because all the bindings are checked at compile time. For example, there is little danger of inserting an object of the wrong type in a container instantiated from a template. However, in a container expecting pointers to a common base class, there is a possibility that these pointers unintentionally end up pointing to complete objects of different types.
In practice, template instantiations can also cause some grief when different semantic assumptions hide behind identical-looking interfaces. For example, surprises can occur when a template that assumes an associative operator + is instantiated for a type that is not associative with respect to that operator. In practice, this kind of semantic mismatch occurs less often with inheritance-based hierarchies, presumably because the interface specification is more explicitly specified.

Combining Both Forms

Of course, you could combine both forms of inheritance. For example, you could derive different kinds of geometric objects from a common base class to be able to handle inhomogeneous collections of geometric objects. However, you can still use templates to write code for a certain kind of geometric object.
The combination of inheritance and templates is further described in Chapter 16. We will see (among other things) how the virtuality of a member function can be parameterized and how an additional amount of flexibility is afforded to static polymorphism using the inheritance-based curiously recurring template pattern (or CRTP).

Generic Programming

Static polymorphism leads to the concept of generic programming. However, there is no one universally agreed-on definition of generic programming (just as there is no one agreed-on definition of object-oriented programming). According to [CzarneckiEiseneckerGenProg], definitions go from programming with generic parameters to finding the most abstract representation of efficient algorithms. The book summarizes:
Generic programming is a subdiscipline of computer science that deals with finding abstract representations of efficient algorithms, data structures, and other software concepts, and with their systematic organization…. Generic programming focuses on representing families of domain concepts. (pages 169 and 170)
In the context of C++, generic programming is sometimes defined as programming with templates (whereas object-oriented programming is thought of as programming with virtual functions). In this sense, just about any use of C++ templates could be thought of as an instance of generic programming. However, practitioners often think of generic programming as having an additional essential ingredient: Templates have to be designed in a framework for the purpose of enabling a multitude of useful combinations.
By far the most significant contribution in this area is the STL (the Standard Template Library, which later was adapted and incorporated into the C++ standard library). The STL is a framework that provides a number of useful operations, called algorithms, for a number of linear data structures for collections of objects, called containers. Both algorithms and containers are templates. However, the key is that the algorithms are not member functions of the containers. Instead, the algorithms are written in a generic way so that they can be used by any container (and linear collection of elements). To do this, the designers of STL identified an abstract concept of iterators that can be provided for any kind of linear collection. Essentially, the collection-specific aspects of container operations have been factored out into the iterators' functionality.
As a consequence, implementing an operation such as computing the maximum value in a sequence can be done without knowing the details of how values are stored in that sequence:
template <class Iterator> 
Iterator max_element (Iterator beg,   // refers to start of collection 
                      Iterator end)   // refers to end of collection 
{ 
    // use only certain Iterator's operations to traverse all elements 
    // of the collection to find the element with the maximum value 
    // and return its position as Iterator 
    … 
}
Instead of providing all useful operations such as max_element() by every linear container, the container has to provide only an iterator type to traverse the sequence of values it contains and member functions to create such iterators:
namespace std { 
    template <class T, … > 
    class vector { 
      public: 
        typedef … const_iterator;     // implementation-specific iterator 
        …                             // type for constant vectors 
        const_iterator begin() const; // iterator for start of collection 
        const_iterator end() const;   // iterator for end of collection 
        … 
    }; 

    template <class T, ... > 
    class list { 
      public: 
        typedef … const_iterator;     // implementation-specific iterator 
        …                             // type for constant lists 
        const_iterator begin() const; // iterator for start of collection 
        const_iterator end() const;   // iterator for end of collection 
        … 
    }; 
}
Now, you can find the maximum of any collection by calling the generic max_element() operation with the beginning and end of the collection as arguments (special handling of empty collections is omitted):
// poly/printmax.cpp 

#include <vector> 
#include <list> 
#include <algorithm> 
#include <iostream> 
#include "MyClass.hpp" 

template <typename T> 
void print_max (T const& coll) 
{ 
    // declare local iterator of collection 
    typename T::const_iterator pos; 

    // compute position of maximum value 
    pos = std::max_element(coll.begin(),coll.end()); 

    // print value of maximum element of coll (if any): 
    if (pos != coll.end()) { 
        std::cout << *pos << std::endl; 
    } 
    else { 
        std::cout << "empty" << std::endl; 
    } 
} 

int main() 
{ 
    std::vector<MyClass> c1; 
    std::list<MyClass> c2; 
    … 
    print_max (c1); 
    print_max (c2); 
}
By parameterizing its operations in terms of these iterators, the STL avoids an explosion in the number of operation definitions. Instead of implementing each operation for every container, you implement the algorithm once so that it can be used for every container. The generic glue is the iterators that are provided by the containers and that are used by the algorithms. This works because iterators have a certain interface that is provided by the containers and used by the algorithms. This interface is usually called a concept, which denotes a set of constraints that a template has to fulfill to fit into this framework.

In principle, functionally such as an STL-like approach could be implemented with dynamic polymorphism. In practice, however, it would be of limited use because the iterator concept is too lightweight compared with the virtual function call mechanism. Adding an interface layer based on virtual functions would most likely slow down our operations by an order of magnitude (or more).

Generic programming is practical exactly because it relies on static polymorphism, which resolves interfaces at compile time. On the other hand, the requirement that the interfaces be resolved at compile time also calls for new design principles that are different in many ways from object-oriented design principles. Many of the most important of these generic design principles are described in the remainder of this book.

Afternotes

Container types were a primary motivation for the introduction of templates into the C++ programming language. Prior to templates, polymorphic hierarchies were a popular approach to containers. A popular example was the National Institutes of Health Class Library (NIHCL), which to a large extent translated the container class hierarchy of Smalltalk (see Figure 14.5).
Figure 14.5. Class hierarchy of the NIHCL
graphics/14fig05.gif
Much like the C++ standard library, the NIHCL supported a rich variety of containers as well as iterators. However, the implementation followed the Smalltalk style of dynamic polymorphism: Iterators used the abstract base class Collection to operate on different types of collections:
Bag c1; 
Set c2; 
… 
Iterator i1(s); 
Iterator i2(b); 
…
Unfortunately, the price of this approach was high both in terms of running time and memory usage. Running time was typically orders of magnitude worse than equivalent code using the C++ standard library because most operations ended up requiring a virtual call (whereas in the C++ standard library many operations are inlined, and no virtual functions are involved in iterator and container interfaces). Furthermore, because (unlike Smalltalk) the interfaces were bounded, built-in types had to be wrapped in larger polymorphic classes (such wrappers were provided by the NIHCL), which in turn could lead to dramatic increases in storage requirements.
Some sought solace in macros, but even in today's age of templates many projects still make suboptimal choices in their approach to polymorphism. Clearly there are many situations when dynamic polymorphism is the "right choice." Heterogeneous iterations are an example. However, in the same vein, many programming tasks are naturally and efficiently solved using templates, and homogeneous containers are an example of this.
Static polymorphism lends itself well to code very fundamental computing structures. In contrast, the need to choose a common base type implies that a dynamic polymorphic library will normally have to make domain-specific choices. It's no surprise then that the STL part of the C++ standard library never included polymorphic containers, but it contains a rich set of containers and iterators that use static polymorphism (as demonstrated in Section 14.5 on page 241).
Medium and large C++ programs typically need to handle both kinds of polymorphism discussed in this chapter. In some situations it may even be necessary to combine them very intimately. In many cases the optimal design choices are clear in light of our discussion, but spending some time thinking about long-term potential evolutions almost always pays off.



Followers

 

Tontenk