11. function template, class template, implementation vector sequence container, and space adapter

//  Declaration of template 
template<typename T> 
bool compare(T a, T b)
{
    
	return a>b;
}

int main()
{
    
	compare<int>(20,30);
	// Template argument deduction ！
	compare(20,30);
}

The compiler takes the function name as an ordinary function first , If you can't find it , Just consider a function template ！：
compare (“aaa”,“bbb”);

Templates cannot be separated from file definitions （ A file definition , A file uses ）！ Because compilation produces symbols , No symbols found while linking , There is an error ！ So the template code is usually placed in the header file .h In the definition of ！ If I want to separate in another cpp What about file definitions ？
In another cpp Write possible instantiation types in the file ： Be similar to
template bool compare(int,int);
template bool compare(double,double);

Class template

// Implement stack container 
template<typename T>
class SeqStack // Template name + Type parameter list = Class name 
{
    
public:
	// Constructors and destructors don't need to add <T>, In other places where the template appears, you need to add the type parameter list 
	SeqQueue(int size=10)
		:_pstack(new T[size])
		,_top(0)
		,_size(size)
	{
    }
	~SeqQueue()
	{
    
		delete[] _pstack;
		_pstack=nullptr;
	}
	SeqQueue(const SeqQueue<T>& stack)
		:_top(stack._top)
		,_size(stack._size)
	{
    
		_pstack = new T[_size];
		// Do not use memcpy Copy （ If it is an object, it cannot be used ）
		for(int i=0;i<_top;++i)
		{
    
			_pstack[i] = stack._pstack[i];
		}
	}
	SeqStack<T>& operqtor=(const SeqStack<T>& stack)
	{
    
		if(this == &syack)
			return *this;
		delete[] _pstack;
		_top=stack._top;
		_size=stack._size;
		_pstack=new T[_size];
		for(int i=0;i<_top;++i)
		{
    
			_pstack[i] = stack._pstack[i];
		}
	}

	void push(const T& val)
	{
    
		if(full())
		{
    
			expand();
		}
		_pstack[top++]=val;
	}
	void pop()
	{
    
		if(empty())
			return;
		--_top;
	}
	T top() const
	{
    
		if(empty())
		{
    
			throw "stack is empty!";
		}
		return _pstack[top-1];
	}
	bool full() const
	{
    
		return _top == _size;
	}
	bool empty() const
	{
    
		return _top == 0;
	}
private:
	T* _pstack;
	int _size;
	int _top;
	// Bottom array of sequential stack 2 Double expansion 
	void expand()
	{
    
		T* ptmp = new T[_size*2];
		for(int i=0;i<_top;++i)
		{
    
			ptmp[i] = _pstack[i];
		}
		delete[] _pstack;
		_pstack = ptmp;
		_size *= 2;
	}
};

//vector
template<typename T>
{
    
public:
	vector(int size=10)
	{
    
		_first=new T[size];
		_last=_first;
		_end=_first+size;
	}
	~vector()
	{
    
		delete[] _first;
		_first = _last = _end = nullptr;
	}
	vector(const vector<T>& rhs)
	{
    
		int size=rhs._end - rhs._first;
		_first=new T[size];
		int len = rhs._last - rhs._first;
		for(int i=0;i<len;++i)
		{
    
			_first[i] = rhs._first[i];
		}
		_last = _first+len;
		_end = _first+size;
	}
	vector<T>& operator= (const vector<T>& rhs)
	{
    
		if(this == &rhs)
			return ;
		delete[] _first;
		int size = rhs._end - rhs._first;
		_first=new T[size];
		int len = rhs._last - rhs._first;
		for(int i=0;i<len;++i)
		{
    
			_first[i] = rhs._first[i];
		}
		_last = _first+len;
		_end = _first+size;
		return *this;
	}
	void push_back(T& val)
	{
    
		if(full())
			expand();
		*_last=val;
		_last++;
	}
	void pop_back()
	{
    
		if(empty())
			return ;
		--_last;
	}
	// Returns the value at the end of the container 
	T back()const
	{
    
		return *(_last-1);
	}
	bool full()const
	{
    
		return _last == _end;
	}
	bool empty()const
	{
    
		return _first == _last;
	}
	int size()const
	{
    
		return _last - _first;
	}
private:
	T* _first;// Point to the starting position of the array 
	T* _last;// Points to the subsequent position of a valid element in the array 
	T* _end;// Points to the subsequent position of the array space 
	void expand()//2 Double expansion 
	{
    
		int size = _end - _first;
		T* ptmp = new T[2*size];
		for(int i=0;i<size;i++)
		{
    
			ptmp[i] = _first[i];
		}
		delete[] _first;
		_first = ptmp;
		_last = _fist + size;
		_end = _first + size*2;
	}
}

