C++ vector类的模拟实现

vector和string虽然底层都是通过顺序表来实现的,但是他们利用顺序表的方式不同,string是指定好了类型,通过使用顺序表来存储并对数据进行操作,而vector是利用了C++中的泛型模板,可以存储任何类型的数据,并且在vector中,并没有什么有效字符和容量大小的说法,底层都是通过迭代器进行操作的,迭代器底层实现也就是指针,所以说,vector是利用指针对任何顺序表进行操作的。
C++ vector类的模拟实现

vector属性

  1. _start用于指向第一个有效元素
  2. _finish用于指向最后一个有效元素的下一个位置
  3. _endOfStorage用于指向已经开辟了的空间的最后一个位置的下一个位置
  4. vector的迭代器是原生态T*迭代器
template<class T> class Vector { public: 	typedef T* iterator; 	typedef const T* const_iterator;  private: 	iterator _start; 	iterator _finish; 	iterator _endOfStorage; }; 

构造函数

  1. 无参默认构造函数,将所有属性都置空
  2. 以n个val初始化的构造函数,先开辟n个空间,再将这些空间的值都置为val,并更新_finish和_endOfStorage的位置
  3. 通过迭代器传参初始化的构造函数,使用新的迭代器,通过尾插将数据插入到新的空间

使用新的迭代器的原因是使传入的迭代器可以是任意类型的,如果使用Vector的迭代器,那么传入的迭代器的类型只能和Vector的类型一样,这里拿string举例,创建一个char类型的Vector,Vector,但是传入的迭代器并不是char类型的,可以是字符数组的迭代器或者是string的迭代器。只要通过解引用是char类型就可以

//无参默认构造 	Vector() 		:_start(nullptr) 		,_finish(nullptr) 		,_endOfStorage(nullptr) 	{}  	//n个val的构造函数 	Vector(int n, const T& val = T()) 		:_start(new T[n]) 		,_finish(_start +n) 		,_endOfStorage(_finish) 	{ 		for (int i = 0; i < n; ++i) 		{ 			_start[i] = val; 		} 	}  	//通过迭代器产生的构造函数 	template<class InputIterator> 	Vector(InputIterator first, InputIterator last) 		:_start(nullptr) 		, _finish(nullptr) 		, _endOfStorage(nullptr) 	{ 		while (first != last) 		{ 			pushBack(*first); 			++first; 		} 	} 

运行结果在begin() 和end()实现中

size()和capacity()

指针相减得到的值就是这两个指针之间的元素个数

	size_t size() const 	{ 		return _finish - _start; 	}  	size_t capacity() const 	{ 		return _endOfStorage - _start; 	} 
C++ vector类的模拟实现

