引言
關(guān)于STL容器的學(xué)習(xí)，我們來(lái)到了運(yùn)用最廣泛、最常見(jiàn)的vector。有了之前關(guān)于string的學(xué)習(xí)，我們對(duì)容器設(shè)計(jì)有了一個(gè)大概的了解，而今天在熟悉的基礎(chǔ)上去探求vector相比于string有哪些異同，同時(shí)迎來(lái)更多的新挑戰(zhàn)……
一、成員變量
vector類中包含了
- _start（指向有效空間的頭）
- _finish（指向有效空間的尾）
- _end_of_storage（指向可用空間的尾）
細(xì)節(jié)：
- 三個(gè)成員變量均迭代器（此刻即指針）
- 使用缺省值，不必寫(xiě)多份初始化列表
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;
};
二、默認(rèn)成員函數(shù)
2.1 constructor
無(wú)參構(gòu)造
vector()
{}
帶參構(gòu)造
細(xì)節(jié)：
- 分別重載 size_t 和 int 類型，防止參數(shù)匹配時(shí)，匹配到迭代器區(qū)間構(gòu)造，從而導(dǎo)致間接尋址錯(cuò)誤
- 初始化的val的缺省值，是匿名構(gòu)造的對(duì)象
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; ++i)
{
_start[i] = val;
}
_finish = _start + n;
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; ++i)
{
_start[i] = val;
}
_finish = _start + n;
}
迭代器區(qū)間構(gòu)造
細(xì)節(jié)：
- 使用類模板，可以傳任意類型的迭代器
- 迭代器訪問(wèn)，條件最好使用不等于（！=）
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
2.2 destructor
~vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
2.3 copy constructor
近代寫(xiě)法
細(xì)節(jié)：
- 先開(kāi)辟一維空間
- 再用賦值重載，進(jìn)行深拷貝（不能用memcpy，它是淺拷貝）
vector(const vector<T>& x)
{
_start = new T[x.capacity()];
for (size_t i = 0; i < x.size(); ++i)
{
_start[i] = x._start[i];
}
_finish = _start + x.size();
_end_of_storage = _start + x.capacity();
}
現(xiàn)代寫(xiě)法
細(xì)節(jié)：
- 用迭代器區(qū)間構(gòu)造，構(gòu)造出臨時(shí)對(duì)象
- 再使用vector中的swap，交換*this和tmp的值，完成拷貝構(gòu)造
vector(const vector<T>& x)
{
vector<T> tmp(x.begin(), x.end());
swap(tmp);
}
2.4 operator=
近代寫(xiě)法
細(xì)節(jié)：大體與拷貝構(gòu)造相同
vector<T>& operator=(const vector<T>& x)
{
if (this != &x)
{
_start = new T[x.capacity()];
for (size_t i = 0; i < x.size(); ++i)
{
_start[i] = x._start[i];
}
_finish = _start + x.size();
_end_of_storage = _start + x.capacity();
}
return *this;
}
現(xiàn)代寫(xiě)法
細(xì)節(jié)：
- 傳參變成傳值，這樣就會(huì)拷貝構(gòu)造出一個(gè)臨時(shí)對(duì)象
- 再使用vector中的swap，交換*this和tmp的值，完成賦值重載
vector<T>& operator=(vector<T> x)
{
swap(x);
return *this;
}
三、迭代器
3.1 begin
迭代器的實(shí)現(xiàn)和編譯器有關(guān)，不同的編譯器有不同的實(shí)現(xiàn)方式。這里用指針來(lái)實(shí)現(xiàn)迭代器。
同時(shí)，重載了普通迭代器和const迭代器。
iterator begin()
{
return _start;
}
const_iterator begin() const
{
return _start;
}
3.2 end
迭代器遵循左閉右開(kāi)的原則，begin指向首元素，end指向末元素的下一位。
iterator end()
{
return _finish;
}
const_iterator end() const
{
return _finish;
}
悄悄告訴你：范圍for的底層實(shí)現(xiàn)，就是運(yùn)用了迭代器。
四、元素訪問(wèn)
4.1 operator[ ]
為了方便的訪問(wèn)元素，我們重載了[ ]運(yùn)算符。同時(shí)，也分為普通版本和const版本，對(duì)應(yīng)不同vector類的權(quán)限。
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
五、容量
5.1 size
獲取當(dāng)前有效數(shù)據(jù)個(gè)數(shù)
細(xì)節(jié)：const修飾，保證普通和const類型vector類都能訪問(wèn)
size_t size() const
{
return _finish - _start;
}
5.2 capacity
獲取當(dāng)前最大有效容量
細(xì)節(jié)：同上
size_t capacity() const
{
return _end_of_storage - _start;
}
看了上面size和capacity的實(shí)現(xiàn)，是不是就瞬間明白_start、_finish和_end_of_storage的含義了？
悄悄告訴你：其實(shí)當(dāng)你不懂成員變量的含義時(shí)，可以先看看size和capacity的實(shí)現(xiàn)。
5.3 reserve
改變當(dāng)前最大容量
細(xì)節(jié)：
- 只擴(kuò)容，不縮容
- 用賦值重載，進(jìn)行深拷貝
- 更新成員變量時(shí)（如果按照順序更新），先保存size的大小，防止_finish失效。因?yàn)槿绻麨開(kāi)finish = tmp + size()，等價(jià)于_finish = tmp + _finish - _start，而_start已經(jīng)更新了，所以size()計(jì)算的大小失效，最終_finish并沒(méi)有更新。
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
if (_start)
{
for (size_t i = 0; i < size(); ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
size_t sz = size();
_start = tmp;
_finish = tmp + sz;
_end_of_storage = tmp + n;
}
}
5.4 resize
改變當(dāng)前有效數(shù)據(jù)個(gè)數(shù)
細(xì)節(jié)：
- 如果n<size，則減少有效個(gè)數(shù)，如果n>size，則填充指定值，直至達(dá)到n個(gè)
- 運(yùn)用賦值重載，實(shí)現(xiàn)深拷貝
void resize(size_t n, T val = T())
{
if (n > size())
{
reserve(n);
for (size_t i = size(); i < n; ++i)
{
_start[i] = val;
}
}
_finish = _start + n;
}
5.5 empty
判斷是否為空
細(xì)節(jié)：const修飾，保證普通和const類型vector類都能訪問(wèn)
bool empty() const
{
return _start == _finish;
}
六、修改
6.1 push_back
尾插
細(xì)節(jié)：需要擴(kuò)容時(shí)，判斷容量是否為空
void push_back(const T& val)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
*_finish = val;
++_finish;
}
6.2 pop_back
尾刪
細(xì)節(jié)：斷言vector不為空，才進(jìn)行刪除
void pop_back()
{
assert(!empty());
--_finish;
}
6.3 insert
指定位置插入
細(xì)節(jié)：
- 斷言判斷pos的合法性
- 擴(kuò)容前，先保存pos的相對(duì)位置，擴(kuò)容后，刷新pos，防止迭代器失效
- 返回指向新插入元素的迭代器，防止迭代器失效
iterator insert(iterator pos, const T& val)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = val;
++_finish;
return pos;
}
6.4 erase
指定位置刪除
細(xì)節(jié)：
- 斷言判斷pos的合法性
- 返回指向刪除元素的后一位的迭代器，防止迭代器失效
iterator erase(iterator pos)
{
assert(pos >= _start && pos < _finish);
iterator start = pos + 1;
while (start < _finish)
{
*(start - 1) = *start;
++start;
}
--_finish;
return pos;
}
上述有兩種迭代器失效：
- 野指針
- 指向含義改變
關(guān)于迭代器失效，我們統(tǒng)一認(rèn)為，進(jìn)行過(guò)插入或刪除操作的迭代器pos，已經(jīng)失效，不能再使用。只有接收其返回值，刷新pos，才能重新使用。
6.5 swap
交換兩個(gè)vector類的值
細(xì)節(jié)：使用std庫(kù)中的swap函數(shù)，交換各個(gè)成員變量的值文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-821868.html
void swap(vector<T>& x)
{
std::swap(_start, x._start);
std::swap(_finish, x._finish);
std::swap(_end_of_storage, x._end_of_storage);
}
總結(jié)
我們?cè)谟辛藢W(xué)習(xí)string的基礎(chǔ)后，學(xué)習(xí)vector的成本降低了不少，函數(shù)名和用法大體相同。但是，我們依舊遇到了新的問(wèn)題與挑戰(zhàn)，如多層深拷貝，迭代器失效等。我與C++的故事，仍在無(wú)聲地訴說(shuō)……
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-821868.html
到了這里，關(guān)于【C++練級(jí)之路】【Lv.7】【STL】vector類的模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![C++ [STL之vector模擬實(shí)現(xiàn)]](https://imgs.yssmx.com/Uploads/2024/02/500268-1.png)
