?? 歡迎大家來到貝蒂大講堂??

🎈🎈養(yǎng)成好習(xí)慣，先贊后看哦~🎈🎈

所屬專欄：C++學(xué)習(xí)
貝蒂的主頁：Betty’s blog

為了讓我們更加深入理解vector，接下來我們將模擬實(shí)現(xiàn)一個(gè)·簡(jiǎn)易版的vector。而為了和STL庫中的vecotr以示區(qū)分，我們將使用命名空間namespace對(duì)其封裝。

1. vector的成員變量

vector的底層其實(shí)就是我們之前在數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的順序表，但是與順序表不同的是vector的成員變量是三個(gè)迭代器，也可以說是三個(gè)指針。

下面是vector的成員變量：

namespace betty 
{template<class T>class vector {public://...private:iterator _start;iterator _finish;iterator _end_of_storage;};
}

其中start指向起始位置，_finish指向有效數(shù)據(jù)末尾的后一個(gè)位置，最后_end_of_storage指向容量大小末尾的后一個(gè)位置。

2. vector的成員函數(shù)

在知道vector的成員變量之后，接下來我們將探究vector的成員函數(shù)，而常見成員函數(shù)的用法我們?cè)缭谥熬鸵呀?jīng)介紹過了 ，下面我們將來具體實(shí)現(xiàn)一下：

2.1. vector的迭代器

首先我們來模擬實(shí)現(xiàn)一下迭代器iterator，而在vector中迭代器iterator與string中的迭代器類似就是一個(gè)指針。所以我們直接使用typedef實(shí)現(xiàn)

typedef char* iterator;//普通迭代器
typedef const char* const_iterator;//const迭代器

接下來我們來實(shí)現(xiàn)begin()與end()，其中begin()指向的是數(shù)組的起始位置即_start，而end指向有效長(zhǎng)度最后的下一位即_finish的位置。

iterator begin()
{return _start;
}iterator end()
{return _finish;
}

實(shí)現(xiàn)完普通迭代器之后，我們可以順便重載一個(gè)const_iterator的版本。

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

我們知道在vector中還有一個(gè)反向迭代器，這個(gè)我們?cè)谥髸?huì)統(tǒng)一實(shí)現(xiàn)。

2.2. vector的初始化與銷毀

2.2.1. 構(gòu)造函數(shù)與拷貝構(gòu)造

我們之前在學(xué)習(xí)vector時(shí)知道其初始化方式有很多，可以通過默認(rèn)構(gòu)造函數(shù)給其初始化，n個(gè)val初始化，也可以通過迭代器初始化。

首先我們寫一個(gè)默認(rèn)構(gòu)造函數(shù)，將其所有變量都設(shè)為空。

vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{;
}

接下來我們來實(shí)現(xiàn)迭代器初始化，而因?yàn)槲覀兛梢酝ㄟ^其他容器的迭代器對(duì)其初始化，所以要通過模版來實(shí)現(xiàn)。

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

最后我們來實(shí)現(xiàn)n個(gè)val初始化。

vector(size_t n, const T& val = T())
{resize(n, val);
}
vector(int n, const T& val = T())
{resize(n, val);
}

至于為什么要同時(shí)重載int與size_t兩種不同類型，那是為了防止在傳兩個(gè)int類型的參數(shù)時(shí)被編譯器交給模版InputIterator識(shí)別，然后報(bào)錯(cuò)。

拷貝構(gòu)造也十分簡(jiǎn)單，直接拷貝就行，但是也有一些注意事項(xiàng)。

vector(const vector<T>& v)
{_start = new T[v.capacity()];//開辟capacity的空間for (size_t i = 0; i < v.size(); ++i){_start[i] = v._start[i];//進(jìn)行深拷貝}_finish = _start + v.size();//更新_finish_end_of_storage = _start + v.capacity();//更新_end_of_storage
}

