C++:vector增删查改模拟实现

我会带着你远行 2024-02-17 12:28 44阅读 0赞

#### C++:vector增删查改模拟实现 ####

*  前言
 *  一、迭代器
 *   *  1.1 非const迭代器：begin()、end()
     *  1.2 const迭代器：begin()、end()
 *  二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现
 *   *  2.1 构造函数
     *   *  2.1.1 无参构造
         *  2.1.2 迭代器区间构造
         *  2.1.3 n个值构造
     *  2.2 拷贝构造
     *  2.3 赋值重载
     *  3 析构函数
 *  三、容量相关：capacity()、size()、reserve()、resize()
 *   *  3.1 capacity()
     *  3.2 size()
     *  3.3 reserve()
     *  3.4 resize()
 *  四、operator\[ \]重载
 *  五、元素相关：insert、erase、push\_back、pop\_back
 *   *  5.1 insert()
     *  5.2 erase()
     *   *  5.2.1 erase迭代器失效
     *  5.3 push\_bach()
     *  5.4 pop\_back()
 *  六、所有代码

--------------------

## 前言 ##

提前在这说明下，vector增删查改模拟实现的成员变量博主采用**SGI版本**。下面给出其库中成员变量是哪些，后续的模拟实现都基于此。

![在这里插入图片描述][62245629e3044f5a9a531c72ce09aae0.png]  
我们发现库中定义了3个T\*的变量。同时3个成员变量的意义如下：

![在这里插入图片描述][147b230ea39c4df2aa72bf02a5cff95e.png]

## 一、迭代器 ##

### 1.1 非const迭代器：begin()、end() ###

typedef T* iterator;
    
    iterator begin()
    {
        
    	return _start;
    }
    
    iterator end()
    {
        
    	return _finish;
    }

### 1.2 const迭代器：begin()、end() ###

typedef const T* const_iterator;
    
    const_iterator begin()const
    {
        
    	return _start;
    }
    
    const_iterator end()const
    {
        
    	return _finish;
    }

## 二、构造函数、拷贝构造函数、赋值重载、析构函数模拟实现 ##

### 2.1 构造函数 ###

我们先来看看[vector库中的构造][vector]类型如下：  
![在这里插入图片描述][55f3056995a0458ebb5001c76c11c573.png]  
我们知道有三种构造方式，下面给出各种的实现方式。

#### 2.1.1 无参构造 ####

vector()
    		:_start(nullptr)
    		,_finish(nullptr)
    		, _endofstorage
    	{
        }

#### 2.1.2 迭代器区间构造 ####

template<class InputIterator>//使用模板是为了，当数据类型匹配时就可以使用
    vector(InputIterator first, InputIterator last)
    {
        
    	while (first != last)
    	{
        
    		push_back(*first);
    		first++;
    	}
    }

#### 2.1.3 n个值构造 ####

vector(size_t  n, const T& value = T())
    {
        
    	reserve(n);
    	for (size_t i = 0; i < n; i++)
    	{
        
    		push_back(value);
    	}
    }
    
    //防止定义vector<int>这种类型走迭代区间的构造函数，我们在多实现一个以下类型函数
    //当使用vector<int>类型的去构造时，此时调用的构造函数两个参数都是int。所有他会走最匹配的函数，即迭代器区间构造生成的构造函数，程序会出错。
    //而下面给出了现成的最匹配构造函数，编译器调用时就不会走模板。
    vector(int n, const T& value = T())
    {
        
    	reserve(n);
    	for (size_t i = 0; i < n; i++)
    	{
        
    		push_back(value);
    	}
    }

### 2.2 拷贝构造 ###

拷贝构造我们先调用开好一块空间，在依次插入数据即可。

//vector(const vector& x) //库中实现模式, 直接使用类名。但C++，类型不是类名。
    //这里各位读者了解下这里直接类名做类型也正确即可，但不建议各位这样做。
    vector(const vector<T>& v)
    {
        
    	reserve(v.capacity());//后面会给出实现
    	for (auto& e : v)
    	{
        
    		push_back(e);
    	}
    }

### 2.3 赋值重载 ###

赋值重载这里我们不要传引用，而是直接传参即可。编译器调用拷贝构造生成形参后，在调用swap()函数依次交换形参和this即可。

//赋值重载
    void swap(vector<T>& v)
    {
        
    	std::swap(_start, v._start);
    	std::swap(_finish, v._finish);
    	std::swap(_endofstorage, v_endofstorage);
    }
    
    vector<T>& operator= (vector<T> tmp)
    {
        
    	swap(tmp);
    	return *this;
    }

### 3 析构函数 ###

