Function Templates and Class Templates

Templates can implement parametric polymorphism, which parameterizes the types of objects that programs process, enabling a single program to handle multiple different types of objects.

Function Templates

The purpose of function templates is simply to avoid repetitive writing of functions that only differ in the data types they handle, greatly improving code reusability and thus enhancing software development efficiency.

The syntax form adds the statement template<template parameter list> before the function definition

Contents of the template parameter list:

Type parameters: class (or typename) identifier
Constant parameters: type specifier identifier
Template parameters: template class identifier

Example:

//Universal absolute value function
template<typename T>
T abs(T x){
  return x>0 ? x : -x;
}

Function templates are fundamentally different from functions

Function templates themselves do not generate any object code at compile time; only instances of function templates generate object code.
Function templates referenced by multiple source files need to be placed in header files along with the function body, not just the declaration like ordinary functions.
Function pointers can only point to instances of function templates, not to function templates.

Class Templates

Using class templates allows you to define a pattern for a class, enabling certain data members, parameters of certain member functions, return values, or local variables in the class to take any type.

The declaration method of class templates is the same as function templates,

//Define member functions outside the class template
template<模板参数表>
类型名 类名<模板参数标识符列表>::函数名(参数表)
{
  ...
}

//Use template class to define objects
模板名<模版参数类型>对象名1,...,对象名n;

Linear Groups

Linear groups, as the name suggests, have elements whose positions correspond to their positional relationships. They can be classified into direct access, sequential access, and indexed access. Direct access means jumping directly to the position that needs to be accessed without following order, while sequential access can only access from the beginning according to the element arrangement order.

Direct Access Groups - Array Class

Required to design a variable-length array, click to view source code, and list some syntax points to note.

Syntax rules state that “=”, “[ ]”, “( )”, “->” can only be overloaded as member functions, and the “=” operator function in derived classes will always hide the “=” operator in the base class.

If we want to use Array class objects like ordinary arrays in programs, we need to overload the pointer conversion operator.

Role of Pointer Conversion Operator

To explain the necessity of overloading the pointer conversion operator, let’s first look at the following program:

#include<iostream>
using namespace std;
void read (int *p, int n)
{
  for (int i=0;i<n;i++）
        cin>>p[i];
}

int main()
{
  int a[10];
    read(a,10);
    return 0;
}

Here, the first parameter of the read function is an int pointer, and the array name a is an int address constant, so the types match exactly. If we want to use Array class objects like ordinary arrays in programs, modify the main function as follows:

int main ()
{
  Arrays<int> a(10);
    read(a,10);
    return 0;
}

What will happen? This time when calling read, it will be found that the actual parameter type is different from the formal parameter type. At this point, the compilation system will attempt automatic type conversion: converting the object name to int * type. Since a is a custom type object, the automatic conversion function provided by the compilation system cannot implement this conversion, so we need to write our own overloaded pointer type conversion function. In C++, if you want to implicitly or explicitly convert an object of custom type T to type S, you can define operator S as a member function of T. This way, when converting a T type object implicitly to S type, or using static_cast to explicitly convert to S type, this member function will be called. The overloaded function of the conversion operator does not need to specify the return value type, because in this case the return type of the overloaded function is consistent with the operator name, so the C++ standard stipulates that return value types cannot be specified for such functions (and void should not be written). When the object itself is a constant, to avoid modifying array content through pointers, the object can only be converted to a constant pointer.

The way to overload the pointer conversion operator in this Array class is as follows:

template<class T>
Array<T>::operator T *()  //不用写返回值的类型
{
  return list;//First address of the array
}

Sequential Access Groups - Linked List Class

// LinkedList.h
#ifndef LINKEDLIST_H 
#define LINKEDLIST_H
#include "Node.h"
template <class T>
class LinkedList
{
private:
    Node<T> *front, *rear;      //Head and tail pointers
    Node<T> *prevPtr, *currPtr; //Pointers recording current traversal position in the list, updated by insert and delete operations
    int size;                   //Number of elements in the list
    int position;               //Position index of current element in the list. Used by reset function
    //Generate new node with data field item and pointer field ptrNext
    Node<T> *newNode(const T &item, Node<T> *ptrNext = NULL);
    void freeNode(Node<T> *p); //Free node
    //Copy linked list L to current list (assuming current list is empty), called by copy constructor and operator =
    void copy(const LinkedList<T> &L);

public:
    LinkedList();                                     //Constructor
    LinkedList(const LinkedList<T> &L);               //Copy constructor
    ~LinkedList();                                    //Destructor
    LinkedList<T> &operator=(const LinkedList<T> &L); //Overloaded assignment operator
    int getSize() const;                              //Return number of elements in linked list bool isEmpty() const; //Whether linked list is empty
    void reset(int pos = 0);                          //Initialize cursor position
    void next();                                      //Move cursor to next node
    bool endOfList() const;                           //Whether cursor has reached end of list
    int currentPosition() const;                      //Return current cursor position
    void insertFront(const T &item);                  //Insert node at head
    void insertRear(const T &item);                   //Add node at tail
    void insertAt(const T &item);                     //Insert node before current node
    void insertAfter(const T &item);                  //Insert node after current node
    T deleteFront();                                  //Delete head node
    void deleteCurrent();                             //Delete current node
    T &data();                                        //Return reference to current node member data
    const T &data() const;                            //Return const reference to current node member data
    //Clear linked list: free memory space of all nodes. Called by destructor and operator=
    void clear();
}
#endif // LINKEDLIST_H 
//Linked list class template function implementation code can be downloaded from the internet

Basic operations of linked lists:

Generate linked list
Insert nodes
Search nodes
Delete nodes
Traverse linked list
Clear linked list

Stack Class

Stack class template implementation, click to view source code.

Stack elements can actually be represented using arrays or linked lists.

Basic operations of stacks:

Initialize
Push
Pop
Clear stack
Access top element
Check stack status (full, empty)

Queue Class

Designed as a circular queue using arrays, which is quite troublesome for additions and deletions. Actually, I think using linked lists wouldn’t require circular implementation.

Click here to view source code