C++中vector的實現(xiàn)方法示例詳解
1. vector介紹
vector本質(zhì)其實就是和我們數(shù)據(jù)結(jié)構(gòu)中的順序表類似，都是對一個數(shù)組進(jìn)行增刪查改等操作，但是這里vector的實現(xiàn)和順序表的實現(xiàn)有所不同，vector的底層源碼的實現(xiàn)是通過三個迭代器實現(xiàn)的，一個是指向開始的位置_start，一個是指向有效數(shù)據(jù)末尾的迭代器_finish還有一個是指向有效空間的迭代器_end_of_storage；而順序表則是一個指針指向一塊空間，和兩個計數(shù)器int size計算有效空間內(nèi)有效的元素個數(shù)和int capacity 記錄有效空間大小的整形變量；
2. vector的實現(xiàn)
2.1 vector的類的基本結(jié)構(gòu)
如上所述，vector的實現(xiàn)是通過三個成員即三個迭代器實現(xiàn)的；但庫內(nèi)的vector的使用通常有可以使用不同的類型例如vector<int>， vector<char>，vector<double>等等，所以我們就需要實現(xiàn)一個vector的模板，然后還要實現(xiàn)他們的迭代器，我們同源碼的迭代器實現(xiàn)不同，但迭代器其實就跟指針的用法幾乎一樣，所以我們這里通過指針來實現(xiàn)迭代器；如下代碼所示：
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; //指向有效空間末尾
};2.2 vector構(gòu)造和析構(gòu)函數(shù)的實現(xiàn)
如上三個迭代器成員可見，我們已經(jīng)給了缺省參數(shù)nullptr，那么在實例化的過程中我們只需要有一個構(gòu)造函數(shù)，他們就會自動走初始化列表使用缺省參數(shù)進(jìn)行初始化；而這里我們有了個創(chuàng)建一個構(gòu)造函數(shù)的新的用法，這是在C++11才加進(jìn)的；如下代碼所示：
vector() = default;
然后是拷貝構(gòu)造，拷貝構(gòu)造其實就是實例化出一個新的對象，而新的對象的值和傳入拷貝的對象的值相同，那我們就可以直接通過一個范圍for讓把被拷貝的對象的值依次插入實例化出的新的對象里面即可，這里先提前使用下面會講到的內(nèi)容，我們只需要知道push_back就是往里插入數(shù)據(jù)；
vector(const vector<T>& v)
{
for (auto e : v)
{
push_back(e);
}
}再者就是傳入一段迭代器進(jìn)行構(gòu)造實例化出新的對象；但我們這里要重新寫一個模板，這樣我們就可以把一些不同類型的不同結(jié)構(gòu)的對象存到vector里面來；
template<class InterIterator>
vector(InterIterator first, InterIterator last)
{
while (first != last)
{
push_back(*(first));
++first;
}
}最后是析構(gòu)函數(shù)就不過多介紹；
~vector()
{
if (_start)
delete[]_start;
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}2.3 賦值運(yùn)算符重載、swap、begin()、end()、capacity()、size()
swap的實現(xiàn)：由于和string類的實現(xiàn)一樣，如果說我們調(diào)用庫的swap并且是大量的數(shù)據(jù)進(jìn)行交換的話效率會降低效率；如下圖：
至于為什么會降低效率是因為紅色方框那里會調(diào)用一次拷貝構(gòu)造；然后綠色方框那也說了會降低效率，所以我們自主實現(xiàn)一個在類內(nèi)且不會調(diào)用拷貝構(gòu)造的swap；如下代碼所示：
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}賦值運(yùn)算符重載的實現(xiàn)：如下圖
賦值運(yùn)算符重載其實只需要調(diào)用swap就可以，而且我們的參數(shù)是傳值 不是傳引用，所以不會對v的原數(shù)據(jù)造成影響，最后再返回*this即可；如下代碼所示：
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector& operator=(vector<T> v)
{
swap(v);
return *this;
}然后是begin()傳回首元素的迭代器、end()傳回尾部元素的迭代器、capacity()傳回有效空間大小、size()傳回有效元素個數(shù)以及empty()判斷vector容器是否為空的實現(xiàn)如下；
begin()和end()其實就是直接返回_start和_finish即可，但是他們還有一個const_iterator就是指向不可被修改的所以實現(xiàn)了兩種；如下代碼所示：
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}capacity()和size()這里返回他們的大小，應(yīng)該是整型才對，但是我們的底層是迭代器，那該怎么辦呢？ 其實這里涉及到我們指針的一個知識點，那就是指針減指針返回的是兩個指針之間的元素個數(shù)，那我們就用用到這里來；如下代碼所示：
size_t capacity()const
{
return _end_of_storage - _start;
}
size_t size()const
{
return _finish - _start;
}最后一個是判空empt()，這個其實只需要看他的_start指向的空間和_finish指向的空間是否是同一塊空間即可如下代碼所示：
bool empty()
{
return _start == _finish;
}
2.4 reserve的實現(xiàn)（重點）
reserve就是預(yù)先開空間，如果說開的空間比原有的空間小的話capacity 和size不會變化，但是比原有的空間大的話就會給他們開足n個空間；如下測試可知：
#include<vector>
#include<iostream>
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.push_back(6);
v.push_back(7);
cout << "capcaity is:> " << v.capacity() << endl;
cout << "size is:> " << v.size() << endl;
v.reserve(3);
cout << "After reserve(3) capcaity is:> " << v.capacity() << endl;
cout << "After reserve(3) size is:> " << v.size() << endl;
v.reserve(20);
cout << "After reserve(20) capcaity is:> " << v.capacity() << endl;
cout << "After reserve(20) size is:> " << v.size() << endl;
return 0;
}?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
運(yùn)行結(jié)果為：
那我們的實現(xiàn)也要和源碼的功能一樣，如果n比capacity小則不出現(xiàn)變化，如果比capacity大的話就需要進(jìn)行擴(kuò)容，而這里也涉及了深淺拷貝問題，我們需要自己new一段n一樣大的空間然后把數(shù)據(jù)往里放，我先直接上代碼，里面有些需要注意的地方在下面進(jìn)行講解：
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* temp = new T[n];
//memcpy(temp, _start, size() * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
temp[i] = _start[i];
}
delete[]_start;
_start = temp;
//_finish = temp + size();//這個是錯誤的示范，因為delete掉_start了，
//那temp = _strt +size()（_finish-_start) 就為_finish，但是finish為NULL
//因為已經(jīng)被釋放了
_finish = temp + old_size;
_end_of_storage = temp + n;
}
}重點！重點！重點！重點！重點！重點！重點！重點！重點！重點！重點！重點！重點！
（內(nèi)心所言：換個顏色的字體會不會讓眼睛看的舒服點哈哈哈哈）
首先需要注意的第一點是：上面代碼加了一個old_size進(jìn)行記錄size()并不是多余，如果說上面不加的話會出現(xiàn)錯誤，因為前面已經(jīng)釋放了_start，而size() = _finish - _start， 而_finish還指向原來已經(jīng)被釋放的空間，_finish = temp + _finish - _start；而_start = temp，_finish被釋放了為NULL， 所以最后的結(jié)果會為NULL，所以我們需要預(yù)先把size()保存下來；
然后先說一下賦值運(yùn)算符重載vv = v的實現(xiàn)實質(zhì)上是把vv原有的空間釋放掉，然后開一片和v一樣大的空間，上面做到了開一樣的空間，而只需要把v的值復(fù)制到vv就可以，但為什么我把memcpy注釋掉了呢？ 因為memcpy只是進(jìn)行單純的值和值賦值操作，如果說我用一個vector容器儲存string類呢？ 只進(jìn)行值的拷貝就會導(dǎo)致淺拷貝而出現(xiàn)錯誤；下面舉出了例子：
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* temp = new T[n];
memcpy(temp, _start, size() * sizeof(T));
delete[]_start;
_start = temp;
_finish = temp + old_size;
_end_of_storage = temp + n;
}
}
private:
//有三個迭代器
iterator _start = nullptr; //指向開頭
iterator _finish = nullptr; //指向有效元素末尾后一個位置
iterator _end_of_storage = nullptr; //指向有效空間末尾
};
void test2()
{
vector<string> v;
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
v.push_back("11111111111111111111");
Print_Container(v);
v.push_back("11111111111111111111");
Print_Container(v);
}
int main()
{
test2();
return 0;
}
這里就是把memcpy解開了，那讓我們來看看結(jié)果如何
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
運(yùn)行結(jié)果為：
出現(xiàn)很多隨機(jī)值，正如我們所說，單純的memcpy只會把值進(jìn)行淺拷貝如下圖所示：
但為什么我們只進(jìn)行單純的賦值操作就可以實現(xiàn)深拷貝了呢？那是因為我們傳了string類型即vector<string>，而
改段賦值其實就是調(diào)用了string里的賦值運(yùn)算符，庫內(nèi)的已經(jīng)重載過了，所以會進(jìn)行深拷貝操作；
2.5 push_back和pop_back()操作實現(xiàn)
其實也沒有什么可講的，因為和string類實現(xiàn)的非常相似，我們只需要注意當(dāng)容器滿的時候就需要進(jìn)行擴(kuò)容，然后把值放到*_finish里，然后finish還要往后走；而尾刪pop_back更簡單，因為她不需要考慮空間是否充足，只需要看空間是否為空即可；如下代碼所示：
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
(*_finish) = x;
_finish++;
}
void pop_back()
{
assert(!empty());
--_finish;
}2.6 resize的實現(xiàn)
resize顧名思義就是改變size的，實現(xiàn)他的話有兩種需要注意的情況，第一種如果說改變的大小n如果size < n < capacity的話則需要改變_finish的位置，但是capacity不會變；第二種如果說n>capacity的話則需要擴(kuò)容，如果有給值則初始化新開的空間的值，如果沒有則給匿名對象實例化出的值進(jìn)行初始化如下代碼所示：
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
//這里包括兩種情況，一種是 size < n < capacity;
//還有一種是capacity < n 那就需要拿n來進(jìn)行擴(kuò)容操作，而這步操作在reserve(n)
//會實現(xiàn)
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
}這里第二個參數(shù)是T val = T()，T()其實就是匿名對象（這也看出匿名對象的作用，就是給不知道給什么類型缺省值的參數(shù)用的）；
2.7 insert和erase的實現(xiàn)
insert不單純只是說插入數(shù)據(jù)，這里面還涉及到一個迭代器失效的知識點，就是當(dāng)如果調(diào)用v.insert(p,10) 想在p的位置插入10的，但出現(xiàn)了空間不足需要擴(kuò)容的情況后，p迭代器需要被更新，因為擴(kuò)容后是新開的一塊空間，但p還指向原來的空間，所以會出現(xiàn)野迭代器的情況；而解決方案是，我們先記錄相對位置，即len = _start到pos位置的距離，最后再讓pos走到相對位置處即pos = _start +len最后再返回pos即可；
上面標(biāo)色的是特殊的迭代器失效的情況；下面是實現(xiàn)insert的思路：
1. 首先判斷空間是否充足，因為你要插入數(shù)據(jù)；
2. 插入數(shù)據(jù)前需要把數(shù)據(jù)往后挪，然后再在pos位置插入數(shù)據(jù)；
3. 最后記得讓_finish++, 因為插入數(shù)據(jù)后容量發(fā)生變化；如下代碼所示：
iterator insert(iterator pos, const T& v)
{
if (_finish == _end_of_storage)
{
//記下相對位置,因為擴(kuò)容會讓迭代器失效，成為野迭代器
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 = v;
++_finish;
return pos;
}erase的實現(xiàn)：
erase也會出現(xiàn)迭代器失效的問題，如果說編譯器出現(xiàn)縮容的情況下也會出現(xiàn)和上面insert的一樣，而且還有一種情況就是如果說erase了某個迭代器，那么我們就不能對這個迭代器進(jìn)行訪問，因為編譯器會強(qiáng)行檢察報錯，他們不允許再使用一個調(diào)用了erase且未更新的迭代器；如下代碼所示：
void testErase()
{
std:: vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
v.erase(it);
}
else
{
++it;
}
}
}?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
調(diào)試結(jié)果為：
直接崩掉了，但我們加上it = v.erase更新他的話就可以過；如下代碼所示：
void testErase()
{
std:: vector<int>v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
v.push_back(5);
auto it = v.begin();
while (it != v.end())
{
if (*it % 2 == 0)
{
it = v.erase(it);
}
else
{
++it;
}
}
}?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??
運(yùn)行結(jié)果為：
所以由此可見erase的返回值應(yīng)該是個迭代器，那么我們就可以來實現(xiàn)自己的erase；
實現(xiàn)思路：
1、首先要判斷pos的位置不能不在有效數(shù)據(jù)內(nèi)
2、刪除操作和順序表一樣，直接讓后面的數(shù)覆蓋需要刪除的數(shù)即可；
3、最后需要--finish 因為刪掉了數(shù)據(jù)，然后還要返回pos；如下代碼所示：
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
auto it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}2.8 方括號重載即下標(biāo)訪問
直接返回對應(yīng)下標(biāo)的值即可直接上代碼：
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i)const
{
assert(i < size());
return _start[i];
}2.9 實現(xiàn)Print_vector操作
打印值其實很簡單，但是里面有一點需要注意的是：在沒有實例化的類模板里，編譯器不能區(qū)分const_iterator是類型還是靜態(tài)成員變量所以需要在前面加個typename，還有另外的解決方案如下代碼所示：
template<class T>
void Print_vector(const vector<T>& v)
{
// 規(guī)定，沒有實例化的類模板里面取東西，編譯器不能區(qū)分這里const_iterator
// 是類型還是靜態(tài)成員變量，需要在前面加個typename
vector<T>::const_iterator it = v.begin();
//或者換一種
//auto it = v.begin();
//第一種遍歷vector容器
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//第二種遍歷vector容器
//for (auto e : v)
//{
// cout << e << " ";
//}
//cout << endl;
}
2.10 實現(xiàn)打印所有容器（加餐）
template <class Container>
void Print_Container(const Container& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}3. 完整的vector實現(xiàn)代碼如下
vector.h
#pragma once
#include<iostream>
#include<assert.h>
#include <vector>
namespace Tao
{
using namespace std;
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
//構(gòu)造函數(shù)
//這個是前置構(gòu)造函數(shù)
vector() = default;
vector(const vector<T>& v)
{
for (auto e : v)
{
push_back(e);
}
}
template<class InterIterator>
vector(InterIterator first, InterIterator last)
{
while (first != last)
{
push_back(*(first));
++first;
}
}
~vector()
{
if (_start)
delete[]_start;
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
void swap(vector<T>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
vector& operator=(vector<T> v)
{
swap(v);
return *this;
}
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
size_t capacity()const
{
return _end_of_storage - _start;
}
size_t size()const
{
return _finish - _start;
}
bool empty()
{
return _start == _finish;
}
//reserve開空間
void reserve(size_t n)
{
if (n > capacity())
{
size_t old_size = size();
T* temp = new T[n];
//memcpy(temp, _start, size() * sizeof(T));
for (size_t i = 0; i < old_size; i++)
{
temp[i] = _start[i];
}
delete[]_start;
_start = temp;
//_finish = temp + size();//這個是錯誤的示范，因為delete掉_start了，
//那temp = _strt +size()（_finish-_start) 就為_finish，但是finish為NULL
//因為已經(jīng)被釋放了
_finish = temp + old_size;
_end_of_storage = temp + n;
}
}
void push_back(const T& x)
{
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : capacity() * 2);
}
(*_finish) = x;
_finish++;
}
void pop_back()
{
assert(!empty());
--_finish;
}
void resize(size_t n, T val = T())
{
if (n < size())
{
_finish = _start + n;
}
//這里包括兩種情況，一種是 size < n < capacity;
//還有一種是capacity < n 那就需要拿n來進(jìn)行擴(kuò)容操作，而這步操作在reserve(n)
//會實現(xiàn)
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
_finish++;
}
}
}
iterator insert(iterator pos, const T& v)
{
if (_finish == _end_of_storage)
{
//記下相對位置,因為擴(kuò)容會讓迭代器失效，成為野迭代器
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 = v;
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start);
assert(pos < _finish);
auto it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
T& operator[](size_t i)
{
assert(i < size());
return _start[i];
}
const T& operator[](size_t i)const
{
assert(i < size());
return _start[i];
}
private:
//有三個迭代器
iterator _start = nullptr; //指向開頭
iterator _finish = nullptr; //指向有效元素末尾后一個位置
iterator _end_of_storage = nullptr; //指向有效空間末尾
};
template<class T>
void Print_vector(const vector<T>& v)
{
// 規(guī)定，沒有實例化的類模板里面取東西，編譯器不能區(qū)分這里const_iterator
// 是類型還是靜態(tài)成員變量，需要在前面加個typename
vector<T>::const_iterator it = v.begin();
//或者換一種
//auto it = v.begin();
//第一種遍歷vector容器
while (it != v.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//第二種遍歷vector容器
//for (auto e : v)
//{
// cout << e << " ";
//}
//cout << endl;
}
template <class Container>
void Print_Container(const Container& v)
{
for (auto e : v)
{
cout << e << " ";
}
cout << endl;
}
總結(jié)
到此這篇關(guān)于C++中vector實現(xiàn)的文章就介紹到這了,更多相關(guān)C++ vector的實現(xiàn)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)五子棋游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
使用代碼怎么才能鎖定鼠標(biāo)？這個功能很簡單只要一個ClipCursor()就可以搞定,需要的朋友可以參考下2014-01-01
這篇文章主要介紹了c++仿函數(shù)和函數(shù)適配器的使用詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
這篇文章主要介紹了c++ vector 常用函數(shù)示例解析，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
這篇文章主要介紹了Python HTTP服務(wù)搭建顯示本地文件的相關(guān)資料,需要的朋友可以參考下2017-02-02
C++11新特性之隨機(jī)數(shù)庫(Random?Number?Library)詳解
相對于C++11之前的隨機(jī)數(shù)生成器來說,C++11的隨機(jī)數(shù)生成器是復(fù)雜了很多,下面這篇文章主要給大家介紹了關(guān)于C++11新特性之隨機(jī)數(shù)庫(Random?Number?Library)的相關(guān)資料,需要的朋友可以參考下2022-06-06
C/C++ Qt TreeWidget 嵌套節(jié)點操作使用
本文主要介紹了TreeWidget的如何使用，實現(xiàn)對樹形框多節(jié)點的各種操作，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
Trae+Qt+MSVC環(huán)境配置的實現(xiàn)示例
本文主要介紹了Trae+Qt+MSVC環(huán)境配置,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-03-03
C++實現(xiàn)十六進(jìn)制字符串轉(zhuǎn)換成int整形值的示例
今天小編就為大家分享一篇關(guān)于C++實現(xiàn)十六進(jìn)制字符串轉(zhuǎn)換成int整形值的示例，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2018-12-12
這篇文章主要介紹了C++ decltype 說明符，檢查實體的聲明類型，或表達(dá)式的類型和值類別。下面我們來看看文章中的具體內(nèi)容吧2021-12-12