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: 7.2.0) 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.
Templates can not only be constructed for functions but also for complete
classes. Constructing a
class template can be considered when the class
should be able to handle different types of data. Class templates are
frequently used in C++: chapter 12 discusses data structures
like vector, stack
and queue
, which are implemented as class
templates. With class templates, the
algorithms and the data on
which the algorithms operate are completely separated from each other. To use
a particular
data structure, operating on a particular data type, only the
data type needs to be specified when the class template object is defined
or declared, e.g., stack<int> iStack
.
In this chapter constructing and using class templates is discussed. In a sense, class templates compete with object oriented programming (cf. chapter 14), 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 operate 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.
The correspondence between class templates and polymorphic classes is
well-known. In their book C++ Coding Standards (Addison-Wesley, 2005)
Sutter and Alexandrescu (2005) refer to
static polymorphism
and
dynamic polymorphism.
Dynamic polymorphism is what we use when overriding virtual members:
Using the
vtable construction the function that's actually called depends
on the type of object a (base) class pointer points to. Static
polymorphism is used when templates are used: depending on the actual types,
the compiler creates the code, compile time, that's appropriate for those
particular types. There's no need to consider static and dynamic polymorphism
as mutually exlusive variants of polymorphism. Rather, both can be used
together, combining their strengths. A warning is in place, though. When a
class template defines virtual members all virtual members are
instantiated for every instantiated type. This has to happen, since the
compiler must be able to construct the class's vtable
.
Generally, class templates are easier to use. It is certainly easier to write
stack<int> istack
to create a stack of ints
than to derive a new
class Istack: public stack
and to implement all necessary member functions
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
class template 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_ptr
s rather than plain
pointers we not only ensure proper memory management, but we may also prevent
memory leaks when objects of classes using pointer data-members cannot
completely be constructed.
The one disadvantage of
auto_ptr
s is that
they can only be used for single objects and not for pointers to
arrays of objects. Here we'll construct the class template 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 although it would be entirely possible to
define it as a member returning a reference to the first element of its array
of objects, the member operator+(int index)
, returning the address of
object index
would most likely be expected too. These extensions of
FBB::auto_ptr
are left as exercises to the reader.
template
, which is also followed by a non-empty list of
template type
and/or non-type parameters, surrounded by angle brackets. The
template
keyword followed by the template parameter list enclosed in
angle 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 angle 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
class template member functions or class template constructors:
class template type parameters
should preferably be defined as Type const &
, rather than Type
, to
prevent unnecessary copying of large
data structures. Template
class constructors should use
member initializers rather than member
assignment within the body of the constructors, 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(); auto_ptr(auto_ptr<Data> &other); auto_ptr(Data *data); ~auto_ptr(); auto_ptr<Data> &operator=(auto_ptr<Data> &rvalue); Data &operator[](size_t index); Data const &operator[](size_t index) const; Data *get(); Data const *get() const; Data *release(); void reset(Data *p = 0); private: void destroy(); void copy(auto_ptr<Data> &other); Data &element(size_t idx) const; }; template <typename Data> inline auto_ptr<Data>::auto_ptr() : d_data(0) {} template <typename Data> inline auto_ptr<Data>::auto_ptr(auto_ptr<Data> &other) { copy(other); } template <typename Data> inline auto_ptr<Data>::auto_ptr(Data *data) : d_data(data) {} template <typename Data> inline auto_ptr<Data>::~auto_ptr() { destroy(); } template <typename Data> inline Data &auto_ptr<Data>::operator[](size_t index) { return d_data[index]; } template <typename Data> inline Data const &auto_ptr<Data>::operator[](size_t index) const { return d_data[index]; } template <typename Data> inline Data *auto_ptr<Data>::get() { return d_data; } template <typename Data> inline Data const *auto_ptr<Data>::get() const { return d_data; } template <typename Data> inline void auto_ptr<Data>::destroy() { delete[] d_data; } template <typename Data> inline void auto_ptr<Data>::copy(auto_ptr<Data> &other) { d_data = other.release(); } template <typename Data> auto_ptr<Data> &auto_ptr<Data>::operator=(auto_ptr<Data> &rvalue) { if (this != &rvalue) { destroy(); copy(rvalue); } return *this; } 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; } } // FBBThe 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 ordinary types, followed by an abstraction phase changing all necessary
references to ordinary 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. Class template 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 class template, 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.
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
is mentioned in the implementation, the
template's type parameter is mentioned as well. This is obligatory. Actually,
the class template's type name is the name of the class template plus its
template argument. Thus, a vector<int>
represents another class type
than a vector<float>
.
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.
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; 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 class template objects for which default parameter values have been defined the type specifications may be omitted, but the angle 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. Function templates, even member function templates, 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 class template 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 the declaration and the definition of a template class. As a rule of thumb default values should be omitted from declarations, as class template 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 ordinary classes. Such defaults should be specified in the member functions' declarations and not in their definitions.
Class templates also may define non-type parameters. Like the non-const parameters used with function templates they must be constants whose values are known by the time an object is instantiated.
However, their values are not deduced by the compiler using arguments
passed to constructors. Assume we modify the class template FBB::auto_ptr
so that it has an additional non-type parameter size_t 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, size_t Size> class auto_ptr { Data *d_data; size_t d_n; public: auto_ptr(auto_ptr<Data, Size> &other); auto_ptr(Data2 *data); auto_ptr(Data const (&arr)[Size]); ... }; template <typename Data, size_t Size> inline auto_ptr<Data, Size>::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 deduced by the compiler. When the compiler is asked to compile the following
main()
function it reports a
mismatch between the required and actual number of template parameters:
int main() { int arr[30]; 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, size_t Size> class FBB::auto_ptr' */Defining
Size
as 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 need another value,
we might specify size_t Size = 0
in the templates parameter type list.
However, this causes a mismatch between the default value 0 and the actual
size of the array arr
as defined in the above main()
function. The
compiler using the default value, reports:
In instantiation of `FBB::auto_ptr<int, 0>': ... error: creating array with size zero (`0')So, although class templates 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.
Note that default template parameter values (either type or non-type template parameters) may not be used when template member functions are defined outside the class interface. Function template definitions (and thus: class template member functions) may not be given default template (non) type parameter values. If default template parameter values are to be used for class template members, they have to be specified in the class interface.
Similar to non-type parameters of function templates, non-type parameters of class templates 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).
size_t
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 deduced 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 function template (containing a template announcement of its own), then the compiler will be able to deduce the non-type parameter's value, without us having to specify it explicitly as a class template non-type parameter.
Member functions (or classes) of class templates 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 class template's Data
type parameter, but must provide the member template with a non-type parameter
of its own. The class interface is given the following additional member
declaration:
template <typename Data> class auto_ptr { ... public: template <size_t Size> auto_ptr(Data const (&arr)[Size]); ... };and the constructor's implementation becomes:
template <typename Data> template <size_t Size> inline auto_ptr<Data>::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 class templates, 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);
namespace SomeName { template <typename Type, ...> // class template definition class ClassName { ... }; template <typename Type, ...> // non-inline member definition(s) ClassName<Type, ...>::member(...) { ... } } // namespace closed
template
announcements must be used: the class template's template
announcement is specified first, followed by the member template's
template
announcement.
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 problem can be solved by simply changing the
constructor auto_ptr(Data *data)
into a member template as well, in which
case its template type parameter should be changed into `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 Data> template <typename Data2> // data: dynamically allocated inline auto_ptr<Data>::auto_ptr(Data2 *data) : 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. 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 class templates 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 interfaceIn the above case,
s_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:
s_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's d_data
member, e.g., 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
parameter and and
environ
, for example are char
**
varables, both having a final element equal to 0. The specialization
developed here assumes that there is indeed such a final 0-pointer element.
It this special case we might not be interested in the mere reassignment
of the constructor's parameter to the class's d_data
member, but we might
be interested in copying the complete char **
structure. To implement this,
class template specializations may be used.
Class template specializations are used in cases where member function templates 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.
Class template 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 (size_t 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
class template 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 class template 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 class template. 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 "autoptr.h" namespace FBB { template<> class auto_ptr<char *> { char **d_data; size_t d_n; public: auto_ptr<char *>(); auto_ptr<char *>(auto_ptr<char *> &other); auto_ptr<char *>(char **argv); // template <size_t Size> NI // auto_ptr(char *const (&arr)[Size]) ~auto_ptr(); auto_ptr<char *> &operator=(auto_ptr<char *> &rvalue); char *&operator[](size_t index); char *const &operator[](size_t index) const; char **get(); char *const *get() const; char **release(); void reset(char **argv); void additional() const; // just an additional public // member private: void full_copy(char **argv); void copy(auto_ptr<char *> &other); void destroy(); }; inline auto_ptr<char *>::auto_ptr() : d_data(0), d_n(0) {} inline auto_ptr<char *>::auto_ptr(auto_ptr<char *> &other) { copy(other); } inline auto_ptr<char *>::auto_ptr(char **argv) { full_copy(argv); } inline auto_ptr<char *>::~auto_ptr() { destroy(); } inline void auto_ptr<char *>::reset(char **argv) { destroy(); full_copy(argv); } inline void auto_ptr<char *>::additional() const {} inline void auto_ptr<char *>::full_copy(char **argv) { d_n = 0; char **tmp = argv; while (*tmp++) d_n++; d_data = new char *[d_n]; for (size_t idx = 0; idx < d_n; idx++) { std::string str(argv[idx]); d_data[idx] = strcpy(new char[str.length() + 1], str.c_str()); } } inline void auto_ptr<char *>::destroy() { while (d_n--) delete d_data[d_n]; delete[] d_data; } }
Note that specializations not automatically have empty template
parameter lists. Consider the following example of an (grossly incomplete)
specialization of FBB::auto_ptr
:
#include <iostream> #include <vector> #include "autoptr.h" namespace FBB { template<typename T> class auto_ptr<std::vector<T> *> { public: auto_ptr<std::vector<T> *>(); }; template <typename T> inline auto_ptr<std::vector<T> * >::auto_ptr() { std::cout << "Vector specialization\n"; } }
In this example a specialization is created for the type std::vector>
,
instantiated with any data type T
. Since T
is not specified, it must
be mentioned in the template paramter list as a template type parameter.
E.g., if an FBB::auto_ptr<std::vector<int> *>
is constructed, the compiler
deducts that T
is an int
and will use the vector<T> *
specialization, in which T
could be used as a type specification. The
following basic example shows that the compiler will indeed select the
vector<T>*
specialization:
#include "autoptr4.h" int main(int argc, char **argv) { FBB::auto_ptr<std::vector<int> *> vspec; return 0; }
In this section we'll introduce a variant of these specializations, both in number and types of template parameters that are specialized. Partial specializations may be defined for class templates 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 as consisting of a table of a certain
number of rows and columns, filled with numbers. Immediately we recognize an
opening for using templates: the numbers might be plain double
values, but
they could also be complex numbers, for which our
complex container (cf. section 12.4) might prove
useful. Consequently, our class template should be given a DataType
template type parameter, for which a ordinary 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 when 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 <size_t Rows, size_t 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) marginalsSo, what do we want our class template to offer?
Rows
' rows each containing `Columns
' elements of type
DataType
. It can be an array, rather than a pointer, since the matrix'
dimensions are known a priori. Since a vector of Columns
elements (a
row of the matrix), as well as a vector of Row
elements (a column
of the matrix) is often used, typedefs could be used by the class. The
class interface's initial section therefore contains:
typedef Matrix<1, Columns, DataType> MatrixRow; typedef Matrix<Rows, 1, DataType> MatrixColumn; MatrixRow d_matrix[Rows];
template <size_t Rows, size_t Columns, typename DataType> Matrix<Rows, Columns, DataType>::Matrix() { std::fill(d_matrix, d_matrix + Rows, MatrixRow()); } template <size_t Rows, size_t Columns, typename DataType> Matrix<Rows, Columns, DataType>::Matrix(std::istream &str) { for (size_t row = 0; row < Rows; row++) for (size_t col = 0; col < Columns; col++) str >> d_matrix[row][col]; }
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:
template <size_t Rows, size_t Columns, typename DataType> Matrix<1, Columns, DataType> &Matrix<Rows, Columns, DataType>::operator[](size_t idx) { return d_matrix[idx]; }
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 when computing
marginals and the matrix' sum of all elements. Here are the implementations of
these members:
template <size_t Rows, size_t Columns, typename DataType> Matrix<1, Columns, DataType> Matrix<Rows, Columns, DataType>::columnMarginals() const { return MatrixRow(*this); } template <size_t Rows, size_t Columns, typename DataType> Matrix<Rows, 1, DataType> Matrix<Rows, Columns, DataType>::rowMarginals() const { return MatrixColumn(*this); } template <size_t Rows, size_t Columns, typename DataType> DataType Matrix<Rows, Columns, DataType>::sum() const { return rowMarginals().sum(); }
Class template 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 class template definition. Furthermore, the specialization must
follow the definition of the generic class template 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 class template (partial) specialization, the class name
is followed by a template type parameter list specifying ordinary 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 Rows
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 <size_t Columns, typename DataType> // no default specified class Matrix<1, Columns, DataType>
MatrixRow
contains the data of a single row. So it needs a
data member storing Columns
values of type DataType
. Since Columns
is a constant value, the d_row
data member can be defined as an array:
DataType d_column[Columns];
MatrixRow
's data elements using
DataType
's default constructor:
template <size_t Columns, typename DataType> Matrix<1, Columns, DataType>::Matrix() { std::fill(d_column, d_column + Columns, DataType()); }
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 are 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 <size_t Columns, typename DataType> template <size_t Rows> Matrix<1, Columns, DataType>::Matrix( Matrix<Rows, Columns, DataType> const &matrix) { std::fill(d_column, d_column + Columns, DataType()); for (size_t col = 0; col < Columns; col++) for (size_t row = 0; row < Rows; row++) d_column[col] += matrix[row][col]; }
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:
template <size_t Columns, typename DataType> DataType &Matrix<1, Columns, DataType>::operator[](size_t 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
class template
definition as well as all its specializations are provided in the
cplusplus.yo.zip
archive (at ftp.rug.nl) in the
file yo/classtemplates/examples/matrix.h
):
template <size_t Rows, typename DataType> class Matrix<Rows, 1, DataType>
MatrixRow
constructors were implemented. 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 simply implemented
using the accumulate()
generic algorithm:
template <size_t Rows, typename DataType> DataType Matrix<Rows, 1, DataType>::sum() { return std::accumulate(d_row, d_row + Rows, DataType()); }
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 well:
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 <typename DataType> template <size_t Rows, size_t Columns> Matrix<1, 1, DataType>::Matrix( Matrix<Rows, Columns, DataType> const &matrix) : d_cell(matrix.rowMarginals().sum()) {} template <typename DataType> template <size_t Rows> Matrix<1, 1, DataType>::Matrix(Matrix<Rows, 1, DataType> const &matrix) : d_cell(matrix.sum()) {}
Matrix<1, 1>
is basically a wrapper around a DataType
value, we need members to access that latter value. A type conversion
operator might be usefull, but we'll also need a get()
member to obtain
the value if the conversion operator isn't used by the compiler (which
happens when the compiler is given a choice, see section
9.3). Here are the accessors (leaving out their const
variants):
template <typename DataType> Matrix<1, 1, DataType>::operator DataType &() { return d_cell; } template <typename DataType> DataType &Matrix<1, 1, DataType>::get() { return d_cell; }
main()
function shows how the Matrix
class template
and its partial specializations can be used:
#include <iostream> #include "matrix.h" using namespace std; int main(int argc, char **argv) { Matrix<3, 2> matrix(cin); Matrix<1, 2> colMargins(matrix); cout << "Column marginals:\n"; cout << colMargins[0] << " " << colMargins[1] << endl; Matrix<3, 1> rowMargins(matrix); cout << "Row marginals:\n"; for (size_t 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 class template defines
default template parameter values, albeit that in that case the compiler will
provide the defaults (cf. section 19.5 where double
is used as the
default type to be used with the template's DataType
parameter). The
actual values or types of template parameters are
never deduced, as happens with
function templates: 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 class template 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 class template declaration is sufficient if the compiler encounters
function declarations of functions having return values or parameters which
are class template objects, pointers or references. The following little
source file may be compiled, although the compiler hasn't seen the definition
of the Matrix
class template. Note that generic classes as well as
(partial) specializations may be declared. Furthermore, note that a function
expecting or returning a class template object, reference, or parameter itself
automatically becomes a function template. This is necessary to allow the
compiler to tailor the function to the types of various actual arguments that
may be passed to the function:
#include <stddef.h> template <size_t Rows, size_t Columns, typename DataType = double> class Matrix; template <size_t Columns, typename DataType> class Matrix<1, Columns, DataType>; Matrix<1, 12> *function(Matrix<2, 18, size_t> &mat);
When class templates are used 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 class template 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 4.1.2) these sizes are 3904 bytes (after
stripping). 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
will yield the
same conclusion: only template member functions that are actually used are
initialized. Here is an example of the class template Demo
used for this
little experiment. In main()
only the first constructor and the first
member function are called and thus only these members were instantiated:
#include <iostream> template <typename Type> class Demo { Type d_data; public: Demo(); Demo(Type const &value); void member1(); void member2(Type const &value); }; template <typename Type> Demo<Type>::Demo() : d_data(Type()) {} template <typename Type> void Demo<Type>::member1() { d_data += d_data; } // the following members are commented out before compiling // the second program template <typename Type> Demo<Type>::Demo(Type const &value) : d_data(value) {} template <typename Type> void Demo<Type>::member2(Type const &value) { d_data += value; } int main() { Demo<int> demo; demo.member1(); }
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
class template uses a
qsort()
function, then qsort()
does not depend
on a template parameter. Consequently, qsort()
must be known to the
compiler when it encounters 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 class template 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
syntactic 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 ordinary classes, class templates may declare other functions and
classes as their friends. Conversely, ordinary classes may declare template
classes as their friends. Here too, the friend is constructed as a special
function or class augmenting or supporting the functionality of the declaring
class. Although the friend
keyword can thus be used in any type of class
(ordinary or template) to declare any type of function or class as a
friend, when using class templates 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 a friend should be constructed. One reason, though, is to
allow the function to access the class's 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 size_t s_time; std::vector<Type> d_data; public: Storage(); }; template <typename Type> size_t Storage<Type>::s_time = 0; template <typename Type> Storage<Type>::Storage() {} void basic() { Storage<int>::s_time = time(0); Storage<double> storage; std::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); }; inline::Friend::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)); } }; inline Friend::Friend(std::istream &input) : d_ints(new Composer<int>(input)) {} inline 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 typeIncomplete 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>;
template <typename Key, typename Value> template <typename Key2, typename Value2> Iterator<Key2, Value2> Dictionary<Key, Value>::begin() { return Iterator<Key, Value>(*this); } template <typename Key, typename Value> template <typename Key2, typename Value2> Iterator<Key2, Value2> Dictionary<Key, Value>::subset(Key const &key) { return Iterator<Key, Value>(*this).subset(key); }
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:
template <typename Key, typename Value> typename std::map<Key, Value>::iterator Iterator<Key, Value>::begin() { return d_dict.begin(); }
Dictionary
should be able to construct an Iterator
, as Iterator
is closely tied
to Dictionary
. This can be implemented 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 as a bound friend, we ensure that it
can only create Iterator
s using template parameters identical to its
own. Here is how it's implemented:
template <typename Key, typename Value> class Iterator { friend Dictionary<Key, Value>::Dictionary(); std::map<Key, Value> &d_dict; Iterator(Dictionary<Key, Value> &dict); public:
In this example, Dictionary
's constructor is defined as Iterator
's
friend. Here the friend is a template member. Other members can be declared as
a class's 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:
friend std::vector<Value> Dictionary<Key, Value>::sortValues();
template <typename T> // a function void fun(T *t) // template { t->not_public(); }; template <typename X> // a class template class A { // fun() is used as // friend bound to A, // instantiated for X, // whatever X may be friend void fun<A<X> >(A<X> *); public: A(); private: void not_public(); }; template <typename X> A<X>::A() { fun(this); } template <typename X> void A<X>::not_public() {} int main() { A<int> a; fun(&a); // fun instantiated for // A<int>. }
Here are the syntactic conventions declaring unbound friends:
template <typename Iterator, typename Class, typename Data> Class &ForEach(Iterator begin, Iterator end, Class &object, void (Class::*member)(Data &));
This function template can be declared as an unbound friend in the
following class template Vector2
:
template <typename Type> class Vector2: public std::vector<std::vector<Type> > { template <typename Iterator, typename Class, typename Data> friend Class &ForEach(Iterator begin, Iterator end, Class &object, void (Class::*member)(Data &)); ... };If the function template is defined inside some namespace, 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()
function template 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> > { typedef typename Vector2<Type>::iterator iterator; template <typename Iterator, typename Class, typename Data> friend Class &ForEach(Iterator begin, Iterator end, Class &object, void (Class::*member)(Data &)); public: void process(); private: void rows(std::vector<Type> &row); void columns(Type &str); }; template <typename Type> void Vector2<Type>::process() { ForEach<iterator, Vector2<Type>, std::vector<Type> > (this->begin(), this->end(), *this, &Vector2<Type>::rows); } template <typename Type> void Vector2<Type>::rows(std::vector<Type> &row) { ForEach(row.begin(), row.end(), *this, &Vector2<Type>::columns); std::cout << std::endl; } template <typename Type> void Vector2<Type>::columns(Type &str) { std::cout << str << " "; } using namespace std; int main() { Vector2<string> c; c.push_back(vector<string>(3, "Hello")); c.push_back(vector<string>(2, "World")); c.process(); } /* Generated output: Hello Hello Hello World World */
template <typename Type> class PtrVector { template <typename Iterator, typename Class> friend class Wrapper; // unbound friend class };All members of the class template
Wrapper
may now instantiate
PtrVector
s using any actual type for its Type
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); };The above class is a class template, which can be used as a base class for the following derived class template
Derived
:
template<typename T> class Derived: public Base<T> { public: Derived(T const &t); }; template<typename T> Derived<T>::Derived(T const &t) : Base(t) {}Other combinations are possible as well: by specifying ordinary template type parameters of the base class, the base class is instantiated and the derived class becomes an ordinary class:
class Ordinary: public Base<int> { public: Ordinary(int x); }; inline Ordinary::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 class template, without the need for constructing a derived class template.
Class template derivation pretty much follows the same rules as ordinary
class derivation, not involving class templates. However, some subtleties
associated with class template derivation may easily cause confusion. In the
following sections class derivation involving class templates will be
discussed. Some of the examples shown in these sections may contain unexpected
statements and expressions, like the use of this
when members of a
template base class are called from a derived class. The `chicken and egg'
problem I encountered here was solved by first discussing the principles of
class template derivation; next the subtleties that are part of class template
derivation are covered by section 20.1.
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 class template 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: private 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;
inline Handler::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 class template derived from the
existing class template Vector
. However, it allows us to perform a
hierarchal 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 functions having the
following prototypes for each of its data members which can be compared:
bool (MultiData::*)(MultiData const &rhv)So, if
MultiData
has two data members, int d_value
and
std::string d_text
, and both may be required for a hierarchal 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_textFurthermore, 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 class template 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 hierarchalSort()
is the actual reason why the
class exists. This class defines the
hierarchal sort criteria. It expects
an array of pointers to member functions of the class indicated by
sortVector
's template Type
parameter as well as a size_t
indicating the size of the array. The array's first element indicates the
class's most significant or first sort criterion, the array's last element
indicates the class's least significant or last sort criterion. Since the
stable_sort()
generic algorithm was designed explicitly to support
hierarchal sorting, the member uses this generic algorithm to sort
SortVector
's elements. With hierarchal sorting, the least significant
criterion should be sorted first. hierarchalSort()
'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 hierarchalSort()
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 class template:
template <typename Type> class SortWith { bool (Type::*d_ptr)(Type const &rhv) const;
It's constructor receives such a pointer and initializes the class's d_ptr
data member:
template <typename Type> SortWith<Type>::SortWith(bool (Type::*ptr)(Type const &rhv) const) : d_ptr(ptr) {}
Its binary predicate member operator()()
should return true
if its
first argument should be sorted before its second argument:
template <typename Type> bool SortWith<Type>::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.outThis 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 class templates having member functions whose implementations do not depend on template parameters. These members may be defined in a separate class which is then used as a base class of the class template derived from it.
As an illustration of this approach we'll develop such a class template in
this section. We'll develop a class Table
derived from an ordinary
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 class template, requiring only one template
type parameter: Iterator
refers to an iterator to some data type:
template <typename Iterator> class Table: public TableType {
TableType
.
Iterator
s 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's constructors:
Table(Iterator const &begin, Iterator const &end, size_t nColumns, FillDirection direction); Table(Iterator const &begin, Iterator const &end, TableSupport &tableSupport, size_t nColumns, FillDirection direction);
Table
's only two public members. Both
constructors use a base class initializer to initialize their TableType
base class and then call the class's private member fill()
to insert data
into the TableType
base class object. Here are the constructor's
implementations:
template <typename Iterator> Table<Iterator>::Table(Iterator const &begin, Iterator const &end, TableSupport &tableSupport, size_t nColumns, FillDirection direction) : TableType(tableSupport, nColumns, direction) { fill(begin, end); } template <typename Iterator> Table<Iterator>::Table(Iterator const &begin, Iterator const &end, size_t nColumns, FillDirection direction) : TableType(nColumns, direction) { fill(begin, end); }
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
class template only has three members, two of them constructors. Therefore, in
most cases only two function templates will have to be instantiated: a
constructor and the class's fill()
member. For example, the following
constructs a table having four columns, vertically filled by string
s
extracted from the standard input stream:
Table<istream_iterator<string> > table(istream_iterator<string>(cin), istream_iterator<string>(), 4, TableType::Vertical);Note here that the fill-direction is specified as
TableType::Vertical
. It could also have been specified using Table
,
but since Table
is a class template, 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's member function returning the element in
table[row][column]
, conditional to the table's fill
direction. TableType
also uses a TableSupport
pointer and a
reference. The constructor not requiring a TableSupport
object uses the
TableSupport *
to allocate a (default) TableSupport
object and then
uses the TableSupport &
as the object's alias. The other constructor
initializes the pointer to 0, and uses the reference data member to refer to
the TableSupport
object provided by its parameter. Alternatively, a static
TableSupport
object 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; size_t d_maxWidth; size_t d_nRows; size_t d_nColumns; WidthType d_widthType; std::vector<size_t> d_colWidth; size_t (TableType::*d_widthFun) (size_t col) const; std::string const &(TableType::*d_indexFun) (size_t row, size_t col) const;
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, size_t nColumns, FillDirection direction) : d_tableSupportPtr(0), d_tableSupport(tableSupport), d_maxWidth(0), d_nRows(0), d_nColumns(nColumns), d_widthType(ColumnWidth), d_colWidth(nColumns), d_widthFun(&TableType::columnWidth), d_indexFun(direction == Horizontal ? &TableType::hIndex : &TableType::vIndex) {}
d_string
has been filled, the table is initialized by
Table::fill()
. The init()
protected member resizes d_string
so
that its size is exactly rows x columns
, and it determines the maximum
width of the elements per column. Its implementation is straightforward:
#include "tabletype.ih" void TableType::init() { if (!d_string.size()) // no elements return; // then do nothing d_nRows = (d_string.size() + d_nColumns - 1) / d_nColumns; d_string.resize(d_nRows * d_nColumns); // enforce complete table // determine max width per column, // and max column width for (size_t col = 0; col < d_nColumns; col++) { size_t width = 0; for (size_t row = 0; row < d_nRows; row++) { size_t len = stringAt(row, col).length(); if (width < len) width = len; } d_colWidth[col] = width; if (d_maxWidth < width) // max. width so far. d_maxWidth = width; } }
insert()
is used by the insertion operator
(operator
<<()
) to insert a Table
into a stream. First it informs the
TableSupport
object about the table's dimensions. Next it displays the
table, allowing the TableSupport
object to write headers, footers and
separators:
#include "tabletype.ih" ostream &TableType::insert(ostream &ostr) const { if (!d_nRows) return ostr; d_tableSupport.setParam(ostr, d_nRows, d_colWidth, d_widthType == EqualWidth ? d_maxWidth : 0); for (size_t row = 0; row < d_nRows; row++) { d_tableSupport.hline(row); for (size_t col = 0; col < d_nColumns; col++) { size_t colwidth = width(col); d_tableSupport.vline(col); ostr << setw(colwidth) << stringAt(row, col); } d_tableSupport.vline(); } d_tableSupport.hline(); return ostr; }
cplusplus.yo.zip
archive contains TableSupport
's full
implementation. This implementation is found in the directory
yo/classtemplates/examples/table
. Most of its remaining members are
private. Among those, the following two members return table element
[row][column]
for, respectively, a horizontally filled table and a
vertically filled table:
inline std::string const &TableType::hIndex(size_t row, size_t col) const { return d_string[row * d_nColumns + col]; } inline std::string const &TableType::vIndex(size_t row, size_t col) const { return d_string[col * d_nRows + row]; }
The support class TableSupport
is used to display headers, footers,
captions and separators. It has four virtual members to perform those tasks
(and, of course, a virtual constructor):
hline(size_t rowIndex)
: called just before the elements in row
rowIndex
will be displayed.
hline()
: called immediately after displaying the final row.
vline(size_t 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) { size_t nCols = 5; if (argc > 1) { istringstream iss(argv[1]); iss >> nCols; } istream_iterator<string> iter(cin); // first iterator isn't const Table<istream_iterator<string> > table(iter, istream_iterator<string>(), nCols, argc == 2 ? TableType::Vertical : TableType::Horizontal); cout << table << 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 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
yet an instantiated class, so iterator
becomes an
implicit typename.
The compiler issues a corresponding warning if typename
has been
omitted. In these cases typename
must be used. Here is the class
interface:
class iterator { friend class PtrVector<Type>; typename std::vector<Type *>::iterator d_begin; iterator(PtrVector<Type> &vector); public: Type &operator*(); };
The implementation of the members shows that the base class's begin()
member is called to initialize d_begin
. Also note that the return type of
PtrVector<Type>::begin()
must again be preceded by typename
:
template <typename Type> PtrVector<Type>::iterator::iterator(PtrVector<Type> &vector) : d_begin(vector.std::vector<Type *>::begin()) {} template <typename Type> Type &PtrVector<Type>::iterator::operator*() { return **d_begin; }
The remainder of the class is simple. Omitting all other functions that
might be implemented, the function begin()
will return a newly constructed
PtrVector<Type>::iterator
object. It may call the constructor since the
class iterator
called its surrounding class its friend:
template <typename Type> typename PtrVector<Type>::iterator PtrVector<Type>::begin() { return iterator(*this); }
Here is a simple
skeleton program, showing how the nested class
iterator
might be used:
int main() { PtrVector<int> vi; vi.push_back(new int(1234)); PtrVector<int>::iterator begin = vi.begin(); std::cout << *begin << endl; }
Nested
enumerations and
typedefs can also be defined in class templates. The class Table
,
mentioned before (section 19.9.3) inherited the enumeration
TableType::FillDirection
. If Table
would have been implemented as a
full class template, then this enumeration would have been defined in
Table
itself as:
template <typename Iterator> class Table: public TableType { public: enum FillDirection { Horizontal, Vertical }; ... };In this case, the actual value of the template type parameter must be specified when referring to a
FillDirection
value or to its type. For
example (assuming iter
and nCols
are defined as in section
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 characteristics 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 class template's first
parameter, and the particular data type to which the iterator points is
defined by the class template's 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.
std::random_access_iterator_tag
. This tag defines a
RandomAccessIterator. Iterators of this type allow reading and
assignment operations, iterating, possibly in alternating directions, over all
elements of the series to which the iterator refers using any available
(random) stepsize.
Note that iterators are always defined over a certain range, e.g.,
[begin, end)
. Increment and decrement operations may result in
undefined behavior of the iterator if the resulting iterator value would refer
to a location outside of this range.
Often, iterators only access the elements of the series to which they refer. Internally, an iterator may use an ordinary pointer, but it is hardly ever necessary for the iterator to allocate its own memory. Therefore, as the overloaded assignment operator and the copy constructor do not have to allocate any memory, the default implementation of the overloaded assignment operator and of the copy constructor is usually sufficient. I.e., usually these members do not have to be implemented at all. As a consequence there is usually also no destructor.
Most classes offering members returning iterators do so by having members constructing the required iterator, which is thereupon returned as an object by these member functions. As the caller of these member functions only has to use or sometimes copy the returned iterator objects, there is normally no need to provide any publicly available constructors, except for the copy constructor. Therefore these constructors may usually be defined as private or protected members. To allow an outer class to create iterator objects, the iterator class will declare the outer class as its friend.
In the following sections, the construction of a RandomAccessIterator, the most complex of all iterators, and the construction of a reverse RandomAccessIterator is discussed. The container class for which a random access iterator must be developed may actually store its data elements in many different ways, e.g., using various containers or using pointers to pointers. Therefore it is difficult to construct a template iterator class which is suitable for a large variety of ordinary (container) classes.
In the following sections, the available std::iterator
class will be
used to construct an inner class representing a random access iterator. This
approach clearly shows how to construct an iterator class. The reader may
either follow this approach when constructing iterator classes in other
contexts, or a full template iterator class can be designed. An example of
such a template iterator class is provided in section 21.6.
The construction of the random access iterator as shown in the next sections aims at the implementation of an iterator reaching the elements of a series of elements only accessible through pointers. The iterator class is designed as an inner class of a class derived from a vector of string pointers.
auto_ptr
objects cannot be stored in containers using
pointer data types for containers was discouraged. However, we might be able
to use pointer data types in specific contexts. In the following class
StringPtr
, a ordinary class is derived from the std::vector
container
using std::string *
as its data type:
#ifndef INCLUDED_STRINGPTR_H_ #define INCLUDED_STRINGPTR_H_ #include <string> #include <vector> class StringPtr: public std::vector<std::string *> { public: StringPtr(StringPtr const &other); ~StringPtr(); StringPtr &operator=(StringPtr const &other); }; #endifNote the declaration of the destructor: as the object stores string pointers, a destructor is required to destroy the strings when the
StringPtr
object itself is destroyed. Similarly, a copy constructor and
overloaded assignment is required. Other members (in particular: constructors)
are not explicitly declared as they are not relevant to this section's topic.
Let's assume that we want to be able to use the sort()
generic
algorithm with StringPtr
objects. This algorithm (see section 17.4.58)
requires two RandomAccessIterators. Although these iterators are available
(via std::vector
's begin()
and end()
members), they return
iterators to std::string *
s, which cannot sensibly be compared.
To remedy this, assume that we have defined an internal type
StringPtr::iterator
, not returning iterators to pointers, but iterators
to the objects these pointers point to. Once this iterator
type is
available, we can add the following members to our StringPtr
class
interface, hiding the identically named, but useless members of its base
class:
StringPtr::iterator begin(); // returns iterator to the first element StringPtr::iterator end(); // returns iterator beyond the last // elementSince these two members return the (proper) iterators, the elements in a
StringPtr
object can easily be sorted:
in main() { StringPtr sp; // assume sp is somehow filled sort(sp.begin(), sp.end()); // sp is now sorted return 0; }To make this all work, the type
StringPtr::iterator
must be
defined. As suggested by its type name, iterator
is a nested type of
StringPtr
, suggesting that we may implement iterator
as a nested class
of StringPtr
. However, to use a StringPtr::iterator
in combination
with the sort()
generic algorithm, it must also be a
RandomAccessIterator
. Therefore, StringPtr::iterator
itself must be
derived from the existing class
std::iterator
, available once the
following preprocessor directive has been specified:
#include <iterator>To derive a class from
std::iterator
, both the iterator type and the
data type the iterator points to must be specified. Take caution: our iterator
will take care of the string *
dereferencing; so the required data type
will be std::string
, and not std::string *
. So, the class
iterator
starts its interface as:
class iterator: public std::iterator<std::random_access_iterator_tag, std::string>Since its base class specification is quite complex, we could consider associating this type with a shorter name using the following
typedef
:
typedef std::iterator<std::random_access_iterator_tag, std::string> Iterator;However, if the defined type (
Iterator
) is used only once or twice,
the typedefinition only adds clutter to the interface, and is better not used.
Now we're ready to redesign StringPtr
's class interface. It contains
members returning (reverse) iterators, and a nested iterator
class. The
members will be discussed in some detail next:
class StringPtr: public std::vector<std::string *> { public: class iterator: public std::iterator<std::random_access_iterator_tag, std::string> { friend class StringPtr; std::vector<std::string *>::iterator d_current; iterator(std::vector<std::string *>::iterator const ¤t); public: iterator &operator--(); iterator const operator--(int); iterator &operator++(); bool operator==(iterator const &other) const; bool operator!=(iterator const &other) const; int operator-(iterator const &rhs) const; std::string &operator*() const; bool operator<(iterator const &other) const; iterator const operator+(int step) const; iterator const operator-(int step) const; iterator &operator+=(int step); // increment over `n' steps iterator &operator-=(int step); // decrement over `n' steps std::string *operator->() const;// access the fields of the // struct an iterator points // to. E.g., it->length() }; typedef std::reverse_iterator<iterator> reverse_iterator; iterator begin(); iterator end(); reverse_iterator rbegin(); reverse_iterator rend(); };
Let's first have a look at StringPtr::iterator
's characteristics:
iterator
defines StringPtr
as its friend, so iterator
's
constructor can remain private: only the StringPtr
class itself is now
able to construct iterator
s, which seems like a sensible thing to
do. Under the current implementation, copy-constructing remains of course
possible. Furthermore, since an iterator is already provided by
StringPtr
's base class, we can use that iterator to access the information
stored in the StringPtr
object.
StringPtr::begin()
and StringPtr::end()
may simply return
iterator
objects. Their implementations are:
inline StringPtr::iterator StringPtr::begin() { return iterator(this->std::vector<std::string *>::begin()); } inline StringPtr::iterator StringPtr::end() { return iterator(this->std::vector<std::string *>::end()); }
iterator
's remaining members are public. It's very easy to
implement them, mainly manipulating and dereferencing the available iterator
d_current
. A RandomAccessIterator
(which is the most
complex of iterators) requires a series of operators. They usually
have very simple implementations, making them good candidates for
inline-members:
iterator &operator++():
the pre-increment operator:
inline StringPtr::iterator &StringPtr::iterator::operator++() { ++d_current; return *this; }
iterator &
operator
--()
:
the pre-decrement operator:
inline StringPtr::iterator &StringPtr::iterator::operator--() { --d_current; return *this; }
iterator
operator
--()
:
the post-decrement operator:
inline StringPtr::iterator const StringPtr::iterator::operator--(int) { return iterator(d_current--); }
iterator &operator=(iterator const &other):
the overloaded
assignment operator. Since iterator
objects do not allocate
any memory themselves, the default assignment operator will do.
bool operator==(iterator const &rhv) const:
testing the equality
of two iterator
objects:
inline bool StringPtr::iterator::operator==(iterator const &other) const { return d_current == other.d_current; }
bool operator<(iterator const &rhv) const:
tests whether the
left-hand side iterator points to an element of the series located
before the element pointed to by the right-hand side
iterator:
inline bool StringPtr::iterator::operator<(iterator const &other) const { return **d_current < **other.d_current; }
int operator-(iterator const &rhv) const:
returns the number of
elements between the element pointed to by the left-hand side
iterator and the right-hand side iterator (i.e., the value to add
to the left-hand side iterator to make it equal to the value of
the right-hand side iterator):
inline int StringPtr::iterator::operator-(iterator const &rhs) const { return d_current - rhs.d_current; }
Type &operator*() const:
returns a reference to the object to
which the current iterator points. With an InputIterator
and
with all const_iterators
, the return type of this overloaded
operator should be Type const &
. This operator returns a
reference to a string. This string is obtained by dereferencing
the dereferenced d_current
value. As d_current
is an
iterator to string *
elements, two dereference operations are
required to reach the string itself:
inline std::string &StringPtr::iterator::operator*() const { return **d_current; }
iterator const operator+(int stepsize) const:
this operator
advances the current iterator by stepsize
steps:
inline StringPtr::iterator const StringPtr::iterator::operator+(int step) const { return iterator(d_current + step); }
iterator const operator-(int stepsize) const:
this operator
decreases the current iterator by stepsize
steps:
inline StringPtr::iterator const StringPtr::iterator::operator-(int step) const { return iterator(d_current - step); }
std::string *operator->() const
is an additionally added
operator. Here only one dereference operation is required,
returning a pointer to the string, allowing us to access the
members of a string via its pointer.
inline std::string *StringPtr::iterator::operator->() const { return *d_current; }
operator+=()
and
operator-=()
. They are not formally required by
RandomAccessIterators
, but they come in handy anyway:
inline StringPtr::iterator &StringPtr::iterator::operator+=(int step) { d_current += step; return *this; } inline StringPtr::iterator &StringPtr::iterator::operator-=(int step) { d_current -= step; return *this; }
operator+(int step)
can be omitted from the interface. Of course, the tag
to use would then be std::forward_iterator_tag
. The tags (and the set of
required operators) varies accordingly for the other iterator types.
std::iterator
a
std::reverse_iterator
exists, which will nicely implement the reverse iterator for us, once we
have defined an iterator class. Its constructor merely requires an object of
the iterator type for which we want to construct a reverse iterator.
To implement a reverse iterator for StringPtr
, we only need to define
the reverse_iterator
type in its interface. This requires us to specify
only one line of code, which must be inserted after the interface of the class
iterator
:
typedef std::reverse_iterator<iterator> reverse_iterator;Finally, the well known members
rbegin()
and
rend()
are added to
StringPtr
's interface. Again, they can easily be implemented inline:
inline StringPtr::reverse_iterator StringPtr::rbegin() { return reverse_iterator(end()); } inline StringPtr::reverse_iterator StringPtr::rend() { return reverse_iterator(begin()); }
Note the arguments the reverse_iterator
constructors receive: the
begin point of the reversed iterator is obtained by providing
reverse_iterator
's constructor with end()
: the endpoint of the
normal iterator range; the endpoint of the reversed iterator is obtained
by providing reverse_iterator
's constructor with begin()
: the
begin point of the normal iterator range.
The following little program illustrates the use of StringPtr
's
RandomAccessIterator
:
#include <iostream> #include <algorithm> #include "stringptr.h" using namespace std; int main(int argc, char **argv) { StringPtr sp; while (*argv) sp.push_back(new string(*argv++)); sort(sp.begin(), sp.end()); copy(sp.begin(), sp.end(), ostream_iterator<string>(cout, " ")); cout << "\n======\n"; sort(sp.rbegin(), sp.rend()); copy(sp.begin(), sp.end(), ostream_iterator<string>(cout, " ")); cout << endl; } /* when called as: a.out bravo mike charlie zulu quebec generated output: a.out bravo charlie mike quebec zulu ====== zulu quebec mike charlie bravo a.out */Although it is thus possible to construct a reverse iterator from a normal iterator, the opposite does not hold true: it is not possible to initialize a normal iterator from a reverse iterator. Let's assume we would like to process all lines stored in a
vector<string> lines
up to any trailing empty lines (or lines only
containing blanks) it might contain. How would we proceed? One approach is to
start the processing from the first line in the vector, continuing until
the first of the trailing empty lines. However, once we encounter an empty
line it does of course not have to be the first line of the set of trailing
empty lines. In that case, we would like to use the following algorithm:
rit = find_if(lines.rbegin(), lines.rend(), NonEmpty());to obtain a
reverse_iterator rit
pointing to the last non-empty
line.
for_each(lines.begin(), --rit, Process());to process all lines up to the first empty line.
reverse_iterator
? The solution is actually not very difficult, as an
iterator may be initialized by a pointer. The reverse iterator rit
is not
a pointer, but &*(rit - 1)
or &*--rit
is. Thus, we can use
for_each(lines.begin(), &*--rit, Process());to process all the lines up to the first of the set of trailing empty lines. In general, if
rit
is a reverse_iterator
pointing to some
element, but we need an iterator
to point to that element, we may use
&*rit
to initialize the iterator. Here, the dereference operator is
applied to reach the element the reverse iterator refers to. Then the address
operator is applied to obtain its address.