西藏城鄉(xiāng)住房建設(shè)廳網(wǎng)站百度賬號(hào)快速注冊入口
這里寫目錄標(biāo)題
- 一、vector的介紹及使用
- 1. vector的介紹
- 2. 構(gòu)造函數(shù)
- 3. 遍歷方式
- 4. 容量操作及空間增長問題
- 5. 增刪查改
- 6. vector二維數(shù)組
- 二、vector的模擬實(shí)現(xiàn)
- 1. 構(gòu)造函數(shù)
- 2. 迭代器和基本接口
- 3. reserve和resize
- 4. push_back和pop_back
- 5. insert和erase
- 5. 迭代器失效問題
- 5. 淺拷貝問題
- 三、vector模擬實(shí)現(xiàn)整體源碼
一、vector的介紹及使用
1. vector的介紹
vector
是表示可變大小數(shù)組的序列容器。- 就像數(shù)組一樣,vector也采用的連續(xù)存儲(chǔ)空間來存儲(chǔ)元素。也就是意味著可以采用下標(biāo)對(duì)vector的元素進(jìn)行訪問,和數(shù)組一樣高效。但是又不像數(shù)組,它的大小是可以動(dòng)態(tài)改變的,而且它的大小會(huì)被容器自動(dòng)處理。
- 本質(zhì)講,vector使用動(dòng)態(tài)分配數(shù)組來存儲(chǔ)它的元素。當(dāng)新元素插入時(shí)候,這個(gè)數(shù)組需要被重新分配大小,為了增加存儲(chǔ)空間。其做法是,分配一個(gè)新的數(shù)組,然后將全部元素移到這個(gè)數(shù)組。 就時(shí)間而言,這是一個(gè)相對(duì)代價(jià)高的任務(wù),因?yàn)槊慨?dāng)一個(gè)新的元素加入到容器的時(shí)候,vector并不會(huì)每次都重新分配大小。
- vector分配空間策略:vector會(huì)分配一些額外的空間以適應(yīng)可能的增長,因?yàn)榇鎯?chǔ)空間比實(shí)際需要的存儲(chǔ)空間更大。 不同的庫采用不同的策略權(quán)衡空間的使用和重新分配。但是無論如何,重新分配都應(yīng)該是對(duì)數(shù)增長的間隔大小,以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的。
- 因此,vector占用了更多的存儲(chǔ)空間,為了獲得管理存儲(chǔ)空間的能力,并且以一種有效的方式動(dòng)態(tài)增長。
- 與其它動(dòng)態(tài)序列容器相比(
deque, list and forward_list
), vector在訪問元素的時(shí)候更加高效,在末尾添加和刪除元素相對(duì)高效。 對(duì)于其它不在末尾的刪除和插入操作,效率更低。比起list和forward_list統(tǒng)一的迭代器和引用更好。
2. 構(gòu)造函數(shù)
vector學(xué)習(xí)時(shí)一定要學(xué)會(huì)查看文檔:vector文檔介紹,vector在實(shí)際中非常的重要,在實(shí)際中我們熟悉常見的接口就可以。當(dāng)然我們使用vector之前需要包頭文件#include<vector>
。
下面我們來看一下vector的構(gòu)造函數(shù):
因?yàn)樵趘ector中是重載了[]訪問運(yùn)算符的,所以我們可以直接使用[]訪問運(yùn)算符來訪問,vector中的元素。下面我們直接來舉幾個(gè)例子來看一下構(gòu)造函數(shù)的用法:
這里我們可以看到和string不同的是,這里的capacity表示的就是所開辟的空間中最多能存儲(chǔ)的元素的個(gè)數(shù),但在string中則需要多開辟一個(gè)空間為’\0’預(yù)留位置。
迭代器區(qū)間構(gòu)造本質(zhì)上是一個(gè)函數(shù)模板,所以我們可以用任意類來構(gòu)造vector對(duì)象。
3. 遍歷方式
💕 [ ]遍歷
int main()
{vector<int> v2(5, 0);for (int i = 0; i < v2.size(); i++)cout << v2[i] << " ";cout << endl;return 0;
}
當(dāng)然了,因?yàn)?code>[ ]重載了const和非const兩個(gè)版本,所以[ ]
既可以對(duì)const對(duì)象使用又可以對(duì)非const對(duì)象使用。
💕 使用迭代器遍歷
vector和string一樣,也有反向迭代器rbegin和rend,他們表示獲取最后一個(gè)數(shù)據(jù)位置的reverse_iterator和第一個(gè)數(shù)據(jù)前一個(gè)位置的reverse_iterator。
int main()
{vector<int> v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);vector<int>::iterator it = v2.begin();while (it != v2.end()){cout << *it << " ";}cout << endl;vector<int>::reverse_iterator rit = v2.rbegin();while (rit != v2.rend()){cout << *rit << " ";}cout << endl;return 0;
}
💕 使用范圍for遍歷
int main()
{vector<int> v2;v2.push_back(1);v2.push_back(2);v2.push_back(3);v2.push_back(4);v2.push_back(5);for (auto e : v2)cout << e << " ";cout << endl;return 0;
}
當(dāng)然范圍for遍歷并不是什么高深的語法,它的本質(zhì)還是被替換成了迭代器進(jìn)行遍歷。
4. 容量操作及空間增長問題
💕 容量操作
這是vector中的容量操作的幾個(gè)api接口,其中第二個(gè)
max_size
和shrink_to_fit
是我們在之前學(xué)習(xí)string的時(shí)候沒有見過的接口,其中max_size是返回這個(gè)容器中可以容納的最多的元素的個(gè)數(shù),這個(gè)接口我們一般都不會(huì)用。shrink_to_fit是讓我們?nèi)萜鞯娜萘繙p少到容器中元素的個(gè)數(shù)。因?yàn)榭s容所消耗的代價(jià)是比較大的。一般都不會(huì)輕易縮容,所以這個(gè)接口我們一般也不會(huì)用。
最重要的兩個(gè)接口還是reserve和rsize,reserve只用于擴(kuò)容,不會(huì)改變size的大小,但是resize不僅會(huì)擴(kuò)容,他還會(huì)改變size的個(gè)數(shù)。
💕 空間增長問題
對(duì)于不同的STL版本,他的擴(kuò)容機(jī)制也是不同的。我們知道,vs下和g++分別用的是不同的STL版本,下面我們分別來看一下他們的擴(kuò)容機(jī)制有什么不同。
//測試vector的默認(rèn)擴(kuò)容機(jī)制
void TestVectorExpand()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}
vs下的擴(kuò)容機(jī)制:
g++下的擴(kuò)容機(jī)制:
這里我們需要注意幾點(diǎn):
- capacity的代碼在vs和g++下分別運(yùn)行會(huì)發(fā)現(xiàn),vs下capacity是按1.5倍增長的,g++是按2倍增長的。這個(gè)問題經(jīng)常會(huì)考察,不要固化的認(rèn)為,vector增容都是2倍,具體增長多少是根據(jù)具體的需求定義的。vs是PJ版本STL,g++是SGI版本STL
- reserve只負(fù)責(zé)開辟空間,如果確定知道需要用多少空間,reserve可以緩解vector增容的代價(jià)缺陷問
題。- resize在開空間的同時(shí)還會(huì)進(jìn)行初始化,影響size
5. 增刪查改
push_back和push_back這兩個(gè)接口我們在string中見過,表示的是尾插和尾刪,這里我們不再細(xì)說。
find
和swap
注意: 這里的find
函數(shù)是算法庫里的一個(gè)函數(shù),而并非vector提供的接口。
這里需要提供一段迭代器區(qū)間,然后在后面跟上我們需要查找的元素,如果查找成功就返回他的迭代器,如果查找不成功,就返回end迭代器位置。
既然算法庫里面已經(jīng)有swap這個(gè)接口了,為什么在vector中還要再次設(shè)計(jì)一個(gè)呢?
其實(shí)這是因?yàn)樗惴◣熘械膕wap函數(shù)具有深拷貝的問題,深拷貝的代價(jià)是很大的,對(duì)于vector這樣的類來說直接使用算法庫里面的swap函數(shù)的拷貝代價(jià)太大,所以vector自己提供了一個(gè)自己的swap函數(shù),其實(shí)vector中的swap函數(shù)的內(nèi)部也是用了算法庫中的swap。
insert
和erase
這里的insert
和erase
和string也有所不同,string中的這兩個(gè)接口在操作完成后會(huì)返回對(duì)象本身,但是在vector中則是操作完成后返回要插入或者刪除的那個(gè)位置的迭代器。當(dāng)然了,不光光是vector,STL中的所有容器的插入和刪除接口都是這樣設(shè)計(jì)的。
基本用法如下:
這里我們需要注意一點(diǎn)是:當(dāng)我們刪除一個(gè)元素的時(shí)候,刪除位置的范圍是
【begin(),end())
,但是當(dāng)我們插入一個(gè)元素的時(shí)候,插入位置的范圍是【begin(),end()】
。
當(dāng)然了,這里存在一種迭代器失效的問題,下面我們在模擬實(shí)現(xiàn)的時(shí)候再來細(xì)說。
6. vector二維數(shù)組
int main()
{//設(shè)置二維數(shù)組的行數(shù)和列數(shù)int row = 5, col = 5;//創(chuàng)建二維數(shù)組并初始化為全0vector<vector<int>> vv(row, vector<int>(col, 0));//獲取二維數(shù)組的行數(shù)int size_row = vv.size();//獲取二維數(shù)組的列數(shù)int size_col = vv[0].size();//插入列元素vv[0].push_back(100);//插入行vv.push_back(vector<int>(5, 1));//遍歷二維數(shù)組for (size_t i = 0; i < vv.size(); i++){for (size_t j = 0; j < vv[i].size(); j++){cout << vv[i][j] << " ";}cout << endl;}return 0;
}
二、vector的模擬實(shí)現(xiàn)
當(dāng)我們在模擬實(shí)現(xiàn)vector容器之前,需要先來參考一下源碼,主要是為了整體看一下庫里面vector的底層實(shí)現(xiàn)邏輯。
那么我們應(yīng)該如何參考源碼呢?讓我們完全看懂源碼是不可能的,所以我們應(yīng)該抓住重點(diǎn)核心來看,最重要的就是這個(gè)類的成員變量和核心的成員函數(shù),下面我們來看一下我們在模擬vector之前需要關(guān)注的源碼中的地方。
template <class T, class Alloc = alloc>
class vector
{
public:typedef T value_type;typedef value_type* iterator;typedef const value_type* const_iterator;//...size_type size() const { return size_type(end() - begin()); }size_type max_size() const { return size_type(-1) / sizeof(T); }size_type capacity() const { return size_type(end_of_storage - begin()); }iterator begin() {return start;}iterator end() {return finish;}
private:iterator start;iterator finish;iterator end_of_storage;
};
通過這一部分的源碼我們可以看到vector中的三個(gè)成員變量是由三個(gè)迭代器實(shí)現(xiàn)的,在這里迭代器是一個(gè)原生指針。然后我們根據(jù)源碼中的size()
和capacity()
等函數(shù)??梢酝茢喑鲞@三個(gè)指針?biāo)淼囊饬x:
start
指向第一個(gè)元素的位置,finish
指向容器中有效元素中最后一個(gè)元素后面的位置,end_of_storage
指向容器能容納最大容量之后的位置。其實(shí)和我們在C數(shù)據(jù)結(jié)構(gòu)階段實(shí)現(xiàn)的順序表沒有什么本質(zhì)的區(qū)別,不過是使用了三個(gè)指針來維護(hù)所開辟的空間罷了。
1. 構(gòu)造函數(shù)
💕 默認(rèn)無參構(gòu)造
//無參構(gòu)造
vector():_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{}
💕 n個(gè)val構(gòu)造
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);}
}
我們在寫構(gòu)造函數(shù)的時(shí)候?yàn)榱朔乐挂爸羔樀某霈F(xiàn),需要在初始化列表中將三個(gè)指針全部初始化為空。為了減少頻繁擴(kuò)容所帶來的消耗,可以先調(diào)用reserve
函數(shù)預(yù)先開辟一塊空間,然后依次將要初始化的對(duì)象進(jìn)行尾插。這里我們可以要初始化的值val預(yù)先設(shè)定缺省參數(shù),這里我們不能將缺省值設(shè)置為0,因?yàn)橐跏蓟膶?duì)象可能是int類型、double類型、還有可能是一個(gè)自定義類型,所以這里我們可以將缺省值給定為一個(gè)T類型
的匿名對(duì)象。
這里我們還需要注意的是:引用會(huì)延長匿名對(duì)象的生命周期到引用對(duì)象域結(jié)束,因?yàn)檫@里的val
就是匿名對(duì)象的別名,如果匿名對(duì)象在當(dāng)前行就之后就銷毀的話,val也會(huì)被銷毀。同時(shí),因?yàn)槟涿麑?duì)象具有常性,所以我們需要用const來修飾val。
💕 迭代器區(qū)間構(gòu)造
template <class InputIterator>
vector(InputIterator first, InputIterator end):_start(nullptr),_finish(nullptr),_end_of_storage(nullptr)
{while (first != end){push_back(*first);first++;}
}
這里我們提供一個(gè)迭代器模板,可以提供任意類型的迭代器。
在提供以上的函數(shù)接口之后,如果我們嘗試構(gòu)造一個(gè)內(nèi)容為5個(gè)10的對(duì)象時(shí)候,這里會(huì)出現(xiàn)間接尋址的錯(cuò)誤,這是因?yàn)榫幾g器在進(jìn)行模板實(shí)例化以及函數(shù)參數(shù)匹配時(shí)會(huì)調(diào)用最匹配的那一個(gè)函數(shù),當(dāng)我們將T實(shí)例化為int之后,由于兩個(gè)參數(shù)都是int,所以迭代器構(gòu)造函數(shù)會(huì)直接將Inputlterator實(shí)例化為int,但是如果n個(gè)val構(gòu)造來說,不僅需要將T實(shí)例化為int,還需要將第一個(gè)參數(shù)隱式轉(zhuǎn)換為size_t;所以編譯器會(huì)優(yōu)先調(diào)用迭代器區(qū)間構(gòu)造函數(shù),直接對(duì)int類型解引用的話就會(huì)報(bào)錯(cuò)。
為了防止這種情況發(fā)生,我們可以采取和STL中一樣的解決方式——重載一份第一個(gè)參數(shù)為int的構(gòu)造函數(shù)。
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)造
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];memcpy(_start, v._start, v.size() * sizeof(T));//——會(huì)導(dǎo)致淺拷貝問題_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}
2. 迭代器和基本接口
💕 迭代器的實(shí)現(xiàn)
為了能夠使用范圍for循環(huán)和其他別的功能,這里我們來實(shí)現(xiàn)一下vector的迭代器,同時(shí),為了能夠?qū)onst對(duì)象也使用迭代器,這里我們還需要設(shè)計(jì)一份const版本的迭代器。
typedef T* iterator;
typedef const T* const_iterator;
//迭代器的實(shí)現(xiàn)
iterator begin()
{return _start;
}
iterator end()
{return _finish;
}const_iterator begin() const
{return _start;
}
const_iterator end() const
{return _finish;
}
💕 基本接口的實(shí)現(xiàn)
size_t size() const
{return _finish - _start;
}
size_t capacity() const
{return _end_of_storage - _start;
}
size_t empty() const
{return _start == _finish;
}
void clear()
{_finish = _start;
}
//析構(gòu)函數(shù)
~vector()
{delete[] _start;_start = _finish = _end_of_storage = nullptr;
}T& operator[](size_t pos)
{assert(pos < size());return _start[pos];
}
const T& operator[](size_t pos) const
{assert(pos < size());return _start[pos];
}
由于以上的接口比較簡單,這里我們就不再做過多的解釋。
3. reserve和resize
💕 reserve的實(shí)現(xiàn)
void reserve(size_t n)
{if (n > capacity()){int sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}
如果我們需要擴(kuò)的容量的大小小于原來的容量時(shí),我們默認(rèn)不執(zhí)行擴(kuò)容操作。這里我們需要先定義一個(gè)臨時(shí)變量sz將擴(kuò)容之前的元素個(gè)數(shù)保存下來,因?yàn)閿U(kuò)容之后給finish賦值時(shí),start已經(jīng)指向了新的空間,但是finishi還未改變,所以直接使用size()會(huì)出現(xiàn)問題,當(dāng)然了,在這個(gè)接口里面存在著一個(gè)嚴(yán)重的問題,我們到后面會(huì)指正。
💕 resize的實(shí)現(xiàn)
void resize(size_t n,T val = T())
{if (n < size()){//刪除數(shù)據(jù)_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = val;_finish++;}}
}
這里我們和前面的構(gòu)造函數(shù)一樣,給一個(gè)匿名對(duì)象的缺省值,如果需要擴(kuò)的容量比原來的容量小時(shí),
我們只需要將容器中的有效的數(shù)據(jù)個(gè)數(shù)size()減少即可。否則的話,如果n的個(gè)數(shù)大于原來的容量時(shí),我們可以先使用reserve函數(shù)將原來的空間擴(kuò)大,然后再依次添加到finish之后即可。直到finish的大小等于capacity的大小。
4. push_back和pop_back
//push_back的實(shí)現(xiàn)
void push_back(const T& x)
{if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;
}//pop_back的實(shí)現(xiàn)
void pop_back()
{assert(!empty());_finish--;
}
這兩個(gè)接口的實(shí)現(xiàn)就非常簡單了,push_back的實(shí)現(xiàn),如果finish等于capacity容量的大小我們則需要先調(diào)用reserve函數(shù)進(jìn)行擴(kuò)容。當(dāng)然在這里我們判斷capacity的時(shí)候,需要特殊處理一下,因?yàn)槿绻谝淮蝿?chuàng)建的未初始化的對(duì)象的capacity是0時(shí),直接調(diào)用reverse(capacity)會(huì)出現(xiàn)問題。對(duì)于pop_back的實(shí)現(xiàn)我們還需要先實(shí)現(xiàn)一個(gè)判空操作的函數(shù)。
5. insert和erase
💕 insert
iterator insert(iterator pos, const T& val)
{assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;
}
這里的實(shí)現(xiàn)邏輯也很簡單,先判斷要插入的位置是否符合規(guī)范,在判斷是否需要擴(kuò)容,最后我們重后往前挪動(dòng)數(shù)據(jù)即可。當(dāng)然,最后別忘了finish需要++。
💕 erase
iterator erase(iterator pos)
{assert(pos >= _start && pos < _finish);iterator end = pos + 1;while (end < _finish){*(end - 1) = *end;end++;}_finish--;return pos;
}
這里我們首先需要注意的是,pos位置不能等于finish,因?yàn)閒inish是最后一個(gè)有效元素的后一個(gè)位置,重前往后挪動(dòng)數(shù)據(jù)。最后記得finish–。
5. 迭代器失效問題
💕 野指針問題
這里我們可以看到,當(dāng)我們插入一個(gè)元素后,再次打印的時(shí)候就會(huì)出現(xiàn)問題,其實(shí)本質(zhì)上還是我們的insert函數(shù)寫的有問題。
這里我們修改一下insert函數(shù),當(dāng)需要擴(kuò)容的時(shí)候先使用一個(gè)變量記錄一下pos位置相對(duì)于第一個(gè)元素的位置,再擴(kuò)容之后更新一下pos指針的位置。這樣第一種迭代器失效的問題就得到解決了。
iterator insert(iterator pos, const T& val)
{assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){int sz = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + sz;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;
}
💕 擴(kuò)容之后pos位置的迭代器失效
這里我們可以看到在我們將某個(gè)位置插入一個(gè)數(shù)字后,迭代器可能會(huì)失效,因?yàn)槭莻髦祩鬟f所以insert之后pos的地址可能已經(jīng)發(fā)生改變了,所以insert之后,默認(rèn)pos迭代器失效了的,因?yàn)椴恢滥囊淮螘?huì)進(jìn)行擴(kuò)容操作。所以insert之后的我們需要用pos接受一下就可以解決這種問題。
vector<int> v2;
v2.push_back(1);
v2.push_back(2);
v2.push_back(3);
v2.push_back(4);func(v2);
auto pos = find(v2.begin(), v2.end(), 3);
if (pos != v2.end())
{pos = v2.insert(pos, 100);
}
(*pos)++;
func(v2);
💕 erase之后默認(rèn)迭代器失效
其實(shí)不僅僅是insert,erase之后迭代器也會(huì)失效,下面我們來看一下erase之后迭代器失效的問題,這里我們先來舉三個(gè)例子——刪除一個(gè)序列中所有的偶數(shù)。
為什么同樣的代碼當(dāng)數(shù)據(jù)不同時(shí)會(huì)出現(xiàn)截然不同的結(jié)果呢?
- 第一份代碼能夠運(yùn)行出正確的結(jié)果完全是一個(gè)偶然??梢钥吹?#xff0c;第二份代碼由于刪除元素后 pos 不再指向原位置,而是指向下一個(gè)位置,所以 erase 之后會(huì)導(dǎo)致一個(gè)元素被跳過,導(dǎo)致部分偶數(shù)沒有被刪除,但好在末尾是奇數(shù),所以程序能夠正常運(yùn)行。
- 但是最后一份代碼就沒那么好運(yùn)了,由于最后一個(gè)元素是偶數(shù),所以 erase 之后 pos 直接指向了 _finish 的下一個(gè)位置,循環(huán)終止條件失效,發(fā)生越界。
所以,我們統(tǒng)一認(rèn)為 insert 和 erase 之后迭代器失效,必須更新后才能再次使用。
那么正確的做法就是當(dāng)每次插入或者刪除數(shù)據(jù)后都是用pos來接受一下。更新一下pos位置的數(shù)據(jù),如果沒有插入或者刪除數(shù)據(jù),則直接pos++即可。
auto it2 = v3.begin();while (it2 != v3.end()){if (*it2 % 2 == 0){it2 = v3.erase(it2);}else{it2++;}}for (auto e : v3){cout << e << " ";}cout << endl;
5. 淺拷貝問題
💕 拷貝構(gòu)造問題
//拷貝構(gòu)造
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];memcpy(_start, v._start, v.size() * sizeof(T));//——會(huì)導(dǎo)致淺拷貝問題_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}
這份代碼在我們看來并沒有什么問題,但其實(shí)它存在一個(gè)隱藏的問題,當(dāng)我們實(shí)例化的對(duì)象是內(nèi)置類型時(shí),并不會(huì)發(fā)生淺拷貝,但是如果我們實(shí)例化的對(duì)象是自定義類型時(shí),特別是自定義類型的對(duì)象中有資源分配的時(shí)候,這份代碼就會(huì)導(dǎo)致嚴(yán)重的問題。
當(dāng)我們的vector中的元素是string類型時(shí),直接這樣寫就會(huì)導(dǎo)致淺拷貝問題,這里我們來看一下原因。
在這里我們確實(shí)是開辟了一塊新的空間,同時(shí)也將原來對(duì)象中的數(shù)據(jù)拷貝到了新的空間中,但是由于這個(gè)對(duì)象是一個(gè)string字符串類型,直接使用memcpy進(jìn)行拷貝是按照字節(jié)進(jìn)行了拷貝,也就是說兩個(gè)對(duì)象中的vector中的string中的_str同時(shí)指向了一塊空間,所以最后調(diào)用自定義類型的析構(gòu)函數(shù)時(shí),同一塊空間會(huì)被析構(gòu)兩次。最后程序奔潰。
正確的寫法:
vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _end_of_storage(nullptr)
{_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();
}
💕 reserve問題
//reserve擴(kuò)容
void reserve(size_t n)
{if (n > capacity()){int sz = size();T* tmp = new T[n];if (_start){memcpy(tmp, _start, size() * sizeof(T));delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}
這份代碼和上面的代碼的原因大同小異,也是因?yàn)閙emcpy會(huì)帶來淺拷貝問題,下面我們來看一個(gè)例子:當(dāng)我們大量插入元素的時(shí)候,會(huì)導(dǎo)致擴(kuò)容的出現(xiàn),那么擴(kuò)容又會(huì)帶來什么樣的問題呢?
當(dāng)在push_back內(nèi)部調(diào)用 reserve 函數(shù)進(jìn)行擴(kuò)容時(shí),擴(kuò)容時(shí)我們雖然進(jìn)行了深拷貝,但是空間里面的內(nèi)容我們是使用 memcpy 按字節(jié)拷貝過來的,這就導(dǎo)致原來的 v 里面的 string 元素和臨時(shí)空間里面的string元素指向的是同一塊空間。所以當(dāng)拷貝完數(shù)據(jù)就會(huì)delete掉原來的空間,由于二者指向的是同一塊空間,所以現(xiàn)在v中的string元素指向的是一塊已經(jīng)被釋放掉的空間,當(dāng)最后出了作用域調(diào)用析構(gòu)的時(shí)候就會(huì)出現(xiàn)問題。
正確的寫法:
void reserve(size_t n)
{if (n > capacity()){int sz = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}
}
💕 賦值運(yùn)算符重載的問題
如果我們不重載=
賦值運(yùn)算符,使用vector中的元素是vector類型時(shí),這里還是會(huì)出現(xiàn)淺拷貝問題,因?yàn)閹熘械膕tring類重載了=
,所以直接賦值進(jìn)行的是深拷貝,這里我們需要重載一下=
,這樣無論我們的vector中存儲(chǔ)的是哪一種自定義類型都可以進(jìn)行深拷貝了。
vector<T>& operator=(const vector<T>& v)
{vector<T> tmp(v);swap(tmp);return *this;
}
三、vector模擬實(shí)現(xiàn)整體源碼
namespace cjl
{template <class T>class vector {public:typedef T* iterator;typedef const T* const_iterator;//迭代器的實(shí)現(xiàn)iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}無參構(gòu)造//vector()// :_start(nullptr)// ,_finish(nullptr)// ,_end_of_storage(nullptr)//{}構(gòu)造函數(shù)//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);// }//}//構(gòu)造函數(shù)的——現(xiàn)代寫法(在成員變量聲明的時(shí)候給缺省值)//無參構(gòu)造vector(){}//構(gòu)造函數(shù)vector(size_t n, const T& val = T()){reserve(n);for (int 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);}}//拷貝構(gòu)造vector(const vector<T>& v){_start = new T[v.capacity()];for (size_t i = 0; i < v.size(); i++){_start[i] = v._start[i];}_finish = _start + v.size();_end_of_storage = _start + v.capacity();}//迭代器區(qū)間構(gòu)造template <class InputIterator> vector(InputIterator first, InputIterator end){while (first != end){push_back(*first);first++;}}//resize的實(shí)現(xiàn)void resize(size_t n,T val = T()){if (n < size()){//刪除數(shù)據(jù)_finish = _start + n;}else{if (n > capacity()){reserve(n);}while (_finish != _start + n){*_finish = val;_finish++;}}}//reserve的實(shí)現(xiàn)void reserve(size_t n){if (n > capacity()){int sz = size();T* tmp = new T[n];if (_start){for (size_t i = 0; i < sz; i++){tmp[i] = _start[i];}delete[] _start;}_start = tmp;_finish = _start + sz;_end_of_storage = _start + n;}}//push_back的實(shí)現(xiàn)void push_back(const T& x){if (_finish == _end_of_storage){reserve(capacity() == 0 ? 4 : capacity() * 2);}*_finish = x;_finish++;}//pop_back的實(shí)現(xiàn)void pop_back(){assert(!empty());_finish--;}//insert的實(shí)現(xiàn)iterator insert(iterator pos, const T& val){assert(pos >= _start && pos <= _finish);if (_finish == _end_of_storage){int sz = pos - _start;reserve(capacity() == 0 ? 4 : capacity() * 2);pos = _start + sz;}iterator end = _finish - 1;while (end >= pos){*(end + 1) = *end;end--;}*pos = val;_finish++;return pos;}//erase的實(shí)現(xiàn)iterator erase(iterator pos){assert(pos >= _start && pos < _finish);iterator end = pos + 1;while (end < _finish){*(end - 1) = *end;end++;}_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];}//重載=運(yùn)算符vector<T>& operator=(const vector<T>& v){vector<T> tmp(v);swap(tmp);return *this;}//swap函數(shù)的實(shí)現(xiàn)void swap(vector<T>& v){std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_end_of_storage, v._end_of_storage);}size_t size() const{return _finish - _start;}size_t capacity() const{return _end_of_storage - _start;}size_t empty() const{return _start == _finish;}void clear(){_finish = _start;}//析構(gòu)函數(shù)~vector(){delete[] _start;_start = _finish = _end_of_storage = nullptr;}private:iterator _start = nullptr;iterator _finish = nullptr;iterator _end_of_storage = nullptr;};
}