Template 1

1.1 generic programming

First, let's add two numbers

int Add(int x, int y)
{
	return x + y;
}

double Add(double x, double y)
{
	return x + y;
}
char Add(char x, char y)
{
	return x + y;
}

Although function overloading can be implemented, there are several disadvantages:

1. Overloaded functions only have different types, and the reuse rate of code is relatively low. As long as new types appear, corresponding functions need to be added
2. The maintainability of the code is relatively low. An error may occur in all overloads

It can be seen that the above functions only have different variable types, and the others are the same. Then you can design a template, give the template a certain type every time you use it, and then generate the corresponding code and call the function to realize the function.

In view of this situation, C + + proposes generic programming
Generic programming: writing generic code independent of type is a means of code reuse. Templates are the foundation of generic programming.

1.2 function template

1.2.1 function template concept

The function template represents a function family. The function template is independent of type and is parameterized when used. The specific function of the function is generated according to the actual parameter type

1.2.2 function template format

template<typename T1, typename T2,...,typename Tn>
Return value type function name (parameter list) {}

template<class T> //Template parameter list -- parameter type
T Add(T x, T y)
{
	return x + y;
}

class is the keyword used to define template parameters. You can also use typename

1.2.3 instantiation of function template

Principle of formwork:
In the compiler compilation stage, for the use of template functions, the compiler needs to deduce and generate functions of corresponding types according to the input argument types for calling. For example, when using the function template with double type, the compiler determines T as double type through the argument type, and then generates a code specially dealing with double type, which is the same for character type.

When a function template is used with different types of parameters, it is called instantiation of the function template. Template parameter instantiation can be divided into implicit instantiation and explicit instantiation.

1. Implicit instantiation: let the compiler deduce the actual type of template parameters according to the actual parameters

2. Explicit instantiation: specify the actual type of template parameter in < > after the function name

template<class T>
T Add(T x, T y)
{
	return x + y;
}

int main()
{
	int a = 10, b = 20;
	double c = 1, d = 2;
	//implicit instantiation 
	cout << Add(a, b) << endl;
	cout << Add(c, d) << endl;
	//Different types cannot be passed directly
	//cout << Add(a, c) << endl;
	//But there are two ways
	//1. Cast type
	cout << Add(a, (int)c) << endl;
	//2. Explicitly instantiate and directly specify the template type
	//If the types do not match, the compiler will attempt implicit type conversion. If the conversion fails, the compiler will report an error.
	cout << Add<int>(a, c) << endl;
	return 0;
}

If the types do not match, the compiler will attempt implicit type conversion. If the conversion fails, the compiler will report an error.

1.2.4 matching principle of template parameters

1. A non template function can exist simultaneously with a function template with the same name, and the function template can also be instantiated as the non template function.
2. For non template functions and function templates with the same name, if other conditions are the same, the non template function will be called first during transfer, and an instance will not be generated from the template. If the template can produce a function with a better match, the template will be selected

// An addition function that deals specifically with int
int Add(int left, int right)
{
	return left + right;
}
// General addition function
template<class T1, class T2>
T1 Add(T1 left, T2 right)
{
	return left + right;
}
void Test()
{
	Add(1, 2); // It exactly matches the non function template type and does not require function template instantiation
	Add(1, 2.0); // The template function can generate a more matching version, and the compiler generates a more matching Add function according to the arguments
}

1. Template functions do not allow automatic type conversion, but ordinary functions can perform automatic type conversion

Type 1.3 formwork

1.3.1 definition format of class template

template<class T1, class T2, ..., class Tn>
class template name
{
//Intra class member definition
};

// Class template
// Stack class name
// Stack < T > type
template<class T>
class Stack
{
public:
	Stack(int capacity = 4)
		:_top(0)
		, _capacity(capacity)
	{
		_a = new T[capacity];
	}

	~Stack()
	{
		delete[] _a;
		_a = nullptr;
		_capacity = _top = 0;
	}

	void Push(const T& x);

private:
	T* _a;
	int _top;
	int _capacity;
};
// Note: when the functions in the class template are defined outside the class, the template parameter list needs to be added
template<class T>
void Stack<T>::Push(const T& x)
{
	// ...
}

When the functions in the class template are defined outside the class, the template parameter list needs to be added

1.3.2 instantiation of class template

Class template instantiation is different from function template instantiation. Class template instantiation needs to be followed by < >, and then put the instantiated type in < >. The class template name is not a real class, but the instantiation result is a real class.
Class instantiation must be explicit and cannot be implicit.

int main()
{
	//This class can be instantiated into various types
	Stack<int> st1;     // Store int
	Stack<double> st2;  // Store double
	Stack<char> st3;
	Stack<int*> st4;

	st1.Push(1);
	st1.Push(2);
	st1.Push(3);

	return 0;
}

2, STL

2.1 what is STL

STL (Standard Template Library): it is an important part of C + + standard library. It is not only a reusable component library, but also a software framework including data structures and algorithms.

2.2 STL six components

STL has six components, but it mainly includes three parts: container, algorithm and iterator.

1. Containers: used to manage a collection of objects of a certain type. Various data structures, such as vector, list, deque, set and map, are used to store data. From the implementation point of view, STL container is a class template.
2. Algorithms: used to process elements in an object set. Various commonly used algorithms, such as sort, find, copy, and for_each. From the perspective of implementation, STL algorithm is a function template.
3. Iterators: used to traverse elements of a collection of objects. It acts as the glue between container and algorithm. There are five types. From the implementation point of view, iterator is a class template that overloads pointer related operations such as operator *, operator - >, operator + +, operator -. All STL containers come with their own iterators. Only the designer of the container knows how to traverse its own elements. A native pointer is also an iterator.
4. Imitation function: the behavior is similar to the function, which can be used as a strategy of the algorithm. From an implementation point of view, a functor is a class or class template that overloads operator().
5. Adapter: something used to decorate a container or an interface to an emulator or iterator.
6. Space configurator: responsible for space configuration and management. From the perspective of implementation, the configurator is a class temp that implements dynamic space configuration, space management and space release.