C++ templates and template specialization, template extensions and smart pointers —— (14)

Template

Concept

The function of the template is to realize the common type and reduce the redundancy of the code
Templates can define different types of versions for an algorithm

Implementation mechanism:

Copy code uses type parameters to break through type restrictions and lose certain type safety
Templates need to be instantiated before they can be used, instantiation is done by the compiler

Classification of templates

function template
A function template is a function with type parameters. The return value of the function, formal parameters, and local variables can all use type parameters. Function templates support type inference (formal parameters).
rust copy code function template —–> instantiation —–> function
compile

Class Template

A class template is a class with type parameters, member variables of the class, member functions… You can use type parameters, and class templates do not support type inference.
rust copy code class template —–> instantiation —–> class —–> instantiation —–> object
compile run

Use of templates

Function Template

grammar:
arduino copy code//declaration of function template
templatetype parameter/…>
return value type function template name (parameter list)
{
…// can use T as type
}

//Call of the function template
function template name (arguments);
//If the type parameter of the function template can be judged by the actual parameter, the passed type can be omitted

practise:
Use function templates to sort an array and achieve universal array element types
arduino copy code void mysort(int *arr,int n);

class template
grammar:
arduino copy code//declaration of class template
template type parameter/…>
class class template name {
//…class can use T type directly
};

// use of class template
class template name object;
// class template does not support type inference

template specialization
If the behavior of some special types of templates needs to be redefined, template specialization can be performed at this time.
Specializations of function templates
grammar:
arduino copy code template <>
return value type function template name (parameter list)
{
// …redefines the behavior of the specialized type
}

//When the compiler instantiates the function template, if there is a specialized template, the limited selection of the specialized template is instantiated
//Function templates are not allowed to specialize some parameters, they must be fully specialized

Specialization of a class template (full class specialization)
grammar:
arduino copy code template <>
class class template name {
// the contents of the …class redefine the behavior of the bit specialization type
};

practise:
implement a specialization of const char * for the sort class template
member specialization of a class template
For a class template, it is possible to specialize the whole class, or specialize only part of the member functions related to the specialized type. When the member function is specialized, the specialized interface must be consistent with the original general template.
grammar:
arduino copy code//Member specialization outside the class
template <>
return value type class template name :: member function name (parameter list)
{
// …redefining the behavior of the function using a specialized type
}

local specialization of a class template
For a class template with multiple type parameters, only some of the parameters can be specialized, and the compiler will give priority to the version with the highest degree of specialization.
Specialize some parameters
arduino copy code template
class xxx{…}

// local specialization
template
class xxx{…}

template
class xxx{…}

xxx a; —— select the third version for instantiation
xxx b; ——- choose the second version for instantiation
xxx c; —— select the first version for instantiation

// For class templates with multiple type parameters, some parameters can be specialized
// The compiler gives priority to the version with the highest degree of specialization

Relationships Between Specialized Type Parameters
arduino copy code template
class xxx{…}

// local specialization
template
class xxx{…}

template
class xxx{…}

//For class templates with multiple type parameters, the relationship of type parameters can be specialized
// The compiler gives priority to the version with the highest degree of specialization

Specializations for Pointer and Array Types
arduino copy code template
class xxx{…}

// local specialization

template
class xxx{…}

template
class xxx{…}

// For class templates with multiple type parameters, specialization can be performed for pointer and array types
// The compiler gives priority to the version with the highest degree of specialization

Assignment:

1. Use function templates and class templates (function objects) to implement binary search, and at the same time realize the specialization of const char * for function templates, and implement the specialization of const char * members (search member functions) for class templates.

Default values for template parameters, non-type parameters and template parameters

Default values for template parameters

1. The parameters of the class template can have default values, and the type parameters with default values must be on the right
  If the instantiation does not provide the type of the parameter, the default value is used
2. The default value of the type parameter on the right can be the type parameter on the left

Non-type parameters of class templates

1. Class templates can receive non-type parameters
2. Non-type parameters can only be constants, constant expressions, and constant attribute variables
3. Non-type parameters can also have default values
4. Function templates can also receive non-type parameters and default values

The following understanding is ok, the actual development may not be used

Template parameters for templates

In addition to receiving type parameters and non-type parameters, templates can also receive templates as parameters. The syntax is as follows:

template <template <typename T> class xxx>
class Crab{
    //... You can use parameter class templates, and the incoming templates remain uniform
};

Template members

Templates can be used as class templates or members/friends of classes, and the implementation of STL uses this syntax

1. Class template members
    The type parameters of a class template instantiation can come from an external class template, or can be specified directly.

2. Function template members
    The type of function template instantiation can come from an external class template or be specified directly, and type inference is also supported
    
3. Function templates and class templates as friends
    If the friend uses the type parameter of the class template it belongs to, it is a constrained friend template
    Otherwise it is an unconstrained friend template

Inheritance of class templates

Class inheritance class template

grammar:

template <typename T>
class BaseA{
public:
    //...
private:
    T data;
};

// class inheritance class template
class Derived: public BaseA<int>{
    //...
};

Class template inheritance class

grammar:

