Don't hesitate to send in feedback: send an e-mail if you like the C++ Annotations; if you think that important material was omitted; if you find errors or typos in the text or the code examples; or if you just feel like e-mailing. Send your e-mail to Frank B. Brokken.Please state the document version you're referring to, as found in the title (in this document: 6.2.3) and please state chapter and paragraph name or number you're referring to.
All received mail is processed conscientiously, and received suggestions for improvements will usually have been processed by the time a new version of the Annotations is released. Except for the incidental case I will normally not acknowledge the receipt of suggestions for improvements. Please don't interpret this as me not appreciating your efforts.
Like function templates, templates can be constructed for complete
classes. A
template class can be considered when the class should be able
to handle different types of data. Template classes are frequently used in
C++: chapter 12 covered general data structures like
vector, stack and queue, defined as template classes. With
template classes, the
algorithms and the data on which the
algorithms operate are completely separated from each other. To use a
particular
data structure, operating on a particular data type, only the
data type needs to be specified when the template class object is defined
or declared, e.g., stack<int> iStack.
Below the construction of template classes is discussed. In a sense, template classes compete with object oriented programming (cf. chapter 14), where a mechanism somewhat similar to templates is seen. Polymorphism allows the programmer to postpone the definitions of algorithms, by deriving classes from a base class in which the algorithm is only partially implemented, while the data upon which the algorithms operated may first be defined in derived classes, together with member functions that were defined as pure virtual functions in the base class to handle the data. On the other hand, templates allow the programmer to postpone the specification of the data upon which the algorithms operate. This is most clearly seen with the abstract containers, completely specifying the algorithms but at the same time leaving the data type on which the algorithms operate completely unspecified.
Generally, template classes are easier to use. It is certainly easier to write
stack<int> istack to create a stack of ints than it is to derive a new
class Istack: public stack and to implement all necessary member functions
to be able to create a similar stack of ints using object oriented
programming. On the other hand, for each different type that is used with a
template class the complete class is reinstantiated, whereas in the context of
object oriented programming the derived classes use, rather than copy,
the functions that are already available in the base class (but see also
section 19.9).
In chapter 17 we've encountered the auto_ptr class (section
17.3). The auto_ptr, also called
smart pointer, allows us to
define an object, acting like a pointer. Using auto_ptrs rather than plain
pointers we not only ensure proper memory management, but we also may prevent
memory leaks when objects of classes using pointer data-members cannot
completely be constructed.
The one disadvantage of
auto_ptrs is that
they can only be used for single objects and not for pointers to
arrays of objects. Here we'll construct the template class FBB::auto_ptr,
behaving like auto_ptr, but managing a pointer to an array of objects.
Using an existing class as our point of departure also shows an important
design principle: it's often easier to construct a template (function or
class) from an existing template than
to construct the template completely from scratch. In this case the existing
std::auto_ptr acts as our model. Therefore, we want to provide the class
with the following members:
FBB::auto_ptr;
operator=();
operator[]() to retrieve and reassign the elements given
their indices.
std::auto_ptr, with the exception of
the dereference operator (
operator*()), since our FBB::auto_ptr object
will hold multiple objects, and thus the dereference operator cannot be
defined unambiguously.
template, which is also followed by a non-empty list of
template type
and/or non-type parameters, surrounded by angular brackets. The
template keyword followed by the template parameter list enclosed in
pointed brackets is called a
template announcement in the C++
Annotations. In some cases the template announcement's parameter list may be
empty, leaving only the poined brackets.
Following the template announcement the class interface is provided, in
which the formal template type parameter names may be used to represent types
and constants. The class interface is constructed as usual. It starts with the
keyword class and ends with a semicolon.
Normal
design considerations should be followed when constructing
template class member functions or template class constructors:
template class 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, again to prevent double
assignment of composed objects: once by the default constructor of the object,
once by the assignment itself.
Here is our initial version of the class
FBB::auto_ptr
showing all its members:
namespace FBB
{
template <typename Data>
class auto_ptr
{
Data *d_data;
public:
auto_ptr()
:
d_data(0)
{}
auto_ptr(auto_ptr<Data> &other)
{
copy(other);
}
auto_ptr(Data *data)
:
d_data(data)
{}
~auto_ptr()
{
destroy();
}
auto_ptr<Data> &operator=(auto_ptr<Data> &rvalue);
Data &operator[](unsigned index)
{
return d_data[index];
}
Data const &operator[](unsigned index) const
{
return d_data[index];
}
Data *get()
{
return d_data;
}
Data const *get() const
{
return d_data;
}
Data *release();
void reset(Data *);
private:
void destroy()
{
delete [] d_data;
}
void copy(auto_ptr<Data> &other)
{
d_data = other.release();
}
Data &element(unsigned idx) const;
};
}
The class interface shows the following features:
Data is an ordinary type,
the class interface appears to have no special characteristics at all. It
looks like any old class interface. This is generally true. Often a template
class can easily be constructed after having constructed the class for one or
two concrete types, followed by an abstraction phase changing all necessary
references to concrete data types into generic data types, which then become
the template's type parameters.
auto_ptr objects, but
rather references to auto_ptr<Data> objects. Template class objects (or
their references or pointers) always require the template type parameters
to be specified.
const
references. This has nothing to do with the class being a template class, but
is a consequence of auto_ptr's design itself: both the copy constructor
and the overloaded assignment operator take the other's object's pointer,
effectively changing the other object into a
0-pointer.
operator*()), the well-known
pair of
operator[]() members are defined. Since the class receives no
information about the size of the array of objects, these members cannot
support
array-bound checking.
copy() and destroy() members (see section
7.5.1) are very simple, but were added to the implementation to
promote standardization of classes containing pointer members.
namespace FBB
{
template <typename Data>
auto_ptr<Data> &auto_ptr<Data>::operator=(auto_ptr<Data> &rvalue)
{
if (this != &rvalue)
{
destroy();
copy(rvalue);
}
return *this;
}
}
Note in particular:
template phrase. The function's declaration must
also start with a
template phrase, but that is implied by the interface
itself, which already provides the required phrase at its very beginning;
auto_ptr type include the template's type
parameter. This is obligatory.
release() and reset() members are
also fairly simple. Here they are:
namespace FBB
{
template <typename Data>
Data *auto_ptr<Data>::release()
{
Data *ret = d_data;
d_data = 0;
return ret;
}
template <typename Data>
void auto_ptr<Data>::reset(Data *ptr)
{
destroy();
d_data = ptr;
}
}
std::string array, storing all command-line arguments. Then, the first
command-line argument is printed. Next, the auto_ptr object is used to
initialize another auto_ptr of the same type. It is shown that the
original auto_ptr now holds a 0-pointer, and that the second auto_ptr
object now holds the command-line arguments:
#include <iostream>
#include <algorithm>
#include <string>
#include "autoptr.h"
using namespace std;
int main(int argc, char **argv)
{
FBB::auto_ptr<string> sp(new string[argc]);
copy(argv, argv + argc, sp.get());
cout << "First auto_ptr, program name: " << sp[0] << endl;
FBB::auto_ptr<string> second(sp);
cout << "First auto_ptr, pointer now: " << sp.get() << endl;
cout << "Second auto_ptr, program name: " << second[0] << endl;
FBB::auto_ptr<> iap(new int[10]);
cout << iap[0] << endl;
return 0;
}
/*
Generated output:
First auto_ptr, program name: a.out
First auto_ptr, pointer now: 0
Second auto_ptr, program name: a.out
*/
FBB::auto_ptr 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. So, when instantiating
template class objects for which default parameter values have been defined
the type specifications may be omitted, but the pointed brackets must
remain. So, assuming a default type for the FBB::auto_ptr class, an object
of that class may be defined as:
FBB::auto_ptr<> intAutoPtr;
No defaults must be specified for template members defined outside of
their class interface. Template functions, even template member functions,
cannot specify default parameter values. So, the definition of, e.g., the
release() member will always begin with the same template
specification:
template <typename Data>
When a template class uses multiple template parameters, all may be given default values. However, like default function arguments, once a default value is used, all remaining 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.
namespace FBB
{
template <typename Type>
class auto_ptr;
}
Here default types may also be specified. However, default type values
cannot be specified in both a declaration and a definition of a template
class. As a
rule of thumb default values should be omitted from
declarations, as template class declarations are never used when
instantiating objects, but only for the occasional forward reference. Note
that this differs from default parameter value specifications for member
functions in concrete classes. Such defaults should be specified in the member
functions' declarations and not in their definitions.
Handler defines a typename Container as its type parameter, and
a data members storing the container's begin() iterator. Furthermore, the
template class Handler has a constructor accepting any container
supporting a begin() member. The skeleton of our
class Handler could then be:
template <typename Container>
class Handler
{
Container::const_iterator d_it;
public:
Handler(Container const &container)
:
d_it(container.begin())
{}
};
What were the considerations we had in mind when designing this class?
Container represents any container supporting
iterators.
begin(). The
initialization d_it(container.begin()) clearly depends on the
template's type parameter, so it's only checked for basic syntactical
correctness.
const_iterator, defined in the class Container. Since container is
a const reference, the iterator returned by begin() is a
const_iterator rather than a plain iterator.
Handler using the following main()
function we run into a compilation error:
#include "handler.h"
#include <vector>
using namespace std;
int main()
{
vector<int> vi;
PairHandler<vector<int> > ph(vi);
}
/*
Reported error:
handler.h:4: error: syntax error before `;' token
*/
Apparently the line
Container::const_iterator d_it;
in the Handler class causes a problem. The problem is the following:
When using template type parameters, plain syntax checking allows the compiler
to decide that a container refers to a Container. Such a Container
might very well support a begin() member, hence container.begin() is
syntactically ok. However, that member begin() might actually not exist
for a particular Container type. Of course, the existence of begin()
will only be known by the time the Containter's actual type has been
specified. On the other hand, the compiler is unable to infer what a
Container::const_iterator is. Assuming it is a member of the mysterious
Container, a plain syntax check clearly fails, as the statement
Container::const_iterator d_it;
is always syntactically wrong when const_iterator is a member of
Container. That the compiler indeed assumes X::a is a member a of
the class X is illustrated by the error message we get when we try to
compile main() using the following implementation of Handler's
constructor:
PairHandler(Container const &container)
:
d_it(container.begin())
{
unsigned x = Container::ios_end;
}
/*
Reported error:
error: `ios_end' is not a member of type `std::vector<int,
std::allocator<int> >'
*/
In cases like these, where the intent is to refer to a type defined in
a formal class like Container, this must explicitly be indicated to the
compiler, using the typename keyword. Here is the Handler class once
again, now using typename:
template <typename Container>
class Handler
{
typename Container::const_iterator d_it;
public:
Handler(Container const &container)
:
d_it(container.begin())
{}
};
Now main() will compile correctly.
However, their values are not deducted by the compiler using arguments
passed to constructors. Assume we modify the template class FBB::auto_ptr
so that it has an additional non-type parameter unsigned Size. Next we use
this Size parameter in a new constructor defining an array of Size
elements of type Data as its parameter. The new FBB::auto_ptr template
class becomes (showing only the relevant constructors, note the two template
type parameters that are now required, e.g., when specifying the type of the
copy constructor's parameter):
namespace FBB
{
template <typename Data, unsigned Size>
class auto_ptr
{
Data *d_data;
unsigned d_n;
public:
auto_ptr(auto_ptr<Data, Size> &other)
{
copy(other);
}
auto_ptr(Data2 *data)
:
d_data(data),
d_n(0)
{}
auto_ptr(Data const (&arr)[Size])
:
d_data(new Data2[Size]),
d_n(Size)
{
std::copy(arr, arr + Size, d_data);
}
...
};
}
Unfortunately, this new setup doesn't satisfy our needs, as the values of
template non-type parameters are not deducted 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];
FBB::auto_ptr<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, unsigned int Size>
class FBB::auto_ptr'
*/
Making Size into a non-type parameter having a default value doesn't
work either. The compiler will use the default, unless explicitly specified
otherwise. So, reasoning that Size can be 0 unless we know otherwise, we
might specify unsigned Size = 0 in the templates parameter type list
causes a mismatch between the default value 0 and the actual size of the array
arr defined in the above main() function. The compiler, using
the default value, now reports
In instantiation of `FBB::auto_ptr<int, 0>':
...
error: creating array with size zero (`0')
So, although template classes may use non-type parameters, they must be
specified like the type parameters when an object of the class is
defined. Default values can be specified for those non-type parameters, but
then the default will be used when the non-type parameter is left unspecified.
Moving the constructor's definition out of the interface, doesn't work either. It's still the same template function, even though it's now placed outside of its class interface. In particular note that no default template (non) type parameter values may be used when template member functions are defined outside their interface. Template functions (and thus: template class member functions) may not be given default template (non) type parameter values.
Similar to non-type parameters of template functions, non-type parameters of template classes may only be specified as constants:
const pointer.
short can be used when an int is called for, a
long when a double is called for).
unsigned parameter is specified, an int may be used too.
const modifier, however, may be used, as their values never change.
Although our attempts to define a constructor of the class
FBB::auto_ptr accepting an array as its argument, allowing us to use the
array's size within the constructor's code has failed so far, we're not yet
out of options. In the next section an approach will be described allowing us
to reach our goal, after all.
On the other hand, when template functions are used, the actual template parameters are deducted from the arguments used when calling the function. This opens an approach route to the solution of our problem. If the constructor itself is made into a member which itself is a template function (containing a template announcement of its own), then the compiler will be able to deduct the non-type parameter's value, without us having to specify it explicitly as a template class non-type parameter.
Member functions (or classes) of template classes which themselves are
templates are called member templates.
Member templates are defined in the same way as any other template,
including the template <typename ...> header.
When converting our earlier FBB::auto_ptr(Data const (&array)[Size])
constructor into a member template we may use the template class's Data
type parameter, but must provide the member template with a non-type parameter
of its own. The constructor's inline implementation becomes:
template <unsigned Size>
auto_ptr(Data const (&arr)[Size])
:
d_data(new Data[Size]),
d_n(Size)
{
std::copy(arr, arr + Size, d_data);
}
Member templates have the following characteristics:
FBB::auto_ptr object of a given
data type. As usual for template classes, the data type must be specified when
the object is constructed. To construct an FBB::auto_ptr object from the
array int array[30] we define:
FBB::auto_ptr<int> object(array);
template <typename Data>
template <unsigned Size>
auto_ptr<Data>::auto_ptr(Data const (&arr)[Size])
:
d_data(new Data[Size]),
d_n(Size)
{
std::cout << "fixed array\n";
std::copy(arr, arr + Size, d_data);
}
When defining a template member below its class
namespace SomeName
{
template <typename Type, ...> // template class definition
class ClassName
{
...
};
template <typename Type, ...> // non-inline member definition(s)
ClassName<Type, ...>::member(...)
{
...
}
} // namespace closed
FBB::auto_ptr, instantiated for the formal template parameter type
Data. Since we're already inside the namespace FBB, the function
header starts with auto_ptr<Data>::auto_ptr.
FBB::auto_ptr
object from a fixed-size array the above constructor is not used. Instead, the
constructor FBB::auto_ptr<Data>::auto_ptr(Data *data) is activated. As the
latter constructor is not a member template, it is considered a more
specialized version of a constructor of the class FBB::auto_ptr than the
former constructor. Since both constructors accept an array
the compiler will call auto_ptr(Data *) rather than auto_ptr(Data const
(&array)[Size]). This little problem can be solved by simply changing the
constructor auto_ptr(Data *data) in a member template as well. When doing
so, its template type parameter is merely Data. The only remaining
subtlety is that template parameters of member templates may not shadow
the template parameters of their class. Renaming Data into Data2
takes care of this subtlety. Here is the (inline) definition of the
auto_ptr(Data *) constructor, followed by an example in which both
constructors are actually used:
template <typename Data2>
auto_ptr(Data2 *data) // must have been dynamically allocated
:
d_data(data),
d_n(0)
{}
Calling both constructors in main():
int main()
{
int array[30];
FBB::auto_ptr<int> ap(array);
FBB::auto_ptr<int> ap2(new int[30]);
return 0;
}
template <typename Type>
class TheClass
{
static int s_objectCounter;
};
There will be one TheClass<Type>::objectCounter for each different
Type specification. However, the following instantiates just one single
static variable, shared among the different objects:
TheClass<int> theClassOne;
TheClass<int> theClassTwo;
Mentioning static members in interfaces does not mean these members are
actually defined: they are only declared by their classes and must be
defined separately. With static members of template classes this is not
different. The
definitions of static members
are usually provided immediately following (i.e., below) the template
class interface. The static member s_objectCounter will thus be defined as
follows, just below its class interface:
template <typename Type> // definition, following
int TheClass<Type>::s_objectCounter = 0; // the interface
In the above case objectCounter is an int, and thus independent of
the template type parameter Type.
In a list-like construction, where a
pointer to objects of the class
itself is required, the template type parameter Type must be used to
define the static variable, as shown in the following 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: objectPtr of the class TheClass<Type> is
a pointer to an object of TheClass<Type>.
Finally, when a static variable of a template's type parameter is defined,
it should of course not be given the initial value 0. The default constructor
(e.g., Type() will usually be more appropriate):
template <typename Type> // s_type's definition
Type TheClass<Type>::s_type = Type();
FBB::auto_ptr can be used for many different
types. Their common characteristic is that they can simply be assigned to the
class' d_data member, e.g., using using auto_ptr(Data *data). However,
this is not always as simple as it looks. What if Data's actual type is
char *? Examples of a char **, data's resulting type, are
well-known: main()'s argv and envp, for example are char **
parameters.
It this special case we might not be interested in the mere reassignment
of the constructor's parameter to the class' d_data member, but we might
be interested in copying the complete char ** structure. To realize this,
template class specializations may be used.
Template class specializations are used in cases where template member functions cannot (or should not) be used for a particular actual template parameter type. In those cases specialized template members can be constructed, fitting the special needs of the actual type.
Template class member specializations are specializations of existing
class members. Since the class members already exist, the specializations will
not be part of the class interface. Rather, they are defined below the
interface as members, redefining the more generic members using explicit
types. Furthermore, as they are specializations of existing class members,
their function prototypes must exactly match the prototypes of the member
functions for which they are specializations. For our Data = char *
specialization the following definition could be designed:
template <>
auto_ptr<char *>::auto_ptr(char **argv)
:
d_n(0)
{
char **tmp = argv;
while (*tmp++)
d_n++;
d_data = new char *[d_n];
for (unsigned idx = 0; idx < d_n; idx++)
{
std::string str(argv[idx]);
d_data[idx] =
strcpy(new char[str.length() + 1], str.c_str());
}
}
Now, the above specialization will be used to construct the following
FBB::auto_ptr object:
int main(int argc, char **argv)
{
FBB::auto_ptr<char *> ap3(argv);
return 0;
}
Although defining a template member specialization may allow us to use the
occasional exceptional type, it is also quite possible that a single template
member specialization is not enough. Actually, this is the case when designing
the char * specialization, since the template's destroy()
implementation is not correct for the specialized type Data = char *. When
multiple members must be specialized for a particular type, then a complete
template class specialization might be considered.
A completely specialized class shows the following characteristics:
template <> announcement, but should immediately start
with the member function's header.
Below a full specialization of the template class FBB::auto_ptr for
the actual type Data = char * is given, illustrating the above
characteristics. The specialization should be appended to the file already
containing the generic template class. To reduce the size of the example
members that are only declared may be assumed to have identical
implementations as used in the generic template.
#include <iostream>
#include <algorithm>
#include "autoptr1.h"
namespace FBB
{
template<>
class auto_ptr<char *>
{
char **d_data;
unsigned d_n;
public:
auto_ptr<char *>()
:
d_data(0),
d_n(0)
{}
auto_ptr<char *>(auto_ptr<char *> &other)
{
copy(other);
}
auto_ptr<char *>(char **argv)
{
full_copy(argv);
}
// template <unsigned Size> NI
// auto_ptr(char *const (&arr)[Size])
~auto_ptr()
{
destroy();
}
auto_ptr<char *> &operator=(auto_ptr<char *> &rvalue);
char *&operator[](unsigned index);
char *const &operator[](unsigned index) const;
char **get();
char *const *get() const;
char **release();
void reset(char **argv)
{
destroy();
full_copy(argv);
}
void additional() const // just an additional public
{} // member
private:
void full_copy(char **argv)
{
d_n = 0;
char **tmp = argv;
while (*tmp++)
d_n++;
d_data = new char *[d_n];
for (unsigned idx = 0; idx < d_n; idx++)
{
std::string str(argv[idx]);
d_data[idx] =
strcpy(new char[str.length() + 1], str.c_str());
}
}
void copy(auto_ptr<char *> &other);
void destroy(); // implemented below
};
void auto_ptr<char *>::destroy()
{
while (d_n--)
delete d_data[d_n];
delete [] d_data;
}
}
In this section we'll intruduce a variant of these specializations, both in number and types of template parameters that are specialized. Partial specializations may be defined for template classes having multiple template parameters. With partial specializations a subset (any subset) of template type parameters are given specific values.
Having discussed specializations of template type parameters in the previous section, we'll discuss specializations of non-type parameters in the current section. Partial specializations of template non-type parameters will be illustrated using some simple concepts defined in matrix algebra, a branch of linear algebra.
A matrix is commonly thought of a consisting of a table of a certain
number of rows and columns, filled with numbers. Immediately we recognize a
opening for using templates: the numbers might be plain double values, but
they could also very well be complex numbers, for which our
complex container (cf. section 12.4) might prove
useful. So, our template class might benefit from its having a typename
DataType, for which a concrete class can be specified when a matrix is
constructed. Some simple matrices, using double values, are:
1 0 0 An identity matrix,
0 1 0 a 3 x 3 matrix.
0 0 1
1.2 0 0 0 A rectangular matrix,
0.5 3.5 18 23 a 2 x 4 matrix.
1 2 4 8 A matrix of one row,
a 1 x 4 matrix, also known as a
`row vector' of 4 elements.
(column vectors are analogously defined)
Since matrices consist of a specific number of rows and columns (the
dimensions of the matrix), which normally do not change while using
matrices, we might consider specifying their values as template non-type
parameters. Since the DataType = double selection will be used in the
majority of cases, double can be selected as the template's default
type. Since it's having a sensible default, the DataType template type
parameter is put last in the template type parameter list. So, our template
class Matrix starts off as follows:
template <unsigned Rows, unsigned Columns, typename DataType = double>
class Matrix
...
Various operations are defined on matrices. They may, for example be
added, subtracted or multiplied. We will not focus on these operations
here. Rather, we'll concentrate on a simple operation: computing marginals and
sums. The row marginals are obtained by computing, for each row, the sum of
all its elements, putting these Rows sum values in corresponding elements
of a column vector of Rows elements. Analogously, column marginals are
obtained by computing, for each column, the sum of all its elements, putting
these Columns sum values in corresponding elements of a row vector of
Columns elements. Finally, the sum of the elements of a matrix can be
computed. This sum is of course equal to the sum of the elements of its
marginals. The following example shows a matrix, its marginals, and its sum:
matrix: row
marginals:
1 2 3 6
4 5 6 15
column 5 7 9 21 (sum)
marginals
So, what do we want our template class to offer?
Rows rows of 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, typedefs may be considered. The class interface's initial
section therefore contains:
public:
typedef Matrix<1, Columns, DataType> MatrixRow;
typedef Matrix<Rows, 1, DataType> MatrixColumn;
private:
MatrixRow d_matrix[Rows];
Matrix(std::istream &str)
{
for (unsigned row = 0; row < Rows; row++)
for (unsigned col = 0; col < Columns; col++)
str >> d_matrix[row][col];
}
Matrix()
{
std::fill(d_matrix, d_matrix + Rows, MatrixRow());
}
operator[]() member (and its const variant) only
handles the first index, returning a reference to a complete
MatrixRow. How to handle the retrieval of elements in a MatrixRow will
be covered shortly. To keep the example simple, no array bound check has been
implemented:
MatrixRow &operator[](unsigned idx)
{
return d_matrix[idx];
}
Matrix. Considering that marginals are vectors,
either a MatrixRow, containing the column marginals, a MatrixColumn,
containing the row marginals, or a single value, either computed as
the sum of a vector of marginals, or as the value of a 1 x 1 matrix,
initialized from a generic Matrix, we can now construct partial
specializations to handle MatrixRow and MatrixColumn objects,
and a partial specialization handling 1 x 1 matrices. Since we're about
to define these specializations, we can use them already when computing
marginals and the matrix' sum of all elements. Here are the implementations of
these members:
MatrixRow columnMarginals() const
{
return MatrixRow(*this);
}
MatrixColumn rowMarginals() const
{
return MatrixColumn(*this);
}
DataType sum() const
{
return rowMarginals().sum();
}
Template class partial specializations may 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 the special case where we construct a row of a generic Matrix,
specifically aiming at (but not restricted to) the construction of column
marginals. Here is how such a partial specialization is constructed:
DataType = double), since the defaults have already been specified by the
generic template class definition. Furthermore, the specialization must
follow the definition of the generic template class definition, or the
compiler will complain that it doesn't know what class is being
specialized. Following the template announcement, the class interface
starts. Since it's a template class (partial) specialization the class name is
followed by a template type parameter list specifying concrete values or types
for all template parameters specified in this specialization, and using the
template's generic (non-)type names for the remaining template parameters. In
the MatrixRow specialization Row is specified as 1, since we're
talking here about one single row. Both Columns and DataType remain to
be specified. So, the MatrixRow partial specialization starts as follows:
template <unsigned Columns, typename DataType> // no default specified
class Matrix<1, Columns, DataType>
MatrixRow contains the data of a single row. So it need a
data member storing Column values of type DataType. Since Column
is a constant value, the d_row data member can be defined as an array:
DataType d_column[Columns];
MatrixRow's data elements, using
DataType's default constructor:
Matrix()
{
std::fill(d_column, d_column + Columns, DataType());
}
However, we also need a constructor 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. In cases
like this, the
rule of thumb is to define a member template allowing us to
keep the general nature of the parameter. Since the generic Matrix
template requires three template parameters, two of which already provided by
the template specialization, the third parameter must be specified in the
member template's template announcement. Since this parameter refers to the
generic matrix' number of rows, let's simply call it Rows. Here, then, is
the definition of the second constructor, initializing the MatrixRow's
data with the column marginals of a generic Matrix object:
template <unsigned Rows>
Matrix(Matrix<Rows, Columns, DataType> const &matrix)
{
std::fill(d_column, d_column + Columns, DataType());
for (unsigned col = 0; col < Columns; col++)
for (unsigned row = 0; row < Rows; row++)
d_column[col] += matrix[row][col];
}
Note the way the constructor's parameter is defined: it's a reference to a
Matrix template, using the additional Row template parameter as well
as the template parameters of the partial specialization itself.
MatrixRow an overloaded
operator[]() is of course useful. Again, the const variant can be
implemented like the non-const variant. Here is its implementation:
DataType &operator[](unsigned idx)
{
return d_column[idx];
}
Matrix class as well as the
partial specialization defining a single row, the compiler will select the
row's specialization whenever a Matrix is defined using Row = 1. For
example:
Matrix<4, 6> matrix; // generic Matrix template is used
Matrix<1, 6> row; // partial specialization is used
The partial specialization for a MatrixColumn is constructed
similarly. Let's present its highlights (the full Matrix template class
definition as well as all its specializations are provided in the
cplusplus.yo.zip archive (at fpt.rug.nl) in the
file yo/templateclasses/examples/matrix.h):
template <unsigned Rows, typename DataType>
class Matrix<Rows, 1, DataType>
MatrixRow constructors were implented. Their implementations are left
as an exercise to the reader (and they can be found in matrix.h).
sum() is defined to compute the sum of the
elements of a MatrixColumn vector. It's implementation is simply realized
using the accumulate() generic algorithm:
DataType sum()
{
return std::accumulate(d_row, d_row + Rows, DataType());
}
The reader might wonder what happens if we specify the following matrix:
Matrix<1, 1> cell;
Is this a MatrixRow or a MatrixColumn specialization? The answer
is: neither. It's
ambiguous, precisely because both the columns and
the rows could be used with a (different) template partial specialization. If
such a Matrix is actually required, yet another specialized template must
be designed. Since this template specialization can be useful to
obtain the sum of the elements of a Matrix, it's covered here as welll:
DataType. The class definition
specifies two fixed values, using 1 for both the number of rows and the number
of columns:
template <typename DataType>
class Matrix<1, 1, DataType>
Matrix type are implemented as
member templates. For example:
template <unsigned Rows, unsigned Columns>
Matrix(Matrix<Rows, Columns, DataType> const &matrix)
:
d_cell(matrix.rowMarginals().sum())
{}
template <unsigned Rows>
Matrix(Matrix<Rows, 1, DataType> const &matrix)
:
d_cell(matrix.sum())
{}
Matrix<1, 1> is basically a wrapper around a DataType
value, we need members to access that latter value. An type conversion
operator might be usefull, but we'll also need a get() member to obtain
the value if the conversion operator isn't used by the compiler (which
happpens when the compiler is given a choice, see section
9.3). Here are the accessors (leaving out their const
variants):
operator DataType &()
{
return d_cell;
}
DataType &get()
{
return d_cell;
}
main() function shows how the Matrix template class
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] << endl;
Matrix<3, 1> rowMargins(matrix);
cout << "Row marginals:\n";
for (unsigned idx = 0; idx < 3; idx++)
cout << rowMargins[idx] << endl;
cout << "Sum total: " << Matrix<1, 1>(matrix) << endl;
return 0;
}
/*
Generated output from input: 1 2 3 4 5 6
Column marginals:
9 12
Row marginals:
3
7
11
Sum total: 21
*/
Template parameters are also specified when a template class defines
default template parameter values, albeit that the compiler in that case will
provide the defaults. The actual values or types of template parameters are
never deducted, as with
template functions: To define a Matrix of elements that are complex
values, the following construction is used:
Matrix<3, 5, std::complex> complexMatrix;
while the following construction defines a matrix of elements that are
double values, with the compiler providing the (default) type double:
Matrix<3, 5> doubleMatrix;
A template class object may be declared using the keyword
extern.
For example, the following construction is used to declare the matrix complexMatrix:
extern Matrix<3, 5, std::complex> complexMatrix;
A template class declaration
is sufficient if function declarations are compiled of functions having
return values or parameters which are template class objects, pointers or
references. The following little source file may be compiled, although the
compiler hasn't seen the definition of the Matrix template class.
Note that generic classes as well as (partial) specializations may be
declared. Furthermore, note that a function expecting or returning a template
class object, reference, or parameter itself automatically becomes a template
function, as this is necessary to specify the nature of the various template
parameters:
template <unsigned Rows, unsigned Columns, typename DataType = double>
class Matrix;
template <unsigned Columns, typename DataType>
class Matrix<1, Columns, DataType>;
template<unsigned Columns, typename DataType>
Matrix<1, Columns, DataType> function(Matrix<Rows, Columns, DataType> mat)
{}
When template classes are used they have to be processed by the compiler
first. 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 when a template class object is defined.
The compiler will only instantiate those members that are actually
used. This is illustrated by the following simple class Demo, having two
constructors and two members. When we create a main() function in which
one constructor is used and one member is called, we can make a note of the
sizes of the resulting object file and executable program. Next the class
definition is modified such that the unused constructor and member are
commented out. Again we compile and link the main() function and the
resulting sizes are identical to the sizes obtained earlier (on my computer,
using g++ version 3.3.3 these sizes are 2380 and 13504,
respectively). There are other ways to illustrate the point that only members
that are used are instantiated, like using the
nm program, showing the
symbolic contents of object files. Using programs like nm, however, will
yield the same conclusion: only template member functions that are actually
used are initialized. Here is an example of the template class Demo used
for this little experiment. In main() the first constructor and the first
member function are called.
#include <iostream>
template <typename Type>
class Demo
{
Type d_data;
public:
Demo()
:
d_data(Type())
{}
void member1()
{
d_data += d_data;
}
// the following members are commented out before compiling
// the second program
Demo(Type const &value)
:
d_data(value)
{}
void member2(Type const &value)
{
d_data += value;
}
};
int main()
{
Demo<int> demo;
demo.member1();
}
Code that does not depend on template parameters is verified by the
compiler when the template is defined. E.g., if a member function in a
template class uses a
qsort() function, then qsort() does not depend
on a template parameter. Consequently, qsort() must be known to the
compiler when it encounters the qsort() function call. In practice this
implies that
cstdlib or
stdlib.h must have been processed by the
compiler before it will be able to process the template class definition.
On the other hand, if a template defines a <typename Type> template
type parameter, which is the return type of some template member function,
e.g.,
Type member() ...
then we distinguish the following situations where the compiler encounters
member() or the class to which member() belongs:
member(). So, it won't accept a definition or declaration like Type
&&member(), because C++ does not support functions returning references
to references. Furthermore, it will check the existence of the actual typename
that is used for instantiating the object. This typename must be known to the
compiler at the object's point of instantiation.
Type parameter
must of course still be known, and member()'s statements that depend on
the Type template parameter are now checked for syntactical
correctness. For example, if member() contains a statement like
Type tmp(Type(), 15);
then this is in principle a syntactically valid statement. However, when
Type = int and member() is called, its instantiation will fail,
because int does not have a constructor expecting two int
arguments. Note that this is not a problem when the compiler instantiates
an object of the class containing member(): at the point of instantiation
of the object its member() member function is not instantiated, and so the
invalid int construction remains undetected.
Like concrete classes, template classes may declare other functions and
classes as their friends. Conversely, concrete 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 thus be used in any type of class
(concrete or template) to declare any type of function or class as a
friend, when using template classes the following cases should be
distinguished:
ostream objects.
friend declaration is used
determine (bind) the template parameters of the friend class or function,
resulting in a one-to-one correspondence between the template's parameters and
the friend's template parameters.
Concrete classes and ordinary functions can be declared as friends, but before a single class member function can be declared as a friend, the compiler must have seen the class interface declaring that member. Let's consider the various possibilities:
void function(std::vector<Type> &vector)
unless function() itself is a template, it is not immediately clear
how and why such friend should be constructed. One reason, though, is to allow
the function to access the class' private static members. Furthermore, such
friends could themselves instantiate objects of classes declaring them as
friends, and directly access such object's private members. For example:
template <typename Type>
class Storage
{
friend void basic();
static unsigned s_time;
std::vector<Type> d_data;
public:
Storage()
{}
};
template <typename Type>
unsigned Storage<Type>::s_time = 0;
void basic()
{
Storage<int>::s_time = time(0);
Storage<double> storage;
std::random_shuffle(storage.d_data.begin(), storage.d_data.end());
}
class Friend;
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)
{
std::copy(std::istream_iterator<int>(input),
std::istream_iterator<int>(),
back_inserter(d_ints.d_data));
}
};
randomizer() 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 randomizer();
};
template <typename Type>
class Composer
{
friend void Friend::randomizer();
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));
}
};
Friend::Friend(std::istream &input)
:
d_ints(new Composer<int>(input))
{}
void Friend::randomizer()
{
std::random_shuffle(d_ints->d_data.begin(), d_ints->d_data.end());
}
In this example note that Friend::d_ints is a pointer member. It
cannot be a Composer<int> object, since 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 will have.
!key1.find(key2) is probably more
useful, but for the current example operator==() is acceptable:
template <typename Key, typename Value>
class Dictionary;
template <typename Key, typename Value>
Dictionary<Key, Value>
subset(Key const &key, Dictionary<Key, Value> const &dict);
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;
}
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:
template <typename Key, typename Value>
class Iterator;
template <typename Key, typename Value>
class Dictionary
{
friend class Iterator<Key, Value>;
Iterator<Key, Value> begin()
{ // uses the friend's
return Iterator<Key, Value>(*this); // constructor
}
Iterator<Key, Value> subset(Key const &key)
{ // uses a member function
return Iterator<Key, Value>(*this).subset(key);
}
Dictionary it can safely define a
std::map data member, which is initialized by its constructor, accessing
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)
{}
Iterator member begin() simply returns a map
iterator. However, since it is not known to the compiler what the
instantiation of the map will look like, a map<Key, Value>::iterator
is a (deprecated)
implicit typename. To make it an explicit typename,
simply prefix typename to begin()'s return type:
typename std::map<Key, Value>::iterator begin()
{
return d_dict.begin();
}
Dictionary
should be able to construct an Iterator, as Iterator is closely tied
to Dictionary. This can be realized by defining Iterator's constructor
in its private section, and declaring Dictionary Iterator's
friend. Consequently, only Dictionary can create its own Iterator. By
declaring Iterator's constructor a bound friend, we ensure that it
can only create Iterators using identical template parameters as
itself. Here is how it's realized:
template <typename Key, typename Value>
class Iterator
{
friend Dictionary<Key, Value>::Dictionary();
std::map<Key, Value> &d_dict;
Iterator(Dictionary<Key, Value> &dict)
:
d_dict(dict.d_dict)
{}
public:
In this example, Dictionary's constructor is defined as Iterator's
friend. Here the friend is a template member. Other members can be declared as
a class' friend as well, in which case their prototypes must be used,
including the types of their return values. So, assuming that
std::vector<Value> sortValues()
is a member of Dictionary, returning a sorted vector of its values,
then the corresponding bound friend declaration would be:
std::vector<Value> Dictionary<Key, Value>::sortValues()
Here are the syntactical conventions declaring unbound friends:
template <typename Iterator, typename Class,
void (Class::*member)(Data &)>
Class &ForEach(Iterator begin, Iterator end, Class &object,
void (Class::*member)(Data &));
This template function can be declared as an unbound friend in the
following template class 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 template function is defined inside some namespace, the namespace
must be mentioned as well. E.g., 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 uses ForEach() to have its private
rows() member called, which in turn uses ForEach() to call its private
columns() member. Consequently, Vector2 uses two instantiations of
ForEach(), and therefore an unbound friend is appropriate here. It is
assumed that Type class objects can be inserted into ostream objects
(The definition of the ForEach() template function can be found in the
cplusplus.yo.zip archive at the ftp.rug.nl ftp-server). Here is the
program:
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 &));
public:
void process()
{
ForEach(begin(), end(), *this, &Vector2<Type>::rows);
}
private:
void rows(std::vector<Type> &row)
{
ForEach(row.begin(), row.end(), *this,
&Vector2<Type>::columns);
std::cout << std::endl;
}
void 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
*/
template <typename Type>
class PtrVector
{
template <typename Iterator, typename Class>
friend class Wrapper; // unbound friend class
};
All members of the template class Wrapper may now instantiate
PtrVectors using any actual type for its Type template parameter, at
the same time allowing Wrapper's instantiation to access all of
PtrVector's private members.
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);
...
};
Consider the following base class:
template<typename T>
class Base
{
T const &t;
public:
Base(T const &t)
:
t(t)
{}
};
The above class is a template class, which can be used as a
base class
for the following
derived template class Derived:
template<typename T>
class Derived: public Base<T>
{
public:
Derived(T const &t)
:
Base(t)
{}
};
Other combinations are possible as well: By specifying concrete template
type parameters of the base class, the base class is instantiated and the
derived class becomes an ordinary (non-template) class:
class Ordinary: public Base<int>
{
public:
Ordinary(int x)
:
Base(x)
{}
};
// With the following object definition:
Ordinary
o(5);
This construction allows us in a specific situation to
add functionality to a template class, without the need for
constructing a derived template class.
map can easily be used in combination with the find_if() generic
algorithm (section 17.4.16) to locate a particular element, it requires
the construction of a class and at least two additional function objects of
that class. If this is considered too much overhead in a particular context,
extending a template class with some tailor-made functionality might be
considered.
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 defining a process(string const &cmd) to do the actual command
processing, the 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 complex 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:
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, we use private derivation
here:
class Handler: public std::map<std::string,
void (Handler::*)(std::string const &cmd)>
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;
Handler()
:
std::map<std::string,
void (Handler::*)(std::string const &cmd)>
(s_cmds, s_cmds_end)
{}
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 << endl;
}
The following class SortVector is a template class derived from the
existing template class Vector. However, it allows us to perform a
hierarchical sort of its elements, using any order of any members its
data elements may contain. To accomplish this there is but one requirement:
the SortVector's data type must have dedicated member functions comparing
its members. For example, if SortVector's data type is an object of class
MultiData, then MultiData should implement member function 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 required for a hierarchical sort, then
MultiData should offer members like:
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 also assumed that operator<<() and
operator>>() have been defined for MultiData objects, but that assumption as
such is irrelevant to the current discussion.
The template class SortVector is derived directly from the template
class std::vector. Our implementation inherits all members from that base
class, as well as 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)
{}
However, its member hierarchicalSort() is the actual raison why the
class exists. This class defines the
hierarchical sort criteria. It expects
an array of pointers to member functions of the class indicated by
sortVector's template Type parameter as well as an unsigned
indicating the size of the array. The array's first element indicates the
class' most significant or first sort criterion, the array's last element
indicates the class' least significant or last sort criterion. Since the
stable_sort() generic algorithm was designed explicitly to suppport
hierarchical sorting, the member uses this generic algorithm to sort
SortVector's elements. With hierarchical sorting, the least significant
criterion should be sorted first. hierarchicalSort()'s implementation,
therefore, is easy, assuming the existence of a support class SortWith
whose objects are initialized by the addresses of the member functions passed
to the hierarchicalSort() member:
template <typename Type>
class SortWith
{
bool (Type::*d_ptr)(Type const &rhv) const;
The class SortWith is a simple
wrapper class around a pointer to
a predicate function. Since it's dependent on SortVector's actual data
type SortWith itself is also a template class:
template <typename Type>
class SortWith
{
bool (Type::*d_ptr)(Type const &rhv) const;
It's constructor receives such a pointer and initializes the class' d_ptr
data member:
SortWith(bool (Type::*ptr)(Type const &rhv) const)
:
d_ptr(ptr)
{}
Its binary predicate member operator()() should return true if its
first argument should be sorted before its second argument:
bool operator()(Type const &lhv, Type const &rhv) const
{
return (lhv.*d_ptr)(rhv);
}
Finally, an illustration is provided by the following main() function.
SortVector object is created for MultiData objects,
using 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));
bool (MultiData::*arr[])(MultiData const &rhv) const =
{
&MultiData::textCmp,
&MultiData::intCmp,
};
sv.hierarchicalSort(arr, 2);
MultiData's
member functions are swapped, and the previous step is repeated:
swap(arr[0], arr[1]);
sv.hierarchicalSort(arr, 2);
echo a 1 b 2 a 2 b 1 | a.out
This results in the following output:
a 1 b 2 a 2 b 1
====
a 1 a 2 b 1 b 2
====
a 1 b 1 a 2 b 2
====
This approach may be used for all template classes 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 template class derived from it.
As an illustration of this approach we'll develop such a template class in
this section. We'll develop a class Table derived from a non-template
class TableType. The class Table will display elements of some type in
a table having a configurable number of columns. The elements are either
displayed horizontally (the first k elements occupying the first row) or
vertically (the first r elements occupying a first column).
When displaying the table's elements they are inserted into a stream. This
allows us to define the handling of the table in 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)
can be implemented in Table, but the handling of the strings is left to
TableType. We'll cover some characteristics of TableType shortly,
concentrating on Table's interface first:
Table is a template class, requiring only one template
type parameter: Iterator refers to an iterator to some data type:
template <typename Iterator>
class Table: public TableType
{
TableType.
Iterators used to iterate over the elements to enter into the
table. Furthermore, 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 type that is actually
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
TableSupport reference parameter. The class TableSupport will be
developed later as a virtual class allowing clients to exercise this
control. Here are the class' constructors:
Table(Iterator const &begin, Iterator const &end,
unsigned nColumns, FillDirection direction);
Table(Iterator const &begin, Iterator const &end,
TableSupport &tableSupport,
unsigned nColumns, FillDirection direction);
Table's only two public members. Both
constructors use a base class initializer to initialize their TableType
base class and then call the class' 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,
unsigned nColumns, FillDirection direction)
:
TableType(tableSupport, nColumns, direction)
{
fill(begin, end);
}
template <typename Iterator>
Table<Iterator>::Table(Iterator const &begin, Iterator const &end,
unsigned nColumns, FillDirection direction)
:
TableType(nColumns, direction)
{
fill(begin, end);
}
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 a 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();
}
Table. Note that this
template class only has three members, two of them constructors. Therefore, in
most cases only two template functions will have to be instantiated: a
constructor and the class' fill() member. For example, the following
constructs a table having four columns, vertically filled by strings
extracted from the standard input stream:
Table<istream_iterator<string> >
table(istream_iterator<string>(cin), istream_iterator<string>(),
4, TableType::Vertical);
Note here that the fill-direction is specified as
TableType::Vertical. It could also have been specified using Table,
but since Table is a template class the specification would become
somewhat 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:
Table's base
class.
d_colWidth, a
vector storing the width of the widest element per column and d_indexFun,
pointing to the class' 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 might 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;
unsigned d_maxWidth;
unsigned d_nRows;
unsigned d_nColumns;
WidthType d_widthType;
std::vector<unsigned> d_colWidth;
unsigned (TableType::*d_widthFun)
(unsigned col) const;
std::string const &(TableType::*d_indexFun)
(unsigned row, unsigned col) const;
string objects populating the table are stored in a
protected data member:
std::vector<std::string> d_string;
TableSupport object:
#include "tabletype.ih"
TableType::TableType(TableSupport &tableSupport, unsigned 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)
{}
d_data has been filled, the table is initialized by
Table::fill(). The init() protected member resizes d_data 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 (unsigned col = 0; col < d_nColumns; col++)
{
unsigned width = 0;
for (unsigned row = 0; row < d_nRows; row++)
{
unsigned 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;
}
}
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 (unsigned row = 0; row < d_nRows; row++)
{
d_tableSupport.hline(row);
for (unsigned col = 0; col < d_nColumns; col++)
{
unsigned colwidth = width(col);
d_tableSupport.vline(col);
ostr << setw(colwidth) << stringAt(row, col);
}
d_tableSupport.vline();
}
d_tableSupport.hline();
return ostr;
}
cplusplus.yo.zip archive contains TableSupport's full
implementation. This implementation is found in the directory
yo/templateclasses/examples/table. Most of its remaining members are
private. Among those, the following two members return table element
[row][column] for, respectively, a horizontally filled table and a
vertically filled table:
std::string const &hIndex(unsigned row, unsigned col) const
{
return d_string[row * d_nColumns + col];
}
std::string const &vIndex(unsigned row, unsigned 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(unsigned rowIndex): called just before the elements in row
rowIndex will be displayed.
hline(): called immediately after displaying the final row.
vline(unsigned colIndex): called just before the element in column
colIndex will be displayed.
vline(): called immediately after displaying all elements in a row.
cplusplus.yo.zip archive for the full
implementation of the classes Table, TableType and TableSupport.
Here is a small 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)
{
unsigned 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 << endl;
return 0;
}
/*
Example of generated output:
After: echo a b c d e f g h i j | demo 3
a e i
b f j
c g
d h
After: echo a b c d e f g h i j | demo 3 h
a b c
d e f
g h i
j
*/
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 reverse_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 will store pointers to
Type values, rather than the values themselves. Of course, a destructor is
needed now, since the (externally allocated) memory for the Type objects
must eventually be freed. Alternatively, the allocation might be part of
PtrVector's tasks, when storing new elements. Here it is assumed that the
PtrVector's clients do the required allocations, and that the destructor
will be implemented later on.
The nested class defines its constructor as a private member, and allows
PtrVector<Type> objects to access 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, containing the required friend
declaration. Note the use of the typename keyword: since
std::vector<Type *>::iterator depends on a template parameter, it is not
yes an instantiated class, so iterator becomes an
implicit typename.
The compiler issues a corresponding warning if typename has been
omitted. The advice is to use typename in these cases. Furthermore note
that the base class' begin() member is called to initialize d_begin:
class iterator
{
friend class PtrVector<Type>;
typename std::vector<Type *>::iterator d_begin;
iterator(PtrVector<Type> &vector)
:
d_begin(vector.std::vector<Type *>::begin())
{}
public:
Type &operator*()
{
return **d_begin;
}
};
The remainder of the class is simple. Omitting all other functions that
might be implemented, the function begin() will return a newly constructed
PtrVector<Type>::iterator object. It may call the constructor since the
class iterator called its surrounding class its friend:
iterator 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 << endl;
}
Nested
enumerations and
typedefs can also be defined in template classes. The class Table,
mentioned before (section 19.9.3) inherited the enumeration
TableType::FillDirection. If Table would have been implemented as a
full template class, 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
exampe (assuming iter and nCols are defined as in section
19.9.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);
In section 17.2 the characterstics of iterators were introduced: all iterators should support an increment operation, a dereference operation and a comparison for (in)equality.
However, when iterators must be used in the context of generic algorithms they must meet additional requirements. This is caused by the fact that generic algorithms check the types of the iterators they receive. Simple pointers are usually accepted, but if an iterator-object is used it must be able to specify the kind of iterator it represents.
To ensure that an object of a class is interpreted as a particular type of
iterator, the class must be derived from the
class iterator. The
particular type of iterator is defined by the template class' first
parameter, and the particular data type to which the iterator points is
defined by the template class' second parameter. Before a class may be
inherited from the class iterator, the following header file must have
been included:
#include <iterator>
The particular type of iterator that is implemented by the derived class
is specified using a so-called
iterator_tag, provided as the
first template argument of the class iterator. For the five basic iterator
types, these tags are:
std::input_iterator_tag. This tag 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.
std::output_iterator_tag. This tag defines an
OutputIterator.
Iterators of this type allow for assignment operations, iterating from
the first to the last element of the series to which the iterator refers.
std::forward_iterator_tag. This tag 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.
std::bidirectional_iterator_tag. This tag defines a
BidirectionalIterator. Iterators of this type allow reading
and assignment operations, iterating step by step, possibly in alternating
directions, over all elements of the series to which the iterator refers.
<