[C++]vector的模擬實現

? ? ? ? 下面是簡單的實現vector的功能，沒有涉及使用內存池等復雜算法來提高效率。

一、vector的概述

（一）、抽象數據類型定義

容器：向量（vector）

vector是表示大小可以變化的數組的序列容器。像數組一樣，向量對其元素使用連續的存儲位置，這意味著也可以使用指向其元素的常規指針上的偏移量來訪問其元素，并且與數組中的元素一樣高效。但與數組不同的是，它們的大小可以動態變化，它們的存儲由容器自動處理。

模板類

template<class T>

操作

一、構造函數
vector();? ? ? ? 默認構造
vector(size_t n,const T val = T());????????用n個val進行填充初始化

vector(int n, const T val = T());? ?防止vector(int,int)與下面的模板函數發生歧義
template<class InputIterator>????????
vector(InputIterator first, Inputiterator last);????????迭代器區間初始化

vector(std::initializer_list list);? ? ? ? 用初始化列表進行初始化
vector(const vector<T>& v)；????????拷貝構造函數
vector<T>& operator=(const vector<T>& v); ? ? ? 賦值構造
~vector();????????析構函數

二、迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;

三、容量
size_t size() const;????????返回當前容器存儲的數據個數
size_t capacity() const;????????返回當前容器的容量大小
void resize(size_t n);????????改變容器數據個數
bool empty() const;????????判斷當前容器是否為空
void reserve(size_t n);????????改變容量大小

四、訪問數據
T& operator[](size_t n);? ? ? ? 可讀可寫
const T& operator[](size_t n) const;? ? ? ? 只可讀

五、修改操作
void push_back(const T& val);????????尾插操作
void pop_back();????????尾刪操作
iterator insert(iterator pos, const T& x);????????在指定位置插入
iterator erase(iterator pos);? ? ? ? 指定位置刪除
void swap(vector<T>& v);????????交換兩個vector容器的數據

（二）、成員變量

template<class T>
class vector
{
public://vector的迭代器可以為原生指針typedef T* iterator;typedef const T* const_iterator;
private:iterator _start = nullptr;//指向第一個數據的迭代器iterator _finish = nullptr;//指向最后一個有效數據的后一個位置iterator _endOfStorage = nullptr;//指向數組末尾的后一個位置
};

? ? ? ? ?這里的迭代器就是我們的原生指針T*，它的私有成員變量就和線性表一樣，要存儲數據的起始位置的指針、數據的有效數據的個數、存儲容量等。這里直接全部定義成指針來維護容器的數據數組，_start指向數組的起始位置，_finish指向有效數據個數的后一個的位置，當我們將這兩個指針相減，_finish - _start?就能得到數據的有效數據個數了。最后一個endOfStorage就是指向數組的末尾的下一個位置(雖然越界但不解引用就沒事),當我們拿_endOfStorage -??_start 就得到了這段空間的容量個數。

? ? ? ? 注意：我們的每個構造函數，在一開始時都要把迭代器置為空指針，而我們在聲明迭代器時，順便給上初始值，這樣會更好，以免忘記初始化帶來不必要的麻煩。

迭代器維護的空間示意圖:

二、具體實現

? ? ? ? 我們不按上面的函數聲明的順序來依次定義函數，我們按照從易到難的順序，一點一點實現其成員函數的定義，每個階段測試一下。

（一）、默認構造、析構、迭代器、尾插、尾刪、下標訪問

（1）、默認構造、析構

//默認構造
vector() :_start(nullptr), _finish(nullptr), _endOfStorage(nullptr) { ; }

? ? ? ? ?因為是空容器，所以三個指針都初始化為nullptr。

//析構
~vector()
{delete[] _start;_start = _finish = _endOfStorage = nullptr;
}

? ? ? ? 刪除動態分配的空間后記得將指針置為空，因為析構是可以手動調用的。

（2）、迭代器

//迭代器
iterator begin() { return _start; }
iterator end() { return _finish; }
const_iterator begin() const { return _start; }
const_iterator end() const { return _finish; }

? ? ? ?兩組迭代器分別構成重載。

????????注意：重載不是因為返回值的不同，而是其參數不同，一個是this，另一個是const this的指針。

