{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "slideshow": {
     "slide_type": "skip"
    }
   },
   "outputs": [],
   "source": [
    "#include <vector>\n",
    "#include <iostream>\n",
    "#include <stdexcept> // stdexcept header contains runtime_error\n",
    "#include <deque>\n",
    "using namespace std; "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Templates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Intro\n",
    "\n",
    "- Function templates enable you to conveniently specify a variety of related (overloaded) functions - called **function-template specializations**.\n",
    "- Class templates enable you to conveniently specify a variety of related classes - called **class-template specializations**.\n",
    "- Programming with templates is known as **generic programming**.\n",
    "- Function templates and class templates are like stencils out of which we trace shapes\n",
    "    - function-template specializations and class-template specializations are like the separate tracings that all have the same shape, but could, for example, be drawn in different colors , line thickneses and textures."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Class Templates\n",
    "\n",
    "- Class templates are called **parameterized types**\n",
    "    - They require one or more type parameters to specify how to customize a generic class template to form a class-template specialization.\n",
    "    - When a particular specialization is needed, you use a concise, simple notation, and the compiler writes the specialization source code.    \n",
    "- Class templates encourage software reusability by enabling a variety of type-specific class template specializations to be instantiated from a single class template."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Class Templates: Example"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "template<typename T>\n",
    "class Stack {\n",
    "public:\n",
    "    // return the top element of the Stack\n",
    "    const T& top() {\n",
    "        return stack.front();\n",
    "    }\n",
    "    // push an element onto the Stack\n",
    "    void push(const T& value);\n",
    "    \n",
    "    // pop an element from the stack\n",
    "    void pop() {\n",
    "        stack.pop_front();\n",
    "    }\n",
    "private:\n",
    "    deque<T> stack; // internal representation of the Stack    \n",
    "};\n",
    "\n",
    "template<typename T>\n",
    "void Stack<T>::push(const T& value) {\n",
    "    stack.push_front(value);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Class Templates: Syntax\n",
    "\n",
    "- The class-template definition looks like a conventional class definition, with a few key differences.\n",
    "```c++\n",
    "template <typename T>\n",
    "```\n",
    "    - Class templates begin with `template` followed by a list of template parameters enclosed in angle brackets (< and >).\n",
    "    - Each template parameter that represents a **type** must be preceded by either of the interchangeable keywords `typename` or `class`.\n",
    "    - `T` acts as a placeholder for the element type.\n",
    "        - Can be any valid identifier\n",
    "    - Type parameters names must be **unique** inside a template definition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Class Templates: Member Functions\n",
    "\n",
    "- The member-function definitions of a class template are **function templates**\n",
    "    - but are not preceded with the template keyword and template parameters in angle brackets (< and >) when they're defined within the class template's body.\n",
    "- They do use the class template's template parameter `T` to represent the element type.\n",
    "- `Animal` class template does not define it's own constructors\n",
    "    - the default constructor provided by the compiler will invoke the `vector` default constructor."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Outside Declaration of Class Template's Member Functions\n",
    "\n",
    "- Member-function definitions can appear outside a class template definition.\n",
    "- If so, each must begin with `template` followed by the **same set of template parameters** as the class template.\n",
    "- In addition, the member functions must be **qualified with the class name and scope resolution operator**.\n",
    "\n",
    "```c++\n",
    "template <typename T>\n",
    "void Stack<T>::push(const T& p) {\n",
    "    stack.push_front(p);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack top element is Q\n",
      "Stack top element is P\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "    Stack<char> s;\n",
    "    s.push('P');\n",
    "    s.push('Q');\n",
    "    \n",
    "    cout << \"Stack top element is \" << s.top() << endl;\n",
    "    s.pop();\n",
    "    cout << \"Stack top element is \" << s.top() << endl;    \n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack top element is 20\n",
      "Stack top element is 10\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "    Stack<int> s;\n",
    "    s.push(10);\n",
    "    s.push(20);\n",
    "    \n",
    "    cout << \"Stack top element is \" << s.top() << endl;\n",
    "    s.pop();\n",
    "    cout << \"Stack top element is \" << s.top() << endl;    \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Nontype Parameters\n",
    "\n",
    "- Class template `Stack` used only a type parameter in its template declaration.\n",
    "- It's also possible to use **nontype template parameters**, which can have default arguments and are treated as constants.\n",
    "- For example, the C++ standard’s array class template begins with the template declaration:\n",
    "```c++\n",
    "template <class T, size_t N>\n",
    "```    \n",
    "    - Recall that keywords class and typename are **interchangeable** in template declarations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Nontype Parameters: Example\n",
    "\n",
    "- A declaration creates a 100-element array of doubles class-template specialization, then uses it to instantiate the object `fixeSizeArray`.\n",
    "\n",
    "```c++\n",
    "// doulbe fixeSizeArray[100];\n",
    "std::array<double, 100> fixeSizeArray; \n",
    "```\n",
    "\n",
    "- The array class template encapsulates a **built-in array**.\n",
    "- When you create an array class-template specialization, the array's built-in array data member has the type and size specified in the declaration."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "template <typename T, size_t N>\n",
    "class FixedStack {\n",
    "public:\n",
    "    // return the top element of the Stack\n",
    "    const T& top() {\n",
    "        return stack.front();\n",
    "    }\n",
    "    // push an element onto the Stack\n",
    "    void push(const T& value) {\n",
    "        if (stack.size() < N)\n",
    "            stack.push_front(value);\n",
    "        else\n",
    "            throw runtime_error{\"Stack is full\"};\n",
    "    }\n",
    "    // pop an element from the stack\n",
    "    void pop() {\n",
    "        stack.pop_front();\n",
    "    }\n",
    "private:\n",
    "    deque<T> stack; // internal representation of the Stack    \n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Added 'A' to stack\n",
      "Added 'B' to stack\n"
     ]
    },
    {
     "ename": "Standard Exception",
     "evalue": "Stack is full",
     "output_type": "error",
     "traceback": [
      "Standard Exception: Stack is full"
     ]
    }
   ],
   "source": [
    "{\n",
    "    FixedStack<char, 2> s;\n",
    "    s.push('A'); cout << \"Added 'A' to stack\" << endl;\n",
    "    s.push('B'); cout << \"Added 'B' to stack\" << endl;    \n",
    "    s.push('C'); cout << \"Added 'C' to stack\" << endl;\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Default Arguments for Template Type Parameters\n",
    "\n",
    "- In addition, a type parameter can specify a **default type argument**.\n",
    "- For example, the C++ standard's stack container adapter class template begins with:\n",
    "```c++\n",
    "template <typename T, class S, class Container = deque<T>>\n",
    "```\n",
    "- which specifies that a stack uses a `deque` by default to store the stack's elements of type `T`.\n",
    "\n",
    "- **Default type parameters** must be the **rightmost** (trailing) parameters in a template's type-parameter list.\n",
    "    - When you instantiate a template with two or more default arguments, if an omitted argument is not the rightmost, then all type parameters to the right of it also must be omitted.\n",
    "    - As of C++11, you can now use default type arguments for template type parameters in function templates."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "template <typename T, class Container=deque<T>>\n",
    "class CustomStack {\n",
    "public:\n",
    "    // return the top element of the Stack\n",
    "    const T& top() {\n",
    "        return stack.back();\n",
    "    }\n",
    "    // push an element onto the Stack\n",
    "    void push(const T& value) {\n",
    "        stack.push_back(value);\n",
    "    }\n",
    "    // pop an element from the stack\n",
    "    void pop() {\n",
    "        stack.pop_back();\n",
    "    }\n",
    "private:\n",
    "    Container stack; // internal representation of the Stack    \n",
    "};"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack top element is P\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "    CustomStack<char> s;\n",
    "    s.push('P');\n",
    "    cout << \"Stack top element is \" << s.top() << endl;\n",
    "    s.pop();\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Stack top element is P\n"
     ]
    }
   ],
   "source": [
    "{\n",
    "    CustomStack<char, vector<char>> s;\n",
    "    s.push('P');\n",
    "    cout << \"Stack top element is \" << s.top() << endl;\n",
    "    s.pop();\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Overloading Function Templates\n",
    "\n",
    "- When overloaded functions perform **identical** operations on **different** types of data, they can be expressed more compactly and conveniently using function templates.\n",
    "- You can then write function calls with different types of arguments and let the compiler generate separate **function-template specializations** to handle each function call appropriately.\n",
    "- The function-template specializations generated from a given function template all have the same name, so the compiler uses overload resolution to invoke the proper function."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Overloading Function Templates (cont.)\n",
    "\n",
    "- You may also **overload** function templates.\n",
    "- For example, you can provide other function templates that specify the **same** function name but **different** function parameters.\n",
    "- A function template also can be overloaded by providing nontemplate functions with the same function name but different function parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "template <typename T> \n",
    "T mymax(T x, T y) { \n",
    "   return (x > y) ? x : y; \n",
    "} "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mymax(10, 20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "slideshow": {
     "slide_type": "fragment"
    }
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'a'"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mymax('a', '2')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## Matching Process for Overloaded Functions\n",
    "- The compiler performs a matching process to determine what function to call when a function is invoked.\n",
    "- It looks at both existing functions and function templates to locate a function or generate a function-template specialization whose function name and argument types are consistent with those of the function call.\n",
    "- If there are no matches, the compiler issues an error message. If there are multiple matches for the function call, the compiler attempts to determine the best match.\n",
    "- If there's more than one best match, the call is ambiguous and the compiler issues an error message."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "C++14",
   "language": "C++14",
   "name": "xcpp14"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "14"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}