The above code is missing a space adapter ！

class Test
{
    
public:
	Test(){
    cout << "Test()" << endl;}
	~Test(){
    cout << "~Test()" << endl;}
};
// This time, there are many constructions and destructions ！ Because of self realization vector The internal implementation is new Out of the space 
// But we think the container is empty , But in fact, there is already a default size It's an object ！ unreasonable ！
vector<Test> vec;
// So in pop_back when , The internal implementation is to move the pointer , This will cause the object memory not to be freed !
// We need to improve ,pop_back You need to free memory ！

Introducing a space adapter ！
allocator Do four things ： Memory development / Memory free 、 Object construction / Object deconstruction

template<typename T>
struct Allocator
{
    
	// Responsible for memory development 
	T* allocate(size_t size)
	{
    
		return (T*)malloc(sizeof(T)*size);
	}
	// Responsible for memory release ！
	void deallocate(void* p)
	{
    
		free(p);
	}
	// Responsible for object construction ！
	void construct(T* p,const T&val)
	{
    
		new(p) T(val);// location new, At the specified address （p） Deposit val
	}
	void destroy(T* p)
	{
    
		p->~T();//~T() representative T Type destructor 
	}
};

Put the above vector Code improvements ：

//vector
template<typename T,typename Alloc = Allocator<T>>
{
    
public:
	vector(int size=10,const Alloc& alloc = Allocator<T>())
		:_allocator(alloc)
	{
    
		//_first=new T[size];
		_first = _allocator.allocate(size);
		_last=_first;
		_end=_first+size;
	}
	// The effective number of elements in the destruct container , Then release _first Pointer to the heap memory 
	~vector()
	{
    
		//delete[] _first;
		for(T* p=_first;p!=_last;++p)
		{
    
			// hold _first Destruct the valid elements of the array pointed to by the pointer 
			_allocator.destory(p);
		}
		_allocator.deallocate(_first);
		_first = _last = _end = nullptr;
	}
	vector(const vector<T>& rhs)
	{
    
		int size=rhs._end - rhs._first;
		//_first=new T[size];
		_first = _allocator.allocate(size);
		int len = rhs._last - rhs._first;
		for(int i=0;i<len;++i)
		{
    
			//_first[i] = rhs._first[i];
			_allocator.construct(_first+i,rhs._first[i]);
		}
		_last = _first+len;
		_end = _first+size;
	}
	vector<T>& operator= (const vector<T>& rhs)
	{
    
		if(this == &rhs)
			return ;
		//delete[] _first;
		for(T* p=_first;p!=_last;++p)
		{
    
			// hold _first Destruct the valid elements of the array pointed to by the pointer 
			_allocator.destory(p);
		}
		_allocator.deallocate(_first);
		
		int size=rhs._end - rhs._first;
		//_first=new T[size];
		_first = _allocator.allocate(size);
		int len = rhs._last - rhs._first;
		for(int i=0;i<len;++i)
		{
    
			//_first[i] = rhs._first[i];
			_allocator.construct(_first+i,rhs._first[i]);
		}
		_last = _first+len;
		_end = _first+size;
		return *this;
	}
	void push_back(T& val)
	{
    
		if(full())
			expand();
		//*_last=val;
		//_last++;
		_allocator.construct(_last,val);
		_last++;
	}
	void pop_back()
	{
    
		if(empty())
			return ;
		--_last;
		_allocator.destroy(_last);
	}
	// Returns the value at the end of the container 
	T back()const
	{
    
		return *(_last-1);
	}
	bool full()const
	{
    
		return _last == _end;
	}
	bool empty()const
	{
    
		return _first == _last;
	}
	int size()const
	{
    
		return _last - _first;
	}
private:
	T* _first;// Point to the starting position of the array 
	T* _last;// Points to the subsequent position of a valid element in the array 
	T* _end;// Points to the subsequent position of the array space 
	Alloc _allocator;// Define the space adapter object of the container ！
	void expand()//2 Double expansion 
	{
    
		int size = _end - _first;
		//T* ptmp = new T[2*size];
		T* ptmp = _allocator.allocate(2*size);
		for(int i=0;i<size;i++)
		{
    
			//ptmp[i] = _first[i];
			_allocator.construct(ptmp+i,_first[i]);
		}
		//delete[] _first;
		for(T* p=_first;p!=_last;++p)
		{
    
			_allocator.destroy(p);
		}
		_allocator.deallocate(_first)
		_first = ptmp;
		_last = _fist + size;
		_end = _first + size*2;
	}
}