C++ vector類的模擬實現(xiàn)方法

更新時間：2021年05月01日 10:41:03 作者：WhiteShirtI

這篇文章主要介紹了C++ vector類的模擬實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

vector和string雖然底層都是通過順序表來實現(xiàn)的，但是他們利用順序表的方式不同，string是指定好了類型，通過使用順序表來存儲并對數(shù)據(jù)進行操作，而vector是利用了C++中的泛型模板，可以存儲任何類型的數(shù)據(jù)，并且在vector中，并沒有什么有效字符和容量大小的說法，底層都是通過迭代器進行操作的，迭代器底層實現(xiàn)也就是指針，所以說，vector是利用指針對任何順序表進行操作的。

在這里插入圖片描述

vector屬性

_start用于指向第一個有效元素
_finish用于指向最后一個有效元素的下一個位置
_endOfStorage用于指向已經(jīng)開辟了的空間的最后一個位置的下一個位置vector的迭代器是原生態(tài)T*迭代器

template<class T>
class Vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;

private:
	iterator _start;
	iterator _finish;
	iterator _endOfStorage;
};

構(gòu)造函數(shù)

無參默認構(gòu)造函數(shù)，將所有屬性都置空
以n個val初始化的構(gòu)造函數(shù)，先開辟n個空間，再將這些空間的值都置為val，并更新_finish和_endOfStorage的位置
通過迭代器傳參初始化的構(gòu)造函數(shù)，使用新的迭代器，通過尾插將數(shù)據(jù)插入到新的空間

使用新的迭代器的原因是使傳入的迭代器可以是任意類型的，如果使用Vector的迭代器，那么傳入的迭代器的類型只能和Vector的類型一樣，這里拿string舉例，創(chuàng)建一個char類型的Vector，Vector，但是傳入的迭代器并不是char類型的，可以是字符數(shù)組的迭代器或者是string的迭代器。只要通過解引用是char類型就可以

//無參默認構(gòu)造
	Vector()
		:_start(nullptr)
		,_finish(nullptr)
		,_endOfStorage(nullptr)
	{}

	//n個val的構(gòu)造函數(shù)
	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;
		}
	}

	//通過迭代器產(chǎn)生的構(gòu)造函數(shù)
	template<class InputIterator>
	Vector(InputIterator first, InputIterator last)
		:_start(nullptr)
		, _finish(nullptr)
		, _endOfStorage(nullptr)
	{
		while (first != last)
		{
			pushBack(*first);
			++first;
		}
	}

運行結(jié)果在begin() 和end()實現(xiàn)中

size()和capacity()

指針相減得到的值就是這兩個指針之間的元素個數(shù)

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

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

在這里插入圖片描述

pushBack()

檢查容量，如果_finish和_endOfStorage指針相等，說明容量已經(jīng)滿了，需要開辟更大的空間
在_finish位置插入新的數(shù)據(jù)
更新_finish

void pushBack(const T& val)
	{
		//檢查容量
		if (_finish == _endOfStorage)
		{
			size_t newC = _endOfStorage == nullptr ? 1 : 2 * capacity();
			reserve(newC);
		}

		//插入數(shù)據(jù)
		*_finish = val;
		//更新finish
		++_finish
	}

運行結(jié)果在begin() 和end()實現(xiàn)中

reserve

檢查n的合理性，reserve只能擴大不能縮小空間
保存有效元素的個數(shù)，用于后面更新_finish使用
申請空間并將數(shù)據(jù)拷貝到新的空間中，釋放舊的空
更新3個成員變量，注意_finish不能更新為_finish+size()，原因是size()是通過兩指針運算得出來的，此時的_fiinsh已經(jīng)指向了釋放的空間，再去使用會出錯，所以這也是有第二步的原因

以下代碼存在淺拷貝問題，文章末尾會給出正確深拷貝代碼和詳細解釋

	void reserve(size_t n)
	{
		//reserve只能擴大空間不能縮小空間
		if (n > capacity())
		{
			//保存有效元素
			size_t sz = size();
			//申請空間
			T* tmp = new T[n];
			//將數(shù)據(jù)拷貝到新的空間
			if (_start != nullptr)
			{
				//拷貝有效元素
				memcpy(tmp, _start, sizeof(T) * size());
				delete[] _start;
			}
			//更新
			_start = tmp;
			_finish = _start + sz;
			_endOfStorage = _start + n;
		}
	}

運行結(jié)果在begin() 和end()實現(xiàn)中

begin() 和end()

iterator begin()
	{
		return _start;
	}

	iterator end()
	{
		return _finish;
	}

	const_iterator begin() const
	{
		return _start;
	}

	const_iterator end() const
	{
		return _finish;
	}

在這里插入圖片描述