這里注意不能利用memcpy()等庫函數(shù)進(jìn)行拷貝，因?yàn)檫@些函數(shù)都是進(jìn)行的淺拷貝。如果模版參數(shù)T是string，vector等自定義類型，當(dāng)程序結(jié)束回收內(nèi)存時(shí)就會(huì)發(fā)生內(nèi)存錯(cuò)誤。

當(dāng)然我們也可以通過一個(gè)取巧的方式來實(shí)現(xiàn)拷貝構(gòu)造。

vector(vector<int>& v)
{// 根據(jù)v的capacity()去開出對(duì)應(yīng)的空間reserve(v.capacity());//進(jìn)行深拷貝for (size_t i = 0; i < v.size(); i++){push_back(v[i]);}
}

首先通過構(gòu)造出一個(gè)與數(shù)組相同的數(shù)組v，然后讓this所指向的數(shù)組與其交換，這樣出了作用域之后銷毀的就是原this所指向的數(shù)組。當(dāng)然我們必須先將this所指向的數(shù)組先初始化擴(kuò)容。

2.2.2. 賦值重載與析構(gòu)函數(shù)

賦值運(yùn)算符重載與拷貝構(gòu)造的實(shí)現(xiàn)就非常類似了，直接實(shí)現(xiàn)即可。

vector<T> operator = (vector<T> v)
{swap(v);return *this;
}

最后我們實(shí)現(xiàn)析構(gòu)函數(shù)，只需要清理資源即可

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

2.3. vector的容量操作

2.3.1. 有效長(zhǎng)度與容量大小

首先我們先實(shí)現(xiàn)返回?cái)?shù)組有效長(zhǎng)度的size() 與容量大小的capacity()。并且為了適配const對(duì)象，最后用const修飾this指針。

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

2.3.2. 容量操作

接下來我們來實(shí)現(xiàn)擴(kuò)容函數(shù)reserve()與·resize()，其中reserve()最簡(jiǎn)單，只要新容量大于舊容量就發(fā)生擴(kuò)容，其中注意需要提前記錄size大小，防止數(shù)組異地?cái)U(kuò)容原數(shù)組釋放之后找不到原數(shù)組大小。

void reserve(size_t n)
{//提前原本記錄長(zhǎng)度size_t sz = size();if (n > capacity()){T* tmp = new T[n];if (_start){//深拷貝for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];//賦值重載}delete[]_start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}

而resize()的邏輯就比較復(fù)雜，需要分三種情況討論。設(shè)字符串原來有效長(zhǎng)度為size，容量為capacity，新容量為n

1. 當(dāng)n<size時(shí)，resize會(huì)刪除有效字符到指定大小。
2. 當(dāng)size<n<capcity時(shí)，resize會(huì)補(bǔ)充有效字符(默認(rèn)為0)到指定大小。
3. 當(dāng)n>capacity時(shí)，resize會(huì)補(bǔ)充有效字符(默認(rèn)為0)到指定大小。

void resize(size_t n,const T&val=T())
{if (n < size()){//更新數(shù)組大小_finish = _start + n;}else{//擴(kuò)容reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}
}

2.4. vector的訪問操作

為了符合我們C語言訪問數(shù)組的習(xí)慣，我們可以先重載operator[]。當(dāng)然我們也要提供兩種不同的接口：可讀可寫與可讀不可寫。并且使用引用返回，減少不必要的拷貝。

// 可讀可寫
T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
// 可讀不可寫
T& operator[](size_t pos)const
{assert(pos < size());return _start[pos];
}

同理我們也可以實(shí)現(xiàn)front()與back()函數(shù)。

// 可讀可寫
char& front()
{return _start[0];
}
char& back()
{return _start[_size() - 1];
}
// 可讀不可寫
const char& front()const
{return _start[0];
}
const char& back()const
{return _start[_size() - 1];
}

2.5. vector的修改操作

2.5.1. 常見的修改操作

首先我們將實(shí)現(xiàn)兩個(gè)常用的修改函數(shù)：push_back()與pop_back()。

void push_back(const T& x)
{//判斷是否擴(kuò)容if (_finish == _end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newCapacity);}*_finish = x;++_finish;
}
void pop_back()
{--_finish;
}

隨后我們來實(shí)現(xiàn)數(shù)組的交換swap()函數(shù)，我們知道vector的交換其實(shí)就是指針_start，_finish，_end_of_storage的交換。

void swap(vector<T>& v)
{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);
}

2.5.2. 迭代器失效

接下來我們實(shí)現(xiàn)insert()與erase()兩個(gè)函數(shù)。其中insert()在插入時(shí)可能擴(kuò)容，這時(shí)就需要記錄起始長(zhǎng)度，方便更新迭代器返回。

iterator insert(iterator pos, const T& x)
{assert(pos <= _finish && pos >= _start);//檢查是否擴(kuò)容if (_finish == _end_of_storage){//先記錄長(zhǎng)度size_t len = pos - _start;size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);//更新迭代器指向新空間pos = _start + len;}//往后覆蓋iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;
}

同樣的為了防止迭代器失效，需要返回新的迭代器。

iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);iterator end = pos + 1;while (end != _finish){*(end - 1) = *end;++end;}--_finish;return pos;
}