（3）、尾插和尾刪操作

? ? ? ? ?注意:需要對容器滿時進行擴容處理。

1、輔助其擴容的函數

empty()：判斷容器是否為空

bool empty() const { return (_finish - _start) == 0; }

size()：返回容器的有效數據個數

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

capacity()：返回容器的容量

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

reserve()：擴容操作

void reserve(size_t n)//改變容量大小
{//如果n為0,默認給4個空間n = n == 0 ? 4 : n;//不允許縮容if (n <= capacity())return;//擴容size_t nSize = size();//保存有效數據個數iterator itTem = new T[n];//拷貝到新數組for (int i = 0; i < nSize; i++){*(itTem + i) = *(_start + i);}delete[] _start;_start = itTem;_finish = _start + nSize;_endOfStorage = _start + n;
}

2、尾插、尾刪

//修改操作
void push_back(const T& val)//尾插操作
{//判斷容器空間是否足夠if (size() == capacity()){size_t newCapacity = capacity() * 2;//兩倍擴容//擴容reserve(newCapacity);//std::cout << capacity() << " ";}//尾插*_finish = val;_finish++;
}

void pop_back()//尾刪操作
{if (!empty())_finish--;
}

（4）、下標訪問

		//訪問操作T& operator[](size_t n){//防止越界訪問assert(n >= 0 && n < size());return *(_start + n);}const T& operator[](size_t n) const{//防止越界訪問assert(n >= 0 && n < size());return *(_start + n);}

? ? ? ? 注意：構成函數重載的是參數，不是返回值。

（5）、代碼測試

void test1()
{const int N = 10;//測試數據的個數MySpace::vector<int> v1;for (int i = 0; i < N; i++){v1.push_back(i + 1);}//手動使用迭代器遍歷MySpace::vector<int>::iterator it1 = v1.begin();while (it1 != v1.end()){cout << *it1 << " ";it1++;}cout << endl;//數組方式訪問for (int i = 0; i < N; i++)cout << v1[i] << " ";cout << endl;//測試尾刪for (int i = 0; i < N + 2; i++)//+2是為了測試一下刪空容器{cout << endl;for (auto e : v1)//測試范圍for{cout << e << " ";}v1.pop_back();}
}

運行結果:

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7
1 2 3 4 5 6
1 2 3 4 5
1 2 3 4
1 2 3
1 2
1

（二）、其余的構造函數

（1）、迭代器區間和參數初始化表初始化

迭代器區間初始化構造函數

????????因為迭代器的類型可能不同，不一定所有的迭代器的類型都是指針，有可能是自定義類型。所以用模板函數。

template<class InputIterator>
vector(InputIterator first, InputIterator last)
{size_t size = last - first;reserve(size);//提前開好空間，防止頻繁擴容//一個一個數據尾插while (first != last){push_back(*first);first++;}
}

參數初始化列表初始化構造函數

//復用上面的迭代器區間構造函數即可
vector(std::initializer_list<T> list) :vector(list.begin(), list.end()) { ; }

（2）拷貝構造函數

		//拷貝構造vector(const vector<T>& v){reserve(v.capacity());for (auto& e : v){push_back(e);}}

（3）交換兩個容器和賦值構造函數

實現交換容器的函數swap()來輔助賦值構造函數的實現

void swap(vector<T>& v)//交換兩個的數據
{std::swap(_start, v._start);std::swap(_finish,v._finish);std::swap(_endOfStorage, v._endOfStorage);
}

賦值構造函數

//賦值構造
vector<T>& operator=(const vector<T>& v)
{//復用拷貝構造函數vector<T> tem(v);swap(tem);return *this;
}

（4）填充初始化

		//填充初始化vector(size_t n, const T val = T())//用n個val進行初始化{reserve(n);for (int i = 0; i < n; i++){push_back(val);}}//用來防止調用vector(int,int)時發生歧義//發生歧義的函數:vector<InputIterator InputIterator>vector(int n, const T val = T()){reserve(n);for (int i = 0; i < n; i++){push_back(val);}}

（5）、代碼測試

