目錄

一.vector的介紹

1.vector的介紹

二.vector的定義模擬實(shí)現(xiàn)

三.vector各接口的模擬實(shí)現(xiàn)

1.vector迭代器的模擬實(shí)現(xiàn)

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

? ?2.1無(wú)參構(gòu)造

2.2 n個(gè)val構(gòu)造

2.3迭代器區(qū)間構(gòu)造

2.4通過對(duì)象初始化（拷貝構(gòu)造）

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

4.size

5.operator=

6.capacity

7.reserve

8.resize

9.operator[ ]

10.insert

11.push_back

12.erase

13.pop_back

14.empty

---

一.vector的介紹

1.vector的介紹

這是官方的文檔介紹
cplusplus.com/reference/vector/vector/

1. vector是表示可變大小數(shù)組的序列容器。

2. 就像數(shù)組一樣，vector也采用的連續(xù)存儲(chǔ)空間來(lái)存儲(chǔ)元素。也就是意味著可以采用下標(biāo)對(duì)vector的元素進(jìn)行訪問，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動(dòng)態(tài)改變的，而且它的大小會(huì)被容器自動(dòng)處理。

3. 本質(zhì)講，vector使用動(dòng)態(tài)分配數(shù)組來(lái)存儲(chǔ)它的元素。當(dāng)新元素插入時(shí)候，這個(gè)數(shù)組需要被重新分配大小為了增加存儲(chǔ)空間。其做法是，分配一個(gè)新的數(shù)組，然后將全部元素移到這個(gè)數(shù)組。就時(shí)間而言，這是一個(gè)相對(duì)代價(jià)高的任務(wù)，因?yàn)槊慨?dāng)一個(gè)新的元素加入到容器的時(shí)候，vector并不會(huì)每次都重新分配大小。

4. vector分配空間策略：vector會(huì)分配一些額外的空間以適應(yīng)可能的增長(zhǎng)，因?yàn)榇鎯?chǔ)空間比實(shí)際需要的存儲(chǔ)空間更大。不同的庫(kù)采用不同的策略權(quán)衡空間的使用和重新分配。但是無(wú)論如何，重新分配都應(yīng)該是對(duì)數(shù)增長(zhǎng)的間隔大小，以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的。

5. 因此，vector占用了更多的存儲(chǔ)空間，為了獲得管理存儲(chǔ)空間的能力，并且以一種有效的方式動(dòng)態(tài)增長(zhǎng)。

6. 與其它動(dòng)態(tài)序列容器相比（deques, lists and forward_lists）， vector在訪問元素的時(shí)候更加高效，在末尾添加和刪除元素相對(duì)高效。對(duì)于其它不在末尾的刪除和插入操作，效率更低。比起lists和forward_lists統(tǒng)一的迭代器和引用更好

二.vector的定義模擬實(shí)現(xiàn)

首先我們先 定義一個(gè)命名空間 來(lái)模擬實(shí)現(xiàn)咱們的vector類

類里面有三個(gè)私有 指針變量 分別指向數(shù)據(jù)塊的開始，尾和存儲(chǔ)容量的尾

namespace zyl
{template<class T>class vector{public:// Vector的迭代器是一個(gè)原生指針typedef T* iterator;typedef const T* const_iterator;private:iterator _start; // 指向數(shù)據(jù)塊的開始iterator _finish; // 指向有效數(shù)據(jù)的尾iterator _endOfStorage; // 指向存儲(chǔ)容量的尾};
}

三.vector各接口的模擬實(shí)現(xiàn)

1.vector迭代器的模擬實(shí)現(xiàn)

vector的迭代器分為倆種

一種是普通迭代器 指向的內(nèi)容可以被修改

一種是const迭代器 不可以修改只可讀

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

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

vector 的四種構(gòu)造函數(shù)

? ?2.1無(wú)參構(gòu)造

主要是對(duì)各個(gè)指針初始化 賦值為空

 vector():_endOfStorage(nullptr),_start(nullptr),_finish(nullptr){}

2.2 n個(gè)val構(gòu)造

直接向數(shù)組中尾插數(shù)據(jù)，用reserve提前擴(kuò)容, 提高效率

然后需要注意的是? 這里傳參的第二個(gè)參數(shù)使用匿名對(duì)象，const T& val = T() 這種寫法會(huì)調(diào)用默認(rèn)構(gòu)造(可以是任意類型)，我們前面講內(nèi)置類型是沒有默認(rèn)構(gòu)造函數(shù)的, 理論而言是沒有的, 但是調(diào)用模板之后必須要支持默認(rèn)構(gòu)造

