Template function syntax may take one of several forms:
template<typename T>
void f(T t) { ... }
template<class R, class A1, class A2, class A3>
R g(A1 a1, A2& a2, A3&& a3) { ... }
template<typename T>
T h() {
// t ε T defined in function scope
// then returned
}
For the first two forms, calling code provides arguments and the compiler infers the types, compiling
a function for those types. In the second form, function g takes: a1 by value,
a2 by lvalue reference (&), and a3 by rvalue reference (&&).
That second form uses "class" instead of "typename".
Both are valid, but typename is preferred.
Passing by value copies the argument into the function's stackframe. Passing by lvalue
reference creates a reference in the function's stackframe, bound to the argument in the caller's
scope. lvalue references do not bind to non-const temporaries. rvalue references behave like lvalue
references but can bind to temporaries - rvalues - and are most frequently used with move operations.
For the third case, the compiler cannot infer the type from arguments because there are none,
and it does not analyze the body to determine the type. You must supply the type explicitly, as shown
in the last line of code below.
int i{ 3 };
f(i);
double d{ 3.1415927 };
const std::string s = "a demo string";
int j = g<int>(d, s, 'z');
std::string s = h<std::string>();
For the first case, the compiler knows the type of i
and compiles f as if it were defined as:
void f(int i) { ... }
It handles the remaining two cases the same way.
7.2 Overloading Template Functions
Template functions provide generic recipes for their operations. Often that is sufficient
for a program's needs. But some types may not compile or behave correctly with the generic
pattern, requiring a function overload that handles those types correctly.
The code below expands the T max(T t1,T t2) example from Chapter #1
by allowing the two arguments to have different types, which produces some interesting behavior.
Examining the output from the using code:
-
In the first use case, the arguments are 4 and 2, each inferred to be int and the generic
version is compiled for that case.
-
In the second case, the arguments are 3.5, a double, and 2L, a long int. The C++ language
supports comparing a value of double with an integral value, so the generic template is compiled.
-
For the third case the arguments are 3.5 and 4L. When compared, the 4L is promoted to a double
with value 4 and that is returned. Note that the return type is double, not long int. Since
there is only one type for the return value, that is inferred to be the more inclusive type.
-
The fourth case matches the overload, and the C++ language guarantees that if an overload
matches it will be the form compiled.
-
The fifth and last case has arguments of std::string and const char*. That cannot match the
overload, but the generic version works correctly. The string is compared to the const char*
value by promoting the const char* to a std::string using a string constructor, and the two
strings are compared.
The larger value, passed as the const char*, is returned as a std::string.
Using two distinct parameter types allows max to compile in cases that would fail
with both arguments required to be the same type. Only the first and fourth examples compile
for the original T max(T t1, T t2) function.
Returning the result as auto avoids the problem of stating the return type
when either T1 or T2 could be returned.
Template Code
template<typename T1, typename T2>
auto max(T1 t1, T2 t2) {
displayDemo("--- using generic template ---");
return t1 > t2 ? t1 : t2;
}
using pChar = const char*;
auto max(pChar s1, pChar s2) {
displayDemo("--- using overload for const char* ---");
return ((strcmp(s1, s2) > 0) ? s1 : s2);
}
Output
Demonstrate Template Functions
================================
--- using generic template ---
max(4,2) returns 4
the return type of the last statement is: int
--- using generic template ---
max(3.5, 2L) returns 3.5
the return type of the last statement is: double
--- using generic template ---
max(3.5, 4L) returns 4
the return type of the last statement is: double
--- using overload for const char* ---
max("aardvark", "zebra") returns zebra
the return type of the last statement is: char const *
--- using generic template ---
max(std::string("a string"), "b string") returns "b string"
the return type of the last statement is:
class std::basic_string<
char,struct std::char_traits<char>,
class std::allocator<char>
>
Using Code
auto test1 = max(4, 2);
std::cout << "\n max(4,2) returns " << test1;
auto test2 = max(3.5, 2L);
std::cout << "\n max(3.5, 2L) returns " << test2;
std::cout << "\n the return type of the last statement is: ";
std::cout << typeid(test2).name();
auto test3 = max(3.5, 4L);
std::cout << "\n max(3.5, 4L) returns " << test3;
std::cout << "\n the return type of the last statement is: ";
std::cout << typeid(test3).name();
auto test4 = max("aardvark", "zebra");
std::cout << "\n max(\"aardvark\", \"zebra\") returns " << test4;
std::cout << "\n the return type of the last statement is: ";
std::cout << typeid(test4).name();
auto test5 = max(std::string("a string"), "b string");
std::cout << "\n max(std::string(\"a string\"), \"b string\") returns "
<< "\"" << test5 << "\"";
decltype(test5) what;
std::cout << "\n the return type of the last statement is:";
std::cout << "\n " << typeid(what).name();
To understand how template functions work, we examine type categories and type inference - the process
the compiler uses to establish argument types after they pass to template functions.
7.2.1 Type Categories
Before C++11, there were only two type categories, lvalue and rvalue:
-
An lvalue is any named variable - anything for which we can evaluate an address.
The name derives from the fact that lvalues appear on the left side of an assignment:
char ch = 'z';
Here, ch is an lvalue.
-
An rvalue is any entity for which you cannot evaluate an address. It has no name
and is usually a temporary. rvalues can only appear on the right side of an assignment
expression, such as the 'z' of the previous item.
Since C++17, things are somewhat more complicated. rvalues split into xvalues and prvalues:
-
An xvalue is an entity that can serve as the source of a move operation. These are almost
always values of temporary objects created in a function scope and returned by value
syntactically. An xvalue is not copied but moved - its resources transfer to the return target.
-
A prvalue is an expression that defines the initialization of the destination. Under return
value optimization, the prvalue initializes the target instance directly. When rvo does
not apply, the prvalue initializes an xvalue as part of a move operation, provided the
returned object has a move constructor and move assignment operator.
Most implementations do not require thinking about these categories unless you write code that
runs partially at compile time, such as template metaprogramming.
7.2.2 Type Transformations
When passing arguments to functions, template type deduction does not always produce the same type
as the argument in the caller's scope. This is an intentional transformation for performance
or usability, not an inference error.
Non-template functions have only one such transformation, which occurs for array arguments.
When the function's stackframe is built, the compiler creates a pointer in stack memory bound
to the first element of the array, rather than copying the array.
All array access within the function goes through that pointer to the caller's array.
This process is called type decay - the array type decays to a pointer type in the function's scope.
Template functions apply more complicated argument type transformations. The most important are:
-
passing a template parameter by value will strip off constant, volatile, and reference
(cvr) qualifiers
-
lvalue references (T&) can bind only to lvalues and const rvalues. The resulting type
is always an lvalue reference. C++ classifies literal strings as lvalues. All other literals,
e.g., 42 and 3.14159, are classified as rvalues.
-
rvalue references (T&& in a context with no type deduction) can bind only to rvalues.
-
Widget&& w = createWidget();
-
void f(Widget&& w);
-
universal a.k.a. forwarding references (T&& in a context with type deduction) can bind to anything.
-
template<typename T>
void f(T&& t);
-
auto&& x1 = x2;
For the details look here:
Type Transformation Details
This section examines type transformations that occur when passing arguments to functions,
especially template functions. The C++ typeid operator cannot explore these effects - passing
an argument to a template function by value strips its constant, volatile, and reference (cvr)
qualifiers, and typeid is itself a template function that strips the same qualifiers.
The Boost libraries provide a workaround with their boost::typeindex::type_id_with_cvr()
operator1. All type analysis reported below uses that operator.
Table 1. shows that in all non-template cases tested, only the array argument undergoes type decay.
This holds generally - for non-template functions, type decay occurs only with array arguments.
Table 1. - Type of arg in bodies of non-template functions
| arg definition |
f(int arg) |
f(const int* arg) |
f(int arg[3]) |
| int i{ 3 }; |
int |
NA |
NA |
| const int& j = &i; |
int |
NA |
NA |
| const int* pI = &i; |
NA |
int const * |
NA |
| int iarr[4] |
NA |
NA |
int * |
| 42 |
int |
NA |
NA |
Template functions differ. When compiling an instantiated template, the compiler infers
argument types from invocation syntax. That inference follows several rules:
-
Passing an argument by value removes all const, volatile, and reference (cvr) qualifiers.
Array arguments decay to pointers.
-
Passing an argument by lvalue reference (T&) preserves qualifiers, and arrays do not
decay because they will not be copied. An lvalue reference binds only to lvalues or const rvalues.
C++ classifies literal strings as lvalues; all other literals, such as ints and doubles, are rvalues.
-
Passing an argument by pointer preserves qualifiers, but arrays decay because the argument
becomes a pointer.
-
Passing an argument by universal reference (T&& where T is being deduced) preserves qualifiers,
and arrays do not decay. Universal references bind to both lvalues and rvalues.
Table 2. - Type Transformations for template functions
| arg definition |
template<class T>
f1(T arg) |
template<class T>
f2(T& arg) |
template<class T>
f2C(const T& arg) |
template<class T>
f3(T* arg) |
template<class T>
f3C(const T* arg) |
template<class T>
f4(T&& arg) |
int i{ 3 };
lvalue |
T = int |
T& = int & |
const T& = int const & |
NA |
NA |
T&& = int & |
const int& j = &i;
lvalue |
T = int |
T& = int const & |
const T& = int const & |
NA |
NA |
T&& = int const & |
const int* pI = &i;
lvalue |
T = int const * |
T& = int const * & |
const T& = int const * const & |
T* = int const * |
const T* = int const * |
T&& = int const * & |
iarr[4]
lvalue |
T = int * |
T& = int (&)[4] |
const T& = int const (&)[4] |
T* = int * |
const T* = int const * |
T&& = int (&)[4] |
"a string literal"
lvalue |
T = char const * |
T& = char const (&)[17] |
const T& = char const (&)[17] |
T* = const char * |
const T* = char const * |
T&& = char const & * |
42
rvalue |
T = int |
doesn't compile |
const T& = int const & |
NA |
NA |
T&& = int && |
Usually these rules require no attention - inference works as expected.
On rare occasions you may need them to understand unexpected compilation or run-time
behavior of template code.
7.2.3 Substitution Failure Is Not An Error (SFINAE)
When compiling overloaded template functions, type deduction may fail for one or more overloads.
Each deduction involves a substitution into the overload. Substitution failure is not a compile
error - the build succeeds as long as at least one deduction succeeds.
SFINAE Details
The example below provides two function overloads, each displaying the contents of a collection.
The first shows array contents; the second shows vector contents.
The Using Code main has three cases:
-
First case: no SFINAE -
show(array)
The array matches both overloads, but show(const T (&array)[N]) is a more
specific match and is compiled.
-
Second case: SFINAE with build success -
show(vInt)
vInt fails to match show(const T (&array)[N]) but does match
show(const CÁ cont) and is compiled. SFINAE prevents the
substitution failure from causing a compile error.
-
Third case: SFINAE with build failure not due to substitution -
show(3.14159)
Substitution of 3.14159 into the first overload fails but is not a compile
error. Substitution into the second overload succeeds, but the body fails to compile
since a double does not satisfy the requirements of a range-based for loop.
SFINAE Code
#include <iostream>
#include <vector>
#include "../Display/Display.h"
template<typename T, size_t N>
void show(const T (&array)[N]) {
displayDemo("--- show array contents ---");
std::cout << "\n ";
for (size_t i = 0; i < N; ++i)
std::cout << array[i] << " ";
}
template<typename C>
void show(const C& cont) {
displayDemo("--- show container contents ---");
std::cout << "\n ";
for (auto item : cont) {
std::cout << item << " ";
}
}
Using Code
int main() {
displayTitle("SFINAE Demo");
std::cout << "\n displaying array:";
double array[5]{ -0.5, 0.0, 0.5, 1.0, 1.5 };
show(array);
std::cout << "\n displaying vector";
std::vector<int> vInt{ -1, 0, 1, 2, 3 };
show(vInt);
// show(array);
// attempted template argument deduction for both show functions
// - show(const T (&array)[n]) succeeded, built, and used
// - show(const C& cont) succeeded but less specific so not used
// show(vInt)
// attempted template argument deduction for both show functions
// - show(const T (&array)[n]) failed, vInt is not an array,
// but this is not a compilation error (SFINAE)
// - show(const C& cont) succeeded, built, and used
// show(3.14159);
// argument deduction for show(const T (&array)[N]) fails
// - double is not an array
// argument deduction succeeds with show(const C& cont)
// - compilation of body for double fails, i.e.,
// no iterator, begin(), or end() for range-based for
std::cout << "\n\n";
}
Output
SFINAE Demo
=============
displaying array:
--- show array contents ---
-0.5 0 0.5 1 1.5
displaying vector
--- show container contents ---
-1 0 1 2 3
The key point is that function code can work for some types but not others, as long as another
overload succeeds in type deduction and provides working code for all types the program uses
in that set of invocations.
SFINAE for template classes is covered in the next chapter - Template Metaprogramming.
7.3 Template Function Examples
Several standard template functions prove useful, especially for template metaprogramming:
Table 1. - Standard Template Functions
| Function name |
Return Type |
Semantics |
| std::move(T& t) |
static_cast<typename std::remove_reference<T>::type&&(t) |
Casts t to an r value type, e.g., can be moved from. Nothing is actually moved.
|
| std::forward(T&& t) |
type of t in the caller's context |
Used in a function to un-decay T's type1.
Revert back to caller's value category (rvalue or lvalue).
This is a cast operation. Nothing is actually forwarded.
|
| std::apply<F&& f, Tuple&& t> |
value returned by f |
Use tuple items as arguments of function f. The t argument may be a std::tuple, std::array, or
std::pair.
|
| std::invoke(F&& f, Args&&... args) |
std::Invoke_Result_t<F, Args...> |
Invoke the callable object f with parameters Args.
|
This next table holds type traits that are often associated with the standard functions cited in the
previous table.
Table 2. - Selected type_traits
| type_trait |
Semantics |
| template<class T> struct decay |
decay has a public member type which converts T to the decayed type that results from making a call
f(T t) inside the scope of f. That is, decay<T>::type is the decayed type.
|
| template<class T> struct remove_reference |
remove_reference::type evaluates as T with a reference removed if T is a reference type, otherwise
evaluates as T.
|
Next are some example template function designs. The first two come from the
CppUtilities repository.
Converter<T>::toString(t), in the CodeUtilities folder, converts a value of t ε T
to its string representation.
Given the conversion string, ConvStr, Converter<T>::toValue(ConvStr)
converts back to a new instance with the original value.
Converter Example
Converter function
///////////////////////////////////////////////////////
// Converter class
// - supports converting unspecified types to and
// from strings
// - type is convertible if it provides insertion
// and extraction operators
template <typename T>
class Converter
{
public:
static std::string toString(const T& t);
static T toValue(const std::string& src);
};
//----< convert t to a string >------------------
template <typename T>
std::string Converter<T>::toString(const T& t) {
std::ostringstream out;
out << t;
return out.str();
}
//----< convert a string to an instance of T >---
/*
* - the string must have been generated by
* Converter<T>::toString(const T& t)
* - T::operator>> must be the inverse of T::operator<<
*/
template<typename T>
T Converter<T>::toValue(const std::string& src) {
std::istringstream in(src);
T t;
in >> t;
return t;
}
Using Code
title("test std::string Converter<T>::toString(T)");
std::string conv1 = Converter<double>::toString(3.1415927);
std::string conv2 = Converter<int>::toString(73);
std::string conv3 =
Converter<std::string>::toString("a_test_string plus more");
std::cout << "\n Converting from values to strings: ";
std::cout << conv1 << ", " << conv2
<< ", " << conv3;
putline();
title("test T Converter<T>::toValue(std::string)");
std::cout << "\n Converting from strings to values: ";
std::cout << Converter<double>::toValue(conv1) << ", ";
std::cout << Converter<int>::toValue(conv2) << ", ";
std::cout << Converter<std::string>::toValue(conv3);
Output
test std::string Converter<T>::toString(T)
--------------------------------------------
Converting from values to strings:
3.14159, 73, a_test_string plus more
test T Converter<T>::toValue(std::string)
-------------------------------------------
Converting from strings to values:
3.14159, 73, a_test_string
Converter works simply because it uses std::ostringstream to convert
values to string representation, and std::istringstream to convert back.
The std::stringstream library classes do all the work.
The second example, in the StringUtilities folder, presents string utility functions
trim and split with capabilities similar to those in the C# string class.
String Utilities
String Utilities Code
/*
- remove whitespace from front and back of string argument
- does not remove newlines
*/
template <typename T>
inline std::basic_string<T> trim(
const std::basic_string<T>& toTrim
) {
if (toTrim.size() == 0)
return toTrim;
std::basic_string<T> temp;
std::locale loc;
typename std::basic_string<T>::const_iterator iter =
toTrim.begin();
while (isspace(*iter, loc) && *iter != '\n')
{
if (++iter == toTrim.end())
{
break;
}
}
for (; iter != toTrim.end(); ++iter)
{
temp += *iter;
}
typename std::basic_string<T>::reverse_iterator riter;
size_t pos = temp.size();
for (riter = temp.rbegin(); riter != temp.rend(); ++riter)
{
--pos;
if (!isspace(*riter, loc) || *riter == '\n')
{
break;
}
}
if (0 <= pos && pos < temp.size())
temp.erase(++pos);
return temp;
}
/*---
split sentinel separated strings into vector of trimmed strings
---*/
template <typename T>
inline std::vector<std::basic_string<T>> split(
const std::basic_string<T>& toSplit, T splitOn = ','
) {
std::vector<std::basic_string<T>> splits;
std::basic_string<T> temp;
typename std::basic_string<T>::const_iterator iter;
for (iter = toSplit.begin(); iter != toSplit.end(); ++iter)
{
if (*iter != splitOn)
{
temp += *iter;
}
else
{
splits.push_back(trim(temp));
temp.clear();
}
}
if (temp.length() > 0)
splits.push_back(trim(temp));
return splits;
}
/*--- show collection of string splits ----------------------*/
template <typename T>
inline void showSplits(
const std::vector<std::basic_string<T>>& splits,
std::ostream& out = std::cout
) {
out << "\n";
for (auto item : splits)
{
if (item == "\n")
out << "\n--" << "newline";
else
out << "\n--" << item;
}
out << "\n";
}
Using Code
#include <cctype>
#include <iostream>
#include "StringUtilities.h"
#include "../CodeUtilities/CodeUtilities.h"
#ifdef TEST_STRINGUTILITIES
using namespace Utilities;
int main()
{
Title("Testing Utilities Package");
putline();
title("test split(std::string, ',')");
std::string test =
"a, \n, bc, de, efg, i, j k lm nopq rst";
std::cout << "\n test string = "
<< test;
std::vector<std::string> result =
split(test);
showSplits(result);
title("test split(std::string, ' ')");
std::cout << "\n test string = "
<< test;
result = split(test, ' ');
showSplits(result);
putline(2);
return 0;
}
#endif
Output
Testing Utilities Package
===========================
test split(std::string, ',')
------------------------------
test string = a,
, bc, de, efg, i, j k lm nopq rst
--a
--newline
--bc
--de
--efg
--i
--j k lm nopq rst
test split(std::string, ' ')
------------------------------
test string = a,
, bc, de, efg, i, j k lm nopq rst
--a,
--
,
--bc,
--de,
--efg,
--i,
--j
--k
--lm
--nopq
--rst
The last template function example shows how to create
generic lambdas.
They use auto parameters, as shown, equivalent to a template function without template syntax.
The auto declarators generate the type deduction that makes them generic.
Generic Lambda Code
Generic Lambda Code
auto genericLambda = [](auto arg) {
std::cout << "\n the type of genericLambda's arg is: "
<< typeid(arg).name();
std::cout << "\n arg's value is: " << arg;
};
Using Code
displaySubtitle("Demo generic lambda");
genericLambda(double{ 3.5 });
genericLambda("this is a string");
Output
Demo generic lambda
---------------------
the type of genericLambda's arg is: double
arg's value is: 3.5
the type of genericLambda's arg is: char const *
arg's value is: this is a string
Template functions appear again in Chapter #7 - Template Metaprogramming, which explores
functions used to provide displays for code demonstrations throughout this story.
7.4 Template Classes
Template classes use the syntax shown in the blocks below. Wherever the class name SynDemo
appears as a type, it requires the template parameter, e.g., SynDemo<T>.
Both template declarations and
definitions must appear in the class's header file, as shown below.
The included file display.h is found here.
Template Code in SynDemo.h
namespace Chap6 {
template<typename T>
class SynDemo {
public:
void value(T t);
T value();
private:
T t_;
};
template<typename T>
void SynDemo<T>::value(T t) {
t_ = t;
}
template<typename T>
T SynDemo<T>::value() {
return t_;
}
}
Using Code in Demo.cpp
#include <iostream>
#include <string>
#include "../Display/Display.h"
#include "SynDemo.h"
int main() {
displayTitle("Demonstrating Template Syntax");
using namespace Chap6;
SynDemo<std::string> sd;
sd.value("hello world");
std::cout << "\n " << sd.value();
putline(2);
}
Output
Demonstrating Template Syntax
===============================
hello world
The two-phase compilation model for C++ templates requires placing all method implementations
in the header file.
7.4.1 Stack<T> Class Example
The Stack<T> class example below illustrates this syntax
for professionally developed code. It also demonstrates:
-
Template members:
A copy constructor template <class U> stack(const stack<U>&); and
assignment operator
template <class U> stack<T>& operator=(const stack<U>&);
are declared as methods with a potentially different type U. That could be
the same as T, providing the usual copy and assignment, or different, allowing
assignment of a stack<int> to a stack<double>, for example.
The example code demonstrates that use. Template type inference enables this flexibility.
-
Inner classes:
Inner classes rarely appear in C++ programs, but when a parent class needs a small,
specialized helper class, using an inner class makes sense.
The struct stacknode is such an example.
-
Friend relationships:
Friend relationships expand encapsulation from the granting class to its friends,
so use them sparingly. When needed, they are straightforward to apply, as shown here.
This stack<T> class grants friend access to its template members so they
can access private data - necessary because stack<T> and
stack<U> are different classes.
This example was adapted from one presented in Effective C++, by Scott Meyers.
Stack Class
Stack Code
template<class T> class stack {
template <class U> friend class stack;
private:
struct stacknode {
T data;
stacknode *next;
stacknode(
const T& newdata, stacknode *nextnode
) : data(newdata), next(nextnode) { }
};
stacknode *top;
public:
stack();
~stack();
void push(const T& object);
T pop(void);
void flush();
int size() const;
// member templates
template <class U> stack(
const stack<U>&
);
template <class U>
stack<T>& operator=(
const stack<U>&
);
};
//----< void constructor >-------------
template<class T>
stack<T>::stack() : top(0) { }
//----< destructor >-------------------
template <class T>
stack<T>::~stack(void) {
while (top) {
stacknode *next_to_die = top;
top = top->next;
delete next_to_die;
}
}
//----< push data onto stack >---------
template<class T>
void stack<T>::push(const T &object) {
top = new stacknode(object, top);
}
//----< pop data from stack >----------
template <class T>
T stack<T>::pop(void) {
if (!top) {
throw std::out_of_range(
"\n attempt to pop empty stack\n"
);
}
stacknode *save = top;
top = top->next;
T data = save->data;
delete save;
return data;
}
//----< empty stack >------------------
template <class T>
void stack<T>::flush() {
stacknode* node = top;
while(node)
{
stacknode *next_to_die = node;
node = node->next;
delete next_to_die;
}
}
//---< number of elements on stack >---
template <class T>
int stack<T>::size() const {
stacknode* node = top;
int count = 0;
while(node)
{
count++;
node = node->next;
}
return count;
}
//--< copy and promo ctor, a member template >--
template <class T>
template <class U>
stack<T>::stack(
const stack<U>& s
) : top(0)
{
stack<U>::stacknode* node =
const_cast<stack<U>::stacknode*>(s.top);
while(node)
{
this->push(node->data);
node = node->next;
}
}
//--< assignment from stack of compatible type >--
template <class T>
template <class U>
stack<T>&
stack<T>::operator=(const stack<U>& s)
{
if((void*)this == (void*)&s)
return *this;
flush();
stack<U>::stacknode* node2 =
const_cast<stack<U>::stacknode*>(s.top);
while(node2)
{
this->push(static_cast<T>(node2->data));
node2 = node2->next;
}
return *this;
}
Using Code
#include <iostream>
#include "stack.h"
using namespace std;
template <class T> void print_field(T t) {
cout.width(10);
cout << t;
}
//----< test stub >--------------------
void main() {
cout <<
"\nTesting Template Based Stack Class\n";
try
{
stack<int> int_stack;
stack<double> double_stack;
int x=1, y=2, z=3;
double u=-1.5, v=0.5, w=2.5;
cout << "\n pushing stack: ";
print_field(x); int_stack.push(x);
cout << "\n pushing stack: ";
print_field(y); int_stack.push(y);
cout << "\n pushing stack: ";
print_field(z); int_stack.push(z);
cout << endl;
cout << "\n stack size = "
<< int_stack.size()
<< endl;
stack<double> copyStack = int_stack;
// copy construction with data conversion
cout << "\n popping stack: ";
print_field(int_stack.pop());
cout << "\n popping stack: ";
print_field(int_stack.pop());
cout << "\n popping stack: ";
print_field(int_stack.pop());
cout << "\n";
cout << "\n stack size = "
<< int_stack.size()
<< endl;
cout <<
"\n popping double copy of int stack:";
cout << "\n popping stack: ";
print_field(copyStack.pop());
cout << "\n popping stack: ";
print_field(copyStack.pop());
cout << "\n popping stack: ";
print_field(copyStack.pop());
cout << "\n";
cout << "\n pushing stack: ";
print_field(u); double_stack.push(u);
cout << "\n pushing stack: ";
print_field(v); double_stack.push(v);
cout << "\n pushing stack: ";
print_field(w); double_stack.push(w);
cout << endl;
stack<int> int2_stack;
int2_stack = double_stack;
// assignment with data conversion
cout << "\n popping stack: ";
print_field(double_stack.pop());
cout << "\n popping stack: ";
print_field(double_stack.pop());
cout << "\n popping stack: ";
print_field(double_stack.pop());
cout << "\n";
cout <<
"\n popping int copy of double stack:";
cout << "\n popping stack: ";
print_field(int2_stack.pop());
cout << "\n popping stack: ";
print_field(int2_stack.pop());
cout << "\n popping stack: ";
print_field(int2_stack.pop());
cout << "\n";
int2_stack.pop(); // popping empty stack
cout << "\n\n";
}
catch(exception& ex)
{
cout << "\n " << ex.what()
<< endl;
}
catch(...)
{
cout << "\n stack error\n\n";
}
}
Output
Testing Template Based Stack Class
pushing stack: 1
pushing stack: 2
pushing stack: 3
stack size = 3
popping stack: 3
popping stack: 2
popping stack: 1
stack size = 0
popping double copy of int stack:
popping stack: 1
popping stack: 2
popping stack: 3
pushing stack: -1.5
pushing stack: 0.5
pushing stack: 2.5
popping stack: 2.5
popping stack: 0.5
popping stack: -1.5
popping int copy of double stack:
popping stack: -1
popping stack: 0
popping stack: 2
attempt to pop empty stack
You will not use this class in your own designs. The Standard Template Library (STL) provides
a stack adapter class1, which all C++ developers know how to use.
The STL offers a rich set of template class examples, one for each STL container.
Demonstrations of each appear in
STL-Containers.html in the Demonstrations section of
CppRepositories.html.
7.4.2 Directory Explorer Example
The next example, DirExplorerT, shows how to build a reusable directory navigator
component - one that works in many different applications without changing its code.
It achieves reusability by parameterizing the navigator on an application-specific class,
DirExplorerT<App>.
The application class must provide methods doFile(const std::string& fileName)
and doDir(const std::string& dirName) to handle all application-specific
requirements for file and directory information.
DirExplorerT
Code: DirExplorerT
#include <vector>
#include "../FileSystem/FileSystem.h"
namespace FileSystem
{
template<typename App>
class DirExplorerT
{
public:
using patterns = std::vector<std::string>;
static std::string version() { return "ver 1.2"; }
DirExplorerT(const std::string& path);
void addPattern(const std::string& patt);
void hideEmptyDirectories(bool hide);
void maxItems(size_t numFiles);
void showAllInCurrDir(bool showAllCurrDirFiles);
bool showAllInCurrDir();
void recurse(bool doRecurse = true);
void search();
void find(const std::string& path);
bool done();
void showStats();
size_t fileCount();
size_t dirCount();
private:
App app_;
std::string path_;
patterns patterns_;
bool hideEmptyDir_ = false;
bool showAll_ = false;
// show files in current dir
// even if maxItems_ exceeded
size_t maxItems_ = 0;
size_t dirCount_ = 0;
size_t fileCount_ = 0;
bool recurse_ = false;
};
//---< ctor using default pattern >--
template<typename App>
DirExplorerT<App>::DirExplorerT(
const std::string& path
) : path_(path)
{
patterns_.push_back("*.*");
}
//---< add patts selecting files >---
template<typename App>
void DirExplorerT<App>::addPattern(
const std::string& patt
)
{
if (
patterns_.size() == 1
&& patterns_[0] == "*.*"
)
patterns_.pop_back();
patterns_.push_back(patt);
}
//---< option to hide empty dirs >---
template<typename App>
void DirExplorerT<App>
::hideEmptyDirectories(bool hide)
{
hideEmptyDir_ = hide;
}
//---< max num files to display >----
template<typename App>
void DirExplorerT<App>::maxItems(
size_t numFiles
)
{
maxItems_ = numFiles;
app_.maxItems(maxItems_);
}
//---< show all files in dir >-------
template<typename App>
void DirExplorerT<App>::showAllInCurrDir(
bool showAllCurrDirFiles
)
{
showAll_ = showAllCurrDirFiles;
}
//---< show all files in dir? >------
template<typename App>
bool DirExplorerT<App>::showAllInCurrDir()
{
return showAll_;
}
//---< recusively walk dir tree >--
template<typename App>
void DirExplorerT<App>::recurse(bool doRecurse)
{
recurse_ = doRecurse;
}
//---< start at path_ >------------
template<typename App>
void DirExplorerT<App>::search()
{
if (showAllInCurrDir())
app_.showAllInCurrDir(true);
find(path_);
}
//---< search directories >----------
/*
Recursively find all dirs and files on
specified path, executing doDir when
entering a directory and doFile when
finding a file
*/
template<typename App>
void DirExplorerT<App>::find(
const std::string& path
)
{
if (done()) // stop searching
return;
bool hasFiles = false;
std::string fpath =
FileSystem::Path::getFullFileSpec(path);
if (!hideEmptyDir_)
app_.doDir(fpath);
for (auto patt : patterns_)
{
std::vector<std::string> files =
FileSystem::Directory::getFiles(fpath, patt);
if (!hasFiles && hideEmptyDir_)
{
if (files.size() > 0)
{
app_.doDir(fpath);
hasFiles = true;
}
}
for (auto f : files)
{
app_.doFile(f);
}
}
if (done()) // stop recursion
return;
std::vector<std::string> dirs =
FileSystem::Directory::getDirectories(fpath);
for (auto d : dirs)
{
if (d == "." || d == "..")
continue;
std::string dpath = fpath + "\\" + d;
if (recurse_)
{
find(dpath);
}
else
{
app_.doDir(dpath);
}
}
}
//---< num files processed >---------
template<typename App>
size_t DirExplorerT<App>::fileCount()
{
return App.fileCount();
}
//---< num dirs processed >----------
template<typename App>
size_t DirExplorerT<App>::dirCount()
{
return App.dirCount();
}
//---< counts for files & dirs >-----
template<typename App>
void DirExplorerT<App>::showStats()
{
app_.showStats();
}
template<typename App>
bool DirExplorerT<App>::done()
{
return app_.done();
}
}
Code: Application.h
#include <iostream>
#include <string>
class Application
{
public:
Application();
// App defines handling files and dirs,
// when to quit, and how to display final
// results.
// None of this requires alteration of
// DirExplorerT's code.
void doFile(
const std::string& filename
);
void doDir(
const std::string& dirname
);
size_t fileCount();
size_t dirCount();
bool done();
void showStats();
// configure application options
void showAllInCurrDir(
bool showAllFilesInCurrDir
);
bool showAllInCurrDir();
void maxItems(size_t maxItems);
private:
size_t fileCount_ = 0;
size_t dirCount_ = 0;
size_t maxItems_ = 0;
bool showAll_ = false;
};
inline Application::Application()
{
std::cout
<< "\n Using App methods "
<< doFile and doDir\n";
}
inline void Application::doFile(
const std::string& filename
)
{
++fileCount_;
if(showAll_ || !done())
{
std::cout << "\n file--> "
<< filename;
}
}
inline void Application::doDir(
const std::string& dirname
)
{
++dirCount_;
std::cout << "\n dir---> "
<< dirname;
}
inline size_t Application::fileCount()
{
return fileCount_;
}
inline size_t Application::dirCount()
{
return dirCount_;
}
inline void Application::showAllInCurrDir(
bool showAllFilesInCurrDir
)
{
showAll_ = showAllFilesInCurrDir;
}
inline bool Application::showAllInCurrDir()
{
return showAll_;
}
inline void Application::maxItems(
size_t maxItems
)
{
maxItems_ = maxItems;
}
//---< counts for files and dirs >-----
inline void Application::showStats()
{
std::cout << "\n\n processed "
<< fileCount_
<< " files in "
<< dirCount_
<< " directories";
if(done())
{
std::cout <<
"\n stopped - max num files exceeded";
}
}
inline bool Application::done()
{
return (
0 < maxItems_
&& maxItems_
< fileCount_
);
}
Using Code
#include "DirExplorerT.h"
#include "Application.h"
#include "../StringUtilities/StringUtilities.h"
#include "../CodeUtilities/CodeUtilities.h"
#include <iostream>
#include <string>
using namespace Utilities;
using namespace FileSystem;
std::string customUsage()
{
/* code elided */
return usage;
}
int main(int argc, char *argv[])
{
Title("Demonstrate DirExplorer-Template");
ProcessCmdLine pcl(argc, argv);
pcl.usage(customUsage());
preface("Command Line: ");
pcl.showParse();
putline();
if (pcl.parseError())
{
pcl.usage();
std::cout << "\n\n";
return 1;
}
DirExplorerT<Application>
de(pcl.path());
for (auto patt : pcl.patterns())
{
de.addPattern(patt);
}
if (pcl.hasOption('s'))
{
de.recurse();
}
if (pcl.hasOption('h'))
{
de.hideEmptyDirectories(true);
}
if (pcl.hasOption('a'))
{
de.showAllInCurrDir(true);
}
if (pcl.maxItems() > 0)
{
de.maxItems(pcl.maxItems());
}
de.search();
de.showStats();
std::cout << "\n\n";
return 0;
}
Output
Demonstrate DirExplorer-Template
==================================
Command Line:
Path: .
options:
patterns:
Regex: .*
Using Application methods doFile and doDir
dir---> C:\github\JimFawcett\CppUtilities...
file--> Application.cpp
file--> Application.h
file--> Application1.cpp.html
file--> Application1.h.html
file--> DirExplorer-Template-classes.gliffy
file--> DirExplorer-Template-classes.jpg
file--> DirExplorer-Template.jpg
file--> DirExplorer-Template.vcxproj
file--> DirExplorer-Template.vcxproj.filters
file--> DirExplorer-Template.vcxproj.user
file--> DirExplorerT.cpp
file--> DirExplorerT.h
file--> DirExplorerT1.cpp.html
file--> DirExplorerT1.h.html
dir---> C:\github\JimFawcett\CppUtilities...
processed 14 files in 2 directories
DirExplorerT contains substantial code, but studying it reveals a powerful method
for building flexible, reusable components.
7.5 Template Parameters
Template parameters may be:
-
Type Parameters:
typename TypeName [= defaultTypeName]
TypeName is a formal parameter that represents an unspecified struct or class;
defaultTypeName is the name of a class or struct.
Example: template<typename X=std::string> class Y { ... };
-
Template type parameters:
typename TypeName, template<class TypeName> class TemplateTypeName
TemplateTypeName is a formal parameter that represents an unspecified template struct or class
Example: template<typename C, template <class C> class X> class Y { ... };
This specifies that X is a template class that has the parameter C,
e.g., the second parameter X is templated on the first parameter C.
-
Value parameters:
Type [= value]
Example: size_t N = 10
template<size_t N=10> class Array { ... };
This specifies that the templated class uses N with value 10 unless
specified otherwise.
Type parameters may hold processing that customizes a template
class's behavior for specific applications.
They also define application-specific data structures.
Applications often define type parameters for unique processing to use with an existing
template class framework.
Template type parameters are themselves templates. The Template
Functors example below uses a functor, X<C>, parameterized on C
- the type of an STL container - in a traversal function that operates on all container members.
Value parameters are values rather than classes.
The std::Array<T,N> class
uses value parameter N to define the number of elements it holds.
The Template Functors code example below contains a global function Traverse
defined with template parameter C and
template template parameter X<C>:
template <class C, template <class C> class X>
void tranverse(
typename C::iterator& Begin, typename C::iterator& End,
X<C>& x,
void(X<C>::*fptr)(typename C::iterator&)
) {
...
}
where C represents an STL container and X is a function
object that operates on C in a way specified by the application defining
X<C>.
Template Functors
Template Functor Code
///////////////////////////////////////////////////////////////
// FunctorsEtc.cpp - Demonstrate Functors, Function Pointers //
// with template arguments //
// //
// Jim Fawcett, CSE67 - Object Oriented Design, Spring 2009 //
///////////////////////////////////////////////////////////////
#include <iterator>
#include <string>
// Functor interface, to support substitutability
template <typename C>
struct IFunctor
{
virtual void operator()(typename C::iterator& iter)=0;
};
// Global funct accepts iterators & base functor reference,
// templatized on a container argument.
template <typename C>
void Traverse(
typename C::iterator& Begin, typename C::iterator& End,
IFunctor<C>& funct
)
{
C::iterator iter;
for(iter=Begin; iter!=End; ++iter)
funct(iter);
}
// Global funct accepts iterators & member function pointer
// templatized on a container argument
template <class C, template <class C> class X>
void Traverse(
typename C::iterator& Begin,
typename C::iterator& End,
X<C>& x,
void(X<C>::*fptr)(typename C::iterator&)
)
{
C::iterator iter;
for(iter=Begin; iter!=End; ++iter)
{
(x.*fptr)(iter);
}
}
Using Code
#include <string>
#include <iostream>
// one possible operation to apply to some container
class aFunctor : public IFunctor<std::string>
{
void operator()(std::string::iterator& iter)
{
// seperate each char with space
std::cout << *iter << " ";
}
};
// template class has member function we will point to
template <typename C>
class X
{
public:
void doOp(typename C::iterator& iter)
{
std::cout << *iter << " ";
}
};
// alias for template function pointer to member
typedef void (X<std::string>::*fptr)(
std::string::iterator&
);
void main()
{
std::string test =
"CSE687 - Object Oriented Design";
// testing functor
aFunctor func;
std::cout << "\n ";
Traverse(test.begin(), test.end(), func);
// testing function pointer to member
std::cout << "\n ";
X<std::string> x;
fptr f = &X<std::string>::doOp;
Traverse<std::string>(
test.begin(), test.end(), x, f
);
// this syntax works too
std::cout << "\n ";
Traverse<std::string>(
test.begin(), test.end(),
x, &X<std::string>::doOp
);
std::cout << "\n\n";
}
Output
C S E 6 8 7 - O b j e c t O r i e n t e d D e s i g n
C S E 6 8 7 - O b j e c t O r i e n t e d D e s i g n
C S E 6 8 7 - O b j e c t O r i e n t e d D e s i g n
Section 6.6 discusses template class specialization - a mechanism for providing both a generic
implementation pattern and alternate implementations for special cases where the generic
pattern performs poorly.
7.6 Template Class Specialization
Templates define classes configured with subordinate classes. The code block below configures
class X to use helper classes P and Q.
Each application chooses which helpers to use or implements application-specific helpers.
Template specialization adds another degree of design freedom.
Specialization defines a template class with one or more template arguments, then provides
additional classes with the same name but with at least one argument specialized.
The code below specializes X<P,Q> for cases:
X<P,Q1>, X<P1,Q>, and X<P1,Q1>. Each
specialization provides its own class implementation, differing in ways required for those
specific cases. These are distinct classes. When compiling a template class, the compiler
searches for specializations and compiles a matching one when found.
The code block below illustrates template specialization syntax. The logger example that
follows demonstrates specialization in a practical application.
Template Class
/*----------------------------------------
Classes P0, P1,Q0, and Q1 defined
before this code.
*/
/*-----------------------------------------
Class used for generic operations
*/
template<typename P = P0, typename Q = Q0>
class X {
public:
X() {
std::cout << "\n Generic X Template";
}
void doProc() {
p_.doProc();
q_.doProc();
}
private:
P p_;
Q q_;
};
/*-----------------------------------------
Class specialized to use Q1
*/
template<typename P>
class X<P, Q1> {
public:
X() {
std::cout <<
"\n X partially specialized for Q1";
}
void doProc() {
p_.doProc();
q_.doProc();
}
private:
P p_;
Q1 q_;
};
/*-----------------------------------------
Class specialized to use P1
*/
template<typename Q>
class X<P1, Q> {
public:
X() {
std::cout <<
"\n X partially specialized for P1";
}
void doProc() {
p_.doProc();
q_.doProc();
}
private:
P1 p_;
Q q_;
};
/*-----------------------------------------
Class fully specialized to use P1 and Q1
*/
template<>
class X<P1, Q1> {
public:
X() {
std::cout <<
"\n X fully specialized for P1 & Q1";
}
void doProc() {
p_.doProc();
q_.doProc();
}
private:
P1 p_;
Q1 q_;
};
Using Code:
int main() {
displayDemo("-- generic processing --");
X<P0, Q0> x1;
x1.doProc();
displayDemo(
"\n -- using default template args --"
);
X<> x2;
x2.doProc();
displayDemo(
"\n -- Using full specializ'n --"
);
X<P1, Q1> x3;
x3.doProc();
displayDemo(
"\n -- Using specializ'n for P1 --"
);
X<P1, Q0> x4;
x4.doProc();
displayDemo(
"\n -- Using specializ'n for Q1 --"
);
X<P0, Q1> x5;
x5.doProc();
putline(2);
}
Output
-- generic processing --
Generic X Template
doing P0 processing
doing Q0 processing
-- using default template args --
Generic X Template
doing P0 processing
doing Q0 processing
-- Using full specializ'n --
X fully specialized for P1 & Q1
doing P1 processing
doing Q1 processing
-- Using specializ'n for P1 --
X partially specialized for P1
doing P1 processing
doing Q0 processing
-- Using specializ'n for Q1 --
X partially specialized for Q1
doing P0 processing
doing Q1 processing
Template specialization provides a generic class for common needs.
Each specialization replaces the generic class for a specific case - a specific parameter type
at instantiation. You may add as many specializations as needed.
The logger example below is simpler than the one above. It illustrates template specialization,
using it to provide:
-
A generic logger class, Logger<S, F, T>, that describes Logger structure.
It is not intended for direct use but provides the layout for template arguments.
S is a text-based message, F is a message formatter, and T is a timer.
-
An unadorned logger, Logger<S, FNull, TNull>, that writes text to a specified stream.
The first argument, S, is usually a std::string but can be a structured message.
FNull provides a no-op formatter, and TNull provides a no-op timer.
-
A partial specialization on F for application-specific formatting. This parameter is
itself a template, F<S>, allowing F to handle different message types.
-
A partial specialization on T, to provide elapsed time annotations on each message.
This example deviates from the usual pattern: the generic class serves only as a framework
for subsequent specializations, so every template the application instantiates is a specialization.
This design style is less common than providing a working generic class, but is sometimes easier
to build.
Simplified Logger illustrates specialization
Code: Specialized Logger
struct TNull {};
template<typename S>
struct FNull {};
template<
typename S,
template<typename S> typename F = FNull,
typename T = TNull
>
class Logger {
/*-- used for specializ'n structure --*/
};
/*---------------------------------------
unadorned Logger
---------------------------------------*/
template<typename S>
class Logger<S, FNull, TNull> {
public:
Logger(std::ostream* pStr) : pStream_(pStr) {}
~Logger() {}
void write(S s) {
(*pStream_) << prefix_ << s;
}
private:
std::string prefix_ = "\n ";
std::ostream* pStream_;
};
/*---------------------------------------
template class partial specialization
on Formatter class
- this is partial class specialization
since S and F are still unspecified
---------------------------------------*/
template<typename S>
struct Formatter {
const char* prefix_ = "\n <-- ";
const char* suffix_ = " -->";
std::string transform(const S& s) {
return prefix_ + s + suffix_;
}
};
template<
typename S,
template<typename S> typename F
>
class Logger<S, F, TNull> {
public:
Logger(std::ostream* pStr) : pStream_(pStr) {}
~Logger() {}
void write(S s) {
(*pStream_) << f.transform(s);
}
private:
std::string prefix_ = "\n ";
std::ostream* pStream_;
F<S> f;
};
/*---------------------------------------
template class partial specialization
on Timer class
- See Timer.h for details
---------------------------------------*/
template<typename S, typename T>
class Logger<S, FNull, T> {
public:
Logger(std::ostream* pStr) : pStream_(pStr) {}
~Logger() {
timer_.stop();
}
void start() {
timer_.start();
}
void stop() {
timer_.stop();
}
void write(S s) {
(*pStream_)
<< prefix_ << std::setw(6)
<< timer_.elapsedMicroseconds()
<< " microsec : " << s;
}
private:
std::string prefix_ = "\n ";
T timer_;
std::ostream* pStream_;
};
Using Code
int main() {
displayTitle("Demonstrate Logger Specializ'n");
displayDemo("--- Unadorned Logger ---\n");
/* using defaults F=FNull, T=TNull */
Logger<std::string> log(&std::cout);
log.write("first log item");
log.write("second log item");
displayDemo(
"\n -- Specializ'n for format logs --\n"
);
/* using default T = TNull */
Logger<std::string, Formatter>
flog(&std::cout);
flog.write("first formatted log item");
flog.write("second formatted log item");
displayDemo(
"\n -- Specializ'n for timed logs --\n"
);
/* cite FNull because defaults only at end */
Logger<std::string, FNull, Timer>
tlog(&std::cout);
tlog.start();
tlog.write("first timed log item");
tlog.write("second timed log item");
tlog.write("third timed log item");
std::cout << "\n\n";
}
Output
Demonstrate Logger Specializ'n
================================
--- Unadorned Logger ---
first log item
second log item
--- Specializ'n for format logs ---
<-- first formatted log item -->
<-- second formatted log item -->
--- Specializ'n for timed logs ---
41 microsec : first timed log item
482 microsec : second timed log item
790 microsec : third timed log item
A more complete implementation would also provide a full specialization for both
formatting and timing.
This concludes the discussion of templates, overloading, and specialization. The next
chapter covers Template Metaprogramming.
7.7 Epilogue - Two More Examples and References
The examples below are too large for the main chapter body. They illustrate very common template uses:
-
Graph<V,E> illustrates using template parameters to hold information.
The V type holds vertex-specific information such as a name,
and the E type holds edge-specific information such as the relationship type
between parent and child vertices.
-
Logger<T,C> uses value parameter C to define logger categories,
creating a distinct logger class for each value of C. For example,
Logger<std::string,1> and Logger<std::string,2>
can log information from two threads, t1 and t2.
The first example is a Directed Graph class. Complete code is in the
CppGraph.html repository. A directed graph consists of vertices
connected by directed edges from parent to child. Graphs represent hierarchical relationships
such as package dependencies or social network connections.
This example appears here because it uses two template
type parameters, V and E, representing
information held in each vertex and edge. For example, a class dependency graph would contain
a class name in each vertex and a relationship type in each edge - inheritance, composition,
aggregation, or using.
Before examining the example, review the Graph Documentation
for the CppGraph repository. The diagrams there clarify the code below.
Directed Graph Class
Vertex and Graph Code
namespace GraphLib
{
/////////////////////////////////////////////////////////
// Vertex class
template<typename V, typename E>
class Vertex
{
public:
typedef std::pair<int, E> Edge;
// graph index of target vertex, edge type
typename typedef std::vector<Edge>::iterator iterator;
iterator begin();
iterator end();
Vertex(V v, size_t id);
Vertex(V v);
void add(Edge& edge);
// compiler generated copy ctor, copy assignOp correct
// Vertex(const Vertex<V,E>& v);
// Vertex<V,E>& operator=(const Vertex<V,E>& v);
Edge& operator[](size_t i);
Edge operator[](size_t i) const;
V& value();
size_t& id();
size_t size();
bool& mark();
private:
std::vector<Edge> _edges;
V _v;
size_t _id;
static size_t count;
bool _mark;
};
//--< reserve memory for, and initialize, static count >--
template<typename V, typename E>
size_t Vertex<V,E>::count = 0;
//--< set and return boolean mark, used for traversal >--
template<typename V, typename E>
bool& Vertex<V,E>::mark() { return _mark; }
//----< return iterator pointing to first edge >---------
template<typename V, typename E>
typename Vertex<V,E>::iterator Vertex<V,E>::begin() {
return _edges.begin();
}
//--< return iterator pointing to one past last edge >---
template<typename V, typename E>
typename Vertex<V,E>::iterator Vertex<V,E>::end() {
return _edges.end();
}
//----< construct instance, specifying unique id >-----
template<typename V, typename E>
Vertex<V,E>::Vertex(V v, size_t id) :
_v(v), _id(id), _mark(false) {}
//--< construct instance - creates id sequentially >---
template<typename V, typename E>
Vertex<V,E>::Vertex(V v) :
_v(v), _id(count++), _mark(false) {}
//----< add edge to vertex edge collection >-----------
template<typename V, typename E>
void Vertex<V,E>::add(Edge& edge) {
_edges.push_back(edge);
}
//----< index non-const vertex's edges >---------------
template<typename V, typename E>
typename Vertex<V,E>::Edge&
Vertex<V,E>::operator[](size_t i) {
return _edges[i];
}
//----< index const vertex's edges >-------------------
template<typename V, typename E>
typename Vertex<V,E>::Edge
Vertex<V,E>::operator[](size_t i) const {
return _edges[i];
}
//---< set and read value of vertex's held type, V >---
template<typename V, typename E>
V& Vertex<V,E>::value() { return _v; }
//----< return vertex's id >---------------------------
template<typename V, typename E>
size_t& Vertex<V,E>::id() { return _id; }
//----< return number of edges >-----------------------
template<typename V, typename E>
size_t Vertex<V,E>::size() { return _edges.size(); }
///////////////////////////////////////////////////
// Graph class
template<typename V, typename E>
class Graph
{
public:
typename typedef
std::vector< Vertex<V,E> >::iterator iterator;
iterator begin();
iterator end();
// compiler generated copy ctor, copy assignOp correct
// Graph(const Graph<V,E>& g);
// Graph<V,E>& operator=(const Graph<V,E>& g);
Vertex<V,E>& operator[](size_t i);
Vertex<V,E> operator[](size_t i) const;
void addVertex(Vertex<V,E> v);
void addEdge(
E eval, Vertex<V,E>& parent,
Vertex<V,E>& child
);
size_t findVertexIndexById(size_t id);
size_t size();
template<typename F>
void dfs(Vertex<V,E>& v, F f);
private:
std::vector< Vertex<V,E> > adj;
std::unordered_map<size_t, size_t> idMap;
// id maps to graph index
template<typename F>
void dfsCore(Vertex<V,E>& v, F f);
};
//----< return iterator pointing to first vertex >-----
template<typename V, typename E>
typename Graph<V,E>::iterator Graph<V,E>::begin() {
return adj.begin();
}
//--< return iterator pointing one past last vertex >--
template<typename V, typename E>
typename Graph<V,E>::iterator Graph<V,E>::end() {
return adj.end();
}
//----< index non-const graph's vertex collection >----
template<typename V, typename E>
typename Vertex<V,E>&
Graph<V,E>::operator[](size_t i) {
return adj[i];
}
//----< index const graph's vertex collection >--------
template<typename V, typename E>
typename Vertex<V,E>
Graph<V,E>::operator[](size_t i) const {
return adj[i];
}
//----< add vertex to graph's vertex collection >------
template<typename V, typename E>
void Graph<V,E>::addVertex(Vertex<V,E> v)
{
adj.push_back(v);
idMap[v.id()] = adj.size() - 1;
}
//----< return number of vertices in graph's coll >----
template<typename V, typename E>
size_t Graph<V,E>::size() { return adj.size(); }
//----< return index of vertex with specified id >-----
template<typename V, typename E>
size_t Graph<V,E>::findVertexIndexById(size_t id)
{
return idMap[id];
}
//----< add edge from parent to child vertices >------
template<typename V, typename E>
void Graph<V,E>::addEdge(
E eVal, Vertex<V,E>& parent,
Vertex<V,E>& child
)
{
size_t childIndex = findVertexIndexById(child.id());
if(childIndex == adj.size())
throw std::exception("no edge child");
size_t parentIndex = findVertexIndexById(parent.id());
if(parentIndex == adj.size())
throw std::exception("no edge parent");
Vertex<V,E>::Edge e;
e.first = childIndex;
e.second = eVal;
adj[parentIndex].add(e);
}
//---< recursive depth first search with action f >----
template<typename V, typename E>
template<typename F>
void Graph<V,E>::dfsCore(Vertex<V,E>& v, F f)
{
f(v);
v.mark() = true;
for(auto edge : v)
{
if(adj[edge.first].mark() == false)
dfsCore(adj[edge.first], f);
}
for(auto& vert : adj)
{
if(vert.mark() == false)
dfsCore(vert, f);
}
}
//--< depth first srch, clears marks for next srch >---
template<typename V, typename E>
template<typename F>
void Graph<V,E>::dfs(Vertex<V,E>& v, F f)
{
dfsCore(v, f);
for(auto& vert : adj)
vert.mark() = false;
}
}
Using Code
#include <iostream>
#include <fstream>
#include "Graph.h"
using namespace GraphLib;
typedef Graph<std::string, std::string> graph;
typedef Vertex<std::string, std::string> vertex;
typedef Display<std::string, std::string> display;
void showVert(Vertex<std::string, std::string>& v)
{
std::cout << "\n " << v.id();
}
template<typename V, typename E>
void TshowVert(Vertex<V,E>& v)
{
std::cout << "\n " << v.id();
}
#ifdef TEST_GRAPH
int main()
{
std::cout << "\n Testing Graph Library";
std::cout << "\n =======================\n";
try
{
std::cout << "\n Constructing Graph instance";
std::cout << "\n -----------------------------";
graph g;
vertex v1("v1");
vertex v2("v2");
vertex v3("v3");
vertex v4("v4");
vertex v5("v5", 50);
g.addVertex(v2);
g.addVertex(v1);
g.addVertex(v3);
g.addVertex(v4);
g.addVertex(v5);
g.addEdge("e1",v1,v2);
g.addEdge("e2",v1,v3);
g.addEdge("e3",v2,v3);
g.addEdge("e4",v4,v3);
g.addEdge("e5",v5,v2);
display::show(g);
std::cout << "\n";
std::cout << "\n Making copy of instance";
std::cout << "\n -------------------------";
graph gcopy = g;
display::show(gcopy);
std::cout << "\n";
std::cout << "\n Modifying copy's values";
std::cout << "\n -------------------------";
for(auto& v : gcopy)
v.value() += "copy";
display::show(gcopy);
std::cout << "\n";
std::cout << "\n Assigning instance to copy";
std::cout << "\n ----------------------------";
gcopy = g;
display::show(gcopy);
std::cout << "\n";
std::cout << "\n Vertices with no Parents:";
std::cout << "\n ---------------------------";
std::vector< vertex > verts =
display::vertsWithNoParents(g);
std::cout << "\n ";
for(size_t i=0; i<verts.size(); ++i)
std::cout << verts[i].value().c_str()
<< " ";
std::cout << "\n";
std::cout <<
"\n Testing Depth First Search function pointer";
std::cout <<
"\n ---------------------------------------------";
for(auto& vert : g)
{
std::cout << "\n starting at id "
<< vert.id();
g.dfs(vert, TshowVert<std::string, std::string>);
// this works too:
// g.dfs(vert, showVert);
}
std::cout << "\n";
std::cout <<
"\n Testing Depth First Search with Functor";
std::cout <<
"\n -----------------------------------------";
class showFunctor
{
public:
void operator()(
Vertex<std::string, std::string>& vert
)
{
std::cout << "\n From functor: vertix id = "
<< vert.id();
std::cout << ", number of edges = "
<< vert.size();
}
};
g.dfs(g[0], showFunctor());
std::cout << "\n";
std::cout << "\n Testing Serialization to XML";
std::cout << "\n ------------------------------";
std::string str = GraphToXmlString(g);
std::cout << str << "\n";
std::ofstream out("testGraph.xml");
out << str << "\n";
std::cout <<
"\n Testing Graph construction from XML";
std::cout <<
"\n -------------------------------------";
graph gtest;
GraphFromXmlString(gtest, str);
display::show(gtest);
std::cout << "\n\n";
}
catch(std::exception& ex)
{
std::cout << "\n\n " << ex.what()
<< "\n\n";
}
std::cout << "\n\n";
return 0;
}
#endif
Output
Testing Graph Library
=======================
Constructing Graph instance
-----------------------------
vertex id = 1, value = v2
edge points to vertex with id = 2 and value = v3, edge value = e3
vertex id = 0, value = v1
edge points to vertex with id = 1 and value = v2, edge value = e1
edge points to vertex with id = 2 and value = v3, edge value = e2
vertex id = 2, value = v3
vertex id = 3, value = v4
edge points to vertex with id = 2 and value = v3, edge value = e4
vertex id = 50, value = v5
edge points to vertex with id = 1 and value = v2, edge value = e5
Making copy of instance
-------------------------
vertex id = 1, value = v2
edge points to vertex with id = 2 and value = v3, edge value = e3
vertex id = 0, value = v1
edge points to vertex with id = 1 and value = v2, edge value = e1
edge points to vertex with id = 2 and value = v3, edge value = e2
vertex id = 2, value = v3
vertex id = 3, value = v4
edge points to vertex with id = 2 and value = v3, edge value = e4
vertex id = 50, value = v5
edge points to vertex with id = 1 and value = v2, edge value = e5
Modifying copy's values
-------------------------
vertex id = 1, value = v2copy
edge points to vertex with id = 2 and value = v3copy, edge value = e3
vertex id = 0, value = v1copy
edge points to vertex with id = 1 and value = v2copy, edge value = e1
edge points to vertex with id = 2 and value = v3copy, edge value = e2
vertex id = 2, value = v3copy
vertex id = 3, value = v4copy
edge points to vertex with id = 2 and value = v3copy, edge value = e4
vertex id = 50, value = v5copy
edge points to vertex with id = 1 and value = v2copy, edge value = e5
Assigning original instance to copy
-------------------------------------
vertex id = 1, value = v2
edge points to vertex with id = 2 and value = v3, edge value = e3
vertex id = 0, value = v1
edge points to vertex with id = 1 and value = v2, edge value = e1
edge points to vertex with id = 2 and value = v3, edge value = e2
vertex id = 2, value = v3
vertex id = 3, value = v4
edge points to vertex with id = 2 and value = v3, edge value = e4
vertex id = 50, value = v5
edge points to vertex with id = 1 and value = v2, edge value = e5
Vertices with no Parents:
---------------------------
v1 v4 v5
Testing Depth First Search with function pointer
--------------------------------------------------
starting at id 1
1
2
0
3
50
starting at id 0
0
1
2
3
50
starting at id 2
2
1
0
3
50
starting at id 3
3
2
1
0
50
starting at id 50
50
1
2
0
3
Testing Depth First Search with Functor
-----------------------------------------
From functor: vertix id = 1, number of edges = 1
From functor: vertix id = 2, number of edges = 0
From functor: vertix id = 0, number of edges = 2
From functor: vertix id = 3, number of edges = 1
From functor: vertix id = 50, number of edges = 1
Testing Serialization to XML
------------------------------
<graph>
<vertex id="1" value="v2">
<edge targetId="2" value="e3">
</edge>
</vertex>
<vertex id="0" value="v1">
<edge targetId="1" value="e1">
</edge>
<edge targetId="2" value="e2">
</edge>
</vertex>
<vertex id="2" value="v3">
</vertex>
<vertex id="3" value="v4">
<edge targetId="2" value="e4">
</edge>
</vertex>
<vertex id="50" value="v5">
<edge targetId="1" value="e5">
</edge>
</vertex>
</graph>
Testing Graph construction from XML
-------------------------------------
vertex id = 1, value = v2
edge points to vertex with id = 2 and value = v3, edge value = e3
vertex id = 0, value = v1
edge points to vertex with id = 1 and value = v2, edge value = e1
edge points to vertex with id = 2 and value = v3, edge value = e2
vertex id = 2, value = v3
vertex id = 3, value = v4
edge points to vertex with id = 2 and value = v3, edge value = e4
vertex id = 50, value = v5
edge points to vertex with id = 1 and value = v2, edge value = e5
The Logger class example below has a more complete design than the earlier simplified Logger.
It takes template type parameter T - the type of
message being logged - and value parameter size_t C,
representing a logger category.
Logger uses its C parameter to define a logging level, such as
debug, demonstration, results, or any combination.
Logger Class
Logger Code
namespace Utilities {
enum Level { results = 1, demo = 2, debug = 4, all = 7 };
template <typename T, size_t C = 0>
struct ILogger {
virtual ~ILogger() {}
virtual ILogger<T, C>& add(std::ostream*) = 0;
virtual ILogger<T, C>&
write(T t, size_t level = Level::all) = 0;
virtual void head(T t = "") = 0;
virtual void prefix(T prfix = "\n ") = 0;
virtual void wait() = 0;
virtual void waitForWrites() = 0;
virtual void level(size_t lv) = 0;
virtual void name(const std::string& nm) = 0;
};
template <typename T, size_t C = 0>
class Logger : public ILogger<T, C> {
public:
Logger(const std::string& nm = "");
~Logger();
ILogger<T, C>& add(std::ostream* pOstrm);
virtual ILogger<T, C>&
write(T t, size_t level = 0x7);
virtual void head(T t = "");
virtual void prefix(T prfix = "\n ");
virtual void level(size_t lv);
void name(const std::string& nm);
std::string name();
void wait();
void waitForWrites();
protected:
std::vector<std::ostream*> dstStrm;
BlockingQueue<T> blockingQueue_;
void threadProc();
std::string name_;
std::thread writeThread_;
T head_;
std::string prefix_ = "\n ";
size_t level_ =
0x7; // Level::debug + Level::demo + Level::results;
};
/*--- object factory ----------------------------------
*
* Creates static logger, so calling makeLogger with
* the same value for C will use the same logger.
*/
template<typename T, size_t C>
inline ILogger<T, C>& makeLogger() {
static Logger<T, C> logger;
return logger;
}
/*--- initialize logger with name -------------------*/
template<typename T, size_t C>
Logger<T, C>::Logger(const std::string& nm)
: name_(nm) {
dstStrm.push_back(&std::cout);
std::thread temp(&Logger<T, C>::threadProc, this);
writeThread_ = std::move(temp);
}
/*--- wait for all writes to be sent ----------------*/
template<typename T, size_t C>
Logger<T, C>::~Logger() {
if (writeThread_.joinable())
writeThread_.detach();
for (auto ptrStrm : dstStrm) {
std::ofstream* ptrOfStrm =
dynamic_cast<std::ofstream*>(ptrStrm);
if (ptrOfStrm) {
ptrOfStrm->close();
delete ptrOfStrm;
}
}
}
/*--- reset name ------------------------------------*/
template<typename T, size_t C>
void Logger<T, C>::name(const std::string& nm) {
name_ = nm;
}
/*--- retrieve name ---------------------------------*/
template<typename T, size_t C>
std::string Logger<T, C>::name() {
return name_;
}
/*--- deQ thread processing -------------------------*/
template<typename T, size_t C>
void Logger<T,C>::threadProc() {
while (true) {
T t = blockingQueue_.deQ();
if (t == "quit")
break;
for (auto item : dstStrm) {
(*item) << t;
}
}
}
/*-- enQ stop message, wait for write thread exit --*/
template<typename T, size_t C>
void Logger<T, C>::wait() {
blockingQueue_.enQ("quit");
writeThread_.join();
}
/*-- wait for Q to empty before writing again ------*/
template<typename T, size_t C>
void Logger<T, C>::waitForWrites() {
while (blockingQueue_.size() > 0)
std::this_thread::sleep_for(
std::chrono::milliseconds(20)
);
}
/*--- add another stream for concurrent writes -----*/
template<typename T, size_t C>
ILogger<T, C>&
Logger<T, C>::add(std::ostream* pOstrm) {
if(pOstrm != nullptr)
dstStrm.push_back(pOstrm);
return *this;
}
/*----------------------------------------------------
* write a log message
* - probably one of many in a log stream
*/
template<typename T, size_t C>
ILogger<T, C>&
Logger<T, C>::write(T t, size_t lv) {
if (lv & level_) {
blockingQueue_.enQ(prefix_ + t);
}
return *this;
}
/*----------------------------------------------------
* write a head message
* - expected to be the first in log conversation
*/
template<typename T, size_t C>
void Logger<T, C>::head(T t) {
T temp = (t.size() > 0) ? t : name();
T prfix = (prefix_ == "") ? "\n" : prefix_;
head_ = temp + prfix + DateTime().now();
write(head_);
}
/*--- set message prefix ---------------------------*/
template<typename T, size_t C>
void Logger<T,C>::prefix(T prfix) {
prefix_ = prfix;
}
/*----------------------------------------------------
* set logging level
* - results ==> normal output
* - demo ==> demonstration output
* - debug --> show debugging information
* can be any combination, e.g., demo + results
*/
template<typename T, size_t C>
void Logger<T, C>::level(size_t lv) {
level_ = lv;
}
/*--- helper to open file stream --------------------*/
inline std::ostream* makeStream(
const std::string& fileName
) {
std::ofstream* pOfstrm = new std::ofstream;
pOfstrm->open(fileName);
if (pOfstrm->good())
return pOfstrm;
else
return nullptr;
}
}
Using Code
#include <string>
#include "Logger.h"
int main() {
displayTitle("Testing Logger");
using namespace Utilities;
Logger<std::string> logger("test");
// to see logger demo own test comment next statement
logger.level(Level::results);
logger.write("-- constructed logger --\n", Level::demo);
logger.add(makeStream("test.log"));
logger.write("\n -- added stream --\n", Level::demo);
logger.add(makeStream("does not exist"));
//logger.prefix(" ");
logger.head();
logger.write("\n -- called head --\n", Level::demo);
logger.prefix("");
logger.write("\n -- called write --\n", Level::demo);
logger.write("\n Hi ").write("there ");
logger.write("from Logger.cpp");
logger.write("\n");
logger.write(
"\n -- waiting for writes to complete --\n",
Level::demo
);
logger.waitForWrites();
logger.write("\n setting level = results");
logger.level(Level::results);
logger.write("\n a debug msg", Level::debug);
logger.write("\n a demo", Level::demo);
logger.write("\n a result", Level::results);
logger.write(
"\n -- waiting for writes to complete --\n",
Level::demo
);
logger.waitForWrites();
logger.write("\n setting level = demo");
logger.level(Level::demo);
logger.write("\n a debug msg", Level::debug);
logger.write("\n a demo", Level::demo);
logger.write("\n a result", Level::results);
logger.waitForWrites();
logger.write("\n setting level = debug");
logger.level(Level::debug);
logger.write("\n a debug msg", Level::debug);
logger.write("\n a demo", Level::demo);
logger.write("\n a result", Level::results);
logger.waitForWrites();
logger.write("\n setting level = results + demo");
logger.level(Level::results + Level::demo);
logger.write("\n a debug msg", Level::debug);
logger.write("\n a demo", Level::demo);
logger.write("\n a result", Level::results);
logger.waitForWrites();
// to see logger demo own test comment next statement
logger.level(Level::results);
logger.write(
"\n -- calling makeLogger factory --\n",
Level::demo
);
ILogger<std::string, 0>& logInstance =
makeLogger<std::string, 0>();
logInstance.add(makeStream("staticlog.log"));
logInstance.head("test logger factory");
logInstance.write("log msg #1").write("log msg #2");
ILogger<std::string, 0>& logInstance2 =
makeLogger<std::string, 0>();
logInstance2.head("test 2nd instance of factory");
logInstance2.write("log2 msg #1").write("log2 msg #2");
logInstance2.write("log2 msg #3").write("log2 msg #4");
const auto& logFactory =
[]()->ILogger<std::string,0>& {
return makeLogger<std::string, 0>();
};
logFactory().write("\n using makeLogger");
logger.wait();
logInstance.write("\n done waiting for logger");
logInstance.wait();
putline();
displaySubtitle("Testing Assertions");
Assert(true, "if you see this Assert raised");
Assert(false, "a message", __LINE__);
try {
Assert(
false, "another message", __LINE__, true
);
}
catch (std::exception & ex) {
std::cout << std::string("\n ") + ex.what();
}
putline();
Requires(1 == 1, "1 == 1", __LINE__);
Requires(1 == 2, "1 == 2", __LINE__);
try {
Requires(
1 == 3, "1 == 3", __LINE__, true
);
}
catch (std::exception & ex) {
std::cout << std::string("\n ") + ex.what();
}
putline();
Ensures(1 == 1, "1 == 1", __LINE__);
Ensures(1 == 2, "1 == 2", __LINE__);
try {
Ensures(
1 == 3, "1 == 3", __LINE__, true
);
}
catch (std::exception & ex) {
std::cout << std::string("\n ") + ex.what();
}
putline(2);
}
Output
test
Wed Dec 4 08:20:27 2019
Hi there from Logger.cpp
setting level = results
a result
setting level = demo
a demo
setting level = debug
a debug msg
setting level = results + demo
a demo
a result
Both designs have merit. The best features of each will eventually merge into the
Logger Repository.
C++ templates are a powerful language feature. They enable reusable components that
applications instantiate with specific types. Because templates are constructed at compile
time, type deduction makes building these reusable types remarkably effective.
The next chapter explores this further with template metaprogramming.
7.8 Programming Exercises
-
Write a calculator class with methods for addition, subtraction, multiplication,
and division. Use template parameters to support those operations for all C++
arithmetic types, including unsigned types.
Can you make this work for complex numbers? That requires a specialization.
What will you do for division?
-
Write a CircularBuffer class with an "add" method that accepts
a value of unspecified type and appends it to a private STL container.
After N calls, the method appends the new item and discards the oldest,
keeping the collection at N items. Provide an iterator starting at the
most recent element and moving toward the oldest.
Is there an STL container that makes this easy to implement?
Demonstrate that your CircularBuffer instances behave as expected.
-
Write a query facility for STL containers with a declarative interface similar to
C#'s LINQ - methods like select, where,
sort. This is a proof of concept, not a production library.
Consider selecting a container and flattening it into a std::vector.
Since queries may modify contents, do not operate directly on the original container.
Having most methods return a Query& enables method chaining, as in:
std::vector = Query.select(container).where(predicate).sort().toVector();
Work out the template syntax yourself.
Several operations using STL algorithms would be worth exploring.
7.9 References
class template argument deduction
- Stephan T. Lavavej
isocpp.org - templates
Class template argument deduction in C++17
- Timur Doumler
Understanding lvalues, rvalues and their references - Fluent C++