void test2()
{const int N = 8;MySpace::vector<int> v1;for (int i = 0; i < N; i++){v1.push_back(i + 1);}for (auto e : v1){cout << e << " ";}cout << endl;//測試迭代器區間初始化構造MySpace::vector<int> v2(v1.begin() + 2, v1.end()-2);for (auto e : v2){cout << e << " ";}//測試參數初始化列表構造cout << endl;MySpace::vector<int> v3({ 1,2,3,4,5,6,7,8,9,10 });for (auto e : v3){cout << e << " ";}//測試拷貝構造cout << endl;MySpace::vector<int> v4(v3);for (auto e : v4){cout << e << " ";}//測試賦值構造cout << endl;MySpace::vector<int> v5;v5 = v4;for (auto e : v5){cout << e << " ";}//測試填充初始化cout << endl;MySpace::vector<int> v6(10,7);for (auto e : v6){cout << e << " ";}
}

運行結果：?

1 2 3 4 5 6 7 8
3 4 5 6
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
7 7 7 7 7 7 7 7 7 7?

（三）、指定位置插入和刪除

（1）、指定位置插入

		iterator insert(iterator pos, const T& x)//在指定位置插入{//判斷插入的位置及是否合法assert(pos >= _start && pos <= _finish);//判斷是否需要擴容if (size() == capacity()){//防止擴容后pos迭代器失效size_t nPos = pos - _start;//計算pos距離_start的偏移量size_t newCapacity = capacity() * 2;reserve(newCapacity);pos = _start + nPos;}//將插入位置及之后的元素往后挪iterator it = _finish;while (it > pos){*it = *(it - 1);it--;}//插入元素*pos = x;_finish++;return pos;}

????????注意：擴容時pos迭代器會失效，擴容前要計算pos距離起始位置的偏移量，然后再更新pos的迭代器。所以，外部的迭代器pos是有失效的可能性的，而不管怎么樣外部的pos是不能再繼續使用的，若要繼續使用，則需要接受函數的返回值更新pos的迭代器，防止迭代器失效，此時pos迭代器指向新插入的數據。

（2）、指定位置刪除?

iterator erase(iterator pos)//指定位置刪除
{//判斷刪除的位置是否合法assert(pos >= _start && pos <= _finish - 1);//將pos位置后的元素往前挪iterator cur = pos + 1;while (cur != _finish){*(cur - 1) = *cur;cur++;}_finish--;return pos;
}

? ? ? ? 注意：vector刪除元素時有可能縮容的，雖然這里實現的vector不會縮容，為了防止外部的迭代器失效，我們也需要返回一個迭代器更新其pos的位置，此時pos指向的位置是刪除的元素的下一個元素的位置。

（3）、代碼測試

void test3()
{MySpace::vector<int> v1{ 1,2,3,4,5,6 };//測試指定位置插入v1.insert(v1.begin(), 999);v1.insert(v1.end(), 999);v1.insert(v1.end() - 2, 999);for (auto e : v1){cout << e << " ";}cout << endl;//結合find刪除所有999//找不到則返回結尾的迭代器MySpace::vector<int>::iterator itFind;while ((itFind = std::find(v1.begin(), v1.end(), 999)) != v1.end()){cout << endl;v1.erase(itFind);for (auto e : v1){cout << e << " ";}}
}

（4）運行結果：

999 1 2 3 4 5 999 6 999?

1 2 3 4 5 999 6 999
1 2 3 4 5 6 999
1 2 3 4 5 6

（四）、修改有效數據個數大小

具體實現代碼：

void resize(size_t n)//改變容器數據個數
{assert(n >= 0);//判斷是否需要擴容if (n > capacity()){reserve(n);}//將其他位置初始化為數據的默認構造for (int i = size(); i < n; i++){*(_start + i) = T();}_finish = _start + n;
}

代碼測試：

void test4()
{//測試resizeMySpace::vector<int> v1{ 1,2,3,4,5,6,7,8,9,10 };for (auto e : v1){cout << e << " ";}cout << endl;//縮容v1.resize(2);for (auto e : v1){cout << e << " ";}cout << endl;//調大有效數據個數大小v1.resize(10);for (auto e : v1){cout << e << " ";}
}