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 using code provides arguments and the compiler will infer the types and compile
a function using those types. In the second form function g takes arguments: a1 by value,
a2 by lvalue reference (&), and a3 by rvalue reference (&&).
In that second form we've used "class" instead of "typename".
Both forms are supported, but typename is preferred syntax.
Passing by value makes a copy of the argument in the function's stackframe. Passing with an lvalue
reference creates a reference in the function's stackframe, bound to the argument in the caller's
scope. lvalue references will not bind to non-const temporaries. rvalue references behave like lvalue
references except that they can bind to a temporary, e.g., an rvalue, and are used most frequently with
move operations.
For the
third case, type inference is not possible from the arguments, as there are none, and the compiler does not attempt to
analyze the body code to figure that out, so we have to help by providing the type we want, 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 will compile f as if the
function was defined as:
void f(int i) { ... }
and does the same thing with the remaining two cases.
7.2 Overloading Template Functions
Template functions provide generic recipes for their operation. That is often all we need
for a program we are implementing. However, frequently we need to handle a range of types,
some of which may not compile or operate correctly with the generic pattern. In those cases we
look for a function overload that will work correctly.
In the code below, we've expanded the T max(T t1,T t2) example from Chapter #1
by allowing the two arguments to have different types. That results in some interesting
processing activities.
Looking at the output of the using code, we see that:
-
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 unique parameter types allows max to compile successfully in cases that would
fail if we required both arguments to be the same type. Only the first and fourth examples, below, will
compile for the original T max(T t1, T t2) function.
Returning the result as an auto gets around
the problem of how to state the return type if more than one type could be returned, e.g.,
T1 or T2.
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 need to look at type categories and type inference, the process
compilation uses to establish the types that arguments take after being passed to template functions.
7.2.1 Type Categories
Before C++11, there were only two type categories, lvalue and rvalue:
-
lvalue refers to any named variable, e.g., anything for which we can evaluate an address.
It was called lvalue because it could by used on the left side of an assignment expression:
char ch = 'z';
Here, ch is an lvalue.
-
rvalue refers to any entity for which you cannot evaluate an address, as it has no name
and is usually a temporary. rvalues can only appear on the right side of an assignment
expression, e.g., the 'z' of the previous item.
Things are, since C++17, somewhat more complicated. rvalues split into xvalues and prvalues:
-
An xvalue is an entity that can be the source of a move operation. These are almost always
values of temporary objects created in the scope of some function, and are syntactically returned
by value. An xvalue is not copied, but instead moved by transferring its resources to the
entity that is the target of the return operation.
-
A prvalue is an expression that defines the initialization of the destination. Under return
value optimization the prvalue initializes the creation of a target instance. 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.
For most of your implementations, you won't have to think about these categories unless you are
writing code that runs partially at compile-time, e.g., template metaprogramming.
7.2.2 Type Transformations
When passing arguments to functions, the result of template type deduction is not necessarily the same as
the type of the argument in the caller's scope. This is not an inference error, but an intentional
transformation made for reasons of performance or usability.
For non-template functions there is only one such transformation. That occurs for array arguments.
When the function's stackframe is constructed, a pointer is created in stack memory, bound to
the first element of the array, instead of copying the array.
All access to the array, within the function,
accesses the caller's array via that pointer. It is common to refer to this process as type decay. That is,
the array type decays to a pointer type in the function's scope.
For template functions, transformations of function argument types are more complicated. The most important
of these 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
In this section we will look at type transformations that occur when passing arguments to functions,
especially template functions. Unfortunately you cannot use the C++ typeid operator to explore these
effects. We see below, that passing an argument to a template function by value strips its constant,
volatile, and reference (cvr) qualifiers. But typeid is a template function, so it will strip off
some of the things we are looking for.
The Boost libraries have a work-around with their boost::typeindex::type_id_with_cvr()
operator1. I've used that for all of the type analysis reported below.
We see, from Table 1., that in all non-template cases tested, the only case with type decay is the array argument.
This is true in general, e.g., for non-template functions, the only type decay that happens is 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 are a different story. When compiling an instantiated template, the compiler infers
argument types from syntax of invocations. That inference has several rules:
-
Passing an argument by value removes all const, volatile, and reference (cvr) qulifiers.
Array arguments decay to pointers.
-
Passing an argument by lvalue reference (T&) doesn't remove qualifiers and arrays do not
decay (because they won't be copied). An lvalue reference can only bind to lvalues or const rvalues.
Note that C++ classifies literal strings as lvalues. All other literals, e.g., ints and doubles, are rvalues.
-
Passing an argument by pointer doesn't remove qualifiers, but arrays do decay (because the argument
is a pointer).
-
Passing an argument by universal reference (T&& where T is being deduced) doesn't strip qualifiers and arrays do not
decay. Universal references can 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 you don't have to think about the rules. Inference just works as you would expect.
On rare occasions you may need to consider 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 argument type deduction may fail for one or perhaps several
overloads. These deductions are based on substitutions in each of the overloads. Substitution failure
is not a compile error, so the build should succeed unless none of the deductions succeed.
SFINAE Details
In the example below, we've supplied two function overloads, each displaying the contents of
a collection. The first displays contents of an array, and the second, contents of a vector.
In the Using Code main there are 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 the double 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 satify 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 point of all this is that you can write function code that works for some types
but not for others as long as there is a type deduction for some other function overload that succeeds
and provides working code for any of the types your program will use for this set invocations.
We will look at SFINAE for template classes in the next chapter7 - Template Metaprogramming.
7.3 Template Function Examples
There are a number of standard template functions that 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 we will look at some example template function designs. The first two come from the
CppUtilities repository.
Converter<T>::toString(t), in the CodeUtilities folder, converts the value of t ε T
to its string representation.
And, 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 is simple because it uses std::ostringstream to convert from
values to their string representation, and it uses std::istringstream to convert back.
Thus, the std::stringstream library classes do all the heavy lifting.
The second example, found in the StringUtilities folder, presents string utility functions
trim and split with capabilities similar 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
For our last template function example, the code below shows how to create
generic lambdas.
They are defined using auto parameters, as shown. This is equivalent to a
template function, but doesn't use template syntax. That it is generic is
due to type deduction generated for the auto declarators.
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
We will look at template functions again, in Chapter #7 - Template Metaprogramming, where we explore
some of the functions used to provide displays for code demonstrations throughout this story.
7.4 Template Classes
Template classes use syntax as shown in the blocks below. Everywhere that the class name SynDemo is used
as a type it needs the template parameter, e.g., SynDemo<T>.
Remember that both template declarations and
definitions must appear in the class's header file, as shown below.
Here you will find the included file display.h.
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
Because of the two phase compilation for templates used by C++, the class's
method implementations must be placed in its header file.
7.4.1 Stack<T> Class Example
The Stack<T> class example, below, illustrates this syntax
for a class typical of professionally developed code. It also illustrates:
-
Template members:
A copy constructor template <class U> stack(const stack<U>&); and
assignment operator
template <class U> stack<U>& 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 operations, but could
also be different, allowing one, for example, to assign a stack<int> to a
stack<double>. The example code illustrates that use. Template type inference
is the reason we can design this flexibility.
-
Inner classes:
Inner classes aren't often used for C++ programs, but if a parent class needs
services of a small and simple class that is specialized for the parent, then using an
inner class for the child makes sense. The struct stacknode is an example
of that use.
-
Friend relationships:
We try to avoid using friend relationships because they expand encapsulation
from the granting class to include friends as well. However, when needed it's
easy to use, as shown here. This stack<T> class needs to allow
template members, cited in the first item, to access its private data. That's because
stack<T> is a different class than stack<U>.
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 won't use this class for your own designs. The Standard Template Library (STL) provides
a stack adapter class1 and C++ developers know how that works, so you should use it.
The STL provides a rich set of examples of template classes including one for each of the STL
containers. You will find a demonstration of each of them in
STL-Containers.html in the Demonstrations part of the
CppRepositories.html.
7.4.2 Directory Explorer Example
The next example, DirExplorerT, shows how to build a component - a directory navigator - to be reusable,
e.g., can be used in many different applications without changing any of its code. The way that is done
is to parameterize the navigator on an application specific class, DirExplorerT<App>.
The application class is expected to provide methods doFile(const std::string& fileName)
and doDir(const std::string& dirName) that handle all application specific
requirements for using 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
There is a significant amount of code in DirExplorerT to digest, but the effort will show you
a very powerful method of 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 behavior of
a template class for specific applications.
they may also be used to define specific data structures
for an application. Often an application defines type parameters for
its unique processing to be used with an existing template class framework.
Template type parameters are themselves templates. You will see in
the Template Functors example, below, use of a functor, X<C> that is parameterized on
C, the type of an STL container. It is used in a traversal function to operate on all
the members of the STL container.
Value parameters are values rather than classes.
The std::Array<T,N> class
uses a value parameter, N to define the number of elements it holds.
The Template Functors code example, below, has a global function Traverse that is
defined with a template parameter, C, and a
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 that defines
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
In section 6.6 we discuss template class specialization, a mechanism for providing not only a
generic pattern for implementing a template class, as all templates do, but also alternate
implementations for special
cases for which the generic pattern may not work well.
7.6 Template Class Specialization
Templates provide the means to define classes that are configured with other subordinate
classes. In the code block, below, we're configuring class X to use helper
classes P and Q. Each application can decide which helpers to use
and/or implement another set of helpers specific to that application.
Template specialization gives us another degree of design freedom.
Specialization occurs when
we define a template class with one or more template arguments, but also provide one or more
additional classes with the same name, but with at least one of the arguments specialized.
In the code below, we've specialized X<P,Q> for the cases:
X<P,Q1>, X<P1,Q>, and X<P1,Q1>. Each
specialization provides its own class implementation and each will be different in some
way needed for those specific cases. Note that these are different classes. The compiler
is required, when compiling a template class, to look for specializations, and if one matches
the declaration it's compiling, it must compile the specialized class.
The code block below illustrates template specialization syntax. The following logger example
demonstrates how specialization is used for practical applications.
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, expected to handle common program needs.
Each specialization adds another class that replaces the generic one for a specific case, e.g.
a specific parameter type when instantiated. There may be as many specializations as you need.
The logger example, below, is simpler than that presented above. It is here to illustrate
template specialization. It uses specialization to provide:
-
A generic logger class, Logger<S, F, T>, describing Logger structure.
It's not intended for 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 provides basic logging, i.e.,
writes text to a specified stream. The first argument, S, will usually be a std::string,
but could also be a structured message. The FNull argument provides a do nothing formatter,
and the TNull argument provides a do nothing timer.
-
A partial specialization on F, to provide application specific formatting. Note that this
parameter is a template, e.g., F<S>, allowing F to handle different types of text messages.
-
A partial specialization on T, to provide elapsed time annotations on each message.
This example deviates from the usual pattern in that the generic class is just used to provide a
framework for subsequent specializations, so every template the application instantiates is
a specialization. This design style is used less often than providing a working generic class,
but sometimes it's easier to build this way.
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 fully featured implementation would probably also provide a full specialization for both
formatting and timing.
This concludes our discussion of templates, overloading, and specialization. In the next
chapter we discuss Template Metaprogramming.
7.7 Epilogue - Two More Examples and References
The examples below are too large for the main part of this chapter. They are here to illustrate
very typical uses of templates:
-
Graph<V,E> illustrates the use of template parameters to hold information. The
V type holds information specific to each instance of a graph vertex, perhaps a name,
and the E type holds information specific to each instance of a graph edge, perhaps
the type of relationship between the dependency parent and child vertices.
-
Logger<T,C> uses a value parameter, C, to define categories of
loggers, by creating a different logger class for each value of C. So, for example,
we might define Logger<std::string,1> and Logger<std::string,2>
to log information from two threads, t1 and t2.
The first example is a Directed Graph class. You can find complete code
in the CppGraph.html repository. A directed graph consists of vertices
that are connected with directed edges, from parent vertex to child vertex. Graphs are used to
represent hierarchal relationships, e.g., package dependency or social network friend relationships.
The example is here, because it uses two template
type parameters, V and E, that
represent information held in each vertex and each edge. For example, a class dependency graph
would probably contain a class name in each vertex and in each edge a class relationship
type, e.g., inheritance, composition, aggregation, or using.
Before looking at the example, it will help to look at the Graph Documentation
for the CppGraph repository. We show diagrams there that will help you understand 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
In the Logger class example, below, Logger has a larger design than the earlier
simplified Logger example. It takes a
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, e.g., debug or
demonstration or results or some combination of the three.
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. I will eventually merge the best features of each and put that in the
Logger Repository.
C++ templates are a very powerful feature of the language. We use them to build components that can
be reused by instantiating with application specific types. Because templates are constructed at compile
time, template type deduction makes it suprisingly effective to build these reusable types.
We will explore this further in the next chapter where we look at template metaprogramming.
7.8 Programming Exercises
-
Write a calculator class that provides methods for addition, subtraction, multiplication
and division. Use template parameters to support those operations for all the C++
arithmetic types (that includes unsigned types).
Can you make this work for complex numbers? You will need a specialization
for that. what will you do for division?
-
Write a CircularBuffer class that has an "add" method that accepts
a value of unspecified type and appends it to a private member collection -
one of the STL containers. After the method has been called N times, it
appends the new item and discards the oldest item, keeping the collection
size at N items. Provide an iterator that starts at the most recent and
increments toward the oldest.
Is there an STL container that will make this very easy to implement?
Please demonstrate that your CircularBuffer instances behave as expected.
-
Write a query facility for STL containers that provides a declarative interface,
something like C#'s LINQ, providing methods like select, where,
sort, ... You're trying to do a proof of concept, not a complete
industrial strength library. You might think about selecting some container
and flattening into a std::vector. Since queries may modify the contents
you don't want to operate directly on the original container. If you make most
of the methods return a Query& then you can chain them, e.g.:
std::vector = Query.select(container).where(predicate).sort().toVector();
This is just pseudo-code with all of the template syntax left for you to work out.
It would be interesting to work out several operations, using the STL algorithms
where appropriate.
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++