Chapter 3. Class Templates
Similar to functions, classes can also be parameterized with one or more types. Container classes, which are used to manage elements of a certain type, are a typical example of this feature. By using class templates, you can implement such container classes while the element type is still open. In this chapter we use a stack as an example of a class template.
3.1 Implementation of Class Template Stack
As we did with function templates, we declare and define class Stack<> in a header file as follows (we discuss the separation of declaration and definition in different files in Section 7.3 on page 89):
// basics/stack1.hpp
#include <vector>
#include <stdexcept>
template <typename T>
class Stack {
private:
std::vector<T> elems; // elements
public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}
};
template <typename T>
void Stack<T>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}
template<typename T>
void Stack<T>::pop ()
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
elems.pop_back(); // remove last element
}
template <typename T>
T Stack<T>::top () const
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems.back(); // return copy of last element
}
As you can see, the class template is implemented by using a class template of the C++ standard library: vector<>. As a result, we don’t have to implement memory management, copy constructor, and assignment operator, so we can concentrate on the interface of this class template.
3.1.1 Declaration of Class Templates
Declaring class templates is similar to declaring function templates: Before the declaration, a statement declares an identifier as a type parameter. Again, T is usually used as an identifier:
template <typename T>
class Stack {
…
};
Here again, the keyword class can be used instead of typename:
template <class T>
class Stack {
…
};
Inside the class template, T can be used just like any other type to declare members and member functions. In this example, T is used to declare the type of the elements as vector of Ts, to declare push() as a member function that gets a constant T reference as an argument, and to declare top() as a function that returns a T:
template <typename T>
class Stack {
private:
std::vector<T> elems; // elements
public:
Stack(); // constructor
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
};
The type of this class is Stack<T>, with T being a template parameter. Thus, you have to use Stack<T> whenever you use the type of this class in a declaration. If, for example, you have to declare your own copy constructor and assignment operator, it looks like this1:
template <typename T>
class Stack {
…
Stack (Stack<T> const&); // copy constructor
Stack<T>& operator= (Stack<T> const&); // assignment operator
…
};
However, when the name and not the type of the class is required, only Stack has to be used. This is the case when you specify the name of the class, the constructors, and the destructor.
3.1.2 Implementation of Member Functions
To define a member function of a class template, you have to specify that it is a function template, and you have to use the full type qualification of the class template. Thus, the implementation of the member function push() for type Stack<T> looks like this:
template <typename T>
void Stack<T>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}
In this case, push_back() of the element vector is called, which appends the element at the end of the vector.
Note that pop_back() of a vector removes the last element but doesn’t return it. The reason for this behavior is exception safety. It is impossible to implement a completely exception-safe version of pop() that returns the removed element (this topic was first discussed by Tom Cargill in [CargillExceptionSafety] and is discussed as Item 10 in [SutterExceptional]). However, ignoring this danger, we could implement a pop() that returns the element just removed. To do this, we simply use T to declare a local variable of the element type:
template<typename T>
T Stack<T>::pop ()
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
T elem = elems.back(); // save copy of last element
elems.pop_back(); // remove last element
return elem; // return copy of saved element
}
Because the vectors back() (which returns the last element) and pop_back() (which removes the last element) have undefined behavior when there is no element in the vector, we have to check whether the stack is empty. If it is empty, we throw an exception of type std::out_of_range. This is also done in top(), which returns but does not remove the top element:
template<typename T>
T Stack<T>::top () const
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems.back(); // return copy of last element
}
Of course, as for any member function, you can also implement member functions of class templates as an inline function inside the class declaration. For example:
template <typename T>
class Stack {
…
void push (T const& elem) {
elems.push_back(elem); // append copy of passed elem
}
…
};
3.2 Use of Class Template Stack
To use an object of a class template, you must specify the template arguments explicitly. The following example shows how to use the class template Stack<>:
// basics/stack1test.cpp
#include <iostream>
#include <string>
#include <cstdlib>
#include "stack1.hpp"
int main()
{
try {
Stack<int> intStack; // stack of ints
Stack<std::string> stringStack; // stack of strings
// manipulate int stack
intStack.push(7);
std::cout << intStack.top() << std::endl;
// manipulate string stack
stringStack.push("hello");
std::cout << stringStack.top() << std::endl;
stringStack.pop();
stringStack.pop();
}
catch (std::exception const& ex) {
std::cerr << "Exception: " << ex.what() << std::endl;
return EXIT_FAILURE; // exit program with ERROR status
}
}
By declaring type Stack<int>, int is used as type T inside the class template. Thus, intStack is created as an object that uses a vector of ints as elements and, for all member functions that are called, code for this type is instantiated. Similarly, by declaring and using Stack<std::string>, an object that uses a vector of strings as elements is created, and for all member functions that are called, code for this type is instantiated.
Note that code is instantiated only for member functions that are called. For class templates, member functions are instantiated only when they are used. This, of course, saves time and space. It has the additional benefit that you can instantiate a class even for those types that cannot perform all the operations of all the member functions, as long as these member functions are not called. As an example, consider a class in which some member functions use the operator < to sort elements. If you refrain from calling these member functions, you can instantiate the class template for types for which operator < is not defined.
In this example, the default constructor, push(), and top() are instantiated for both int and strings. However, pop() is instantiated only for strings. If a class template has static members, these are instantiated once for each type.
An instantiated class template’s type can be used just like any other type. You can qualify it with const or volatile, or derive array and reference types from it. You can even use it as a type parameter when building another template type:
void foo (Stack<int> const& s) // parameter s is int stack
{
Stack<int> istack[10]; // istack is array of 10 int stacks
…
}
By using a type definition, you can make using a class template more convenient:
typedef Stack<int> IntStack;
void foo (IntStack const& s) // s is stack of ints
{
IntStack istack[10]; // istack is array of 10 stacks of ints
…
}
Note that in C++ a type definition defines a “type alias” rather than a new type. Thus, after the type definition
typedef Stack<int> IntStack;
IntStack and Stack<int> are the same type and can be used for and assigned to each other.
Template arguments may be any type, such as pointers to floats or even stacks of ints:
Stack<float*> floatPtrStack; // stack of float pointers
Stack<Stack<int> > intStackStack; // stack of stack of ints
The only requirement is that any operation that is called is possible according to this type.
Note that you have to put whitespace between the two closing template brackets. If you don’t do this, you are using operator >>, which results in a syntax error:
Stack<Stack<int>> intStackStack; // ERROR: >> is not allowed
3.3 Specializations of Class Templates
You can specialize a class template for certain template arguments. Similar to the overloading of function templates (see page 15), specializing class templates allows you to optimize implementations for certain types or to fix a misbehavior of certain types for an instantiation of the class template. However, if you specialize a class template, you must also specialize all member functions. Although it is possible to specialize a single member function, once you have done so, you can no longer specialize the whole class.
To specialize a class template, you have to declare the class with a leading template<> and a specification of the types for which the class template is specialized. The types are used as a template argument and must be specified directly following the name of the class:
template<>
class Stack<std::string> {
…
};
For these specializations, any definition of a member function must be defined as an “ordinary” member function, with each occurrence of T being replaced by the specialized type:
void Stack<std::string>::push (std::string const& elem)
{
elems.push_back(elem); // append copy of passed elem
}
Here is a complete example of a specialization of Stack<> for type std::string:
// basics/stack2.hpp
#include <deque>
#include <string>
#include <stdexcept>
#include "stack1.hpp"
template<>
class Stack<std::string> {
private:
std::deque<std::string> elems; // elements
public:
void push(std::string const&); // push element
void pop(); // pop element
std::string top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}
};
void Stack<std::string>::push (std::string const& elem)
{
elems.push_back(elem); // append copy of passed elem
}
void Stack<std::string>::pop ()
{
if (elems.empty()) {
throw std::out_of_range
("Stack<std::string>::pop(): empty stack");
}
elems.pop_back(); // remove last element
}
std::string Stack<std::string>::top () const
{
if (elems.empty()) {
throw std::out_of_range
("Stack<std::string>::top(): empty stack");
}
return elems.back(); // return copy of last element
}
In this example, a deque instead of a vector is used to manage the elements inside the stack. Although this has no particular benefit here, it does demonstrate that the implementation of a specialization might look very different from the implementation of the primary template.2
3.4 Partial Specialization
Class templates can be partially specialized. You can specify special implementations for particular circumstances, but some template parameters must still be defined by the user. For example, for the following class template
template <typename T1, typename T2>
class MyClass {
…
};
the following partial specializations are possible:
// partial specialization: both template parameters have same type
template <typename T>
class MyClass<T,T> {
…
};
// partial specialization: second type is int
template <typename T>
class MyClass<T,int> {
…
};
// partial specialization: both template parameters are pointer types
template <typename T1, typename T2>
class MyClass<T1*,T2*> {
…
};
The following example shows which template is used by which declaration:
MyClass<int,float> mif; // uses MyClass<T1,T2>
MyClass<float,float> mff; // uses MyClass<T,T>
MyClass<float,int> mfi; // uses MyClass<T,int>
MyClass<int*,float*> mp; // uses MyClass<T1*,T2*>
If more than one partial specialization matches equally well, the declaration is ambiguous:
MyClass<int,int> m; // ERROR: matches MyClass<T,T>
// and MyClass<T,int>
MyClass<int*,int*> m; // ERROR: matches MyClass<T,T>
// and MyClass<T1*,T2*>
To resolve the second ambiguity, you can provide an additional partial specialization for pointers of the same type:
template <typename T>
class MyClass<T*,T*> {
…
};
For details, see Section 12.4 on page 200.
3.5 Default Template Arguments
For class templates you can also define default values for template parameters. These values are called default template arguments. They may even refer to previous template parameters. For example, in class Stack<> you can define the container that is used to manage the elements as a second template parameter, using std::vector<> as the default value:
// basics/stack3.hpp
#include <vector>
#include <stdexcept>
template <typename T, typename CONT = std::vector<T> >
class Stack {
private:
CONT elems; // elements
public:
void push(T const&); // push element
void pop(); // pop element
T top() const; // return top element
bool empty() const { // return whether the stack is empty
return elems.empty();
}
};
template <typename T, typename CONT>
void Stack<T,CONT>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}
template <typename T, typename CONT>
void Stack<T,CONT>::pop ()
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::pop(): empty stack");
}
elems.pop_back(); // remove last element
}
template <typename T, typename CONT>
T Stack<T,CONT>::top () const
{
if (elems.empty()) {
throw std::out_of_range("Stack<>::top(): empty stack");
}
return elems.back(); // return copy of last element
}
Note that we now have two template parameters, so each definition of a member function must be defined with these two parameters:
template <typename T, typename CONT>
void Stack<T,CONT>::push (T const& elem)
{
elems.push_back(elem); // append copy of passed elem
}
You can use this stack the same way it was used before. Thus, if you pass a first and only argument as an element type, a vector is used to manage the elements of this type:
template <typename T, typename CONT = std::vector<T> >
class Stack {
private:
CONT elems; // elements
…
};
In addition, you could specify the container for the elements when you declare a Stack object in your program:
// basics/stack3test.cpp
#include <iostream>
#include <deque>
#include <cstdlib>
#include "stack3.hpp"
int main()
{
try {
// stack of ints:
Stack<int> intStack;
// stack of doubles which uses a std::deque<> to mange the elements
Stack<double,std::deque<double> > dblStack;
// manipulate int stack
intStack.push(7);
std::cout << intStack.top() << std::endl;
intStack.pop();
// manipulate double stack
dblStack.push(42.42);
std::cout << dblStack.top() << std::endl;
dblStack.pop();
dblStack.pop();
}
catch (std::exception const& ex) {
std::cerr << "Exception: " << ex.what() << std::endl;
return EXIT_FAILURE; // exit program with ERROR status
}
}
With
Stack<double,std::deque<double> >
you declare a stack for doubles that uses a std::deque<> to manage the elements internally.
3.6 Summary
• A class template is a class that is implemented with one or more type parameters left open.
• To use a class template, you pass the open types as template arguments. The class template is then instantiated (and compiled) for these types.
• For class templates, only those member functions that are called are instantiated.
• You can specialize class templates for certain types.
• You can partially specialize class templates for certain types.
• You can define default values for class template parameters. These may refer to previous template parameters.