 vector(int n, const T& value = T()):_endOfStorage(nullptr), _start(nullptr), _finish(nullptr){reserve(n);//提前開n個(gè)空間for (int i = 0;i < n;i++){push_back(value);//缺省值默認(rèn)為val；}}

2.3迭代器區(qū)間構(gòu)造

這里又要使用模板實(shí)現(xiàn)， 要實(shí)現(xiàn)一個(gè)任意類型的迭代器允許任意類型的數(shù)據(jù)使用，直接用迭代器遍歷數(shù)組, 尾插數(shù)據(jù)即可

template<class InputIterator>vector(InputIterator first, InputIterator last):_endOfStorage(nullptr),_start(nullptr),_finish(nullptr){while (first != last){push_back(*first);++first;}

2.4通過對(duì)象初始化（拷貝構(gòu)造）

? ? ?通過傳一個(gè)vector對(duì)象? 然后進(jìn)行交換?

        vector(const vector<T>& v){vector<T> tmp(v.cbegin(), v.cend());swap(tmp);}

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

? 析構(gòu)函數(shù)的主要功能 釋放掉所有數(shù)據(jù) 然后三個(gè)指針指向空

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

4.size

返回當(dāng)前vector長(zhǎng)度

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

5.operator=

運(yùn)算符重載=? ? ?實(shí)現(xiàn)深拷貝 把v對(duì)象賦給this

       vector<T>& operator= (vector<T> v){if (this != &v){delete[] _start;_start = new T[v.capacity()];for (size_t i = 0;i < v.size();i++){_start[i] = v[i];}_finish = _start + v.size();_endOfStorage = _start + v.capacity();}return *this;}

6.capacity

返回當(dāng)前vector對(duì)象的容量是多少

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

7.reserve

在n>capacity時(shí)去進(jìn)行擴(kuò)容 是為了防止程序縮容

判段當(dāng)前數(shù)據(jù)是為為空，需不需要舊數(shù)據(jù)的拷貝轉(zhuǎn)移

遍歷的時(shí)候，一定要使用深拷貝，不要使用memcpy去進(jìn)行拷貝

 void reserve(size_t n){if (n >capacity()){size_t sz = size();T* tmp = new T[n];if (_start)//如果為空  則不用將舊數(shù)據(jù)轉(zhuǎn)移{for (size_t i = 0;i <size();i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_endOfStorage = _start + n;}}

8.resize

n < size()?就是刪除數(shù)據(jù)，直接改變 _finish的指向即可

n > capacity()調(diào)用reserve函數(shù)擴(kuò)容， 后遍歷給數(shù)組賦值

 void resize(size_t n, const T& value = T()){//查看是否需要擴(kuò)容if (n > capacity()){reserve(n);}if (n > size()){while (_finish > _start + n){*_finish = value;++_finish;}}else{_finish = _start + n;}}

9.operator[ ]

vector也支持下標(biāo)訪問

重載 [ ] 可以快速的對(duì)數(shù)據(jù)進(jìn)行訪問

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

10.insert

檢查容量，觀察是否需要擴(kuò)容,?擴(kuò)容前計(jì)算出pos與start之間，pos與start之間相對(duì)距離不變，擴(kuò)容后更新pos位置(這里存在迭代器失效的問題)

遍歷挪動(dòng)數(shù)據(jù)

將val插入pos位置

注意:?檢查pos位置的合法性

iterator insert(iterator pos, const T& x){//pos范圍必須在_start和_finish之間assert(pos>=_start);assert(pos <= _finish);//內(nèi)存滿了 進(jìn)行擴(kuò)容if (_finish == _endOfStorage){size_t len = pos - _start;reseve(capacity() > 0 ? 4 : capacity * 2);pos = _start + len;}iterator end = _finish;//移動(dòng)數(shù)據(jù) 進(jìn)行插入while (end >= pos){*end = *(end - 1);end--;}*pos = x;++_finish;return pos;}

11.push_back

尾插 直接調(diào)用insert 在_finish位置去插入

void push_back(const T& x){insert(_finish, x);}

12.erase

erase函數(shù)可以刪除所給迭代器pos位置的數(shù)據(jù)

在刪除數(shù)據(jù)前需要判斷容器釋放為空

若為空則需做斷言處理，刪除數(shù)據(jù)時(shí)直接將pos位置之后的數(shù)據(jù)統(tǒng)一向前挪動(dòng)一位，將pos位置的數(shù)據(jù)覆蓋即可。?

iterator erase(iterator pos){//判斷pos是否合法assert(pos > _finish);assert(pos < _start);assert(!empty());iterator begin = pos + 1;while (begin < _finish){*(begin - 1) = *begin;++begin;}--_finish;return pos;}

13.pop_back

pop_back直接調(diào)用erase去_finish位置進(jìn)行刪除

 void pop_back(){erase(_finish);}

14.empty

進(jìn)行判空 直接看_finish == _start是否相同就可以了

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