pushBvoid pushBack(const T& val) { //检查容量 if (_finish == _endOfStorage) { size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity(); reserve(newC); } //插入数据 *_finish = val; //更新finish ++_finish }

运行结果在begin() 和end()实现中

reserve

  1. 检查n的合理性,reserve只能扩大不能缩小空间
  2. 保存有效元素的个数,用于后面更新_finish使用
  3. 申请空间并将数据拷贝到新的空间中,释放旧的空
  4. 更新3个成员变量,注意_finish不能更新为_finish+size(),原因是size()是通过两指针运算得出来的,此时的_fiinsh已经指向了释放的空间,再去使用会出错,所以这也是有第二步的原因

以下代码存在浅拷贝问题,文章末尾会给出正确深拷贝代码和详细解释

	void reserve(size_t n) 	{ 		//reserve只能扩大空间不能缩小空间 		if (n > capacity()) 		{ 			//保存有效元素 			size_t sz = size(); 			//申请空间 			T* tmp = new T[n]; 			//将数据拷贝到新的空间 			if (_start != nullptr) 			{ 				//拷贝有效元素 				memcpy(tmp, _start, sizeof(T) * size()); 				delete[] _start; 			} 			//更新 			_start = tmp; 			_finish = _start + sz; 			_endOfStorage = _start + n; 		} 	} 

运行结果在begin() 和end()实现中

begin() 和end()

	iterator begin() 	{ 		return _start; 	}  	iterator end() 	{ 		return _finish; 	}  	const_iterator begin() const 	{ 		return _start; 	}  	const_iterator end() const 	{ 		return _finish; 	} 

C++ vector类的模拟实现
有了begin()和end就可以使用范围for

template<class T> void printVectorFor(Vector<T>& vec) { 	for (auto& e : vec) 	{ 		cout << e; 	} 	cout << endl; } 
C++ vector类的模拟实现

[]运算符重载

	T& operator[](size_t pos) 	{ 		assert(pos < size()); 		return _start[pos]; 	}  	const T& operator[](size_t pos) const 	{ 		assert(pos < size()); 		return _start[pos]; 	} 
C++ vector类的模拟实现

resize()

  1. n <= size 直接更新_finish的位置即可
  2. size < n <= capacity,从_finish开始补充元素,补充到_start+n的位置,然后执行第一步
  3. n > capacity 增容,执行第二和第一步
	void resize(size_t n, const T& val = T()) 	{ 		//3.n >= capacity 		if (n > capacity()) 		{ 			reserve(n); 		} 		//2.size < n <= capacity 		if (n > size()) 		{ 			while (_finish != _start + n) 			{ 				*_finish = val; 				++_finish; 			} 		} 		//1.n<=size 		_finish = _start + n; 	} 
C++ vector类的模拟实现

insert()

  1. 检查插入的位置的有效性[_start, _finish)
  2. 检查容量,由于增容会导致pos迭代器失效,所以我们可以先保存pos对于_start的偏移量offset,增容后,再将pos重新赋值pos=_start+offset
  3. 移动元素,从后往前移动,最后将pos位置的元素置为val
  4. 更新_finish
void insert(iterator pos, const T& val) 	{ 		//检查位置有效性 		assert(pos >= _start || pos < _finish); 		//检查容量 		if (_finish == _endOfStorage) 		{ 			//增容会导致迭代器失效 			//保存pos和_start的偏移量 			size_t offset = pos - _start; 			size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity(); 			reserve(newC); 			//更新pos 			pos = _start + offset; 		} 		//移动元素 		iterator end = _finish; 		while (end != pos) 		{ 			*end = *(end - 1); 			--end; 		} 		//插入 		*pos = val; 		//更新 		++_finish; 	} 
C++ vector类的模拟实现

erase()

  1. 检查位置有效性
  2. 移动元素,从前向后移动
  3. 更新_finish
	iterator erase(iterator pos) 	{ 		//检查位置有效性 		assert(pos >= _start || pos < _finish); 		//移动元素,从前往后 		iterator start = pos + 1;  		while (start != _finish) 		{ 			*(start - 1) = *start; 			++start; 		} 		//更新 		--_finish; 	} 
C++ vector类的模拟实现

void popBack()

利用erase接口进行尾删

	void popBack() 	{ 		if (size() > 0) 			erase(end() - 1); 	} 
C++ vector类的模拟实现

析构函数

	~Vector() 	{ 		if (_start) 		{ 			delete[] _start; 			_start = _finish = _endOfStorage = nullptr; 		} 	} 

算法库中的find

头文件<algorithm>

template <class InputIterator, class T>    InputIterator find (InputIterator first, InputIterator last, const T& val) 

参数内容(从迭代器的begin起到end中,找到val值,找到返回该值所在的迭代器,找不到返回end)

C++ vector类的模拟实现

reserve的深浅拷贝问题

当我门使用自定义类型时,使用浅拷贝是效率最高的,但是当我们使用自定义类型时,并且存在内存资源的利用,就必须时刻注意存在的深浅拷贝问题。来看以下代码测试

void test() { 	Vector<string> v; 	string str1 = "123"; 	string str2 = "456"; 	string str3 = "789"; 	v.pushBack(str1); 	v.pushBack(str2); 	v.pushBack(str3); } 

调试结果:
C++ vector类的模拟实现
当我们在插入第三个字符串时,就发生了内存异常的问题,我们来看看到底是什么问题。
第一次插入str1,没有问题
C++ vector类的模拟实现
第二次插入str2,插入之前我们会扩容,会创建2倍大的空间tmp,然后通过memcpy内存拷贝(浅拷贝)将内容拷贝到tmp中,此时就有两个指向指向一个资源(123),拷贝完后delete[]要删除原有空间,将123释放后,其实现在新的空间的第一个元素指向的是一个已经释放了的空间,但是问题并没有暴露出来,第二个元素的插入也没有问题
C++ vector类的模拟实现
第三次str3的插入,这次插入也会进行扩容,会先开辟一个2倍大的空间tmp,然后通过memcpy内存拷贝(浅拷贝)将内容拷贝到tmp中,此时有两个指针指向已经释放的资源(123),有两个指针指向资源(456),当拷贝完成后会释放旧的空间,当释放原指针指向的(456)时不会报错,原因和第二次插入原因一样。但是释放原有空的第一个指针时,就会发生内存报错异常,原因是资源(123)已经被释放了,如果再释放就属于二次释放,是不安全的。内存错误就报异常。
C++ vector类的模拟实现
所以我们在扩容的时候不应该只是单纯的浅拷贝,也就是使用memcpy来拷贝内容,我们应该要使用深拷贝。将memcpy改为for (size_t i = 0; i < sz; ++i){tmp[i] = _start[i];}
整体代码如下:

	void reserve(size_t n) 	{ 		//reserve只能扩大空间不能缩小空间 		if (n > capacity()) 		{ 			//保存有效元素 			size_t sz = size(); 			//申请空间 			T* tmp = new T[n]; 			//将数据拷贝到新的空间 			if (_start != nullptr) 			{ 				//拷贝有效元素 				//memcpy(tmp, _start, sizeof(T) * size()); 				//深拷贝 				for (size_t i = 0; i < sz; ++i) 				{ 					//调用自定义类型的赋值运算符重载函数,完成深拷贝 					//前提是该重载函数也是深拷贝,string是STL库中,是被深拷贝处理过 					tmp[i] = _start[i]; 				} 				delete[] _start; 			} 			//更新 			_start = tmp; 			_finish = _start + sz; 			_endOfStorage = _start + n; 		} 	} 

版权声明:玥玥 发表于 2021-04-05 8:29:47。
转载请注明:C++ vector类的模拟实现 | 女黑客导航