3.1 Implementation of Class Template Stack

Ru-Brd

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 T s, 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 this ^[1] :

^[1] According to the standard, there are some exceptions to this rule (see Section 9.2.3 on page 126). However, to be sure, you should always write the full type when the type is required.

 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      }   }; 

Ru-Brd