【STL】 vector 模拟實作

    上一篇部落格說了一下list的使用，其實vector用法基本上和list是一樣的，是以此篇部落格就隻模拟實作以下vector。vector你可以把它了解成一個順序表或者數組。隻是STL裡的vector是由三個疊代器來維護的：_start(資料存放開始的位置),_finish(資料存放結束位置的下一個),_endofstorage(容量的最後一個位置)。vector裡的疊代器其實就是個指針。來看看代碼實作：

#include<iostream>
#include<vector>
using namespace std;

template<class T>
class MyVector
{
public:
	typedef T* Iterator;
	typedef const T* ConstIterator;

	MyVector(size_t n=3)      //構造函數，初始化給3個T類型容量
		:_start(new T[n]), _finish(_start), _end_of_storage(_start+n)
	{
	}
	MyVector(const MyVector<T>& v)   //拷貝構造
	{
		if (v._finish - v._start > _finish - _start)
		{
			delete[] _start;
			_start = new T[v._finish - v._start];
			_finish = _start;
		}
		for (Iterator tmp = v._start; tmp != v._finish; tmp++)
		{
			*(_finish) = *tmp;
			_finish++;
		}
		_end_of_storage = _finish;
	}
	void PushBack(const T& x)   //尾插，這裡注意，即使調用的insert裡檢查了容量，尾插函數仍需檢測
	{
		CheckCapacity();
		Insert(End(), x);
	}
	void PopBack()
	{
		Iterator pos = End();   //前置的--因為傳回的是臨時變量的值，是以不能直接對End()函數進行--
		Erase(--pos);
	}

	void Insert(Iterator pos, const T& x)
	{
		CheckCapacity();
		for (Iterator tmp = End(); tmp != pos;tmp--)
		{
			*tmp = *(tmp - 1);
		}
		*pos = x;
		_finish++;
	}

	void Erase(Iterator pos)
	{
		Iterator end = End();
		for (Iterator tmp = pos; tmp != (--end); tmp++)
		{
			*tmp = *(tmp + 1);
		}
		_finish--;
	}

	size_t Size()
	{
		return _finish - _start;
	}
	/************疊代器部分***********/
	Iterator Begin()
	{
		return _start;
	}
	Iterator End()
	{
		return _finish;
	}
	/*Iterator operator++(int)
	{
		Iterator tmp = *this;
		tmp++;
		return tmp;
	}
	Iterator& operator++()
	{
		Iterator tmp = *this;
		tmp++;
		return *this;
	}
	Iterator operator--(int)
	{
		Iterator tmp = *this;
		tmp--;
		return tmp;
	}
	Iterator& operator--()
	{
		Iterator tmp = *this;
		tmp--;
		return *this;
	}
	*/
private:
	void CheckCapacity()
	{
		if (_finish == _end_of_storage)
		{
			Iterator new_start = new T[2 * Size()];   //一次擴容原來的兩倍
			Iterator new_finish = new_start;
			for (Iterator i = Begin(); i != End(); i++,new_finish++)
			{
				*new_finish = *i;
			}
			delete[] _start;
			_start = new_start;
			_finish = new_finish;
			_end_of_storage = _start + 2 * Size();
		}
	}
private:
	Iterator _start;
	Iterator _finish;
	Iterator _end_of_storage;
};


void TestVector()
{
	MyVector<int> v;
	v.PushBack(1);
	v.PushBack(2);
	v.PushBack(3);
	v.PushBack(4);
	MyVector<int>::Iterator it;
	for (it = v.Begin(); it != v.End(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	v.PopBack();
	v.PopBack();
	for (it = v.Begin(); it != v.End(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
	MyVector<int> v1(v);
	for (it = v1.Begin(); it != v1.End(); it++)
	{
		cout << *it << " ";
	}
	cout << endl;
}
           

寫vector時，犯了好多愚蠢的錯誤：

1.因為pushpack（）函數是調用Insert（）函數實作的，而Insert()函數内部有檢測容量，是以剛開始Pushpack（）就沒有檢測，程式崩潰了。因為在Insert裡擴容時，等于說重新開辟了一塊更大的記憶體，那你Pushback傳過來的End（）位置将永遠也找不到，因為那塊記憶體已經被釋放了。

2.其實這裡的疊代器它就是一個指針，根本沒必要再對它的++，--，什麼的進行重載，我好像是陷入了list的迷陣中無法自拔-_-....

    為什麼會這麼淩亂呢，因為寫vector時，我邊看《老九門》邊敲代碼。。。回頭再看看真是。。。是以，作為程式員，該敲代碼時還是老老實實敲吧。。。

    我這裡在拷貝構造時，隻開辟了有效值個數，考慮到實際中拷貝後應該不會再插入，是以這樣做也是一種省空間的做法。

    vector包含的函數當然不止這些，有興趣可以查閱STL庫看看。