What Are Templates?
Why Use Templates?
Traits
Policies
Type Lists
Compile-Time Computation
For More Information
This paper introduces a style of programming that is often called
metaprogramming. An ordinary program performs its task at
runtime. A metaprogram does its work at compile time. The
metaprogram's task can be as simple as querying the properties (or
traits) of a type, or as complex as a lengthy computation that fills
a static data structure with, say, the first hundred prime numbers.
Templates are best known for permitting type-generic programming,
such as vector<>, which can store objects of
almost any type.
Templates also permit powerful programming techniques such as policy-based programming. For example, suppose you want to write a new container template in a multithreaded environment. A container object that is read and written in multiple threads requires synchronization, but if a container object is accessed solely in one thread, you don't need the overhead of synchronizing access. You can write a single container class template that takes a lock policy as a template parameter; when the container template is instantiated, you supply a lock policy class. In a multithreaded program, the lock policy can use critical sections. In a multiprocessing program, it might use mutexes that are stored in shared memory. For the single-threaded case, use a no-lock policy, that is, one that does nothing in its lock and unlock synchronization functions. The compiler is able to optimize away the unnecessary calls to the no-lock object, so the single-threaded container does not suffer any performance penalty for its generalization. (Don't you wish Delphi strings worked the same way?)
One word of warning: Template metaprogramming is powerful, but it ain't pretty.
A template is a C++ language construct that defines a pattern for creating functions and classes at compile time. The template takes one or more parameters, which can be values, types, or other templates. An instance of a template supplies arguments for the template parameters. An instance of a function template is, for all practical purposes, a function. An instance of a class template is just like an ordinary class. (The difference between an instance of a function template and an ordinary function lies in the resolution of overloaded functions, and is beyond the scope of this paper. Likewise, the difference between an instance of a class template and an ordinary class lies in the overload resolution of the class's member functions.)
The following example shows how to write a function template that
returns the minimum of two values. The function template takes a
single type parameter, T. The template can be instantiated
with almost any type. When the function is instantiated, the compiler
compiles the instantiation, and at that time, it can determine
whether the template argument allows the < operator.
If not, the compiler reports an error.
template<typename T>
T min(const T& a, const T& b)
{
if (a < b)
return a;
else
return b;
}The following example shows a simple class template to represent a point. The point is made of a pair of numbers. The type of the numbers can be any numeric type, specified by the template parameter T. Notice that the template parameter does not restrict the type of T. The syntactic restrictions on T are specified in the definition of the point class. The semantic restrictions are determined by the programmer.
template<typename T>
struct point {
T x;
T y;
};Declaring a function or class template does not produce any code in the final program. The only way to do that is to instantiate the template, that is, create an instance of the template for a specific set of template arguments. An instance can be explicit, with an instance declaration, or implicit, by use. Instantiation is most commonly implicit. For example:
point<int> p; // implicit instance of point<> int i, j; int x = min(i, j); // implicit instance of min<>
Sometimes, you can omit template arguments: a class template can have default template arguments. A call to a function template can have the compiler deduce the template arguments from context. The details are beyond the scope of this paper.
A template is a powerful technique for writing code once and having it work in a multitude of situations. Sometimes, though, you run into exceptions to the general rule. A single template definition is not always adequate to cover all possible cases. To define an exception, you specialize a template. A template specialization can be total or partial. A total specialization must specify an argument for every template parameter, and the specialization applies only when the template is instantiated with those same arguments. A partial specialization supplies values to only some of the template parameters.
For example, the type_traits<> template
characterizes a type with a set of constant declarations:
template<typename T>
struct type_traits
{
typedef T base_type;
enum { is_fundamental = 0 };
enum { is_integer = 0 };
enum { is_float = 0 };
enum { is_pointer = 0 };
enum { is_reference = 0 };
static std::string to_string(const T&);
};
template<typename T>
std::string type_traits<T>::to_string(const T& x)
{
return typeid(x).name();
}
You can specialize the template for particular types. When you
specialize a template, you must provide a complete definition. A
total specialization begins with template<> and is
followed by a declaration or definition. For example:
template<>
struct type_traits<int>
{
typedef int base_type;
enum { is_fundamental = 1 };
enum { is_integer = 1 };
enum { is_float = 0 };
enum { is_pointer = 0 };
enum { is_reference = 0 };
static std::string to_string(const int& x) {
std::ostringstream out;
out << x;
return out.str();
}
};
A partial specialization begins with a template header that lists one
or more template parameters. For example, you can specialize
type_traits for all pointer types as follows:
template<typename T>
struct type_traits<T*>
{
typedef T base_type;
enum { is_fundamental = type_traits<T>::is_fundamental };
enum { is_integer = 0 };
enum { is_float = 0 };
enum { is_pointer = 1 };
enum { is_reference = 0 };
static std::string to_string(const T& x) {
std::ostringstream out;
out << x;
return out.str();
}
};Many uses of templates are readily evident. For example, you can write a simple function to compute the minimum of two values. (This function is part of the standard C++ library, by the way.) You need only one function template definition, and the function can be instantiated with any type.
template<typename T>
T min(const T& a, const T& b)
{
return a < b ? a : b;
}
int i = 10;
int j = min<int>(i, 20);
long k = min<long>(i, 42L);
std::string less = min<std::string>("this", "that");
The C++ standard library uses templates extensively. The part of the
library that is traditionally known as the Standard Template Library
obviously makes use of templates. The STL usually refers to the suite
of containers, iterators, and algorithms in the standard C++ library.
The standard containers are deques, lists, maps, sets, and vectors. A
container can store values of almost any type. Each container has a
single class template definition, which works for any type. (One
exception is vector<>, which has a specialization
for type bool. This specialization is widely considered
a mistake. The details are beyond the scope of this paper.)
Templates have many other uses within the standard library. Two common uses of templates are traits and policies. A trait describes the properties of a type or function. A policy defines an interface for behavior that a class or function can make use of.
Two examples of traits in the C++ standard library are
char_traits<> and iterator_traits<>.
An iterator is an abstraction of a pointer, but one that points to an element of a linear sequence of items, such as the items in a container, or items in an I/O stream. If the container is a plain array, a plain pointer can be an iterator. For other sequences, the iterator type must be a class type. When writing a generic algorithm, that is, a function that can work with any kind of iterator, you need a single interface that works with any kind of iterator.
If you were to assume that an iterator is always a class instance, you might write your algorithm as follows:
template<typename InputIter>
typename InputIter::difference_type
distance(InputIter first, InputIter last)
{
typename InputIter::difference_type count = 0;
while (first != last) {
++first;
++count;
}
return count;
}
If you are not familiar with this use of typename, it is
necessary in any template that uses a qualified name. When the
compiler parses the distance function template, it does not know what
InputIter is or might be. An instantiation of distance
might supply an InputIter argument where
InputIter::difference_type is not declared, or declared
as a member function. Using typename tells the compiler
to assume that difference_type is a type name, so the
compiler can parse distance correctly. It you later try to
instantiate distance with an invalid template argument (that is, one
for which difference_type is not a type), the compiler
will issue an error message.
This definition of distance works for input iterators that are implemented as classes, but not all iterators are implemented that way. A pointer can also be used as an iterator in many cases. For example:
char str[10]; distance(&str[5], &str[2]);
In this case, the distance function cannot be instantiated. The
solution is to use iterator_traits<>, which
exposes the properties of an iterator, which is takes as a template
argument. The template is specialized for pointers, so
difference_type is defined as ptrdiff_t.
The code is a little unwieldy, but you get used to it after a while.
template<typename InputIter>
typename std::iterator_traits<InputIter>::difference_type
distance(InputIter first, InputIter last)
{
typename std::iterator_traits<InputIter>::difference_type count = 0;
while (first != last) {
++first;
++count;
}
return count;
}Another advantage of iterator traits is that you can determine the iterator category. A random access iterator can compute the distance between two iterators by a quick subtraction. For example:
// Helper function, overloaded for random access iterators.
template<typename InputIter>
typename std::iterator_traits<InputIter>::difference_type
compute_dist(InputIter first, InputIter last,
std::random_access_iterator_tag)
{
return last - first;
}
// Helper function, overloaded for all other input iterators.
template<typename InputIter>
typename std::iterator_traits<InputIter>::difference_type
compute_dist(InputIter first, InputIter last,
std::input_iterator_tag)
{
typename std::iterator_traits<InputIter>::difference_type count = 0;
while (first != last) {
++first;
++count;
}
return count;
}
// Main distance function, which calls the helper function,
// using the iterator tag to differentiate the overloaded functions.
template<typename InputIter>
typename std::iterator_traits<InputIter>::difference_type
distance(InputIter first, InputIter last)
{
return compute_dist(first, last,
std::iterator_traits<InputIter>::iterator_category());
}
The char_traits<> template describes properties of
a character type. The standard library specializes the template for
types char and wchar_t. If you have a
special need for some other character type, you can supply your own
character traits class or specialize char_traits for
your character type. In addition to the static characteristics of a
character type, char_traits also implements policies, as
described in the next section.
A policy is similar to a trait, but it is dynamic. Policy-based programming is a style of programming where you write a template that takes a policy as a template parameter, and relies on a specific interface for the policy, and works for any policy that fulfills the interface.
The C++ standard library uses policies in several places. The
char_traits template is a policy template, in addition
to being a traits template. The policy defines an interface for
comparing character arrays, copying character arrays, converting
characters to and from integers, and so on.
Suppose you want to implement a case-insensitive string, that is,
you want a class that works the same way as string and
wstring, except comparisons are made without regard to
case differences. This is a policy decision, and is best implemented
as a character traits object.
template<typename T> struct ci_char_traits {};
template<> struct ci_char_traits<char> {
typedef char char_type;
typedef int int_type;
typedef std::streamoff off_type;
typedef std::streampos pos_type;
typedef std::mbstate_t state_type;
static void assign(char_type& dst, const char_type src) {
dst = src;
}
static char_type* assign(char* dst, size_t n, char c) {
return static_cast<char_type*>(std::memset(dst, n, c));
}
static bool eq(const char_type& c1, const char_type& c2) {
return lower(c1) == lower(c2);
}
static bool lt(const char_type& c1, const char_type& c2) {
return lower(c1) < lower(c2);
}
static int compare(const char_type* s1,
const char_type* s2, size_t n) {
for (size_t i = 0; i < n; ++i)
{
char_type lc1 = lower(s1[i]);
char_type lc2 = lower(s2[i]);
if (lc1 < lc2)
return -1;
else if (lc1 > lc2)
return 1;
}
return 0;
}
...
private:
static int_type lower(char_type c) {
return std::tolower(to_int_type(c));
}
};
typedef std::basic_string<char, ci_char_traits<char> >
ci_string;
typedef std::basic_string<wchar_t, ci_char_traits<wchar_t> >
ci_wstring;You can then use ci_string the same way you would use std::string, except comparisons ignore case differences. For example, if you use ci_string as a key type for a set or map, the key "Foo" is equivalent to the keys "foo" and "FOO".
void print(const std::pair<const ci_string, size_t>& item)
{
std::cout << item.first << '\t' << item.second << '\n';
}
int main()
{
std::map<ci_string, size_t> count;
ci_string word;
while (std::cin >> word)
++count[word];
std::for_each(count.begin(), count.end(), print);
}Every container in the C++ standard library has a constructor of the following form:
template<typename InputIter> container(InputIter first, InputIter last);
The container object is constructed by copying all the elements in
the specified range: [first, last). But the
standard also defines constructors of the form:
container(size_type count, value_type x);
to construct the container as count copies of x. Perhaps
you can see the problem. If not, think about it before reading the
next paragraph. Programming with templates is more difficult than
programming without templates, and sometimes the problems are subtle.
Suppose size_type is unsigned int,
and value_type is unsigned int,
for example, you are constructing a vector<unsigned
int>. In that case, both constructors match.
Fortunately, the compiler prefers non-template functions over
template functions, so it calls the correct constructor. But what if
you construct a vector<int>(10, 42)?
In that case, the template is instantiated with the type InputIter
as int. Without the template form of the constructor,
the compiler would easily convert the integer 10 to size_type,
and be able to construct 10 copies of 42. But with the template form,
the "wrong" constructor is called.
In this case, the standard mandates that if InputIter
is an integral type, the container is constructed with first copies
of last, appropriately cast to the desired types. An integral type
can never be a valid iterator, so the alternate interpretation must
be the correct one.
The question to the library implementor, therefore, is how to tell
when InputIter has an integral type. This seems like a
job for a type traits template, that is, a traits type that can
determine whether a type is integral. C++ lacks such a traits type,
but you can write your own. A common technique is to define special
tag types, say, is_integer_tag, and is_not_integer_tag.
You can overload helper functions based on these tag types.
template<typename InputIter>
construct(InputIter first, InputIter last, is_integer_tag)
{
construct(static_cast<size_type>(first),
static_cast<value_type>(last));
}
template<typename InputIter>
construct(InputIter first, InputIter last, is_not_integer_tag)
{
insert
}
template<typename InputIter>
container(InputIter first, InputIter last)
{
construct(first, last, is_integer<InputIter>::tag);
}
The next task is to specialize your is_integer<>
template for all the integral types, as follows:
template<typename T>
class is_integer {
typedef is_not_integer tag;
};
template<> class is_integer<int> {
typedef is_integer tag;
};
template<> class is_integer<unsigned int> {
typedef is_integer tag;
};Whenever you find yourself repeating lots of code, you should ask yourself whether there might be a better way. In this case, there is. Imagine if you could instead write the following:
typedef list<int, unsigned int, short, unsigned short,
long, unsigned long, char, unsigned char, signed char, bool>::type
integral_types;
template<typename T>
class is_integer {
typedef typename ifelse<is_member<T, integral_type>::value,
is_integer_tag,
is_not_integer_tag>::type tag;
};
Another advantage of using type lists is that it is more easily
generalized. Imagine defining is_float, is_character,
and other traits templates. The more traits you define, the greater
the advantage to using lists.
Now you simply need to define a way to create and work with lists of types. Programming with templates requires thinking in functional terms, not imperative terms. You have no variables, only templates, types, and constants.
struct empty {};
template<typename Head, typename Tail>
struct node {
typedef Head head;
typedef Tail tail;
};A list can be empty or it can contain an item, followed by a list. This definition is familiar to anyone who programs in a functional language (e.g., Lisp, Haskell). Creating a list can be cumbersome:
typedef node<char, node<unsigned char, node<signed char, node<wchar_t,empty> > > > character_types;
To facilitate creating lists, you can take advantage of default template arguments:
template<typename T1, typename T2, typename T3>
struct list {
typedef
typename ifelse<is_same_type<T1,empty>::value, empty, node
<T1, typename ifelse<is_same_type<T2,empty>::value, empty, node
<T2, typename ifelse<is_same_type<T3,empty>::value, empty, node
<T3, empty>
>::type>
>::type
type;
};
typedef list<char, signed char, unsigned char>::type
narrow_char_types;
The only problem with the list template is that it has a
fixed maximum size. If you need to make longer lists, you can
concatenate lists:
template<typename T1, typename T2>
struct concat {
typedef node<typename T1::head,
concat<typename T1::tail, T2>::type> type;
};
template<T2>
struct concat<empty, T2> {
typedef T2 type;
};
template<T1>
struct concat<T1, empty> {
typedef T1 type;
};
template<>
struct concat<empty, empty> {
typedef empty type;
};
typedef list<unsigned int, unsigned short, unsigned long>::type unsigned_types;
typedef list<int, short, long>::type signed_types;
typedef concat<signed_types, unsigned_types>::type int_types;
typedef list<bool, concat<int_types, character_types>::type >::type integral_types;
Notice the conditional template ifelse and the use of
recursion. The only iteration construct in template metaprogramming
is recursion. Template specialization lets you make decisions, such
as implementing ifelse:
template<bool C, typename T, typename F>
struct ifelse {};
template<typename T, typename F>
struct ifelse<false,T,F> {
typedef F type;
};
struct ifelse<true,T,F> {
typedef T type;
};
By now you should be able to see how to implement isempty.
template<typename T>
struct is_empty { enum { value = false }; };
template<>
struct is_empty<empty> { enum { value = true }; };
Finally, you need is_same_type and ifelse:
template<bool Cond, typename IfTrue, typename IfFalse>
struct ifelse {
typedef IfTrue type;
};
template<typename IfTrue, typename IfFalse>
struct ifelse<false, IfTrue, IfFalse> {
typedef IfFalse type;
};
template<typename T, typename U>
struct is_same_type {
enum { value = false };
};
template<typename T>
struct is_same_type<T, T> {
enum { value = true };
};As you can see, template specialization lets you make decisions
and terminate recursion. Within the limitations of the C++ compiler,
programming at compile time with templates is Turing equivalent,
which means you can compute and computable problem. To demonstrate
the is_prime<> template determines at compile time
whether an integer is prime:
template<unsigned N, unsigned D, bool Continue>
struct is_prime_test {
enum { value = 1 };
};
template<unsigned N, unsigned D>
struct is_prime_test<N, D, true> {
enum { value = N % D != 0 && is_prime_test<N, D+1, D+1 < N/2>::value };
};
template<unsigned N>
struct is_prime {
enum { value = is_prime_test<N, 2, 2 <= N/2>::value };
};
template<>
struct is_prime<0> {
enum { value = 0 };
};
template<>
struct is_prime<1> {
enum { value = 0 };
};Andrei Alexandrescu's book, Modern C++ Design, shows how far you can push metaprogramming. It is an excellent book to learn about type lists, policy-based programming, and related issues in template-based programming.
For a more general book about templates, see C++ Templates, by David Vandervoode and Nicolai Josuttis. This book presents everything you need to know about writing and using templates. If you have difficulty understanding dependent name lookup, or don't know what that means, this is a good book for you.
C++ in a Nutshell is a reference for standard C++. Once you learn the concepts of templates and template-based programming, use C++ in a Nutshell as a quick reference to remind you about the syntactic and semantic rules for the language and standard library.
Ray Lischner is a professional goof-off, who has dedicated his life to the avoidance of gainful employment. To help him achieve his goal, Ray has been playing at being an author. He is the author of C++ in a Nutshell and other books.