class BaseA{
public:
    //...
private:
    int data;
};

// class template inheritance class
template <typename T>
class Derived: public BaseA{
public:
    //.....
private:
    T data2;
};

Class template inherits class template

grammar:

template <typename T>
class BaseA{
public:
    //...
private:
    T data;
};

// class template inherits class template
template <typename N>
class Derived: public BaseA<N>{
public:
    //.....
private:
    N data2;
};

Using template parameters in inheritance

grammar:

template <typename T>
class Derived: public T{
    //...
};

Recursive instantiation of templates

The so-called recursive instantiation of the template is to use the class template instantiation as a parameter to continue instantiating the template

MyArray<int> arr;
MyArray<MyArray<int>> arr;//Recursive instantiation
MyArray<MyArray<MyArray<int>>> arr;//Recursive instantiation

Division of templates

In actual C++ development, we will write the class declaration (template declaration) in the header file, and the function implementation in the class/class template in the source file. Since the instantiation of the template is completed at compile time, Therefore, the declaration and implementation of the template must be written in a compilation unit. At this time, it is necessary to use the division of the template to achieve.

The implementation can be added in the header file of the template declaration with the following syntax

#include "xxx.cpp"

Exercise:

The class template of 1search.cpp realizes the division of templates.

class A{
public:
    void show()
    {
        cout<<"show A"<<endl;
    }
};

int main()
{
    A *pa = NULL;
    
    pa->show();
}

Note: You can use the null pointer of the class type to call the member function, because the member function does not belong to the object, nor is it stored in the object, but stored in the code segment. To call the member function, you only need to find the address of the member function. If a member variable is accessed in a member function, a segmentation fault will occur.

Smart pointer

Templating the pointer object realizes the generalization of the type and constitutes a smart pointer.

According to the different processing of smart pointer copy/assignment, it can be divided into three implementation forms

1. Allocate a new address space when copying/assigning, and copy the content pointed by the original pointer
2. When copying/assigning, pass the space and address on the right to the left, and the right will lose the original address space
3. Share the address space when copying/assigning, and increase a reference count at the same time (record the number of objects using the address space)
  Free address space when reference technology is 0

C ++ predefines smart pointers, which can be used directly. There are 4 types of smart pointers, and 3 of them are introduced. To use them, you need to add the header file memory

//C++98 added C++11 deprecated C++17 removed
auto_ptr ------- Use method 2 to achieve (only one object can record the address space)

// C++11 added
unique_ptr ------ method 2 implementation, forbidden to transfer syntax
shared_ptr ------ method 3 implementation, using reference counting

When the smart pointer object is destroyed, it will automatically release the recorded address space, which largely avoids the occurrence of memory leaks.

Assignment:

The code of the template member realizes the division of the template

Additional: The user enters two strings, and writes code to find the longest common substring of the two strings

kkkhellowebye
ghsasabyehellod

===>hello

/*02-Find the longest common substring*/
#include <iostream>
?
using namespace std;
?
// violent solution
string getLCS(const string & amp; str1, const string & amp; str2)
{
    //Record the starting position and length of the longest substring in str1
    size_t max_start = 0, max_len = 0;
?
    for(size_t i=0;i<str1. length();i ++ ){
        for(size_t j=0;j<str2.length();j++){
            //Calculate the current longest common substring
            size_t k,l;
            for(k=i,l=j;k<str1.length() & &l<str2.length();k++,l++){
                if(str1.at(k)!=str2.at(l))
                    break;
            }
            //Record the longest common substring
            if(k-i>max_len){
                max_len = k-i;
                max_start = i;
            }
?
        }
    }
?
    return str1.substr(max_start,max_len);
}
?
//Matrix method to solve
string getLCS1(const string & amp; str1, const string & amp; str2)
{
    //Record the end position and length of the longest substring in str1
    int max_end = 0,max_len = 0;
?
    // create comparison matrix
    int **arr = new int *[str1. length()];
    for(size_t i=0;i<str1. length();i ++ ){
        arr[i] = new int[str2. length()];
        for(size_t j=0;j<str2.length();j++){
            //Compare characters and write the comparison result into the matrix
            if(str1.at(i)==str2.at(j)){//Assign upper left corner + 1
                //if the upper left corner does not exist
                if(i==0||j==0)
                    arr[i][j] = 1;
                else
                    arr[i][j] = arr[i-1][j-1] + 1;
?
                //Record the longest length and the position of the last character in str1 at this time
                if(arr[i][j]>max_len){
                    max_len = arr[i][j];
                    max_end = i;
                }
            }
            else {
                arr[i][j] = 0;
            }
        }
    }
?
    // release space
    for(size_t i=0;i<str1. length();i ++ ){
        delete[] arr[i];
    }
    delete[] arr;
?
    // return the longest common substring
    return str1.substr(max_end-max_len + 1,max_len);
}
?
int main()
{
    string str1 = "kkkhelaaloweyebye";
    string str2 = "kkkhelaaloweyebye111";
?
    cout<<getLCS(str1,str2)<<endl;
    cout<<getLCS1(str1,str2)<<endl;
?
    return 0;
}
?
?
?