3. 源碼

#pragma once
namespace betty
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr){;}vector(size_t n, const T& val = T()){resize(n, val);}vector(int n, const T& val = T()){resize(n, val);}template<class InputIterator>vector(InputIterator first, InputIterator last){while (first != last){push_back(*first);++first;}}//vector(const vector<T>& v)//{//	_start = new T[v.capacity()];//開辟capacity的空間//	for (size_t i = 0; i < v.size(); ++i)//	{//		_start[i] = v._start[i];//循環(huán)拷貝//	}//	_finish = _start + v.size();//更新_finish//	_end_of_storage = _start + v.capacity();//更新_end_of_storage//}vector(vector<int>& v){// 根據(jù)v的capacity()去開出對(duì)應(yīng)的空間reserve(v.capacity());//進(jìn)行深拷貝for (size_t i = 0; i < v.size(); i++){push_back(v[i]);}}vector<T> operator=(vector<T> v){swap(v);return *this;}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin()const{return _start;}const_iterator end()const{return _finish;}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}void reserve(size_t n){//提前原本記錄長(zhǎng)度size_t sz = size();if (n > capacity()){T* tmp = new T[n];if (_start){//深拷貝for (size_t i = 0; i < size(); i++){tmp[i] = _start[i];//賦值重載}delete[]_start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}void push_back(const T& x){//判斷是否擴(kuò)容if (_finish == _end_of_storage){size_t newCapacity = capacity() == 0 ? 4 : 2 * capacity();reserve(newCapacity);}*_finish = x;++_finish;}void resize(size_t n,const T&val=T()){if (n < size()){_finish = _start + n;}else{reserve(n);while (_finish != _start + n){*_finish = val;++_finish;}}}T& operator[](size_t pos){assert(pos < size());return _start[pos];}T& operator[](size_t pos)const{assert(pos < size());return _start[pos];}iterator insert(iterator pos, const T& x){assert(pos <= _finish && pos >= _start);//檢查是否擴(kuò)容if (_finish == _end_of_storage){//先記錄長(zhǎng)度size_t len = pos - _start;size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;reserve(newCapacity);//更新迭代器指向新空間pos = _start + len;}//往后覆蓋iterator end = _finish;while (end > pos){*end = *(end - 1);--end;}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator end = pos + 1;while (end != _finish){*(end - 1) = *end;++end;}--_finish;return pos;}void pop_back(){--_finish;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}~vector(){delete[]_start;_start = _finish = _end_of_storage = nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}
ase(iterator pos){assert(pos >= _start && pos < _finish);iterator end = pos + 1;while (end != _finish){*(end - 1) = *end;++end;}--_finish;return pos;}void pop_back(){--_finish;}void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}~vector(){delete[]_start;_start = _finish = _end_of_storage = nullptr;}private:iterator _start;iterator _finish;iterator _end_of_storage;};
}