?<1>主頁：我的代碼愛吃辣
??<2>知識講解：C++之STL
??<3>創(chuàng)作者：我的代碼愛吃辣
??<4>開發(fā)環(huán)境：Visual Studio 2022
??<5>前言：上次我們已經(jīng)數(shù)字會用了vector，這次我們對其底層更深一步挖掘，其中重點是，Vector中一些深淺拷貝問題。
目錄
一.Vector模擬實現(xiàn)的整體框架
二. Vector的構(gòu)造與析構(gòu)
三.size（），capacity（）
?四.reserve（），resize（）
1.reserve（）
2.resize
五.push_back（），pop_back（）
1.push_back（）
2. pop_back（）
六.Vector的迭代器
?七.operator [ ]
?八.insert（），erase（）
1.迭代器失效
2.insert（）
3.erase（）
九.再看Vector構(gòu)造函數(shù)
十.拷貝構(gòu)造
1.深淺拷貝
2.正確的拷貝構(gòu)造代碼：
3.正確的 reserve（）
4.賦值運算符重載
十一.總體代碼
一.Vector模擬實現(xiàn)的整體框架
我們先認(rèn)識一下Vector的整體模擬實現(xiàn)框架，Vector在功能上就是我們數(shù)據(jù)結(jié)構(gòu)階段實現(xiàn)的順序表基本一致，但是Vector在成員框架上與順序表有所不同，且Vector使用類和對象封裝支持模板泛型。
template<class T>
class Vector
{
public:
//迭代器類型
typedef T* iterator;
typedef const T* const_iterator;
//...
private:
iterator _start;//數(shù)據(jù)存儲首地址
iterator _finish;//有效數(shù)據(jù)尾部地址下一個地址。
iterator _end_of_storage;//容量尾地址下一個地址
};
Vector的迭代器是對順序表原生類型指針的封裝。
二. Vector的構(gòu)造與析構(gòu)
Vector主要是對成員變量初始化：
Vector()
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
}析構(gòu)主要釋放我們申請的空間：
~Vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}三.size（），capacity（）
size（）返回當(dāng)前順序表存儲的數(shù)據(jù)個數(shù)，capacity（）返回當(dāng)前順序表的容量。
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
?四.reserve（），resize（）
1.reserve（）
設(shè)置Vector的容量，注意容量支持增加，但是不支持減小。
void reserve(size_t capa)
{
//僅支持容量擴(kuò)大，不支持容量減小
if (capacity() < capa)
{
size_t sz = size();
iterator tmp = new T[capa];
//分清當(dāng)前的是否已經(jīng)有了容量，如果已經(jīng)有了容量需要釋放之前的容量，
//如果之前沒有容量僅需，將新開的空間指向我們的_start.
if (_start)
{
memcpy(tmp, _start, sizeof(T) * capacity()); /*error ??！*/
delete[] _start;
}
//注意:此處不能直接tmp+size()來計算，因為在計算_start的時候已經(jīng)已經(jīng)改變了_start,
//然后計算的size也并非是，準(zhǔn)確的size。
_start = tmp;
_finish = tmp + sz;
_end_of_storage = _start + capa;
}
}注意:
此處不能直接tmp+size()來計算，因為在計算_start的時候已經(jīng)已經(jīng)改變了_start,然后計算的size也并非是，準(zhǔn)確的size。除此之外這份代碼依舊是有問題的。我們后面解釋。
錯誤代碼如下：
void reserve(size_t capa)
{
if (capacity() < capa)
{
iterator tmp = new T[capa];
if (_start)
{
memcpy(tmp, _start, sizeof(T) * capacity());
delete[] _start;
}
//注意:此處不能直接tmp+size()來計算，因為在計算_start的時候已經(jīng)已經(jīng)改變了_start,
//然后計算的size也并非是，準(zhǔn)確的size。
_start = tmp;
_finish = tmp + size();
_end_of_storage = _start + capa;
}
}
2.resize
提供改變存儲數(shù)據(jù)的個數(shù)的能力。如果 n < size 時就是刪除數(shù)據(jù)，n > size且空間不夠時需要擴(kuò)容+初始化，空間足夠，僅需要初始化剩下的空間。
void resize(size_t n, T val = T())
{
//1.n < size;-->刪除數(shù)據(jù)
if (n < size())
{
_finish = _start + n;
}
//2.n > size
else
{
//(1)如果空間不足，需要擴(kuò)容+初始化
if (n >= capacity())
{
reserve(n);
}
//(2)空間足夠，僅需要初始化剩下的空間
while (_finish != _start + n)
{
*(_finish) = val;
_finish++;
}
}
}
五.push_back（），pop_back（）
1.push_back（）
從尾部插入一個數(shù)據(jù)。
void push_back(const T& val)
{
//檢查是否需要擴(kuò)容
if (_finish == _end_of_storage)
{
capacity() == 0 ? reserve(5) : reserve(capacity() * 2);
}
//插入數(shù)據(jù)
*(_finish) = val;
_finish++;
}2. pop_back（）
bool empty() const
{
return size() == 0;
}
void pop_back()
{
//判空
assert(!empty());
//我們僅需將維護(hù)尾部數(shù)據(jù)的指針向前挪一位。
_finish--;
}六.Vector的迭代器
typedef T* iterator;
typedef const T* const_iterator;Vector底層就是順序存儲的結(jié)構(gòu)，所以可以使用原生指針作為迭代器。
//普通迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//const 迭代器
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}有了迭代器就可以支持迭代器訪問，和范圍for。
int main()
{
Vector<int> v1;
v1.push_back(100);
v1.push_back(200);
v1.push_back(300);
v1.push_back(400);
v1.push_back(500);
v1.push_back(600);
v1.push_back(700);
Vector<int>::iterator it = v1.begin();
while (it != v1.end())
{
cout << *it << " ";
it++;
}
cout << endl;
for (auto e : v1)
{
cout << e << " ";
}
return 0;
}
?七.operator [ ]
//穿引用返回
T& operator[](size_t pos)
{
//判斷位置的合法性
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
?八.insert（），erase（）
1.迭代器失效
在模擬實現(xiàn)之前我們先看一下什么是迭代器失效問題：
迭代器失效問題通常發(fā)生在容器類的成員函數(shù)中，例如erase和insert。在這些函數(shù)中，迭代器被重置或修改，導(dǎo)致原始迭代器不再指向容器的正確位置，從而導(dǎo)致迭代器失效。
int main()
{
vector<int> v1;
v1.push_back(100);
v1.push_back(200);
v1.push_back(300);
v1.push_back(400);
v1.push_back(500);
v1.push_back(600);
v1.push_back(700);
vector<int>::iterator pos = find(v1.begin(), v1.end(),200);
//對pos位置插入
v1.insert(pos, 150);
//pos已經(jīng)失效
v1.insert(pos, 170);
return 0;
}
原理圖：
情況一：
?上述代碼中的迭代器失效問題也是屬于這種情況。
情況二：
2.insert（）
iterator insert(iterator pos,T val)
{
assert(pos >= _start);
assert(pos < _finish);
//迭代器失效問題,記錄pos的相對位置
int len = pos - _start;
if (_finish == _end_of_storage)
{
capacity() == 0 ? reserve(5) : reserve(capacity() * 2);
}
//擴(kuò)容后重新計算pos，沒有發(fā)生擴(kuò)容pos不變
pos = _start + len;
iterator end = _finish;
//數(shù)據(jù)挪動
while (end >= pos)
{
(*end) = *(end - 1);
end--;
}
_finish++;
(*pos) = val;
return pos;
}在使用pos時要注意擴(kuò)容會使得pos失效，需要重新計算pos位置。
3.erase（）
iterator erase(iterator pos)
{
//判斷位置是否合法
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos ;
/挪動數(shù)據(jù)刪除
while (end < _finish)
{
*end = *(end + 1);
end++;
}
_finish--;
return pos;
}九.再看Vector構(gòu)造函數(shù)
std中的vector還支持使用指定個數(shù)和初始化值初始化，和迭代器區(qū)間初始化。這兩個功能在我們平時也是能用到的。
//1.Vector<T> v(5,10);創(chuàng)建一個Vector并且初始化前5個值為10
Vector(size_t n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
//2.迭代器初始化，[frist,lest)
template<class InputIterator>
Vector(InputIterator frist, InputIterator lest)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(lest - frist);
while (frist != lest)
{
push_back(*frist);
frist++;
}
}
//3.防止構(gòu)造函數(shù)調(diào)用錯誤
Vector(int n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
第三個構(gòu)造函數(shù)的作用是防止構(gòu)造調(diào)用錯誤沖突，在我們進(jìn)行如下的調(diào)用時：
Vector<int> v2(5, 10);編譯器會以為我們在調(diào)用迭代器區(qū)間初始化構(gòu)造函數(shù)，因為經(jīng)過模板的推導(dǎo)，只有迭代器區(qū)間初始化構(gòu)造函數(shù)，更適合這個調(diào)用。然后將一個整形當(dāng)作地址在迭代器區(qū)間初始化構(gòu)造函數(shù)里面解引用了，報錯是：非法的間接尋址。
?正常調(diào)用結(jié)果：
十.拷貝構(gòu)造
今天這里編譯器默認(rèn)生成的拷貝構(gòu)造顯然是不能用了。
1.深淺拷貝
萬萬不可以直接使用拷貝函數(shù)按二進(jìn)制或者按字節(jié)直接拷貝了。
錯誤代碼1：
Vector(const Vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(v.capacity());
//萬萬不可以直接按二進(jìn)制拷貝
memcpy(_start, v._start, sizeof(T) * v.capacity()); /*error!!!!*/
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}原因：
調(diào)用處代碼：
int main()
{
string str("abcdefg");
Vector<string> v2(5,str);
Vector<string> v3(v2);
return 0;
}
?會使得我們同一塊空間被delete兩次從而引發(fā)內(nèi)存錯誤。
2.正確的拷貝構(gòu)造代碼：
Vector(const Vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(v.capacity());
//這里我們將數(shù)據(jù)一個一個push進(jìn)去，這樣我們借助push_back底層插入的時候，
//會使用string的賦值構(gòu)造，完成深拷貝。
for (int i = 0; i < v.size(); i++)
{
push_back(v[i]);
}
}
//現(xiàn)代寫法
Vector(const Vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
Vector<T> tmp(v.begin(), v.end());
swap(tmp);
}錯誤代碼2：reserve（）
void reserve(size_t capa)
{
//僅支持容量擴(kuò)大，不支持容量減小
if (capacity() < capa)
{
size_t sz = size();
iterator tmp = new T[capa];
//分清當(dāng)前的是否已經(jīng)有了容量，如果已經(jīng)有了容量需要釋放之前的容量，
//如果之前沒有容量僅需，將新開的空間指向我們的_start.
if (_start)
{
//這里千萬不能按二進(jìn)制直接拷貝.
memcpy(tmp, _start, sizeof(T) * capacity()); /*error ??！*/
delete[] _start;
}
//注意:此處不能直接tmp+size()來計算，因為在計算_start的時候已經(jīng)已經(jīng)改變了_start,
//然后計算的size也并非是，準(zhǔn)確的size。
_start = tmp;
_finish = tmp + sz;
_end_of_storage = _start + capa;
}
}這里我們?nèi)匀皇鞘褂昧薽emcpy。
調(diào)用處代碼：
int main()
{
string str("abcdefg");
Vector<string> v2;
for (int i = 0; i < 6; i++)
{
v2.push_back(str);
}
return 0;
}
3.正確的 reserve（）
void reserve(size_t capa)
{
//僅支持容量擴(kuò)大，不支持容量減小
if (capacity() < capa)
{
size_t sz = size();
iterator tmp = new T[capa];
//分清當(dāng)前的是否已經(jīng)有了容量，如果已經(jīng)有了容量需要釋放之前的容量，
//如果之前沒有容量僅需，將新開的空間指向我們的_start.
if (_start)
{
//這里千萬不能按二進(jìn)制直接拷貝.
//memcpy(tmp, _start, sizeof(T) * capacity()); /*ror ！！*/
for (int i = 0; i < size(); i++)
{
//=內(nèi)置類型直接賦值,自定義類型使用賦值構(gòu)造
tmp[i]=_start[i];
}
delete[] _start;
}
//注意:此處不能直接tmp+size()來計算，因為在計算_start的時候已經(jīng)已經(jīng)改變了_start,
//然后計算的size也并非是，準(zhǔn)確的size。
_start = tmp;
_finish = tmp + sz;
_end_of_storage = _start + capa;
}
}這里有一個細(xì)節(jié)就是在reserve和拷貝構(gòu)造的拷貝數(shù)據(jù)的時候我們都是使用了賦值。問題我們并沒有重載賦值運算符，編譯器自動生成，簡單來說就是這里又會是一個淺拷貝。
4.賦值運算符重載
//傳統(tǒng)寫法
Vector<T>& operator=(const Vector<T>& v)
{
T* tmp = new T[v.capacity()];
if (_start)
{
for (int i = 0; i < v.size(); i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
return *this;
}
//現(xiàn)代寫法
void swap(Vector<T>& v )
{
std::swap(v._start, _start);
std::swap(v._finish, _finish);
std::swap(v._end_of_storage, _end_of_storage);
}
Vector<T>& operator=(Vector<T> v)
{
swap(v);
return *this;
}現(xiàn)代寫法利用，拷貝構(gòu)造拷貝出來的對象，然后交換對象的成員。文章來源：http://www.zghlxwxcb.cn/news/detail-645368.html
十一.總體代碼
#pragma once
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<cassert>
using namespace std;
template<class T>
class Vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
Vector()
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
}
//1.Vector<T> v(5,10);創(chuàng)建一個Vector并且初始化前5個值為10
Vector(size_t n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
//2.迭代器初始化，[frist,lest)
template<class InputIterator>
Vector(InputIterator frist, InputIterator lest)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(lest - frist);
while (frist != lest)
{
push_back(*frist);
frist++;
}
}
//3.防止構(gòu)造函數(shù)調(diào)用沖突
Vector(int n, const T& val = T())
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
//傳統(tǒng)寫法 拷貝構(gòu)造
//Vector(const Vector<T>& v)
// :_start(nullptr),
// _finish(nullptr),
// _end_of_storage(nullptr)
//{
// reserve(v.capacity());
// //這里我們將數(shù)據(jù)一個一個push進(jìn)去，這樣我們借助push_back底層插入的時候，
// //會使用string的賦值構(gòu)造，完成深拷貝。
// for (int i = 0; i < v.size(); i++)
// {
// _start[i] = v[i];
// }
//}
//現(xiàn)代寫法，拷貝構(gòu)造
Vector(const Vector<T>& v)
:_start(nullptr),
_finish(nullptr),
_end_of_storage(nullptr)
{
Vector<T> tmp(v.begin(), v.end());
swap(tmp);
}
//傳統(tǒng)寫法，賦值拷貝
//Vector<T>& operator=(const Vector<T>& v)
//{
// T* tmp = new T[v.capacity()];
// if (_start)
// {
// for (int i = 0; i < v.size(); i++)
// {
// tmp[i] = _start[i];
// }
// delete[] _start;
// }
// _start = tmp;
// _finish = _start + v.size();
// _end_of_storage = _start + v.capacity();
//
// return *this;
//}
void swap(Vector<T>& v )
{
std::swap(v._start, _start);
std::swap(v._finish, _finish);
std::swap(v._end_of_storage, _end_of_storage);
}
//現(xiàn)代寫法，賦值拷貝
Vector<T>& operator=(Vector<T> v)
{
swap(v);
return *this;
}
size_t size() const
{
return _finish - _start;
}
size_t capacity() const
{
return _end_of_storage - _start;
}
void reserve(size_t capa)
{
//僅支持容量擴(kuò)大，不支持容量減小
if (capacity() < capa)
{
size_t sz = size();
iterator tmp = new T[capa];
//分清當(dāng)前的是否已經(jīng)有了容量，如果已經(jīng)有了容量需要釋放之前的容量，
//如果之前沒有容量僅需，將新開的空間指向我們的_start.
if (_start)
{
//這里千萬不能按二進(jìn)制直接拷貝.
//memcpy(tmp, _start, sizeof(T) * capacity()); /*ror ?。?/
for (int i = 0; i < size(); i++)
{
//=內(nèi)置類型直接賦值,自定義類型使用賦值構(gòu)造
tmp[i]=_start[i];
}
delete[] _start;
}
//注意:此處不能直接tmp+size()來計算，因為在計算_start的時候已經(jīng)已經(jīng)改變了_start,
//然后計算的size也并非是，準(zhǔn)確的size。
_start = tmp;
_finish = tmp + sz;
_end_of_storage = _start + capa;
}
}
void resize(size_t n, T val = T())
{
//1.n < size;-->刪除數(shù)據(jù)
if (n < size())
{
_finish = _start + n;
}
//2.n > size
else
{
//(1)如果空間不足，需要擴(kuò)容+初始化
if (n >= capacity())
{
reserve(n);
}
//(2)空間足夠，僅需要初始化剩下的空間
while (_finish != _start + n)
{
*(_finish) = val;
_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 push_back(const T& val)
{
if (_finish == _end_of_storage)
{
capacity() == 0 ? reserve(5) : reserve(capacity() * 2);
}
//內(nèi)置類型直接賦值,自定義類型使用賦值構(gòu)造
*(_finish) = val;
_finish++;
}
bool empty() const
{
return size() == 0;
}
void pop_back()
{
//判空
assert(!empty());
//我們僅需將維護(hù)尾部數(shù)據(jù)的指針向前挪一位。
_finish--;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator end = pos ;
while (end < _finish)
{
*end = *(end + 1);
end++;
}
_finish--;
return pos;
}
iterator insert(iterator pos,T val)
{
assert(pos >= _start);
assert(pos < _finish);
//迭代器失效問題,記錄pos的相對位置
int len = pos - _start;
if (_finish == _end_of_storage)
{
capacity() == 0 ? reserve(5) : reserve(capacity() * 2);
}
//擴(kuò)容后重新計算pos，沒有發(fā)生擴(kuò)容pos不變
pos = _start + len;
iterator end = _finish;
//數(shù)據(jù)挪動
while (end >= pos)
{
(*end) = *(end - 1);
end--;
}
_finish++;
(*pos) = val;
return pos;
}
//普通迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
//const 迭代器
const_iterator begin()const
{
return _start;
}
const_iterator end()const
{
return _finish;
}
~Vector()
{
delete[] _start;
_start = _finish = _end_of_storage = nullptr;
}
private:
iterator _start;//數(shù)據(jù)存儲首地址
iterator _finish;//有效數(shù)據(jù)尾部地址下一個地址。
iterator _end_of_storage;//容量尾地址下一個地址
int tmp;
};
?
文章來源地址http://www.zghlxwxcb.cn/news/detail-645368.html
到了這里，關(guān)于C++ STL vector 模擬實現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
