四、模板编程——学习C++类库的编程基础

一、函数模板

模板不能在一个文件中定义在一个文件中使用。

模板代码调用之前，一定要看到模板定义的地方，这样的话，目标才能够进行正常的实例化，产生能够被编译器编译的代码

所以，模板代码都是放在头文件当中，然后在源文件当中直接进行#include包含

模板的非类型参数

都是常量，只能使用，不能修改

templete<typename T,int SIZE>//非类型参数
void sort(T *arr){
//排序
	for(int i=0;i<SIZE-1;i++){
		for(int j=0;i<SIZE-1-i;j++){
			if(arr[j]>arr[j+1]){
				int tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+11]=tmp;
			}
		}
	}
}

int main(){
	int arr[]={12,455,456,13,54,43};
	const int size=sizeof（arr）/sizeof(arr[0]);
	sort<int,size>(arr);//在这里使用非参数列表，后面的size是const的类型
}

二、类模板

构造和析构函数名不用加，其他出现模板的地方都加上类型参数列表

template<typename T>
class SeqStackT
{
public:

	SeqStackT(int size = 10) 
		:_top(-1),
		_size(size),
		_pstack(new T[size]) {	}

	SeqStackT(const SeqStackT& src)
		:_top(src._top),
		_size(src._top) {
		cout << this << "SeqStackT<>(const SeqStack& src)" << endl;
		_pstack = new T[src._size];
		for (int i = 0; i <= src._top; i++) {
			_pstack[i] = src._pstack[i];
		}
	}

	~SeqStackT() {
		cout << this << "~SeqStack()" << endl;
		delete[] _pstack;
		_pstack = nullptr;
	}

	SeqStackT& operator=(const SeqStackT& src) {
		cout << "operator=" << endl;
		//防止自赋值
		if (this == &src) {
			return *this;
		}
		delete[] _pstack;//需要释放掉自身占用的外部资源
		_pstack = new T[src._size];
		for (int i = 0; i <= src._top; i++) {
			_pstack[i] = src._pstack[i];
		}
		_top = src._top;
		_size = src._size;
		return *this;
	}

	void push(int val) {
		if (full()) {
			resize();
		}
		_pstack[++_top] = val;
	}

	void pop() {
		if (empty()) {
			return;
		}
		--_top;
	}

	int top() {
		return _pstack[_top];
	}

	bool empty() { return _top == -1; }
	bool full() { return _top == _size - 1; }

private:
	T* _pstack;

	int _top;

	int _size;

	void resize() {
		int* ptmp = new T[_size * 2];
		for (int i = 0; i < _size; i++) {
			ptmp[i] = _pstack[i];
		}
		delete[] _pstack;
		_pstack = ptmp;
		_size *= 2;
	}
};

三、实现vector

//
// Created by 26685 on 2022-05-15 20:33.
// Description:
//

#ifndef C___VECTORT_H
#define C___VECTORT_H

using namespace std;

template<typename T>
class VectorT {
public:
    VectorT(int size = 10) {
        _first=new T[size];
        _last=_first;
        _end=_first+size;
    }

    ~VectorT() {
        delete[] _first;
        _first = _last = _end = nullptr;
    }

    VectorT(const VectorT<T> &src) {
        int size = src._end - src._first;
        _first = new T[size];
        int len = src._last - src._first;
        for (int i = 0; i < len; i++) {
            _first[i] = src._first[i];
        }
        _last = _first + len;
        _end = _first + size;
    }

    VectorT<T> &operator=(const VectorT<T> &src) {
        if (src == *this) {
            return *this;
        }
        delete[] _first;

        int size = src._end - src._first;
        _first = new T[size];
        int len = src._last - src._first;
        for (int i = 0; i < len; i++) {
            _first[i] = src._first[i];
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }

    void push_back(T val) {
        if (full()) {
            expend();
        }
        *_last++ = val;
    }

    void pop_back() {
        if (empty()) { return; }
        _last--;
    }

    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;//表示vector起始位置

    T *_last;//表示vector定义元素的末尾

    T *_end;//表示vector的末尾

    void expend() {//size扩大两倍
        int size = _end - _first;
        T *ptmp = new T[size * 2];
        for (int i = 0; i < size; i++) {
            ptmp[i] = _first[i];
        }
        delete[] _first;
        _first = ptmp;
        _last = _first + size;
        _end = _first + (2 * size);
    }
};


#endif //C___VECTORT_H
//实现
int main() {
   
    VectorT<int> vec;
    for(int i=0;i<15;i++){
        vec.push_back(rand()%100);
    }
    while (!vec.empty()){
        cout<<vec.back()<<" ";
        vec.pop_back();
    }
    cout<<endl;
    return 0;
}

空间配置器Allocator

使用空间配置器实现vector容器：

//
// Created by 26685 on 2022-05-15 21:29.
// Description: AllocatorT.h
//
#include <cstdlib>
/**
 * 定义容器的空间配置器，和C++标准库的allocator的实现一致
 * @tparam T
 */
template<typename T>
struct AllocatorT {
    T *allocate(size_t size) {//负责内存开辟
        return (T *) malloc(sizeof(T) * size);
    }

