13 Templates13.1 Basic Template Syntax13.2 A Template for FlexArrays13.3 Adapting a Template13.4 A Precedence Parser: Instantiation of a Template13.4.1 The Operator Class13.4.2 The Main Program13.4.3 UML for Templates13.5 The Standard Template Library13.6 Containers13.7 Iterators13.8 Using Simple STL Classes13.8.1 String13.8.2 Vector13.8.3 MapChapter 13: TemplatesTemplates are patterns. According to Merriam-Websters Unabridged dictionary:template: Something that establishes a pattern.archetype: The original model, form, or pattern from which something is made or from whichsomething develops.From a review of Effective STL : 50 Specific Ways to Improve Your Use of the Standard Template Libraryby ScottMeyers:It’s hard to overestimate the importance of the Standard Template Library: the STL can simplifylife for any C++ programmer who knows how to use it well. Ay, there’s the rub.Templates are the archetypes behind the “container” data structures whose processing methods depend only onthe structuring method and not on the type of the data contained in the structure. The C++ standard librarysupports a set of pre-defined templates that implement stacks, queues, trees, and hash tables. A programmermight use the STL templates, extend them, or define entirely new template classes.A template consists of declarations and functions with one or more type parameters or non-type parameters.Type parameters are used to represent the base type of a data structure. Non-type parameters are relativelynew in C++; they are generally integers and are used to define such things as array lengths. Both kinds ofparameters can be given default values.By itself, a template is not compilable code. Before it can be compiled, actual types must be supplied toreplace the type parameters. The replacement process is called instantiation and happens at compile time. Theresult of instantiation is a class declaration and definitions of the class functions.13.1 Basic Template SyntaxA complete class template consists of a parameterized class declaration together with all its class functions andall related functions such as an extension of operator¡¡. The entire template is written within a .hpp file becauseit is a declaration, not compilable code and all these parts must be available at compile time for instantiationby a client class.• A template declaration starts with a “template” line: the keyword template followed by angle bracketsenclosing another keyword, class, and a name for the type parameter (or parameters). It is customaryto name template parameters with single, upper-case letters. Most templates have only one parameter. Ifthere are two or more, the parameter names are separated by commas. Examples:template <class X>template <class K, class T, int n>• If a class template has remote functions or an extension for the output operator, each function (lines 32,36, 44, 51) must start with a “template” declaration like the one that begins the class declaration (line9). C++ supplies no reasonable syntax that lets us declare template <class T> once and include all theparts that are needed within its scope.• Following each template declaration is a class or function declaration with normal syntax. Within thisdeclaration, the name(s) of the type parameter(s) are used to refer to the future base type of the class.• Being part of a template declaration does not require any extra words or punctuation within the class.Specifically, we refer to the class name within this part of the code without using angle brackets.145146 CHAPTER 13. TEMPLATES• A prototype or the definition of an inline function in a template is the same as for a non-template. (Notethe definition of FlexArray::flexlen and the prototype for FlexArray::operator[].)• The definition of each remotely defined function starts with the name of the template WITH angle bracketsand the name(s) of the parameters. For example, the name of the put function is: FlexArray<T>::put• Even though operator << is not part of the class, its definition must be given as part of the template (lines32–33) because it depends on the type parameter, T.A template for a recursively-defined type. Some data structures require definition of a pair of classessuch that each class definition refers to the other class. An example is a linked list defined as a friendly pairof classes: List and Cell. The List class must have a data member of type Cell*. The Cell class must have afriendship declaration for List. This circular dependency poses no problem for a non-template declaration: bothclasses can be declared in one .hpp file, with the dependent class first, followed by the interface class.However, when we transform this pair of classes into a template pair, a difficulty arises when the compilertries to process the friend declaration. Suppose we were defining the Cell<T> template. In that definition,we must say: friend class List<T>. However, because the Cell<T> declaration comes before List<T>, thecompiler gives a fatal error comment for the friend declaration: Stack is not a template. This can be cured byadding a forward declaration, like this, at the top of the file, above the Cell<T> declaration:template <class T> class Stack; // A forward declaration for Stack<T>.Note: every reference to Cell in the List class must say Cell<T>, and every reference to List in the Cell classmust say List<T>.13.2 A Template for FlexArrays1 #ifndef FLEX2 #define FLEX3 // ==========================================================================4 // Template declaration for a flexible array of base type T.5 // A. Fischer, May 14, 2001 file: flexT.hpp6 #include "tools.hpp"7 #define FLEX_START 4 // Default length for initial array.89 template <class T>10 class FlexArray {11 protected:// ------------------------------------------------------------12 int Max; // Current allocation size.13 int N; // Number of array slots that contain data.14 T* Data; // Pointer to dynamic array of T.1516 private: // --------------------------------------------------------------17 void grow(); // Double the allocation length.1819 public: // ---------------------------------------------------------------20 FlexArray( int ss = FLEX_START ) : Max(ss), N(0), Data( new T[Max] ) {}21 ~FlexArray() { if (Data != NULL) delete[] Data; }2223 int put( T data );24 T& operator[]( int k );25 int flexlen() const { return N; }26 T* extract() { T* tmp=Data; Data=NULL; Max = N = 0; return tmp; }27 ostream& print(