小型教育網(wǎng)站開發(fā)與設(shè)計(jì)品牌推廣的步驟和技巧
?
?📝個(gè)人主頁:@Sherry的成長之路
🏠學(xué)習(xí)社區(qū):Sherry的成長之路(個(gè)人社區(qū))
📖專欄鏈接:C++初階
🎯長路漫漫浩浩,萬事皆有期待
【C++初階】C++STL詳解(三)—— vector的介紹及使用
文章目錄
- vector各函數(shù)接口總覽
- vector當(dāng)中的成員變量介紹
- 默認(rèn)成員函數(shù)
- 構(gòu)造函數(shù)1
- 構(gòu)造函數(shù)2
- 構(gòu)造函數(shù)3
- 拷貝構(gòu)造函數(shù)
- 賦值運(yùn)算符重載函數(shù)
- 析構(gòu)函數(shù)
- 迭代器相關(guān)函數(shù)
- begin和end
- 反向迭代器
- 容量和大小相關(guān)函數(shù)
- size和capacity
- reserve
- resize
- empty
- 修改容器內(nèi)容相關(guān)函數(shù)
- push_back
- pop_back
- insert
- erase
- swap
- 訪問容器相關(guān)函數(shù)
- operator[ ]
- vector迭代器失效問題
- 迭代器失效問題舉例
- 迭代器失效解決方法
- 總結(jié):
vector各函數(shù)接口總覽
namespace sherry
{//模擬實(shí)現(xiàn)vectortemplate<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);//訪問容器相關(guān)函數(shù)T& operator[](size_t i);const T& operator[](size_t i)const;private:iterator _start; //指向容器的頭iterator _finish; //指向有效數(shù)據(jù)的尾iterator _endofstorage; //指向容器的尾};
}
注
:為了防止與標(biāo)準(zhǔn)庫當(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è)容器的尾。
默認(rèn)成員函數(shù)
構(gòu)造函數(shù)1
vector支持一個(gè)無參的構(gòu)造函數(shù),對(duì)于這個(gè)無參的構(gòu)造函數(shù),我們直接將構(gòu)造對(duì)象的三個(gè)成員變量都設(shè)置為空指針即可。
vector():_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{}
構(gòu)造函數(shù)2
vector支持使用一段迭代器區(qū)間進(jìn)行對(duì)象的構(gòu)造。因?yàn)樵摰鲄^(qū)間可以是其他容器的迭代器區(qū)間,也就是說該函數(shù)接收到的迭代器的類型是不確定的,所以我們這里需要將該構(gòu)造函數(shù)設(shè)計(jì)為一個(gè)函數(shù)模板,在函數(shù)體內(nèi)將該迭代器區(qū)間的數(shù)據(jù)一個(gè)個(gè)尾插到容器當(dāng)中即可。
template<class InputIterator> //模板函數(shù)
vector(InputIterator first, InputIterator last):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{//將迭代器區(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)中即可。
vector(size_t n, const T& val=T()):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //調(diào)用reserve函數(shù)將容器容量設(shè)置為nfor (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ù)一次性開辟好空間,避免調(diào)用push_back函數(shù)時(shí)需要增容多次,導(dǎo)致效率降低。
2)該構(gòu)造函數(shù)還需要實(shí)現(xiàn)兩個(gè)重載函數(shù)。
vector(long n, const T& val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //調(diào)用reserve函數(shù)將容器容量設(shè)置為nfor (size_t i = 0; i < n; i++) //尾插n個(gè)值為val的數(shù)據(jù)到容器當(dāng)中{push_back(val);}
}
vector(int n, const T& val):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(n); //調(diào)用reserve函數(shù)將容器容量設(shè)置為nfor (int i = 0; i < n; i++) //尾插n個(gè)值為val的數(shù)據(jù)到容器當(dāng)中{push_back(val);}
}
可以看到,這兩個(gè)重載函數(shù)與之不同的就是其參數(shù)n的類型不同,但這卻是必要的,否則當(dāng)我們使用以下代碼時(shí),編譯器會(huì)優(yōu)先與構(gòu)造函數(shù)2相匹配。
vector<int> v(5, 7); //調(diào)用構(gòu)造函數(shù)3 ?
并且因?yàn)闃?gòu)造函數(shù)2當(dāng)中對(duì)參數(shù)first和last進(jìn)行了解引用(而int類型不能進(jìn)行解引用操作)而報(bào)錯(cuò)。
拷貝構(gòu)造函數(shù)
vector的構(gòu)造函數(shù)涉及深拷貝問題,這里提供兩種深拷貝的寫法:
寫法一:傳統(tǒng)寫法
拷貝構(gòu)造的傳統(tǒng)寫法的思想是我們最容易想到的:先開辟一塊與該容器大小相同的空間,然后將該容器當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過來即可,最后更新_finish和_endofstorage的值即可。
//傳統(tǒng)寫法
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{_start = new T[v.capacity()]; //開辟一塊和容器v大小相同的空間for (size_t i = 0; i < v.size(); i++) //將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過來{_start[i] = v[i];//memcpy(_start.v._start,sizeof(T)*v.size());}_finish = _start + v.size(); //容器有效數(shù)據(jù)的尾_endofstorage = _start + v.capacity(); //整個(gè)容器的尾
}
注意
: 將容器當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過來時(shí)不能使用memcpy函數(shù),當(dāng)vector存儲(chǔ)的數(shù)據(jù)是內(nèi)置類型或無需進(jìn)行深拷貝的自定義類型時(shí),使用memcpy函數(shù)是沒什么問題的,但當(dāng)vector存儲(chǔ)的數(shù)據(jù)是需要進(jìn)行深拷貝的自定義類型時(shí),使用memcpy函數(shù)的弊端就體現(xiàn)出來了。
例如,如果vector當(dāng)中存儲(chǔ)的元素類型是內(nèi)置類型(int)或淺拷貝的自定義類型(Date),使用memcpy函數(shù)進(jìn)行進(jìn)行拷貝構(gòu)造是沒問題的,但如果vector當(dāng)中存儲(chǔ)的元素類型是深拷貝的自定義類型(string),則使用memcpy函數(shù)將不能達(dá)到我們想要的效果。
寫法二:現(xiàn)代寫法
拷貝構(gòu)造函數(shù)的現(xiàn)代寫法也比較簡單,使用范圍for(或是其他遍歷方式)對(duì)容器v進(jìn)行遍歷,在遍歷過程中將容器v中存儲(chǔ)的數(shù)據(jù)一個(gè)個(gè)尾插過來即可。
//現(xiàn)代寫法
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{reserve(v.capacity()); //調(diào)用reserve函數(shù)將容器容量設(shè)置為與v相同for (const auto& e : v) //將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)尾插過來{push_back(e);}
}
注意
: 在使用范圍for對(duì)容器v進(jìn)行遍歷的過程中,變量e就是每一個(gè)數(shù)據(jù)的拷貝,然后將e尾插到構(gòu)造出來的容器當(dāng)中。就算容器v當(dāng)中存儲(chǔ)的數(shù)據(jù)是string類,在e拷貝時(shí)也會(huì)自動(dòng)調(diào)用string的拷貝構(gòu)造(深拷貝),所以也能夠避免出現(xiàn)與使用memcpy時(shí)類似的問題。
//現(xiàn)代寫法
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
{vector<T>tmp(v.begin(),v.end());swap(tmp);
}
賦值運(yùn)算符重載函數(shù)
vector的賦值運(yùn)算符重載也涉及深拷貝問題,我們這里也提供兩種深拷貝的寫法:
寫法一:傳統(tǒng)寫法
首先判斷是否是給自己賦值,若是給自己賦值則無需進(jìn)行操作。若不是給自己賦值,則先開辟一塊和容器v大小相同的空間,然后將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過來,最后更新_finish和_endofstorage的值即可。
//傳統(tǒng)寫法
vector<T>& operator=(const vector<T>& v)
{if (this != &v) //防止自己給自己賦值{delete[] _start; //釋放原來的空間_start = new T[v.capacity()]; //開辟一塊和容器v大小相同的空間for (size_t i = 0; i < v.size(); i++) //將容器v當(dāng)中的數(shù)據(jù)一個(gè)個(gè)拷貝過來{_start[i] = v[i];}_finish = _start + v.size(); //容器有效數(shù)據(jù)的尾_endofstorage = _start + v.capacity(); //整個(gè)容器的尾}return *this; //支持連續(xù)賦值
}
注意
: 這里和拷貝構(gòu)造函數(shù)的傳統(tǒng)寫法類似,也不能使用memcpy函數(shù)進(jìn)行拷貝。
寫法二:現(xiàn)代寫法
賦值運(yùn)算符重載的現(xiàn)代寫法非常精辟,首先在右值傳參時(shí)并沒有使用引用傳參,因?yàn)檫@樣可以間接調(diào)用vector的拷貝構(gòu)造函數(shù),然后將這個(gè)拷貝構(gòu)造出來的容器v與左值進(jìn)行交換,此時(shí)就相當(dāng)于完成了賦值操作,而容器v會(huì)在該函數(shù)調(diào)用結(jié)束時(shí)自動(dòng)析構(gòu)。
//現(xiàn)代寫法
//v1=v2
vector<T>& operator=(vector<T> v) //編譯器接收右值的時(shí)候自動(dòng)調(diào)用其拷貝構(gòu)造函數(shù)v=v2
{swap(v); //交換這兩個(gè)對(duì)象 v1 與v交換 順便帶走v1return *this; //支持連續(xù)賦值
}
注意
: 賦值運(yùn)算符重載的現(xiàn)代寫法也是進(jìn)行的深拷貝,只不過是調(diào)用的vector的拷貝構(gòu)造函數(shù)進(jìn)行的深拷貝,在賦值運(yùn)算符重載函數(shù)當(dāng)中僅僅是將深拷貝出來的對(duì)象與左值進(jìn)行了交換而已。
析構(gòu)函數(shù)
對(duì)容器進(jìn)行析構(gòu)時(shí),首先判斷該容器是否為空容器,若為空容器,則無需進(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ù)類型的指針。
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í)再讓我們來看看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;
反向迭代器
代碼實(shí)現(xiàn):
namespace sherry
{template<class Iterator, class Ref, class Ptr>struct Reverse_iterator{Iterator _it;typedef Reverse_iterator<Iterator, Ref, Ptr> Self;Reverse_iterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}bool operator!=(const Self& s){return _it != s._it;}};template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;// 反向迭代器適配支持typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;const_reverse_iterator rbegin() const{// list_node<int>*return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}};
從功能上區(qū)分:
容量和大小相關(guān)函數(shù)
size和capacity
對(duì)照著vector當(dāng)中三個(gè)成員遍歷各自的指向,我們可以很容易得出當(dāng)前容器中的有效數(shù)據(jù)個(gè)數(shù)和最大容量。
由于兩個(gè)指針相減的結(jié)果,就是這兩個(gè)指針之間對(duì)應(yīng)類型的數(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)思路也是很簡單的,先判斷所給n是否大于當(dāng)前容器的最大容量(否則無需進(jìn)行任何操作),操作時(shí)直接開辟一塊可以容納n個(gè)數(shù)據(jù)的空間,然后將原容器當(dāng)中的有效數(shù)據(jù)拷貝到該空間,之后將原容器存儲(chǔ)數(shù)據(jù)的空間釋放,并將新開辟的空間交給該容器維護(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]; //開辟一塊可以容納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ù)通過_finish - _start計(jì)算出的有效數(shù)據(jù)的個(gè)數(shù)就是一個(gè)隨機(jī)值了。
2)拷貝容器當(dāng)中的數(shù)據(jù)時(shí),不能使用memcpy函數(shù)進(jìn)行拷貝。
當(dāng)vector當(dāng)中存儲(chǔ)的是string的時(shí)候,雖然使用memcpy函數(shù)reserve出來的容器與原容器當(dāng)中每個(gè)對(duì)應(yīng)的string成員都指向同一個(gè)字符串空間,但當(dāng)釋放原容器空間的時(shí)候,原容器當(dāng)中存儲(chǔ)的每個(gè)string在釋放時(shí)會(huì)調(diào)用string的析構(gòu)函數(shù),將其指向的字符串也進(jìn)行釋放,所以使用memcpy函數(shù)reserve出來的容器當(dāng)中的每一個(gè)string所指向的字符串實(shí)際上是一塊已經(jīng)被釋放的空間,訪問該容器時(shí)就是對(duì)內(nèi)存空間進(jìn)行非法訪問。
所以還是用for循環(huán)將容器當(dāng)中的string一個(gè)個(gè)賦值過來,因?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ǔ)類型的默認(rèn)構(gòu)造函數(shù)所構(gòu)造出來的值。
?2、當(dāng)n小于當(dāng)前的size時(shí),將size縮小到n。
根據(jù)resize函數(shù)的規(guī)則,進(jìn)入函數(shù)我們可以先判斷所給n是否小于容器當(dāng)前的size,若小于,則通過改變_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)置類型也可以看作是一個(gè)類,它們也有自己的默認(rèn)構(gòu)造函數(shù),所以在給resize函數(shù)的參數(shù)val設(shè)置缺省值時(shí),設(shè)置為T( )即可。
empty
empty函數(shù)可以直接通過比較容器當(dāng)中的_start和_finish指針的指向來判斷容器是否為空,若所指位置相同,則該容器為空。
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ò)大為原來的兩倍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)
{if (_finish == _endofstorage) //判斷是否需要增容{size_t len = pos - _start; //記錄pos與_start之間的間隔size_t newcapacity = capacity() == 0 ? 4 : 2 * capacity(); //將容量擴(kuò)大為原來的兩倍reserve(newcapacity); //增容pos = _start + len; //通過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之間的間隔,然后通過該間隔確定在增容后的容器當(dāng)中pos的指向,否則pos還指向原來被釋放的空間。
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)用庫當(dāng)中的swap函數(shù)將兩個(gè)容器當(dāng)中的各個(gè)成員變量進(jìn)行交換即可。
//交換兩個(gè)容器的數(shù)據(jù)
void swap(vector<T>& v)
{//交換容器當(dāng)中的各個(gè)成員變量::swap(_start, v._start);::swap(_finish, v._finish);::swap(_endofstorage, v._endofstorage);
}
注意
: 在此處調(diào)用庫當(dāng)中的swap需要在swap之前加上“::”(作用域限定符),告訴編譯器這里優(yōu)先在全局范圍尋找swap函數(shù),否則編譯器會(huì)認(rèn)為調(diào)用的是正在實(shí)現(xiàn)的swap函數(shù)(就近原則)。
訪問容器相關(guān)函數(shù)
operator[ ]
vector也支持我們使用“下標(biāo)+[ ]”的方式對(duì)容器當(dāng)中的數(shù)據(jù)進(jì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容器通過“下標(biāo)+[ ]”獲取到的數(shù)據(jù)只允許進(jìn)行讀操作,不能對(duì)數(shù)據(jù)進(jìn)行修改。
vector迭代器失效問題
迭代器的主要作用就是讓我們?cè)谑褂酶鱾€(gè)容器時(shí)不用關(guān)心其底層的數(shù)據(jù)結(jié)構(gòu),而vector的迭代器在底層實(shí)際上就是一個(gè)指針。迭代器失效就是指迭代器底層對(duì)應(yīng)指針?biāo)赶虻目臻g被銷毀了,而指向的是一塊已經(jīng)被釋放的空間,如果繼續(xù)使用已經(jīng)失效的迭代器,程序可能會(huì)崩潰。
迭代器失效問題舉例
實(shí)例一:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vector<int>::iterator pos = find(v.begin(), v.end(), 2); //獲取值為2的元素的迭代器v.insert(pos, 10); //在值為2的元素的位置插入10//v: 1 10 2 3 4 5v.erase(pos); //刪除元素2 ???error(迭代器失效)//v: 1 2 3 4 5return 0;
}
在該代碼中,我們本意是使用元素2的迭代器在原序列中2的位置插入一個(gè)10,然后將2刪除,但我們實(shí)際上獲取的是指向2的指針,當(dāng)我們?cè)?的位置插入10后,該指針就指向了10,所以我們之后刪除的實(shí)際上是10,而不是2。
實(shí)例二:
#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //刪除容器當(dāng)中的全部偶數(shù){v.erase(it);}it++;}return 0;
}
該代碼看上去實(shí)際上并沒有什么錯(cuò)誤,但如果你畫圖仔細(xì)分析,你就會(huì)發(fā)現(xiàn)該代碼的問題所在,迭代器訪問到了不屬于容器的內(nèi)存空間,導(dǎo)致程序崩潰。
不僅如此,而且在迭代器遍歷容器中的元素進(jìn)行判斷時(shí),并沒有對(duì)1、3、5元素進(jìn)行判斷。
迭代器失效解決方法
使用迭代器時(shí),永遠(yuǎn)記住一句話:每次使用前,對(duì)迭代器進(jìn)行重新賦值。
實(shí)例一解決方案:
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;int main()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);v.push_back(5);//v: 1 2 3 4 5vector<int>::iterator pos = find(v.begin(), v.end(), 2); //獲取值為2的元素的迭代器v.insert(pos, 10); //在值為2的元素的位置插入10//v: 1 10 2 3 4 5pos = find(v.begin(), v.end(), 2); //重新獲取值為2的元素的迭代器v.erase(pos); //刪除元素2//v: 1 10 3 4 5return 0;
}
對(duì)于實(shí)例一,我們?cè)谑褂玫鲃h除元素2時(shí)對(duì)其進(jìn)行重新賦值便可以解決。
實(shí)例二解決方案:
#include <iostream>
#include <vector>
using namespace std;int main()
{vector<int> v;for (size_t i = 1; i <= 6; i++){v.push_back(i);}vector<int>::iterator it = v.begin();while (it != v.end()){if (*it % 2 == 0) //刪除容器當(dāng)中的全部偶數(shù){it = v.erase(it); //刪除后獲取下一個(gè)元素的迭代器}else{it++; //是奇數(shù)則it++}}return 0;
}
對(duì)于實(shí)例二,我們可以接收erase函數(shù)的返回值(erase函數(shù)返回刪除元素的后一個(gè)元素的新位置),并且控制代碼的邏輯:當(dāng)元素被刪除后繼續(xù)判斷該位置的元素(因?yàn)樵撐恢玫脑匾呀?jīng)更新,需要再次判斷)。
總結(jié):
今天我們比較詳細(xì)地完成了vector類的學(xué)習(xí),了解了一些有關(guān)的底層原理。接下來,我們將進(jìn)行STL中vector類的模擬實(shí)現(xiàn)。希望我的文章和講解能對(duì)大家的學(xué)習(xí)提供一些幫助。
當(dāng)然,本文仍有許多不足之處,歡迎各位小伙伴們隨時(shí)私信交流、批評(píng)指正!我們下期見~