529-实现C++STL的vector(结合空间配置器)

骑猪看日落 2022-09-10 13:21 53阅读 0赞

**类模板 =》 实现一个C++ STL里面的一个顺序容器 vector 向量容器（底层是数组，内存是连续的，2倍扩容**

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**容器的空间配置器allocator 做四件事情 内存开辟/内存释放 对象构造/对象析构**

## 如果我们不使用空间配置器，仅仅是实现普通的vector类 ##

我们定义一个测试类

class Test
    {
        
    public:
    	Test() {
         cout << "Test()" << endl; }
    	~Test() {
         cout << "~Test()" << endl; }
    	Test(const Test&) {
         cout << "Test(const Test&)" << endl; }
    };

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
现在只是定义了一个vector，没有push过元素。  
但是运行一下  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
**一个空容器，竟然构造了10个Test对象，出作用域析构的时候，析构了10个Test对象。**  
但是目前我们就定义了一个空容器，没有放任何东西，为什么要构造这么多对象出来？  
因为我们在vector的构造函数中使用了new操作了，不仅仅开辟了空间，还在每个内存空间上构造了对象，这对象不是我们想要的，如果我们传了1000，只是定义了容器，但是又构造了1000次，析构1000次，这不合理！！！  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]  
**我们在构造时需要把内存开辟和对象构造分开处理！！！**  
**当我定义容器对象的时候**，底层应该只是负责开辟空间而已，不能去构造对象的！  
**析构的时候**，不能直接用delete，delete相当于数组的每个元素都当做有效对象去析构了，我们应该怎么操作？数组可能很长，但是里面可能只有几个元素，![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
我们应该是在容器不需要的时候，把里面的有效元素析构掉，然后把整个数组的内存释放掉。析构函数应该是析构容器有效的元素，然后释放\_first指针指向的堆内存。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]

**当我们添加对象**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]

按道理来说，push\_back应该是容器只开辟了内存，没有在内存上构造对象，当执行push\_back的时候，这里的t1,t2,t3相当于在容器底层的某一块内存上构造新对象。但是现在不是这样，现在生成容器的时候底层是用new，相当于容器的每个内存空间都放了一个Test对象，相当于是把t1,t2,t3去给Test对象赋值，这个逻辑不正确！！！  
对于pop\_back，这个容器底层的对象很可能有占用外部资源，而现在的pop\_back只是把last指针减减了而已，这个外部资源很可能找不到了，被下次push\_back的新的指针覆盖了。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
![在这里插入图片描述][5fba69969bd74575839ffb0b4652d42a.png]

而且我们还不能用delete去释放它， 因为delete不仅仅析构对象和外部资源，还把这个数组的内存空间给free掉了。

vec.pop_back();//只需要析构对象。要把对象的析构和内存释放分离开

**在内存管理中，我们不能直接用new和delete**

## 实现C++STL的vector(结合空间配置器) ##

**容器的空间配置器allocator 做四件事情 内存开辟/内存释放 对象构造/对象析构**

#include <iostream>
    using namespace std;
    
    //定义容器的空间配置器，和C++标准库的allocator实现一样
    template<typename T>
    struct Allocator//模板类 struct定义 默认公有的 
    {
        
    	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 destroy(T* p)//负责对象析构
    	{
        
    		p->~T();//~T()代表了T类型的析构函数  p指向的对象的析构 
    	}
    };
    
    /*
    容器底层内存开辟，内存释放，对象构造和析构，都通过allocator空间配置器来实现
    */
    template<typename T, typename Alloc = Allocator<T>>//初始化，让用户不用指定，用默认的 
    class vector
    {
        
    public:
    	vector(int size = 10)//构造函数 
    	{
        
    		//需要把内存开辟和对象构造分开处理
    		//_first = new T[size];
    		_first = _allocator.allocate(size);
    		_last = _first;
    		_end = _first + size;
    	}
    	~vector()//析构函数 
    	{
        
    		//析构容器有效的元素，然后释放_first指针指向的堆内存
    		//delete[]_first;
    		for (T* p = _first; p != _last; ++p)
    		{
        
    			_allocator.destroy(p);//把_first指针指向的数组的有效元素进行析构操作
    		}
    		_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 *this;
    
    		//delete[]_first;
    		for (T* p = _first; p != _last; ++p)
    		{
        
    			_allocator.destroy(p);//把_first指针指向的数组的有效元素进行析构操作
    		}
    		_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(const T& val)//向容器末尾添加元素
    	{
        
    		if (full())
    			expand();
    		//*_last++ = val;   _last指针指向的内存构造一个值为val的对象
    		_allocator.construct(_last, val);
    		_last++;
    	}
    	void pop_back()//从容器末尾删除元素
    	{
        
    		if (empty())
    			return;
    		//--_last; //不仅要把_last指针--，还需要析构删除的元素
    		--_last;
    		_allocator.destroy(_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;//指向数组起始的位置
    	T* _last; //指向数组中有效元素的后继位置
    	T* _end;//指向数组空间的后继位置
    	Alloc _allocator;//定义容器的空间配置器对象
    
    	void expand()//容器的二倍扩容
    	{
        
    		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 = _first + size;
    		_end = _first + 2 * size;
    	}
    };
    
    class Test
    {
        
    public:
    	Test() {
         cout << "Test()" << endl; }
    	~Test() {
         cout << "~Test()" << endl; }
    	Test(const Test&) {
         cout << "Test(const Test&)" << endl; }
    };
    int main()
    {
        
    	Test t1, t2, t3;
    	cout << "-------------------" << endl;
    	vector<Test> vec;
    	vec.push_back(t1);
    	vec.push_back(t2);
    	vec.push_back(t3);
    	cout << "-------------------" << endl;
    	vec.pop_back();//只需要析构对象。 要把对象的析构和内存释放分离开  delete
    	cout << "-------------------" << endl;
    
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/1eb3575cd2ea4aaa8ad0a9ecaafec81b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/238b534297154acea91e79bdfb24be58.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/221cc2227db642e48c2ad61693094452.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_17_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/0f18c94489bb488fb4cc070d433f885d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/216e5c97b9b04ee8a1c9c9a0722a96bd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/b081e52417664d5c98e001a0e1f70bdc.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/829456e209a04da3a93733191d23616f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/eff98ab023c449e0b8d02529342f9a34.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220829/52e647e582ca4fa3bbf108ff9687b26b.png
[5fba69969bd74575839ffb0b4652d42a.png]: /images/20220829/150ecc518b394900aff54c95246bf59d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220829/00b69f1365e1408883e105e40ad8a1d2.png