有了begin()和end就可以使用范圍for

template<class T>
void printVectorFor(Vector<T>& vec)
{
	for (auto& e : vec)
	{
		cout << e;
	}
	cout << endl;
}

在這里插入圖片描述

[]運算符重載

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

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

在這里插入圖片描述

resize()

n <= size 直接更新_finish的位置即可
size < n <= capacity，從_finish開始補充元素，補充到_start+n的位置，然后執(zhí)行第一步
n > capacity 增容，執(zhí)行第二和第一步

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;
	}

在這里插入圖片描述

insert()

檢查插入的位置的有效性[_start, _finish)
檢查容量，由于增容會導(dǎo)致pos迭代器失效，所以我們可以先保存pos對于_start的偏移量offset，增容后，再將pos重新賦值pos=_start+offset
移動元素，從后往前移動，最后將pos位置的元素置為val
更新_finish

void insert(iterator pos, const T& val)
	{
		//檢查位置有效性
		assert(pos >= _start || pos < _finish);
		//檢查容量
		if (_finish == _endOfStorage)
		{
			//增容會導(dǎo)致迭代器失效
			//保存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;
	}

在這里插入圖片描述

erase()

檢查位置有效性
移動元素，從前向后移動
更新_finish

iterator erase(iterator pos)
	{
		//檢查位置有效性
		assert(pos >= _start || pos < _finish);
		//移動元素，從前往后
		iterator start = pos + 1;

		while (start != _finish)
		{
			*(start - 1) = *start;
			++start;
		}
		//更新
		--_finish;
	}

在這里插入圖片描述

void popBack()

利用erase接口進行尾刪

void popBack()
	{
		if (size() > 0)
			erase(end() - 1);
	}

在這里插入圖片描述

析構(gòu)函數(shù)

~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)

參數(shù)內(nèi)容(從迭代器的begin起到end中，找到val值，找到返回該值所在的迭代器，找不到返回end)

在這里插入圖片描述

reserve的深淺拷貝問題

當我門使用自定義類型時，使用淺拷貝是效率最高的，但是當我們使用自定義類型時，并且存在內(nèi)存資源的利用，就必須時刻注意存在的深淺拷貝問題。來看以下代碼測試

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

調(diào)試結(jié)果：

在這里插入圖片描述

當我們在插入第三個字符串時，就發(fā)生了內(nèi)存異常的問題，我們來看看到底是什么問題。
第一次插入str1，沒有問題

在這里插入圖片描述

第二次插入str2，插入之前我們會擴容，會創(chuàng)建2倍大的空間tmp，然后通過memcpy內(nèi)存拷貝(淺拷貝)將內(nèi)容拷貝到tmp中，此時就有兩個指向指向一個資源(123)，拷貝完后delete[]要刪除原有空間，將123釋放后，其實現(xiàn)在新的空間的第一個元素指向的是一個已經(jīng)釋放了的空間，但是問題并沒有暴露出來，第二個元素的插入也沒有問題

在這里插入圖片描述

第三次str3的插入，這次插入也會進行擴容，會先開辟一個2倍大的空間tmp，然后通過memcpy內(nèi)存拷貝(淺拷貝)將內(nèi)容拷貝到tmp中，此時有兩個指針指向已經(jīng)釋放的資源（123），有兩個指針指向資源（456），當拷貝完成后會釋放舊的空間，當釋放原指針指向的（456）時不會報錯，原因和第二次插入原因一樣。但是釋放原有空的第一個指針時，就會發(fā)生內(nèi)存報錯異常，原因是資源（123）已經(jīng)被釋放了，如果再釋放就屬于二次釋放，是不安全的。內(nèi)存錯誤就報異常。

在這里插入圖片描述

所以我們在擴容的時候不應(yīng)該只是單純的淺拷貝，也就是使用memcpy來拷貝內(nèi)容，我們應(yīng)該要使用深拷貝。將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];
			//將數(shù)據(jù)拷貝到新的空間
			if (_start != nullptr)
			{
				//拷貝有效元素
				//memcpy(tmp, _start, sizeof(T) * size());
				//深拷貝
				for (size_t i = 0; i < sz; ++i)
				{
					//調(diào)用自定義類型的賦值運算符重載函數(shù)，完成深拷貝
					//前提是該重載函數(shù)也是深拷貝，string是STL庫中，是被深拷貝處理過
					tmp[i] = _start[i];
				}
				delete[] _start;
			}
			//更新
			_start = tmp;
			_finish = _start + sz;
			_endOfStorage = _start + n;
		}
	}

到此這篇關(guān)于C++ vector類的模擬實現(xiàn)方法的文章就介紹到這了,更多相關(guān)C++ vector類模擬內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: