一、前言

? ? ? ? 之前我們借助手撕string加深了類和對象相關知識，今天我們將一起手撕一個vector，繼續深化類和對象、動態內存管理、模板的相關知識

二、vector相關的前置知識

? ? ? ? 1、什么是vector？

? ? ? ? vector是一個STL庫中提供的類模板，它是存儲元素對象的順序表，其中提供了一些有關增刪查改的接口，它的特點是可以通過下標的方式在表中的任意位置進行讀、寫

? ? ? ? 2、vector中的相關接口

? ? ? ? 在本文接下來的部分會介紹vector的常用接口，事實上借助這些接口就可以解決平常所能遇到的大部分問題，如果還需要了解vector提供的更多接口及使用方法的話，可以跳轉到一下網頁：
????????vector - C++ Referencehttps://legacy.cplusplus.com/reference/vector/vector/?kw=vector

三、手撕一個vector類

? ? ? ? 1、成員變量與整體框架

? ? ? ? 注意：之前的順序表我們都是通過記錄指針、元素個數和空間大小來完成的，順序表的實現自然也可以這樣，但是STL庫中不是這樣實現的，所以今天我們學習一下STL庫中的實現方式

????????

? ? ? ? 上面的_start、_finish、_endofstorge分別代表著指向有效元素起始位置、終止位置的下一個位置和空間終止位置的迭代器，所以在上面我們已經定義了迭代器，事實上就是指針類型，這是由于順序表的一大特點就是在內存中連續存儲，所以可以直接使用未封裝的指針；另一方面，我們在聲明成員變量的同時都給了一個缺省值，這是由于它們都是指針類型，在初始化時我們都要先初始化成空指針再進行下一步操作，所以我們可以直接在這里給一個缺省值，這樣避免了在初始化列表多次的顯示初始化成空指針

? ? ? ? 2、構造函數

? ? ? ? 庫中的函數頭：
????????

? ? ? ? 以上的三個構造函數我們都會一一實現，在這里補充一點：在上面的構造函數中出現了"clloc"，事實上，這是一個內存池，而后面所給的缺省值是STL庫中提供的一個默認的內存池，它可以有效的提高開辟空間的時間消耗，但是比較復雜，所以在這里我們直接new空間，在之后，我們會專門的進行講解

? ? ? ? ? ? ? ? (1).空構造：
????????????????

? ? ? ? ? ? ? ? 在這里實現的空構造是非常簡單的，這是由于我們在聲明時已經給了缺省值，但是該空構造是一定要寫的，這是因為我們還要實現別的構造函數，這時候編譯器就不在自動生成默認構造函數了

? ? ? ? ? ? ? ? (2).用n個元素對象進行初始化：
????????????????

? ? ? ? ? ? ? ? 在使用n個元素對象進行初始化時，我們在參數部分給了一個缺省值T()，很明顯，這是一個匿名對象，同時調用了對應的默認構造函數，這是沒有問題的，但是如果T是int、float等內置類型呢？事實上，這點不用擔心，這是由于C++將這些內置類型都進行了升級，使它們可以象自定義類型一樣調用默認構造函數，舉個例子：如果T是int類型，那么此時T()就會返滬一個0進行初始化

? ? ? ? ? ? ? ? (3).使用一個迭代器區間進行初始化：
????????????????

? ? ? ? ? ? ? ? 在上面的構造函數中，我們再次使用了模板，但這里是函數模板，這是由于我們不僅要支持順序表的迭代器類型初始化，還要支持其它類型的迭代器初始化

? ? ? ? 3、返回順序表一些性質的函數

? ? ? ? ????????(1).size函數：返回此時vector中的元素個數

? ? ? ? ????????庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? 實現：
????????????????

? ? ? ? ? ? ? ? (2).capacity函數：返回此時vector中的空間大小

? ? ? ? ? ? ? ? 庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? 實現：
????????????????

? ? ? ? 4、拷貝構造函數

? ? ? ? 庫中的函數頭：

????????

? ? ? ? 實現：
????????

? ? ? ? 這里需要注意：我們不可以使用memcpy，這是由于memcpy會按字節將x的內容拷貝到_start，但如果T類型是動態開辟內存，也就是說是深拷貝的話，那么雖然vector整體進行了深拷貝，但是vector中的內容卻只完成了淺拷貝，會出現深淺拷貝的問題，此時選擇上面的方式就萬無一失了，這要求元素對象重載了賦值運算符，這一點是必須的

? ? ? ? 5、迭代器相關函數

? ? ? ? ? ? ? ? (1).begin函數：

? ? ? ? ? ? ? ? 庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? begin函數進行了兩個重載，分別是普通begin和const begin它們分別可以返回一個可讀可寫的迭代器和一個只讀不寫的迭代器，都指向vector的首元素位置：
????????????????

? ? ? ? ? ? ? ? (2).end函數:

? ? ? ? ? ? ? ? 庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? end函數仍然進行了兩個重載，返回的迭代器都指向末尾元素的下一個位置：
????????????????

? ? ? ? 6、[]操作符重載

? ? ? ? 庫中的函數頭：
????????

? ? ? ? 庫中對[]操作符進行了兩個重載，與上面的begin類似：
????????

? ? ? ? 庫中對于很多類型進行了封裝，事實上上面我們實現的與庫中的本質是一樣的

? ? ? ? 7、交換函數

? ? ? ? 庫中的函數頭：
????????

? ? ? ? 這里的交換一定是要涉及深拷貝的，在這里我們借用一下算法庫中的swap函數，因為它恰好就是深拷貝：
????????

? ? ? ? 8、賦值運算符重載

? ? ? ? 庫中的函數頭：
????????

? ? ? ? 在這里我們對該函數實現進行一點小改動，但是對于用戶的使用來說是相同的：
????????

? ? ? ? 在上面的實現中，我們采用了傳值傳參，此時形參是實參的拷貝，拷貝會調用我們之前實現過的拷貝構造函數進行深拷貝，再調用swap函數，它也會進行深拷貝之下的交換，最終*this就變成了x的拷貝，最后x這一拷貝出作用域銷毀，調用析構函數(后面會實現)，進行了空間的釋放

? ? ? ? 9、開空間相關函數

? ? ? ? ? ? ? ? (1).reserve函數：會開辟指定大小的空間，如果原來有元素，會進行拷貝，否則不進行任何處理

? ? ? ? ? ? ? ? 庫中的函數頭:
? ? ? ? ? ? ? ??

? ? ? ? ? ? ? ? 實現：
????????????????

? ? ? ? ? ? ? ? 在上面我們又遇到了象拷貝構造函數同樣的問題，所以再次使用了賦值運算符重載的方式進行處理

? ? ? ? ? ? ? ? (2).resize函數：會開辟指定大小的空間，用val進行初始化，缺省值為T()

? ? ? ? ? ? ? ? 庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? 實現:
????????????????

? ? ? ? ? ? ? ? 這里我們直接對之前的函數進行復用即可

? ? ? ? 10、插入相關函數

? ? ? ? ? ? ? ? (1).insert函數：在迭代器指定的位置直接插入一個值，返回最后該位置的迭代器

? ? ? ? ? ? ? ? 庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? 實現：
????????????????

? ? ? ? ? ? ? ? 從上面的代碼可以看出：在insert函數內部可能開辟空間，這時候pos就不是原來的pos了，所以在函數外部，傳給過insert函數的迭代器是不能再次使用的，因為使用過的迭代器可能已經失效，這時候我們通過反回值的方式解決了這個問題，所以如果想再次使用的話，要接受函數的返回值

? ? ? ? ? ? ? ? (2).push_back函數：在vector尾部插入一個對象

? ? ? ? ? ? ? ? 庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? 實現：
????????????????

? ? ? ? ? ? ? ? 事實上在這個位置我們直接復用剛才寫過的insert就非常方便

? ? ? ? 11、刪除相關函數

? ? ? ? ? ? ? ? (1).erase函數：刪除迭代器指定位置的元素，返回該位置的迭代器

? ? ? ? ? ? ? ? 庫中的函數頭：
????????????????

? ? ? ? ? ? ? ? 實現：
????????????????

? ? ? ? ? ? ? ? erase所刪除的位置有可能是最后一個，此時刪除之后傳入的迭代器·就失效了，所以要接收返回值并判斷

? ? ? ? ? ? ? ? (2).pop_back函數

? ? ? ? ? ? ? ? 庫中的函數頭：

????????????????

? ? ? ? ? ? ? ? 實現：
????????????????

? ? ? ? ? ? ? ? 直接復用剛才寫過的erase函數即可

? ? ? ? 12、析構函數

? ? ? ? 由于析構函數的特殊性，這里就不提供庫中的函數頭了：

????????

四、vector

????????下面就是我們今天一起完成的vector了：
????????

#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;
namespace bea
{template<class T>class vector{typedef T* iterator;typedef const T* const_iterator;public://空構造vector() {}//用n個元素對象進行初始化vector(size_t n, const T& val = T()){_start = new T[n + 5];for (size_t i = 0; i < n; i++){_start[i] = val;}_finish = _start + n;_endofstorge = _start + n + 4;}//使用一個迭代器區間進行初始化template<class InputIterator>vector(InputIterator first, InputIterator last){size_t n = last - first;_start = new T[n + 5];InputIterator it1 = first, it2 = _start;while (it1 < last){*it2 = *it1;it1++, it2++;}_finish = _start + n;_endofstorge = _start + n + 4;}//拷貝構造函數vector(const vector& x){size_t sz = x.size();_start = new T[sz + 5];for (size_t i = 0; i < sz; i++){_start[i] = x._start[i];}_finish = _start + sz;_endofstorge = _start + sz + 4;}//size函數size_t size() const{return _finish - _start;}//capacity函數size_t capacity() const{return _endofstorge - _start + 1;}//begin函數iterator begin(){return _start;}const_iterator begin() const{return _start;}//end函數iterator end(){return _finish;}const_iterator end() const{return _finish;}//[]操作符重載T& operator[](size_t pos){assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const{assert(pos < size());return _start[pos];}//交換函數void swap(vector& x){std::swap(x._start, _start);std::swap(x._finish, _finish);std::swap(x._endofstorge, _endofstorge);}//賦值運算符重載vector& operator=(const vector x){swap(x);return *this;}//開空間相關函數void reserve(size_t n){size_t sz = size();if (n <= size()) return;iterator tmp = new T[n + 5];if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_finish = tmp + sz;_start = tmp;_endofstorge = tmp + n + 4;}//insert函數iterator insert(iterator pos, const T& val){assert(pos <= _finish);int n = pos - _start;if (capacity() < size() + 1){reserve(size() + 5);}pos = _start + n;iterator end = _finish - 1, next = _finish;while (next > pos){*next = *end;end--, next--;}*pos = val;_finish++;return pos;}void push_back(const T& val){insert(_finish, val);}void resize(size_t n, T& val = T()){vector(n, val);}//erase函數iterator erase(iterator pos){assert(pos < _finish);iterator end = pos + 1, front = pos;while (end < _finish){*front = *end;front++, end++;}_finish--;if (pos == _finish) return nullptr;else return pos;}//pop_back函數void pop_back(){erase(_finish - 1);}//析構函數~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_endofstorge = nullptr;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorge = nullptr;};
}

五、結語

? ? ? ? 這就是我們所實現的vector的全部內容了，我們的目的仍然是了解vector的用法、加深類和對象和模板等知識點的理解，感謝大家的閱讀，歡迎各位于晏、亦菲和我一起交流、學習、進步！

????????????????

? ? ? ? ? ? ? ?