~vector()
    {
        
    	delete[] _start;
    	_start = _finish = _endofstorage = nullptr;
    }

## 三、容量相关：capacity()、size()、reserve()、resize() ##

### 3.1 capacity() ###

size_t capacity()const
    {
        
    		return _endofstorage - _start;
    }

### 3.2 size() ###

size_t size()const
    {
        
    	return _finish - _start;
    }

### 3.3 reserve() ###

由于stl中我们一般不缩容，所以先判断reserve的空间大小是否比当前空间容量大。  
如果reserve的空间更大，所以我们需要先开好目标大小的空间，在将原数据拷贝过去，最后析构原来空间即可。  
但下面这两种实现方式对吗？

第一种：

void reserve(size_t n)
    {
        
    	if (n > capacity())
    	{
        
    		T* tmp = new T[n];
    		if (_start)//如果原来空间有数据，拷贝到新空间
    		{
        
    			memcpy(tmp, _start, sizeof(T) * size());
    			delete[] _start;
    		}
    		//更新_start、_finish、_endofstorage。指向新空间中相应位置
    		_start = tmp;
    		_finish = _start + size();
    		_endofstorage = _start + n;
    	}
    }

先说结论：上诉这段代码是错的。  
在我们调试后会发现\_finish的值没有更新。（这里大家自行验证下接口）  
   
原因：(win11画图一直很模糊，博主也很无奈，各位将就看吧)  
![在这里插入图片描述][a17e4e7878f043aa852fc9d5ae6eb941.png]

--------------------

第二种：  
为了解决上诉问题，我们可以先记录\_finish和\_start的偏移量，用来代替size()函数。  
所以初学者很容易写出以下代码：

void reserve(size_t n)
    {
        
    	if (n > capacity())
    	{
        
    		size_t sz = size();//记录_finish 和 _start 的偏移量
    		T* tmp = new T[n];
    		if (_start)
    		{
        
    			//memcpy(tmp, _start, sizeof(T) * sz);
    			delete[] _start;
    		}
    
    		_start = tmp;
    		_finish = _start + sz;//不能用size()代替sz，否则会导致迭代器失效
    		_endofstorage = _start + n;
    	}
    }

那这是否正确呢？答案是否定的。  
我们来看看下面这种场景：  
![在这里插入图片描述][b37347eba29c405288831f8f4ce1850e.png]

--------------------

实际上对于这种情况，可以自己循环依次赋值即可。内置类型直接拷贝数据；内置类型调用赋值重载，是一种深拷贝。

最终代码如下：

void reserve(size_t n)
    {
        
    	if (n > capacity())
    	{
        
    		size_t sz = size();//记录_finish 和 _start 的偏移量
    		T* tmp = new T[n];
    		if (_start)
    		{
        
    			//memcpy(tmp, _start, sizeof(T) * sz);
    			for (size_t i = 0; i < sz; i++)
    			{
        
    				tmp[i] = _start[i];
    			}
    			delete[] _start;
    		}
    
    		_start = tmp;
    		_finish = _start + sz;//不能用size()代替sz，否则会导致迭代器失效
    		_endofstorage = _start + n;
    	}
    }

### 3.4 resize() ###

resize逻辑还是很简单的。  
首先判断resize()的目标大小n和有效数据个数size()谁大。如果有效个数size()更大，只需更改\_finish即可；否则要先进行扩容（reserve会将原有数据拷贝到新空间），然后从\_finish开始向扩充的空间插入新的值。  
   
代码如下：

//const会延长匿名对象的生命周期, 匿名对象具有常性
    //模板出来后，对类进行了升级，内置类型也有构造函数
    //void resize(size_t n, T val = T())
    void resize(size_t n, const T& val = T())
    {
        
    	if (n < size())
    	{
        
    		_finish = _start + n;
    	}
    	else
    	{
        
    		reserve(n);
    		while (_finish < _start + n)
    		{
        
    			*_finish = val;
    			_finish++;
    		}
    	}
    }

## 四、operator\[ \]重载 ##

T& operator[](size_t pos)
    {
        
    	assert(pos < size());
    	return _start[pos];
    }
    
    const T& operator[](size_t pos)const
    {
        
    	assert(pos < _finish);
    	return _start[pos];
    }

## 五、元素相关：insert、erase、push\_back、pop\_back ##

### 5.1 insert() ###

任意位置插入数据，首先需判断是否需要扩容。然后将插入位置pos开始往后的数据向后移动，最后将新数据插入到pos处即可。  
tips：

*  如果发生扩容，需要先记录pos和\_start之间的偏移量。在将pos位置跟新，指向新空间中对应位置。否则会导致迭代器失效

