Template
Let's imagine that we want to write a function to compare two values and indicate whether the first is less than, equal to, or greater than the second. In practice, we'd want to define several such functions, each of which could compare values of a given type. Our first attempt might be to define several overloaded functions:
// returns 0 if the values are equal, -1 if v1 is smaller, 1 if v2 is smaller
int compare(const string &v1, const string &v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
int compare(const double &v1, const double &v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
These functions are nearly identical: The only difference between them is the type of their parameters. The function body is the same in each function.
Defining a Function Template
The following is a template version of compare:
// implement strcmp-like generic compare function
// returns 0 if the values are equal, 1 if v1 is larger, -1 if v1 is smaller
template
int compare(const T &v1, const T &v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
A template definition starts with the keyword template followed by a template parameter list, which is a comma-separated list of one or more template parameters bracketed by the less-than (<) and greater-than (>) tokens.
The template parameter list cannot be empty
Template Parameter List
The template parameter list acts much like a function parameter list. A function parameter list defines local variable(s) of a specified type but leaves those variables uninitialized. At run time, arguments are supplied that initialize the parameters.
int main ()
{
// T is int;
// compiler instantiates int compare(const int&, const int&)
cout << compare(1, 0) << endl;
// T is string;
// compiler instantiates int compare(const string&, const string&)
string s1 = "hi", s2 = "world";
cout << compare(s1, s2) << endl;
return 0;
}
the compiler will instantiate two different versions of compare. The compiler will create one version that replaces T by int and a second version that uses string in place of T.
inline Function Templates
A function template can be declared inline in the same way as a nontemplate function. The specifier is placed following the template parameter list and before the return type. It is not placed in front of the template keyword.
// ok: inline specifier follows template parameter list
template inline T min(const T&, const T&);
// error: incorrect placement of inline specifier
inline template T min(const T&, const T&);
Defining a Class Template
template class Queue {
public:
Queue (); // default constructor
Type &front (); // return element from head of Queue
const Type &front () const;
void push (const Type &); // add element to back of Queue
void pop(); // remove element from head of Queue
bool empty() const; // true if no elements in the Queue
private:
// ...
};
A class template is a template, so it must begin with the keyword template followed by a template parameter list. Our Queue template takes a single template type parameter named Type.
Using a Class Template
In contrast to calling a function template, when we use a class template, we must explicitly specify arguments for the template parameters:
Queue qi; // Queue that holds ints
Queue< vector > qc; // Queue that holds vectors of doubles
Queue qs; // Queue that holds strings
Template Parameters
As with a function parameter, the name chosen by the programmer for a template parameter has no intrinsic meaning. In our example, we named compare's template type parameter T, but we could have named it anything:
// equivalent template definition
template
int compare(const Glorp &v1, const Glorp &v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
This code defines the same compare template as before.
Template Parameter Scope
typedef double T;
template T calc(const T &a, const T &b)
{
// tmp has the type of the template parameter T
// not that of the global typedef
T tmp = a;
// ...
return tmp;
}
Restrictions on the Use of a Template Parameter Name
A name used as a template parameter may not be reused within the template:
template T calc(const T &a, const T &b)
{
typedef double T; // error: redeclares template parameter T
T tmp = a;
// ...
return tmp;
}
This restriction also means that the name of a template parameter can be used only once within the same template parameter list:
// error: illegal reuse of template parameter name V
template V calc(const V&, const V&) ;
Of course, just as we can reuse function parameter names, the name of a template parameter can be reused across different templates:
// ok: reuses parameter type name across different templates
template T calc (const T&, const T&) ;
template int compare(const T&, const T&) ;
Template Declarations
As with any other function or class, we can declare a template without defining it. A declaration must indicate that the function or class is a template:
// declares compare but does not define it
template int compare(const T&, const T&) ;
Each template type parameter must be preceded either by the keyword class or typename; each nontype parameter must be preceded by a type name. It is an error to omit the keyword or a type specifier:
// error: must precede U by either typename or class
template T calc (const T&, const U&) ;
Template Type Parameters
// ok: same type used for the return type and both parameters
template T calc (const T& a, const T& b)
{
// ok: tmp will have same type as the parameters & return type
T tmp = a;
// ...
return tmp;
}
Distinction Between typename and class
In a function template parameter list, the keywords typename and class have the same meaning and can be used interchangeably. Both keywords can be used in the same template parameter list:
// ok: no distinction between typename and class in template parameter list
template calc (const T&, const U&);
Designating Types inside the Template Definition
template
Parm fcn(Parm* array, U value)
{
Parm: :size_type * p; // If Parm::size_type is a type, then a declaration
// If Parm::size_type is an object, then multiplication
}
We know that size_type must be a member of the type bound to Parm, but we do not know whether size_type is the name of a type or a data member. By default, the compiler assumes that such names name data members, not types.
If we want the compiler to treat size_type as a type, then we must explicitly tell the compiler to do so:
template
Parm fcn(Parm* array, U value)
{
typename Parm::size_type * p; // ok: declares p to be a pointer
}
Nontype Template Parameters
// initialize elements of an array to zero
template void array_init(T (&parm)[N])
{
for (size_t i = 0; i != N; ++i) {
parm[i] = 0;
}
}
A template nontype parameter is a constant value inside the template definition. A nontype parameter can be used when constant expressions are requiredfor example, as we do hereto specify the size of an array.
A template nontype parameter is a constant value inside the template definition. A nontype parameter can be used when constant expressions are requiredfor example, as we do hereto specify the size of an array.
When array_init is called, the compiler figures out the value of the nontype parameter from the array argument:
int x[42];
double y[10];
array_init(x); // instantiates array_init(int(&)[42]
array_init(y); // instantiates array_init(double(&)[10]
The compiler will instantiate a separate version of array_init for each kind of array used in a call to array_init. For the program above, the compiler instantiates two versions of array_init: The first instance has its parameter bound to int[42], and in the other, that parameter is bound to double[10].
Type Equivalence and Nontype Parameters
Expressions that evaluate to the same value are considered equivalent template arguments for a template nontype parameter. The following calls to array_init both refer to the same instantiation, array_init:
int x[42];
const int sz = 40;
int y[sz + 2];
array_init(x); // instantiates array_init(int(&)[42])
array_init(y); // equivalent instantiation
Writing Generic Programs
The operations performed inside a function template constrains the types that can be used to instantiate the function. It is up to the programmer to guarantee that the types used as the function arguments actually support any operations that are used, and that those operations behave correctly in the context in which the template uses them.
/*-----------------------------------------------
Instantiation
When we write
Queue qi;
the compiler automatially creates a class named Queue. In effect, the compiler creates the Queue class by rewriting the Queue template, replacing every occurrence of the template parameter Type by the type int. The instantiated class is as if we had written:
// simulated version of Queue instantiated for type int
template class Queue {
public:
Queue(); // this bound to Queue*
int &front(); // return type bound to int
const int &front() const; // return type bound to int
void push(const int &); // parameter type bound to int
void pop(); // type invariant code
bool empty() const; // type invariant code
private:
// ...
};
To create a Queue class for objects of type string, we'd write:
Queue qs;
In this case, each occurrence of Type would be replaced by string.
Class Template Arguments Are Required
When we want to use a class template, we must always specify the template arguments explicitly.
Queue qs; // error: which template instantiation?
Queue qi; // ok: defines Queue that holds ints
Queue qs; // ok: defines Queue that holds strings
The type defined by a template class always includes the template argument(s). For example, Queue is not a type; Queue or Queue are.
Function-Template Instantiation
Template Argument Deduction
Multiple Type Parameter Arguments Must Match Exactly
template
int compare(const T& v1, const T& v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
int main()
{
short si;
// error: cannot instantiate compare(short, int)
// must be: compare(short, short) or
// compare(int, int)
compare(si, 1024);
return 0;
}
If the designer of compare wants to allow normal conversions on the arguments, then the function must be defined with two type parameters:
// argument types can differ, but must be compatible
template
int compare(const A& v1, const B& v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
Now the user may supply arguments of different types:
short si;
compare(si, 1024); // ok: instantiates compare(short, int)
However, a < operator must exist that can compare values of those types.
As examples, consider calls to the functions fobj and fref. The fobj function copies its parameters, whereas fref's parameters are references:
template T fobj(T, T); // arguments are copied
template
T fref(const T&, const T&); // reference arguments
string s1("a value");
const string s2("another value");
fobj(s1, s2); // ok: calls f(string, string), const is ignored
fref(s1, s2); // ok: non const object s1 converted to const reference
int a[10], b[42];
fobj(a, b); // ok: calls f(int*, int*)
fref(a, b); // error: array types don't match; arguments aren't converted to pointers
The restriction on type conversions applies only to those arguments whose types are template parameters.
function template sum has two parameters:
template Type sum(const Type &op1, int op2)
{
return op1 + op2;
}
The first parameter, op1, has a template parameter type. Its actual type cannot be known until the function is used. The type of the second parameter, op2, is known: It's int.
Because the type of op2 is fixed, normal conversions can be applied to arguments passed to op2 when sum is called:
double d = 3.14;
string s1("hiya"), s2(" world");
sum(1024, d); // ok: instantiates sum(int, int), converts d to int
sum(1.4, d); // ok: instantiates sum(double, int), converts d to int
sum(s1, s2); // error: s2 cannot be converted to int
Template Argument Deduction and Function Pointers
As an example, assume we have a function pointer that points to a function returning an int that takes two parameters, each of which is a reference to a const int. We could use that pointer to point to an instantiation of compare:
template int compare(const T&, const T&);
// pf1 points to the instantiation int compare (const int&, const int&)
int (*pf1) (const int&, const int&) = compare;
It is an error if the template arguments cannot be determined from the function pointer type. For example, assume we have two functions named func. Each function takes a pointer to function argument. The first version of func takes a pointer to a function that has two const string reference parameters and returns a string. The second version of func takes a pointer to a function taking two const int reference parameters and returning an int. We cannot use compare as an argument to func:
// overloaded versions of func; each take a different function pointer type
void func(int(*) (const string&, const string&));
void func(int(*) (const int&, const int&));
func(compare); // error: which instantiation of compare?
Because it is not possible to identify a unique instantiation for the argument to func, this call is a compile-time (or link-time) error.
Function-Template Explicit Arguments
// T or U as the returntype?
template ??? sum(T, U);
In this case, the answer is that neither parameter works all the time. Using either parameter is bound to fail at some point:
// neither T nor U works as return type
sum(3, 4L); // second type is larger; want U sum(T, U)
sum(3L, 4); // first type is larger; want T sum(T, U)
One approach to solving this problem would be to force callers of sum to cast (Section 5.12.4, p. 183) the smaller type to the type we wish to use as the result:
// ok: now either T or U works as return type
int i; short s;
sum(static_cast(s), i); // ok: instantiates int sum(int, int)
Using a Type Parameter for the Return Type
An alternative way to specify the return type is to introduce a third template parameter that must be explicitly specified by our caller:
// T1 cannot be deduced: it doesn't appear in the function parameter list
template
T1 sum(T2, T3);
// ok T1 explicitly specified; T2 and T3 inferred from argument types
long val3 = sum(i, lng); // ok: calls long sum(int, long)
// poor design: Users must explicitly specify all three template parameters
template
T3 alternative_sum(T2, T1);
then we would always have to specify arguments for all three parameters:
// error: can't infer initial template parameters
long val3 = alternative_sum(i, lng);
// ok: All three parameters explicitly specified
long val2 = alternative_sum(i, lng);
Another example where explicit template arguments would be useful is the ambiguous program from page 641. We could disambiguate that case by using explicit template argument:
template int compare(const T&, const T&);
// overloaded versions of func; each take a different function pointer type
void func(int(*) (const string&, const string&));
void func(int(*) (const int&, const int&));
func(compare); // ok: explicitly specify which version of compare
Template Compilation Models
When the compiler sees a template definition, it does not generate code immediately. The compiler produces type-specific instances of the template only when it sees a use of the template, such as when a function template is called or an object of a class template is defined.
Inclusion Compilation Model
// header file utlities.h
#ifndef UTLITIES_H // header gaurd (Section 2.9.2, p. 69)
#define UTLITIES_H
template int compare(const T&, const T&);
// other declarations
#include "utilities.cc" // get the definitions for compare etc.
#endif
// implemenatation file utlities.cc
template int compare(const T &v1, const T &v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
// other definitions
Separate Compilation Model
Ordinarily, we indicate that a function template is exported as part of its definition. We do so by including the keyword export before the template keyword:
// the template definition goes in a separately-compiled source file
export template
Type sum(Type t1, Type t2) /* ...*/
The declaration for this function template, should, as usual, be put in a header. The declaration must not specify export.
Instead, we export the class in the class implementation file:
// class template header goes in shared header file
template class Queue { ... };
// Queue.ccimplementation file declares Queue as exported
export template class Queue;
#include "Queue.h"
//-------------------------------------------------------------
Class Template Members
The standard library implements queue as an adaptor (Section 9.7, p. 348) on top of another container. To emphasize the programming points involved in using a lower-level data structure, we'll implement our Queue class as a linked list. In practice, using a library container in our implementation would probably be a better decision.
Queue Implementation Strategy
The QueueItem Class
We'll start our implementation by writing the QueueItem class:
template class QueueItem {
// private class: no public section
QueueItem(const Type &t): item(t), next(0) { }
Type item; // value stored in this element
QueueItem *next; // pointer to next element in the Queue
};
Each time we instantiate a Queue class, the same version of QueueItem will be instantiated as well. For example, if we create Queue, then a companion class, QueueItem, will be instantiated.
The Queue Class
We can now flesh out our Queue class:
template class Queue {
public:
// empty Queue
Queue(): head(0), tail(0) { }
// copy control to manage pointers to QueueItems in the Queue
Queue(const Queue &Q): head(0), tail(0)
{ copy_elems(Q); }
Queue& operator=(const Queue&);
~Queue() { destroy(); }
// return element from head of Queue
// unchecked operation: front on an empty Queue is undefined
Type& front() { return head->item; }
const Type &front() const { return head->item; }
void push(const Type &); // add element to back of Queue
void pop (); // remove element from head of Queue
bool empty () const { // true if no elements in the Queue
return head == 0;
}
private:
QueueItem *head; // pointer to first element in Queue
QueueItem *tail; // pointer to last element in Queue
// utility functions used by copy constructor, assignment, and destructor
void destroy(); // delete all the elements
void copy_elems(const Queue&); // copy elements from parameter
};
References to a Template Type in the Scope of the Template
Class-Template Member Functions
It must start with the keyword template followed by the template parameter list for the class.
It must indicate the class of which it is a member.
The class name must include its template parameters.
From these rules, we can see that a member function of class Queue defined outside the class will start as
template ret-type Queue::member-name
The destroy Function
To illustrate a class template member function defined outside its class, let's look at the destroy function:
template void Queue::destroy()
{
while (!empty())
pop();
}
The pop Function
The pop member removes the value at the front of the Queue:
template void Queue::pop()
{
// pop is unchecked: Popping off an empty Queue is undefined
QueueItem* p = head; // keep pointer to head so we can delete it
head = head->next; // head now points to next element
delete p; // delete old head element
}
The push Function
The push member places a new item at the back of the queue:
template void Queue::push(const Type &val)
{
// allocate a new QueueItem object
QueueItem *pt = new QueueItem(val);
// put item onto existing queue
if (empty())
head = tail = pt; // the queue now has only one element
else {
tail->next = pt; // add new element to end of the queue
tail = pt;
}
}
The copy Function
Aside from the assignment operator, which we leave as an exercise, the only remaining function to write is copy_elems. This function is designed to be used by the assignment operator and copy constructor. Its job is to copy the elements from its parameter into this Queue:
template
void Queue::copy_elems(const Queue &orig)
{
// copy elements from orig into this Queue
// loop stops when pt == 0, which happens when we reach orig.tail
for (QueueItem *pt = orig.head; pt; pt = pt->next)
push(pt->item); // copy the element
}
Instantiation of Class-Template Member Functions
Queue qi; // instantiates class Queue
short s = 42;
int i = 42;
// ok: s converted to int and passed to push
qi.push(s); // instantiates Queue::push(const int&)
qi.push(i); // uses Queue::push(const int&)
f(s); // instantiates f(const short&)
f(i); // instantiates f(const int&)
When Classes and Members Are Instantiated
// instantiates Queue class and Queue::Queue()
Queue qs;
qs.push("hello"); // instantiates Queue::push
The first statement instantiates the Queue class and its default constructor. The next statement instantiates the push member function.
The instantiation of the push member:
template void Queue::push(const Type &val)
{
// allocate a new QueueItem object
QueueItem *pt = new QueueItem(val);
// put item onto existing queue
if (empty())
head = tail = pt; // the queue now has only one element
else {
tail->next = pt; // add new element to end of the queue
tail = pt;
}
}
Template Arguments for Nontype Parameters
template
class Screen {
public:
// template nontype parameters used to initialize data members
Screen(): screen(hi * wid, '#'), cursor (0),
height(hi), width(wid) { }
// ...
private:
std::string screen;
std::string::size_type cursor;
std::string::size_type height, width;
};
As with any class template, the parameter values must be explicitly stated whenever we use the Screen type:
Screen<24,80> hp2621; // screen 24 lines by 80 characters
Friend Declarations in Class Templates
There are three kinds of friend declarations that may appear in a class template. Each kind of declaration declares friendship to one or more entities:
A friend declaration for an ordinary nontemplate class or function, which grants friendship to the specific named class or function.
A friend declaration for a class template or function template, which grants access to all instances of the friend.
A friend declaration that grants access only to a specific instance of a class or function template.
Ordinary Friends
A nontemplate class or function can be a friend to a class template:
template class Bar {
// grants access to ordinary, nontemplate class and function
friend class FooBar;
friend void fcn();
// ...
};
This declaration says that the members of FooBar and the function fcn may access the private and protected members of any instantiation of class Bar.
General Template Friendship
A friend can be a class or function template:
template class Bar {
// grants access to Foo1 or templ_fcn1 parameterized by any type
template friend class Foo1;
template friend void templ_fcn1(const T&);
// ...
};
Specific Template Friendship
Rather than making all instances of a template a friend, a class can grant access to only a specific instance:
template class Foo2;
template void templ_fcn2(const T&);
template class Bar {
// grants access to a single specific instance parameterized by char*
friend class Foo2;
friend void templ_fcn2(char* const &);
// ...
};
More common are friend declarations of the following form:
template class Foo3;
template void templ_fcn3(const T&);
template class Bar {
// each instantiation of Bar grants access to the
// version of Foo3 or templ_fcn3 instantiated with the same type
friend class Foo3;
friend void templ_fcn3(const Type&);
// ...
};
Bar bi; // Foo3 and templ_fcn3 are friends
Bar bs; // Foo3, templ_fcn3 are friends
Declaration Dependencies
template class A;
template class B {
public:
friend class A; // ok: A is known to be a template
friend class C; // ok: C must be an ordinary, nontemplate class
template friend class D; // ok: D is a template
friend class E; // error: E wasn't declared as a template
friend class F; // error: F wasn't declared as a template
};
If we have not previously told the compiler that the friend is a template, then the compiler will infer that the friend is an ordinary nontemplate class or function.
// function template declaration must precede friend declaration in QueueItem
template
std::ostream& operator<<(std::ostream&, const Queue&);
template class QueueItem {
friend class Queue;
// needs access to item and next
friend std::ostream&
operator<< (std::ostream&, const Queue&);
// ...
};
template class Queue {
// needs access to head
friend std::ostream&
operator<< (std::ostream&, const Queue&);
};
Defining a Member Template
A template member declaration looks like the declaration of any template:
template class Queue {
public:
// construct a Queue from a pair of iterators on some sequence
template
Queue(It beg, It end):
head(0), tail(0) { copy_elems(beg, end); }
// replace current Queue by contents delimited by a pair of iterators
template void assign(Iter, Iter);
// rest of Queue class as before
private:
// version of copy to be used by assign to copy elements from iterator range
template void copy_elems(Iter, Iter);
};
template template
void Queue::assign(Iter beg, Iter end)
{
destroy(); // remove existing elements in this Queue
copy_elems(beg, end); // copy elements from the input range
}
template template
The first template parameter list templateis that of the class template. The second template parameter list templateis that of the member template.
template template
void Queue::copy_elems(It beg, It end)
{
while (beg != end) {
push(*beg);
++beg;
}
}
Because assign erases elements in the existing container, it is essential that the iterators passed to assign refer to elements in a different container. The standard container assign members and iterator constructors have the same restrictions.
To understand how instantiation works, let's look at uses of these members to copy and assign elements from an array of shorts or a vector:
short a[4] = { 0, 3, 6, 9 };
// instantiates Queue::Queue(short *, short *)
Queue qi(a, a + 4); // copies elements from a into qi
vector vi(a, a + 4);
// instantiates Queue::assign(vector::iterator,
// vector::iterator)
qi.assign(vi.begin(), vi.end());
The Complete Queue Class
For completeness, here is the final definition of our Queue class:
// declaration that Queue is a template needed for friend declaration in QueueItem
template class Queue;
// function template declaration must precede friend declaration in QueueItem
template
std::ostream& operator<<(std::ostream&, const Queue&);
template class QueueItem {
friend class Queue;
// needs access to item and next
friend std::ostream& // defined on page 659
operator<< (std::ostream&, const Queue&);
// private class: no public section
QueueItem(const Type &t): item(t), next(0) { }
Type item; // value stored in this element
QueueItem *next; // pointer to next element in the Queue
};
template class Queue {
// needs access to head
friend std::ostream& // defined on page 659
operator<< (std::ostream&, const Queue&);
public:
// empty Queue
Queue(): head(0), tail(0) { }
// construct a Queue from a pair of iterators on some sequence
template
Queue(It beg, It end):
head(0), tail(0) { copy_elems(beg, end); }
// copy control to manage pointers to QueueItems in the Queue
Queue(const Queue &Q): head(0), tail(0)
{ copy_elems(Q); }
Queue& operator=(const Queue&); // left as exercise for the reader
~Queue() { destroy(); }
// replace current Queue by contents delimited by a pair of iterators
template void assign(Iter, Iter);
// return element from head of Queue
// unchecked operation: front on an empty Queue is undefined
Type& front() { return head->item; }
const Type &front() const { return head->item; }
void push(const Type &);// defined on page 652
void pop(); // defined on page 651
bool empty() const { // true if no elements in the Queue
return head == 0;
}
private:
QueueItem *head; // pointer to first element in Queue
QueueItem *tail; // pointer to last element in Queue
// utility functions used by copy constructor, assignment, and destructor
void destroy(); // defined on page 651
void copy_elems(const Queue&); // defined on page 652
// version of copy to be used by assign to copy elements from iterator range
// defined on page 662
template void copy_elems(Iter, Iter);
};
// Inclusion Compilation Model: include member function definitions as well
#include "Queue.cc"
static Members of Class Templates
template class Foo {
public:
static std::size_t count() { return ctr; }
// other interface members
private:
static std::size_t ctr;
// other implementation members
};
defines a class template named Foo that among other members has a public static member function named count and a private static data member named ctr.
Each instantiation of class Foo has its own static member:
// Each object shares the same Foo::ctrand Foo::count members
Foo fi, fi2, fi3;
// has static members Foo::ctrand Foo::count
Foo fs;
Using a static Member of a Class Template
As usual, we can access a static member of a class template through an object of the class type or by using the scope operator to access the member directly. Of course, when we attempt to use the static member through the class, we must refer to an actual instantiation:
Foo fi, fi2; // instantiates Foo class
size_t ct = Foo::count(); // instantiates Foo::count
ct = fi.count(); // ok: uses Foo::count
ct = fi2.count(); // ok: uses Foo::count
ct = Foo::count(); // error: which template instantiation?
Defining a static Member
As with any other static data member, there must be a definition for the data member that appears outside the class. In the case of a class template static, the member definition must inidicate that it is for a class template:
template
size_t Foo::ctr = 0; // define and initialize ctr
//----------------------------
Defining the Handle Class
Our Handle class will behave like a pointer: Copying a Handle will not copy the underlying object. After the copy, both Handles will refer to the same underlying object. To create a Handle, a user will be expected to pass the address of a dynamically allocated object of the type (or a type derived from that type) managed by the Handle. From that point on, the Handle will "own" the given object. In particular, the Handle class will assume responsibility for deleting that object once there are no longer any Handles attached to it.
Given this design, here is an implementation of our generic Handle:
/* generic handle class: Provides pointerlike behavior. Although access through
* an unbound Handle is checked and throws a runtime_error exception.
* The object to which the Handle points is deleted when the last Handle goes away.
* Users should allocate new objects of type T and bind them to a Handle.
* Once an object is bound to a Handle,, the user must not delete that object.
*/
template class Handle {
public:
// unbound handle
Handle(T *p = 0): ptr(p), use(new size_t(1)) { }
// overloaded operators to support pointer behavior
T& operator*();
T* operator->();
const T& operator*() const;
const T* operator->() const;
// copy control: normal pointer behavior, but last Handle deletes the object
Handle(const Handle& h): ptr(h.ptr), use(h.use)
{ ++*use; }
Handle& operator=(const Handle&);
~Handle() { rem_ref(); }
private:
T* ptr; // shared object
size_t *use; // count of how many Handle spointto *ptr
void rem_ref()
{ if (--*use == 0) { delete ptr; delete use; } }
};
This class looks like our other handles, as does the assignment operator.
template
inline Handle& Handle::operator=(const Handle &rhs)
{
++*rhs.use; // protect against self-assignment
rem_ref(); // decrement use count and delete pointers if needed
ptr = rhs.ptr;
use = rhs.use;
return *this;
}
The only other members our class will define are the dereference and member access operators. These operators will be used to access the underlying object. We'll provide a measure of safety by having these operations check that the Handle is actually bound to an object. If not, an attempt to access the object will throw an exception.
The nonconst versions of these operators look like:
template inline T& Handle::operator*()
{
if (ptr) return *ptr;
throw std::runtime_error
("dereference of unbound Handle");
}
template inline T* Handle::operator->()
{
if (ptr) return ptr;
throw std::runtime_error
("access through unbound Handle");
}
The const versions would be similar and are left as an exercise.
Using the Handle
{ // new scope
// user allocates but must not delete the object to which the Handle is attached
Handle hp(new int(42));
{ // new scope
Handle hp2 = hp; // copies pointer; use count incremented
cout << *hp << " " << *hp2 << endl; // prints 42 42
*hp2 = 10; // changes value of shared underlying int
} // hp2 goes out of scope; use count is decremented
cout << *hp << endl; // prints 10
} // hp goes out of scope; its destructor deletes the int
Using a Handle to Use-Count a Pointer
class Sales_item {
public:
// default constructor: unbound handle
Sales_item(): h() { }
// copy item and attach handle to the copy
Sales_item(const Item_base &item): h(item.clone()) { }
// no copy control members: synthesized versions work
// member access operators: forward their work to the Handle class
const Item_base& operator*() const { return *h; }
const Item_base* operator->() const
{ return h.operator->(); }
private:
Handle h; // use-counted handle
};
double Basket::total() const
{
double sum = 0.0; // holds the running total
/* find each set of items with the same isbn and calculate
* the net price for that quantity of items
* iter refers to first copy of each book in the set
* upper_boundrefers to next element with a different isbn
*/
for (const_iter iter = items.begin();
iter != items.end();
iter = items.upper_bound(*iter))
{
// we know there's at least one element with this key in the Basket
// virtual call to net_priceapplies appropriate discounts, if any
sum += (*iter)->net_price(items.count(*iter));
}
return sum;
}
It's worthwhile to look in detail at the statement that calls net_price:
sum += (*iter)->net_price(items.count(*iter));
This statement uses operator -> to fetch and run the net_price function. What's important to understand is how this operator works:
(*iter) returns h, our use-counted handle member.
(*iter)-> therefore uses the overloaded arrow operator of the handle class
The compiler evaluates h.operator->(), which in turn yields the pointer to Item_base that the Handle holds.
The compiler dereferences that Item_base pointer and calls the net_price member for the object to which the pointer points.
//------------------------------------------------------------------
Template Specializations
template
int compare(const T &v1, const T &v2)
{
if (v1 < v2) return -1;
if (v2 < v1) return 1;
return 0;
}
Specializing a Function Template
The following program defines a specialization of compare when the template parameter type is bound to const char*:
// special version of compare to handle C-style character strings
template <>
int compare(const char* const &v1,
const char* const &v2)
{
return strcmp(v1, v2);
}
Now when we call compare, passing it two character pointers, the compiler will call our specialized version. It will call the generic version for any other argument types (including plain char*):
const char *cp1 = "world", *cp2 = "hi";
int i1, i2;
compare(cp1, cp2); // calls the specialization
compare(i1, i2); // calls the generic version instantiated with int
Declaring a Template Specialization
// declaration of function template explicit specialization
template<>
int compare(const char* const&,
const char* const&);
// error: invalid specialization declarations
// missing template<>
int compare(const char* const&,
const char* const&);
// error: function parameter list missing
template<> int compare;
// ok: explicit template argument const char* deduced from parameter types
template<> int compare(const char* const&,
const char* const&);
Function Overloading versus Template Specializations
// generic template definition
template
int compare(const T& t1, const T& t2) { /* ... */ }
// OK: ordinary function declaration
int compare(const char* const&, const char* const&);
For now, what's important to know is that when we define a nontemplate function, normal conversions are applied to the arguments. When we specialize a template, conversions are not applied to the argument types. In a call to a specialized version of a template, the argument type(s) in the call must match the specialized version function parameter type(s) exactly. If they don't, then the compiler will instantiate an instantiation for the argument(s) from the template definition.
Ordinary Scope Rules Apply to Specializations
Before we can declare or define a specialization, a declaration for the template that it specializes must be in scope. Similarly, a declaration for the specialization must be in scope before that version of the template is called:
// define the general compare template
template
int compare(const T& t1, const T& t2) { /* ... */ }
int main() {
// uses the generic template definition
int i = compare("hello", "world");
// ...
}
// invalid program: explicit specialization after call
template<>
int compare(const char* const& s1,
const char* const& s2)
{ /* ... */ }
A program cannot have both an explicit specialization and an instantiation for the same template with the same set of template arguments.
It is an error for a specialization to appear after a call to that instance of the template has been seen.
Specializing a Class Template
Defining a Class Specialization
One way to provide the right behavior for Queue's of C-style strings is to define a specialized version of the entire class for const char*:
/* definition of specialization for const char*
* this class forwards its work to Queue;
* the push function translates the const char* parameter to a string
* the front functions return a string rather than a const char*
*/
template<> class Queue {
public:
// no copy control: Synthesized versions work for this class
// similarly, no need for explicit default constructor either
void push(const char*);
void pop() {real_queue.pop();}
bool empty() const {return real_queue.empty();}
// Note: return type does not match template parameter type
std::string front() {return real_queue.front();}
const std::string &front() const
{return real_queue.front();}
private:
Queue real_queue; // forward calls to real_queue
};
When a member is defined outside the class specialization, it is not preceded by the tokens template<>.
Our class defines only one member outside the class:
void Queue::push(const char* val)
{
return real_queue.push(val);
}
Specializing Members but Not the Class
template <>
void Queue::push(const char *const &val)
{
// allocate a new character array and copy characters from val
char* new_item = new char[strlen(val) + 1];
strncpy(new_item, val, strlen(val) + 1);
// store pointer to newly allocated and initialized element
QueueItem *pt =
new QueueItem(new_item);
// put item onto existing queue
if (empty())
head = tail = pt; // queue has only one element
else {
tail->next = pt; // add new element to end of queue
tail = pt;
}
}
template <>
void Queue::pop()
{
// remember head so we can delete it
QueueItem *p = head;
delete head->item; // delete the array allocated in push
head = head->next; // head now points to next element
delete p; // delete old head element
}
Now, the class type Queue will be instantiated from the generic class template definition, with the exception of the push and pop functions. When we call push or pop on a Queue, then the specialized version will be called. When we use any other member, the generic one will be instantiated for const char* from the class template.
Specialization Declarations
Member specializations are declared just as any other function template specialization. They must start with an empty template parameter list:
// push and pop specialized for const char*
template <>
void Queue::push(const char* const &);
template <> void Queue::pop();
Class-Template Partial Specializations
If a class template has more than one template parameter, we might want to specialize some but not all of the template parameters. We can do so using a class template partial specialization:
template
class some_template {
// ...
};
// partial specialization: fixes T2 as int and allows T1 to vary
template
class some_template {
// ...
};
Using a Class-Template Partial Specialization
The partial specialization has the same name as the class template to which it correspondsnamely, some_template. The name of the class template must be followed by a template argument list. In the previous example, the template argument list is . Because the argument value for the first template parameter is unknown, the argument list uses the name of the template parameter T1 as a placeholder. The other argument is the type int, for which the template is partially specialized.
As with any other class template, a partial specialization is instantiated implicitly when used in a program:
some_template foo; // uses template
some_template bar; // uses partial specialization
//-------------------------------------------------------------------------
Overloading and Function Templates
An Example of Function-Template Matching
Consider the following set of overloaded ordinary and function templates:
// compares two objects
template int compare(const T&, const T&);
// compares elements in two sequences
template int compare(U, U, V);
// plain functions to handle C-style character strings
int compare(const char*, const char*);
Resolving Calls to Overloaded Function Templates
We could call these functions on a variety of types:
// calls compare(const T&, const T&) with T bound to int
compare(1, 0);
// calls compare(U, U, V), with U and V bound to vector::iterator
vector ivec1(10), ivec2(20);
compare(ivec1.begin(), ivec1.end(), ivec2.begin());
int ia1[] = {0,1,2,3,4,5,6,7,8,9};
// calls compare(U, U, V) with U bound to int*
// and V bound to vector::iterator
compare(ia1, ia1 + 10, ivec1.begin());
// calls the ordinary function taking const char* parameters
const char const_arr1[] = "world", const_arr2[] = "hi";
compare(const_arr1, const_arr2);
// calls the ordinary function taking const char* parameters
char ch_arr1[] = "world", ch_arr2[] = "hi";
compare(ch_arr1, ch_arr2);