    void deallocate(void *p) {//负责内存释放
        free(p);
    }

    void construct(T *p, const T &val) {//负责对象构造
        new(p) T(val);//定位new
    }

    void destory(T *p) {//负责对象析构
        p->~T();//析构函数
    }

};

vector类：

//
// Created by 26685 on 2022-05-15 21:29.
// Description: VectorT.h
//

#include "AllocatorT.h"

using namespace std;

/**
 * 容器底层内存开辟，内存释放，对象构造和析构都通过allocator实现
 * @tparam T
 * @tparam Alloc
 */
template<typename T, typename Alloc=AllocatorT<T> >
class VectorT {
public:
    VectorT(int size = 10) {
//        _first=new T[size];
        _first = _alloctor.allocate(size);
        _last = _first;
        _end = _first + size;
    }

    ~VectorT() {
//        delete[] _first;
        //使用allocator对vector逐个删除
        for (T *p = _first; p != _last; p++) {
            _alloctor.destory(p);
        }
        _alloctor.deallocate(_first);
        _first = _last = _end = nullptr;
    }

    VectorT(const VectorT<T> &src) {
        int size = src._end - src._first;
//        _first = new T[size];
        _first = _alloctor.allocate(size);
        int len = src._last - src._first;
        for (int i = 0; i < len; i++) {
//            _first[i] = src._first[i];
            _alloctor.contruct(_first + 1, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
    }

    VectorT<T> &operator=(const VectorT<T> &src) {
        if (src == *this) {
            return *this;
        }
        //delete[] _first;
        for (T *p = _first; p != _last; p++) {
            _alloctor.destory(p);
        }
        _alloctor.deallocate(_first);

        int size = src._end - src._first;
        _first = new T[size];
        int len = src._last - src._first;
        for (int i = 0; i < len; i++) {
//            _first[i] = src._first[i];
            _alloctor.contruct(_first + 1, src._first[i]);
        }
        _last = _first + len;
        _end = _first + size;
        return *this;
    }

    void push_back(T val) {
        if (full()) {
            expend();
        }
        //*_last++ = val;
        _alloctor.construct(_last, val);
        _last++;
    }

    void pop_back() {
        if (empty()) { return; }
        --_last;
        _alloctor.destory(_last);
    }

    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;//表示vector起始位置

    T *_last;//表示vector定义元素的末尾

    T *_end;//表示vector的末尾

    Alloc _alloctor;//负责内存管理

    void expend() {//size扩大两倍
        int size = _end - _first;
//        T *ptmp = new T[size * 2];
        T *ptmp = _alloctor.allocate(2 * size);
        for (int i = 0; i < size; i++) {
            //ptmp[i] = _first[i];
            _alloctor.construct(ptmp + i, _first[i]);
        }
        //delete[] _first;
        for (T *p = _first; p != _last; p++) {
            _alloctor.destory(p);
        }
        _alloctor.deallocate(_first);

        _first = ptmp;
        _last = _first + size;
        _end = _first + (2 * size);
    }
};

main函数实现：

#include <iostream>
#include "header/vectorT.h"

using namespace std;

struct Test {//测试类，只测试三种函数

    Test() {
        cout << "Test()" << endl;
    }

    Test(const Test& src){
        cout<<"Test(const Test& src)"<<endl;
    }

    ~Test() {
        cout << "~Test()" << endl;
    }
};

int main(){

    Test t1,t2,t3;

    cout<<"______________________"<<endl;

    VectorT<Test> vec;
    vec.push_back(t1);
    vec.push_back(t2);
    vec.push_back(t3);

    cout<<"______________________"<<endl;
    vec.pop_back();
    cout<<"______________________"<<endl;

    return 0;
}