void insert(iterator pos, const T& x)
    {
        
    	assert(pos >= _start);
    	assert(pos <= _finish);
    	if (_finish == _endofstroage)
    	{
        
    		size_t len = pos - _start;
    		reserve(capacity() == 0 ? 4 : capacity() * 2);
    		pos = _start + len;
    	}
    
    	//挪动数据
    	iterator end = _finish - 1;
    	while (end >= pos)
    	{
        
    		*(end + 1) = *end;
    		end--;
    	}
    
    	//插入数据
    	*pos = x;
    	_finish++;
    }

### 5.2 erase() ###

任意位置删除数据，只需要从pos+1开始，将后续数据全部依次向前移动覆盖，最后更新\_finish即可。

iterator erase(iterator pos)
    {
        
    	assert(pos >= _start);
    	assert(pos < _finish);
    
    	iterator it = pos + 1;
    	while (it < _finish)
    	{
        
    		*(it - 1) = *it;
    		++it;
    	}
    
    	--_finish;
    
    	return pos;
    }

#### 5.2.1 erase迭代器失效 ####

void testvector4()
    {
        
    	vector<int> v;
    	v.push_back(1);
    	v.push_back(2);
    	v.push_back(2);
    	v.push_back(4);
    	v.push_back(5);
    	v.push_back(6);
    	auto it = v.begin();
    	while (it < v.end())
    	{
        
    		if (*it % 2 == 0)
    		{
        
    			v.erase(it);
    		}
    			it++;
    	}
    	for (auto e : v)
    	{
        
    		cout << e << " ";
    	}
    	cout << endl;
    }

上述代码本意是将偶数全部删除，结果本该是1 、5。但结果却是：  
![在这里插入图片描述][c9e1f915ea77472da1d5a2e16cd4de70.png]  
为什么呢？  
这是因为我们删除元素后，后续数据会补上空缺。所以当使用erase后，迭代器会失效。（上述结果是g++的实现机制，在vs2019下上述代码会直接报错。原因在于vs2019对erase后的空间做强制检查，不允许访问）。为此stl库给出的解决方案是接受删除位置的下一个元素的返回值。（这也是为什么整个模拟实现中只有erase函数具有返回值）,并接收返回值。  
   
正确删除偶数方法：

void testvector4()
    	{
        
    		//std::vector<int> v;
    		vector<int> v;
    		v.push_back(1);
    		v.push_back(2);
    		v.push_back(2);
    		v.push_back(4);
    		v.push_back(5);
    		v.push_back(6);
    		auto it = v.begin();
    		//迭代器失效
    		/*while (it < v.end())
    		{
    			if (*it % 2 == 0)
    			{
    				v.erase(it);
    			}
    				it++;
    		}*/
    
    		while (it < v.end())
    		{
        
    			if (*it % 2 == 0)
    			{
        
    				it = v.erase(it);
    			}
    			else
    			{
        
    				it++;
    			}
    		}
    
    		for (auto e : v)
    		{
        
    			cout << e << " ";
    		}
    		cout << endl;
    	}

### 5.3 push\_bach() ###

头插复用insert函数即可。

void push_back(const T& x)
    {
        
    	//if (_finish == _endofstroage)
    	//{
        
    	//	reserve(capacity() == 0 ? 4 : capacity() * 2);
    	//}
    
    	插入数据
    	//*_finish = x;
    	//_finish++;
    
    	insert(_finish, x);
    }

### 5.4 pop\_back() ###

复用erase，尾删

void pop_back()
    {
        
    	erase(--end());
    }

## 六、所有代码 ##

[vector增删查改模拟实现gitee链接][vector_gitee]

[62245629e3044f5a9a531c72ce09aae0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/62e23d152103452398306464ae354b05.png
[147b230ea39c4df2aa72bf02a5cff95e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/aca52217a0ea41a186ea0d6289e034ec.png
[vector]: https://legacy.cplusplus.com/reference/vector/vector/vector/
[55f3056995a0458ebb5001c76c11c573.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/ed6fed01becb4e0b8d95627f4d3748e7.png
[a17e4e7878f043aa852fc9d5ae6eb941.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/b950f7b660fe4f80af0be6b46e881868.png
[b37347eba29c405288831f8f4ce1850e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/7190da1e6c694f70a0d72842c7efbf46.png
[c9e1f915ea77472da1d5a2e16cd4de70.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/13740845b4e8446f8dad82046fa734d8.png
[vector_gitee]: https://gitee.com/zhenyucoder/test_c/commit/fdffa681788f484c0ccc9c85958b172970af9734