本專(zhuān)欄內(nèi)容為：C++學(xué)習(xí)專(zhuān)欄，分為初階和進(jìn)階兩部分。 通過(guò)本專(zhuān)欄的深入學(xué)習(xí)，你可以了解并掌握C++。
??博主csdn個(gè)人主頁(yè)：小小unicorn
?專(zhuān)欄分類(lèi)：C++
??代碼倉(cāng)庫(kù)：小小unicorn的代碼倉(cāng)庫(kù)??
??????關(guān)注我?guī)銓W(xué)習(xí)編程知識(shí)
vector各函數(shù)接口總覽
namespace NIC
{
//模擬實(shí)現(xiàn)vector
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//默認(rèn)成員函數(shù)
vector(); //構(gòu)造函數(shù)
vector(size_t n, const T& val); //構(gòu)造函數(shù)
template<class InputIterator>
vector(InputIterator first, InputIterator last); //構(gòu)造函數(shù)
vector(const vector<T>& v); //拷貝構(gòu)造函數(shù)
vector<T>& operator=(const vector<T>& v); //賦值運(yùn)算符重載函數(shù)
~vector(); //析構(gòu)函數(shù)
//迭代器相關(guān)函數(shù)
iterator begin();
iterator end();
const_iterator begin()const;
const_iterator end()const;
//容量和大小相關(guān)函數(shù)
size_t size()const;
size_t capacity()const;
void reserve(size_t n);
void resize(size_t n, const T& val = T());
bool empty()const;
//修改容器內(nèi)容相關(guān)函數(shù)
void push_back(const T& x);
void pop_back();
void insert(iterator pos, const T& x);
iterator erase(iterator pos);
void swap(vector<T>& v);
//訪問(wèn)容器相關(guān)函數(shù)
T& operator[](size_t i);
const T& operator[](size_t i)const;
private:
iterator _start=nullptr; //指向容器的頭
iterator _finish=nullptr; //指向有效數(shù)據(jù)的尾
iterator _endofstorage=nullptr; //指向容器的尾
};
}
注：為了防止與標(biāo)準(zhǔn)庫(kù)當(dāng)中的vector產(chǎn)生命名沖突，模擬實(shí)現(xiàn)時(shí)需放在自己的命名空間當(dāng)中。
vector當(dāng)中的成員變量介紹
在vector當(dāng)中有三個(gè)成員變量_start、_finish、_endofstorage。
_start指向容器的頭，_finish指向容器當(dāng)中有效數(shù)據(jù)的尾，_endofstorage指向整個(gè)容器的尾。
或許有人好奇，為什么是這樣定義的呢？在之前的順序表實(shí)現(xiàn)中，我們采用的是：
這就需要我們看一下在SLT源庫(kù)中是怎么實(shí)現(xiàn)的。
這是vector中所包含的頭文件，這里我們打開(kāi)一下vector.h來(lái)看一下：
在vector.h中，我們可以看到，在這個(gè)摸版中，迭代器采用的是start,finish與end_of_storage，其實(shí)也就是我們按照之前定義的那樣，基本是保持一致的。
我們模擬實(shí)現(xiàn)時(shí)基本按照庫(kù)里面的實(shí)現(xiàn)方式來(lái)進(jìn)行模擬實(shí)現(xiàn)。
以下是stl源碼展示：
對(duì)于我們初學(xué)者來(lái)說(shuō)，現(xiàn)在閱讀源碼會(huì)產(chǎn)生困難，但我們現(xiàn)在剛開(kāi)始學(xué)習(xí)stl，所以在閱讀時(shí)不用特別詳細(xì)的閱讀，只要熟悉相關(guān)的功能即可。
具體來(lái)說(shuō)：
1.可以一行一行的看
2.不要研究細(xì)節(jié)，先拉框架，重點(diǎn)關(guān)注里面的類(lèi)：成員變量與成員函數(shù)。
3.理解同時(shí)可以先猜測(cè)一下，然后想辦法驗(yàn)證一下我們的猜測(cè)。
當(dāng)然，小編也已經(jīng)將STL源碼上傳到了gitee倉(cāng)庫(kù)中，可以下載在自己電腦上，方便查閱。
默認(rèn)成員函數(shù)
構(gòu)造函數(shù)1
vector首先支持一個(gè)無(wú)參的構(gòu)造函數(shù)，對(duì)于這個(gè)無(wú)參的構(gòu)造函數(shù)，我們直接將構(gòu)造對(duì)象的三個(gè)成員變量都設(shè)置為空指針即可。
//構(gòu)造函數(shù)1
vector()
{}
構(gòu)造函數(shù)2
其次，vector還支持使用一段迭代器區(qū)間進(jìn)行對(duì)象的構(gòu)造。因?yàn)樵摰鲄^(qū)間可以是其他容器的迭代器區(qū)間，也就是說(shuō)該函數(shù)接收到的迭代器的類(lèi)型是不確定的，所以我們這里需要將該構(gòu)造函數(shù)設(shè)計(jì)為一個(gè)函數(shù)模板，在函數(shù)體內(nèi)將該迭代器區(qū)間的數(shù)據(jù)一個(gè)個(gè)尾插到容器當(dāng)中即可。
//構(gòu)造函數(shù)2
template<class InputIterator> //模板函數(shù)
vector(InputIterator first, InputIterator last)
{
//將迭代器區(qū)間在[first,last)的數(shù)據(jù)一個(gè)個(gè)尾插到容器當(dāng)中
while (first != last)
{
push_back(*first);
first++;
}
}
構(gòu)造函數(shù)3
此外，vector還支持構(gòu)造這樣一種容器，該容器當(dāng)中含有n個(gè)值為val的數(shù)據(jù)。對(duì)于該構(gòu)造函數(shù)，我們可以先使用reserve函數(shù)將容器容量先設(shè)置為n，然后使用push_back函數(shù)尾插n個(gè)值為val的數(shù)據(jù)到容器當(dāng)中即可。
//構(gòu)造函數(shù)3
vector(size_t n, const T& val= T())
{
reserve(n); //調(diào)用reserve函數(shù)將容器容量設(shè)置為n
for (size_t i = 0; i < n; i++) //尾插n個(gè)值為val的數(shù)據(jù)到容器當(dāng)中
{
push_back(val);
}
}
注意：
1）該構(gòu)造函數(shù)知道其需要用于存儲(chǔ)n個(gè)數(shù)據(jù)的空間，所以最好用reserve函數(shù)一次性開(kāi)辟好空間，避免調(diào)用push_back函數(shù)時(shí)需要增容多次，導(dǎo)致效率降低。
2）該構(gòu)造函數(shù)還需要實(shí)現(xiàn)一個(gè)重載函數(shù)。
vector(int n, const T& val= T())
{
reserve(n); //調(diào)用reserve函數(shù)將容器容量設(shè)置為n
for (int i = 0; i < n; i++) //尾插n個(gè)值為val的數(shù)據(jù)到容器當(dāng)中
{
push_back(val);
}
}
可以看到，這個(gè)重載函數(shù)與之不同的就是其參數(shù)n的類(lèi)型不同，但這卻是必要的，否則當(dāng)我們使用以下代碼時(shí)，編譯器會(huì)優(yōu)先與構(gòu)造函數(shù)2相匹配。
拷貝構(gòu)造函數(shù)
vector的構(gòu)造函數(shù)涉及深拷貝問(wèn)題，這里提供兩種深拷貝的寫(xiě)法：
寫(xiě)法一：傳統(tǒng)寫(xiě)法
拷貝構(gòu)造的傳統(tǒng)寫(xiě)法的思想是我們最容易想到的：先開(kāi)辟一塊與該容器大小相同的空間，然后將該容器當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過(guò)來(lái)即可，最后更新_finish和_endofstorage的值即可。
//傳統(tǒng)寫(xiě)法
vector(const vector<T>& v)
{
_start = new T[v.capacity()]; //開(kāi)辟一塊和容器v大小相同的空間
for (size_t i = 0; i < v.size(); i++) //將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過(guò)來(lái)
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效數(shù)據(jù)的尾
_endofstorage = _start + v.capacity(); //整個(gè)容器的尾
}
注意： 將容器當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過(guò)來(lái)時(shí)不能使用memcpy函數(shù)，當(dāng)vector存儲(chǔ)的數(shù)據(jù)是內(nèi)置類(lèi)型或無(wú)需進(jìn)行深拷貝的自定義類(lèi)型時(shí)，使用memcpy函數(shù)是沒(méi)什么問(wèn)題的，但當(dāng)vector存儲(chǔ)的數(shù)據(jù)是需要進(jìn)行深拷貝的自定義類(lèi)型時(shí)，使用memcpy函數(shù)的弊端就體現(xiàn)出來(lái)了。
例如，當(dāng)vector存儲(chǔ)的數(shù)據(jù)是string類(lèi)的時(shí)候。
并且vector當(dāng)中存儲(chǔ)的每一個(gè)string都指向自己所存儲(chǔ)的字符串。
如果此時(shí)我們使用的是memcpy函數(shù)進(jìn)行拷貝構(gòu)造的話，那么拷貝構(gòu)造出來(lái)的vector當(dāng)中存儲(chǔ)的每個(gè)string的成員變量的值，將與被拷貝的vector當(dāng)中存儲(chǔ)的每個(gè)string的成員變量的值相同，即兩個(gè)vector當(dāng)中的每個(gè)對(duì)應(yīng)的string成員都指向同一個(gè)字符串空間。
這顯然不是我們得到的結(jié)果，那么所給代碼是如何解決這個(gè)問(wèn)題的呢？
代碼中看似是使用普通的“=”將容器當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過(guò)來(lái)，實(shí)際上是調(diào)用了所存元素的賦值運(yùn)算符重載函數(shù)，而string類(lèi)的賦值運(yùn)算符重載函數(shù)就是深拷貝，所以拷貝結(jié)果是這樣的：
總結(jié)一下： 如果vector當(dāng)中存儲(chǔ)的元素類(lèi)型是內(nèi)置類(lèi)型（int）或淺拷貝的自定義類(lèi)型（Date），使用memcpy函數(shù)進(jìn)行進(jìn)行拷貝構(gòu)造是沒(méi)問(wèn)題的，但如果vector當(dāng)中存儲(chǔ)的元素類(lèi)型是深拷貝的自定義類(lèi)型（string），則使用memcpy函數(shù)將不能達(dá)到我們想要的效果。
寫(xiě)法二：現(xiàn)代寫(xiě)法
拷貝構(gòu)造函數(shù)的現(xiàn)代寫(xiě)法也比較簡(jiǎn)單，使用范圍for（或是其他遍歷方式）對(duì)容器v進(jìn)行遍歷，在遍歷過(guò)程中將容器v中存儲(chǔ)的數(shù)據(jù)一個(gè)個(gè)尾插過(guò)來(lái)即可。
//現(xiàn)代寫(xiě)法
vector(const vector<T>& v)
{
reserve(v.capacity()); //調(diào)用reserve函數(shù)將容器容量設(shè)置為與v相同
for (auto e : v) //將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)尾插過(guò)來(lái)
{
push_back(e);
}
}
注意： 在使用范圍for對(duì)容器v進(jìn)行遍歷的過(guò)程中，變量e就是每一個(gè)數(shù)據(jù)的拷貝，然后將e尾插到構(gòu)造出來(lái)的容器當(dāng)中。就算容器v當(dāng)中存儲(chǔ)的數(shù)據(jù)是string類(lèi)，在e拷貝時(shí)也會(huì)自動(dòng)調(diào)用string的拷貝構(gòu)造（深拷貝），所以也能夠避免出現(xiàn)與使用memcpy時(shí)類(lèi)似的問(wèn)題。
賦值運(yùn)算符重載函數(shù)
vector的賦值運(yùn)算符重載當(dāng)然也涉及深拷貝問(wèn)題，我們這里也提供兩種深拷貝的寫(xiě)法：
寫(xiě)法一：傳統(tǒng)寫(xiě)法
首先判斷是否是給自己賦值，若是給自己賦值則無(wú)需進(jìn)行操作。若不是給自己賦值，則先開(kāi)辟一塊和容器v大小相同的空間，然后將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過(guò)來(lái)，最后更新_finish和_endofstorage的值即可。
//傳統(tǒng)寫(xiě)法
vector<T>& operator=(const vector<T>& v)
{
if (this != &v) //防止自己給自己賦值
{
delete[] _start; //釋放原來(lái)的空間
_start = new T[v.capacity()]; //開(kāi)辟一塊和容器v大小相同的空間
for (size_t i = 0; i < v.size(); i++) //將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過(guò)來(lái)
{
_start[i] = v[i];
}
_finish = _start + v.size(); //容器有效數(shù)據(jù)的尾
_endofstorage = _start + v.capacity(); //整個(gè)容器的尾
}
return *this; //支持連續(xù)賦值
}
注意： 這里和拷貝構(gòu)造函數(shù)的傳統(tǒng)寫(xiě)法類(lèi)似，也不能使用memcpy函數(shù)進(jìn)行拷貝
寫(xiě)法二：現(xiàn)代寫(xiě)法
賦值運(yùn)算符重載的現(xiàn)代寫(xiě)法非常精辟，首先在右值傳參時(shí)并沒(méi)有使用引用傳參，因?yàn)檫@樣可以間接調(diào)用vector的拷貝構(gòu)造函數(shù)，然后將這個(gè)拷貝構(gòu)造出來(lái)的容器v與左值進(jìn)行交換，此時(shí)就相當(dāng)于完成了賦值操作，而容器v會(huì)在該函數(shù)調(diào)用結(jié)束時(shí)自動(dòng)析構(gòu)。
//現(xiàn)代寫(xiě)法
vector<T>& operator=(vector<T> v) //編譯器接收右值的時(shí)候自動(dòng)調(diào)用其拷貝構(gòu)造函數(shù)
{
swap(v); //交換這兩個(gè)對(duì)象
return *this; //支持連續(xù)賦值
}
注意： 賦值運(yùn)算符重載的現(xiàn)代寫(xiě)法也是進(jìn)行的深拷貝，只不過(guò)是調(diào)用的vector的拷貝構(gòu)造函數(shù)進(jìn)行的深拷貝，在賦值運(yùn)算符重載函數(shù)當(dāng)中僅僅是將深拷貝出來(lái)的對(duì)象與左值進(jìn)行了交換而已。
析構(gòu)函數(shù)
對(duì)容器進(jìn)行析構(gòu)時(shí)，首先判斷該容器是否為空容器，若為空容器，則無(wú)需進(jìn)行析構(gòu)操作，若不為空，則先釋放容器存儲(chǔ)數(shù)據(jù)的空間，然后將容器的各個(gè)成員變量設(shè)置為空指針即可。
//析構(gòu)函數(shù)
~vector()
{
if (_start) //避免對(duì)空指針進(jìn)行釋放
{
delete[] _start; //釋放容器存儲(chǔ)數(shù)據(jù)的空間
_start = nullptr; //_start置空
_finish = nullptr; //_finish置空
_endofstorage = nullptr; //_endofstorage置空
}
}
迭代器相關(guān)函數(shù)
vector當(dāng)中的迭代器實(shí)際上就是容器當(dāng)中所存儲(chǔ)數(shù)據(jù)類(lèi)型的指針。
typedef T* iterator;
typedef const T* const_iterator;
begin和end
vector當(dāng)中的begin函數(shù)返回容器的首地址，end函數(shù)返回容器當(dāng)中有效數(shù)據(jù)的下一個(gè)數(shù)據(jù)的地址。
iterator begin()
{
return _start; //返回容器的首地址
}
iterator end()
{
return _finish; //返回容器當(dāng)中有效數(shù)據(jù)的下一個(gè)數(shù)據(jù)的地址
}
我們還需要重載一對(duì)適用于const對(duì)象的begin和end函數(shù)，使得const對(duì)象調(diào)用begin和end函數(shù)時(shí)所得到的迭代器只能對(duì)數(shù)據(jù)進(jìn)行讀操作，而不能進(jìn)行修改。
const_iterator begin()const
{
return _start; //返回容器的首地址
}
const_iterator end()const
{
return _finish; //返回容器當(dāng)中有效數(shù)據(jù)的下一個(gè)數(shù)據(jù)的地址
}
此時(shí)再讓我們來(lái)看看vector使用迭代器的代碼也就一目了然了，實(shí)際上就是使用指針遍歷容器。
vector<int> v(5, 3);
vector<int>::iterator it = v.begin();
while (it != v.end())
{
cout << *it << " ";
it++;
}
cout << endl;
現(xiàn)在我們實(shí)現(xiàn)了迭代器，實(shí)際上也就可以使用范圍for遍歷容器了，因?yàn)榫幾g器在編譯時(shí)會(huì)自動(dòng)將范圍for替換為迭代器的形式。
vector<int> v(5, 3);
//范圍for進(jìn)行遍歷
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
容量和大小相關(guān)函數(shù)
size和capacity
對(duì)照著vector當(dāng)中三個(gè)成員遍歷各自的指向，我們可以很容易得出當(dāng)前容器中的有效數(shù)據(jù)個(gè)數(shù)和最大容量。
由于兩個(gè)指針相減的結(jié)果，就是這兩個(gè)指針之間對(duì)應(yīng)類(lèi)型的數(shù)據(jù)個(gè)數(shù)，所以size可以由_finish - _start得到，而capacity可以由_endofstorage - _start得到。
size_t size()const
{
return _finish - _start; //返回容器當(dāng)中有效數(shù)據(jù)的個(gè)數(shù)
}
size_t capacity()const
{
return _endofstorage - _start; //返回當(dāng)前容器的最大容量
}
reserve
reserve規(guī)則：
?1、當(dāng)n大于對(duì)象當(dāng)前的capacity時(shí)，將capacity擴(kuò)大到n或大于n。
?2、當(dāng)n小于對(duì)象當(dāng)前的capacity時(shí)，什么也不做。
reserve函數(shù)的實(shí)現(xiàn)思路也是很簡(jiǎn)單的，先判斷所給n是否大于當(dāng)前容器的最大容量（否則無(wú)需進(jìn)行任何操作），操作時(shí)直接開(kāi)辟一塊可以容納n個(gè)數(shù)據(jù)的空間，然后將原容器當(dāng)中的有效數(shù)據(jù)拷貝到該空間，之后將原容器存儲(chǔ)數(shù)據(jù)的空間釋放，并將新開(kāi)辟的空間交給該容器維護(hù)，最好更新容器當(dāng)中各個(gè)成員變量的值即可。
void reserve(size_t n)
{
if (n > capacity()) //判斷是否需要進(jìn)行操作
{
size_t sz = size(); //記錄當(dāng)前容器當(dāng)中有效數(shù)據(jù)的個(gè)數(shù)
T* tmp = new T[n]; //開(kāi)辟一塊可以容納n個(gè)數(shù)據(jù)的空間
if (_start) //判斷是否為空容器
{
for (size_t i = 0; i < sz; i++) //將容器當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝到tmp當(dāng)中
{
tmp[i] = _start[i];
}
delete[] _start; //將容器本身存儲(chǔ)數(shù)據(jù)的空間釋放
}
_start = tmp; //將tmp所維護(hù)的數(shù)據(jù)交給_start進(jìn)行維護(hù)
_finish = _start + sz; //容器有效數(shù)據(jù)的尾
_endofstorage = _start + n; //整個(gè)容器的尾
}
}
在reserve函數(shù)的實(shí)現(xiàn)當(dāng)中有兩個(gè)地方需要注意：
1在進(jìn)行操作之前需要提前記錄當(dāng)前容器當(dāng)中有效數(shù)據(jù)的個(gè)數(shù)。
因?yàn)槲覀冏詈笮枰耞finish指針的指向，而_finish指針的指向就等于_start指針加容器當(dāng)中有效數(shù)據(jù)的個(gè)數(shù)，當(dāng)_start指針的指向改變后我們?cè)僬{(diào)用size函數(shù)通過(guò)_finish - _start計(jì)算出的有效數(shù)據(jù)的個(gè)數(shù)就是一個(gè)隨機(jī)值了。
2拷貝容器當(dāng)中的數(shù)據(jù)時(shí)，不能使用memcpy函數(shù)進(jìn)行拷貝。
可能你會(huì)想，當(dāng)vector當(dāng)中存儲(chǔ)的是string的時(shí)候，雖然使用memcpy函數(shù)reserve出來(lái)的容器與原容器當(dāng)中每個(gè)對(duì)應(yīng)的string成員都指向同一個(gè)字符串空間，但是原容器存儲(chǔ)數(shù)據(jù)的空間不是已經(jīng)被釋放了，相當(dāng)于現(xiàn)在只有一個(gè)容器維護(hù)這這些字符串空間，這還有什么影響。
但是不要忘了，當(dāng)你釋放原容器空間的時(shí)候，原容器當(dāng)中存儲(chǔ)的每個(gè)string在釋放時(shí)會(huì)調(diào)用string的析構(gòu)函數(shù)，將其指向的字符串也進(jìn)行釋放，所以使用memcpy函數(shù)reserve出來(lái)的容器當(dāng)中的每一個(gè)string所指向的字符串實(shí)際上是一塊已經(jīng)被釋放的空間，訪問(wèn)該容器時(shí)就是對(duì)內(nèi)存空間進(jìn)行非法訪問(wèn)。
所以說(shuō)我們還是得用for循環(huán)將容器當(dāng)中的string一個(gè)個(gè)賦值過(guò)來(lái)，因?yàn)檫@樣能夠間接調(diào)用string的賦值運(yùn)算符重載，實(shí)現(xiàn)string的深拷貝。
resize
resize規(guī)則：
?1、當(dāng)n大于當(dāng)前的size時(shí)，將size擴(kuò)大到n，擴(kuò)大的數(shù)據(jù)為val，若val未給出，則默認(rèn)為容器所存儲(chǔ)類(lèi)型的默認(rèn)構(gòu)造函數(shù)所構(gòu)造出來(lái)的值。
?2、當(dāng)n小于當(dāng)前的size時(shí)，將size縮小到n。
根據(jù)resize函數(shù)的規(guī)則，進(jìn)入函數(shù)我們可以先判斷所給n是否小于容器當(dāng)前的size，若小于，則通過(guò)改變_finish的指向，直接將容器的size縮小到n即可，否則先判斷該容器是否需要增容，然后再將擴(kuò)大的數(shù)據(jù)賦值為val即可。
void resize(size_t n, const T& val = T())
{
if (n < size()) //當(dāng)n小于當(dāng)前的size時(shí)
{
_finish = _start + n; //將size縮小到n
}
else //當(dāng)n大于當(dāng)前的size時(shí)
{
if (n > capacity()) //判斷是否需要增容
{
reserve(n);
}
while (_finish < _start + n) //將size擴(kuò)大到n
{
*_finish = val;
_finish++;
}
}
}
注意： 在C++當(dāng)中內(nèi)置類(lèi)型也可以看作是一個(gè)類(lèi)，它們也有自己的默認(rèn)構(gòu)造函數(shù)，所以在給resize函數(shù)的參數(shù)val設(shè)置缺省值時(shí)，設(shè)置為T(mén)( )即可。
empty
empty函數(shù)可以直接通過(guò)比較容器當(dāng)中的_start和_finish指針的指向來(lái)判斷容器是否為空，若所指位置相同，則該容器為空。
bool empty()const
{
return _start == _finish;
}
修改容器內(nèi)容相關(guān)函數(shù)
push_back
要尾插數(shù)據(jù)首先得判斷容器是否已滿，若已滿則需要先進(jìn)行增容，然后將數(shù)據(jù)尾插到_finish指向的位置，再將_finish++即可。
//尾插數(shù)據(jù)
void push_back(const T& x)
{
if (_finish == _endofstorage) //判斷是否需要增容
{
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //將容量擴(kuò)大為原來(lái)的兩倍
reserve(newcapacity); //增容
}
*_finish = x; //尾插數(shù)據(jù)
_finish++; //_finish指針后移
}
pop_back
尾刪數(shù)據(jù)之前也得先判斷容器是否為空，若為空則做斷言處理，若不為空則將_finish–即可。
//尾刪數(shù)據(jù)
void pop_back()
{
assert(!empty()); //容器為空則斷言
_finish--; //_finish指針前移
}
insert
insert函數(shù)可以在所給迭代器pos位置插入數(shù)據(jù)，在插入數(shù)據(jù)前先判斷是否需要增容，然后將pos位置及其之后的數(shù)據(jù)統(tǒng)一向后挪動(dòng)一位，以留出pos位置進(jìn)行插入，最后將數(shù)據(jù)插入到pos位置即可。
//在pos位置插入數(shù)據(jù)
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage) //判斷是否需要增容
{
size_t len = pos - _start; //記錄pos與_start之間的間隔
size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //將容量擴(kuò)大為原來(lái)的兩倍
reserve(newcapacity); //增容
pos = _start + len; //通過(guò)len找到pos在增容后的容器當(dāng)中的位置
}
//將pos位置及其之后的數(shù)據(jù)統(tǒng)一向后挪動(dòng)一位，以留出pos位置進(jìn)行插入
iterator end = _finish;
while (end >= pos + 1)
{
*end = *(end - 1);
end--;
}
*pos = x; //將數(shù)據(jù)插入到pos位置
_finish++; //數(shù)據(jù)個(gè)數(shù)增加一個(gè)，_finish后移
}
注意： 若需要增容，則需要在增容前記錄pos與_start之間的間隔，然后通過(guò)該間隔確定在增容后的容器當(dāng)中pos的指向，否則pos還指向原來(lái)被釋放的空間。
erase
erase函數(shù)可以刪除所給迭代器pos位置的數(shù)據(jù)，在刪除數(shù)據(jù)前需要判斷容器釋放為空，若為空則需做斷言處理，刪除數(shù)據(jù)時(shí)直接將pos位置之后的數(shù)據(jù)統(tǒng)一向前挪動(dòng)一位，將pos位置的數(shù)據(jù)覆蓋即可。
//刪除pos位置的數(shù)據(jù)
iterator erase(iterator pos)
{
assert(!empty()); //容器為空則斷言
//將pos位置之后的數(shù)據(jù)統(tǒng)一向前挪動(dòng)一位，以覆蓋pos位置的數(shù)據(jù)
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
it++;
}
_finish--; //數(shù)據(jù)個(gè)數(shù)減少一個(gè)，_finish前移
return pos;
}
swap
swap函數(shù)用于交換兩個(gè)容器的數(shù)據(jù)，我們可以直接調(diào)用庫(kù)當(dāng)中的swap函數(shù)將兩個(gè)容器當(dāng)中的各個(gè)成員變量進(jìn)行交換即可。
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
訪問(wèn)容器相關(guān)函數(shù)
operator[ ]
vector也支持我們使用“下標(biāo)+[ ]”的方式對(duì)容器當(dāng)中的數(shù)據(jù)進(jìn)行訪問(wèn)，實(shí)現(xiàn)時(shí)直接返回對(duì)應(yīng)位置的數(shù)據(jù)即可。
T& operator[](size_t i)
{
assert(i < size()); //檢測(cè)下標(biāo)的合法性
return _start[i]; //返回對(duì)應(yīng)數(shù)據(jù)
}
const T& operator[](size_t i)const
{
assert(i < size()); //檢測(cè)下標(biāo)的合法性
return _start[i]; //返回對(duì)應(yīng)數(shù)據(jù)
}
注意： 重載運(yùn)算符[ ]時(shí)需要重載一個(gè)適用于const容器的，因?yàn)閏onst容器通過(guò)“下標(biāo)+[ ]”獲取到的數(shù)據(jù)只允許進(jìn)行讀操作，不能對(duì)數(shù)據(jù)進(jìn)行修改。
測(cè)試相關(guān)接口函數(shù)：
測(cè)試1.對(duì)元素的訪問(wèn)->迭代器.運(yùn)算符重載[]
將容器V1按照[]訪問(wèn)，按照迭代器訪問(wèn)，按照范圍for訪問(wèn)。
void test_vector1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end())
{
*it *= 10;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
測(cè)試結(jié)果：
測(cè)試2.resize
測(cè)試resize
void test_vector2()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.resize(10);
vector<string> v2;
//v2.resize(10, string("xxx"));
v2.resize(10, "xxx");
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
測(cè)試3.insert
測(cè)試Insert
void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(7);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
vector<int>::iterator it = v.begin() + 2;
v.insert(it, 30);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//v.insert(v.begin(), 30);
v.insert(v.begin() + 3, 30);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
測(cè)試4.erase
測(cè)試rease
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(7);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
auto pos = v.begin();
v.erase(pos);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.begin() + 3);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
測(cè)試5.賦值重載與拷貝構(gòu)造：
定義v1，然后拷貝給v2,在將v3賦值給v1:
void test_vector7()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(1);
v1.push_back(1);
v1.push_back(1);
v1.push_back(1);
//拷貝構(gòu)造
vector<int> v2(v1);
cout << "v1為" << endl;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
cout << "拷貝v2為" << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
v3.push_back(40);
v1 = v3;
cout << "賦值后v1為" << endl;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
測(cè)試結(jié)果：
vector模擬實(shí)現(xiàn)源碼展示：
模擬實(shí)現(xiàn)中，我們沒(méi)有進(jìn)行對(duì)其定義與聲明分離，而是將測(cè)試函數(shù)寫(xiě)成成員函數(shù)包裝在命名空間里。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-754899.html
vector.h
#pragma once
#include<assert.h>
namespace NIC
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
vector()
{}
//構(gòu)造2：
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}
//構(gòu)造3
vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
vector(int n, const T& val = T())
{
reserve(n);
for (int i = 0; i < n; i++)
{
push_back(val);
}
}
// v2(v1)
//拷貝構(gòu)造：現(xiàn)代寫(xiě)法：
vector(const vector<T>& v)
{
reserve(v.capacity());
for (auto& e : v)
{
push_back(e);
}
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_endofstorage, v._endofstorage);
}
// v1 = v3
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}
~vector()
{
delete[] _start;
_start = _finish = _endofstorage = nullptr;
}
void reserve(size_t n)
{
if (n > capacity())
{
T* tmp = new T[n];
size_t sz = size();
if (_start)
{
//memcpy(tmp, _start, sizeof(T) * sz);
for (size_t i = 0; i < sz; i++)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz;
_endofstorage = _start + n;
}
}
// T int
// T string
// T vector<int>
//void resize(size_t n, T val = T())
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;
}
}
}
void push_back(const T& x)
{/*
if (_finish == _endofstorage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
*_finish = x;
++_finish;*/
insert(end(), x);
}
void insert(iterator pos, const T& x)
{
assert(pos >= _start);
assert(pos <= _finish);
if (_finish == _endofstorage)
{
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : capacity() * 2);
pos = _start + len;
}
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
*pos = x;
++_finish;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
iterator it = pos + 1;
while (it < _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
T& operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}
const T& operator[](size_t pos) const
{
assert(pos < size());
return _start[pos];
}
size_t capacity() const
{
return _endofstorage - _start;
}
size_t size() const
{
return _finish - _start;
}
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
void test_vector1()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
for (size_t i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
vector<int>::iterator it = v.begin();
while (it != v.end())
{
*it *= 10;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector2()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
v1.push_back(4);
v1.push_back(5);
v1.resize(10);
vector<string> v2;
//v2.resize(10, string("xxx"));
v2.resize(10, "xxx");
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
}
void test_vector3()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(7);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
vector<int>::iterator it = v.begin() + 2;
v.insert(it, 30);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
//v.insert(v.begin(), 30);
v.insert(v.begin() + 3, 30);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector4()
{
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
v.push_back(6);
v.push_back(7);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
auto pos = v.begin();
v.erase(pos);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
v.erase(v.begin() + 3);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
//void test_vector5()
//{
// // 1 2 3 4 5
// // 1 2 3 4 5 6
// // 2 2 3 4 5
// std::vector<int> v;
// v.push_back(1);
// v.push_back(2);
// v.push_back(3);
// v.push_back(4);
// v.push_back(5);
// //v.push_back(6);
// for (auto e : v)
// {
// cout << e << " ";
// }
// cout << endl;
// auto it = v.begin();
// while (it != v.end())
// {
// // vs2019進(jìn)行強(qiáng)制檢查，erase以后認(rèn)為it失效了，不能訪問(wèn)，訪問(wèn)就報(bào)錯(cuò)
// if (*it % 2 == 0)
// {
// v.erase(it);
// }
// ++it;
// }
// for (auto e : v)
// {
// cout << e << " ";
// }
// cout << endl;
//}
void test_vector5()
{
//std::vector<int> v;
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(4);
v.push_back(5);
v.push_back(6);
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector6()
{
vector<string> v;
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
v.push_back("111111111111111111111");
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
void test_vector7()
{
vector<int> v1;
v1.push_back(1);
v1.push_back(1);
v1.push_back(1);
v1.push_back(1);
v1.push_back(1);
//拷貝構(gòu)造
vector<int> v2(v1);
cout << "v1為" << endl;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
cout << "拷貝v2為" << endl;
for (auto e : v2)
{
cout << e << " ";
}
cout << endl;
vector<int> v3;
v3.push_back(10);
v3.push_back(20);
v3.push_back(30);
v3.push_back(40);
v1 = v3;
cout << "賦值后v1為" << endl;
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
}
void test_vector8()
{
//vector<int> v0(10, 0);
vector<string> v1(10, "xxxx");
for (auto e : v1)
{
cout << e << " ";
}
cout << endl;
vector<int> v2;
v2.push_back(10);
v2.push_back(20);
v2.push_back(30);
v2.push_back(40);
vector<int> v3(v2.begin(), v2.end());
string str("hello world");
vector<int> v4(str.begin(), str.end());
for (auto e : v3)
{
cout << e << " ";
}
cout << endl;
for (auto e : v4)
{
cout << e << " ";
}
cout << endl;
}
}
test.c
test.c用于測(cè)試我們實(shí)現(xiàn)的相關(guān)接口函數(shù)：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-754899.html
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;
#include "vector.h"
int main()
{
NIC::test_vector7();
return 0;
}
到了這里，關(guān)于【C++初階】STL詳解（四）vector的模擬實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[STL] vector 模擬實(shí)現(xiàn)詳解](https://imgs.yssmx.com/Uploads/2024/02/595014-1.png)
![C++ [STL之vector模擬實(shí)現(xiàn)]](https://imgs.yssmx.com/Uploads/2024/02/500268-1.png)
