C++ STL vector的模擬實(shí)現(xiàn)
更新時(shí)間：2021年05月07日 11:08:19 投稿：zx
這篇文章主要介紹了C++ STL vector的模擬實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
1. vector的介紹和使用
- vector是表示可變大小數(shù)組的序列容器。
- 就像數(shù)組一樣，vector也采用的連續(xù)存儲(chǔ)空間來(lái)存儲(chǔ)元素。也就是意味著可以采用下標(biāo)對(duì)vector的元素進(jìn)行訪問(wèn)，和數(shù)組一樣高效。但是又不像數(shù)組，它的大小是可以動(dòng)態(tài)改變的，而且它的大小會(huì)被容器自動(dòng)處理。
- 本質(zhì)講，vector使用動(dòng)態(tài)分配數(shù)組來(lái)存儲(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)可能的增長(zhǎng)，因?yàn)榇鎯?chǔ)空間比實(shí)際需要的存儲(chǔ)空間更大。不同的庫(kù)采用不同的策略權(quán)衡空間的使用和重新分配。但是無(wú)論如何，重新分配都應(yīng)該是對(duì)數(shù)增長(zhǎng)的間隔大小，以至于在末尾插入一個(gè)元素的時(shí)候是在常數(shù)時(shí)間的復(fù)雜度完成的。
- 因此，vector占用了更多的存儲(chǔ)空間，為了獲得管理存儲(chǔ)空間的能力，并且以一種有效的方式動(dòng)態(tài)增長(zhǎng)。
- 與其它動(dòng)態(tài)序列容器相比（deques, lists and forward_lists）， vector在訪問(wèn)元素的時(shí)候更加高效，在末尾添加和刪除元素相對(duì)高效。對(duì)于其它不在末尾的刪除和插入操作，效率更低。比起lists和forward_lists統(tǒng)一的迭代器和引用更好。
更為詳細(xì)的可以查看vector文檔介紹。
2. vector的模擬實(shí)現(xiàn)
vector的嵌套型別定義
typedef _Ty value_type; typedef value_type* iterator; typedef value_type& reference; typedef size_t size_type;
vector的成員變量
private:
iterator _start;
iterator _last;
iterator _end;
2.1 vector構(gòu)造函數(shù)和拷貝構(gòu)造函數(shù)
vector():_start(nullptr),_last(nullptr),_end(nullptr)
{}
vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
{
insert(n,value);
}
vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
{
insert(f,l);
}
vector(const vector<int>& iv)
{
reserve(iv.capacity());
iterator it = begin();
iterator vit = iv.end();
while (vit != iv.begin())
{
*it++ = *vit--;
}
}
2.2 insert函數(shù)和eraser函數(shù)
iterator insert(iterator pos,const _Ty& value)
{
//1.當(dāng)size()==capacity()時(shí)，表明vector已滿，再進(jìn)行插入前需要進(jìn)行擴(kuò)容
if(size()== capacity())
{
size_type oldpos = pos - begin();
//這里需要防止一種情況：若vector為空的時(shí)候，他的capacity為0，這個(gè)時(shí)候給他直接擴(kuò)容2倍是行不通的，
//因?yàn)?*0 = 0，因此就需要進(jìn)行判斷
size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
reserve(newcapacity);
//這里空間發(fā)生了變化，pos迭代器會(huì)失效，因此需要重新對(duì)pos進(jìn)行設(shè)置
//reserve不會(huì)使vector的成員變量失效
pos = begin() + oldpos;
}
//2.當(dāng)size() < capacity()時(shí)，表明vector未滿，插入直接在pos的位置進(jìn)行插入
//需要注意的是插入是在pos指向的位置進(jìn)行插入，并且插入需要挪動(dòng)數(shù)據(jù)，
//將pos位置之后的數(shù)據(jù)全部向后挪動(dòng)一個(gè),為防止元素被改寫(xiě)，則需要從后向前進(jìn)行挪動(dòng)
iterator tail = _last;
while(tail > pos)
{
*tail = *(tail-1);
--tail;
}
//這里要注意的是挪動(dòng)數(shù)據(jù)時(shí)，因?yàn)闆](méi)有對(duì)pos位置進(jìn)行操作，所以pos位置的迭代器并沒(méi)有失效，
//但是pos位置之后的迭代器全部失效了，但在這里并沒(méi)有關(guān)系，我們并不會(huì)用到那些迭代器
*pos = value;
//插入完之后，一定要對(duì)_last指針+1，因?yàn)槿肯蚝笈矂?dòng)了一個(gè)元素
++_last;
return pos;
}
void insert(size_type n,const _Ty& value)
{
for(int i = 0;i < n; ++i)
{
insert(end(),value);
}
}
void insert(iterator f,iterator l)
{
while(f!=l)
{
insert(end(),*f);
++f;
}
}
iterator erase(iterator pos)
{
assert(pos >= _start || pos < _last);
//1.刪除pos位置的元素，就是將[pos,end()]這個(gè)區(qū)間向前挪動(dòng)一個(gè)即可
iterator it = pos + 1;
while(it != _last)
{
*(it-1) = *(it);
++it;
}
--_last;
return pos;
}
2.3 reserve函數(shù)和resize函數(shù)
void reserve(size_type n)
{
//若 n 的值大于vector的容量，則開(kāi)辟空間
//若 n 的值小于等于，則不進(jìn)行任何操作
if(n > capacity())
{
//1.新開(kāi)辟一個(gè)空間
size_type oldSize = size();
_Ty* newVector = new _Ty[n];
//2.將原空間的數(shù)值賦值到新空間
if(_start)
{
//注意：這里不能使用memcpy,因?yàn)閙emcpy是一個(gè)淺拷貝。
//memcpy(newVector,_start,sizeof(_Ty)*size());
for(size_type i = 0; i < oldSize; ++i)
{
newVector[i] = _start[i];
}
}
//3.改變?nèi)齻€(gè)指針的指向
//這里直接重新給三個(gè)成員進(jìn)行賦值，所以調(diào)用reserve()函數(shù)不用擔(dān)心迭代器失效的問(wèn)題
_start = newVector;
_last = _start + oldSize;
_end = _start + n;
}
}
void resize(size_type n,const _Ty& value = _Ty())
{
//1.如果n的值小于等于size()的時(shí)候，則只需要將_last的指針往前移動(dòng)即可
if(n <= size())
{
_last = _start + n;
return;
}
//2.如果n的值大于capacity()的時(shí)候，則需調(diào)用reserve()函數(shù)，重新設(shè)置容量大小
if(n > capacity())
{
reserve(n);
}
//若當(dāng)n的值大于size()而小于capacity()的時(shí)候，只需將_last的指針往后移即可
iterator it = _last;
_last = _start + n;
while(it != _last)
{
*it = value;
++it;
}
//resize()函數(shù)也不需要擔(dān)心迭代器失效的問(wèn)題
}
2.4 push_back函數(shù)和pop_back函數(shù)
void push_back(const _Ty& value)
{
insert(end(),value);
}
void pop_back()
{
erase(end()-1);
}
2.5 begin函數(shù)和end函數(shù)
iterator begin()const
{
return _start;
}
iterator end() const
{
return _last;
}
2.6 size函數(shù)、capacity函數(shù)
size_type size()
{
return end()-begin();
}
size_type capacity()const
{
return _end-begin();
}
2.7 empty函數(shù)和operator[]重載
bool empty()const
{
return end() == begin();
}
reference operator[](size_type n)
{
return *(begin() + n);
}
2.8 完整代碼和相應(yīng)測(cè)試
#include <iostream>
#include <assert.h>
using namespace std;
namespace mytest{
template<class _Ty>
class vector
{
public:
typedef _Ty value_type;
typedef value_type* iterator;
typedef value_type& reference;
typedef size_t size_type;
public:
iterator begin()const
{
return _start;
}
iterator end() const
{
return _last;
}
size_type size()
{
return end()-begin();
}
size_type capacity()const
{
return _end-begin();
}
bool empty()const
{
return end() == begin();
}
reference operator[](size_type n)
{
return *(begin() + n);
}
public:
vector():_start(nullptr),_last(nullptr),_end(nullptr)
{}
vector(size_type n,const _Ty& value):_start(nullptr),_last(nullptr),_end(nullptr)
{
insert(n,value);
}
vector(iterator f,iterator l):_start(nullptr),_last(nullptr),_end(nullptr)
{
insert(f,l);
}
vector(const vector<int>& iv)
{
reserve(iv.capacity());
iterator it = begin();
iterator vit = iv.end();
while (vit != iv.begin())
{
*it++ = *vit--;
}
}
public:
void reserve(size_type n)
{
//若 n 的值大于vector的容量，則開(kāi)辟空間
//若 n 的值小于等于，則不進(jìn)行任何操作
if(n > capacity())
{
//1.新開(kāi)辟一個(gè)空間
size_type oldSize = size();
_Ty* newVector = new _Ty[n];
//2.將原空間的數(shù)值賦值到新空間
if(_start)
{
//注意：這里不能使用memcpy,因?yàn)閙emcpy是一個(gè)淺拷貝。
//memcpy(newVector,_start,sizeof(_Ty)*size());
for(size_type i = 0; i < oldSize; ++i)
{
newVector[i] = _start[i];
}
}
//3.改變?nèi)齻€(gè)指針的指向
//這里直接重新給三個(gè)成員進(jìn)行賦值，所以調(diào)用reserve()函數(shù)不用擔(dān)心迭代器失效的問(wèn)題
_start = newVector;
_last = _start + oldSize;
_end = _start + n;
}
}
void resize(size_type n,const _Ty& value = _Ty())
{
//1.如果n的值小于等于size()的時(shí)候，則只需要將_last的指針往前移動(dòng)即可
if(n <= size())
{
_last = _start + n;
return;
}
//2.如果n的值大于capacity()的時(shí)候，則需調(diào)用reserve()函數(shù)，重新設(shè)置容量大小
if(n > capacity())
{
reserve(n);
}
//若當(dāng)n的值大于size()而小于capacity()的時(shí)候，只需將_last的指針往后移即可
iterator it = _last;
_last = _start + n;
while(it != _last)
{
*it = value;
++it;
}
//resize()函數(shù)也不需要擔(dān)心迭代器失效的問(wèn)題
}
void push_back(const _Ty& value)
{
insert(end(),value);
}
void pop_back()
{
erase(end()-1);
}
iterator insert(iterator pos,const _Ty& value)
{
//1.當(dāng)size()==capacity()時(shí)，表明vector已滿，再進(jìn)行插入前需要進(jìn)行擴(kuò)容
if(size()== capacity())
{
size_type oldpos = pos - begin();
//這里需要防止一種情況：若vector為空的時(shí)候，他的capacity為0，
//這個(gè)時(shí)候給他直接擴(kuò)容2倍是行不通的，因?yàn)?*0 = 0，因此就需要進(jìn)行判斷
size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
reserve(newcapacity);
//這里空間發(fā)生了變化，pos迭代器會(huì)失效，因此需要重新對(duì)pos進(jìn)行設(shè)置
//reserve不會(huì)使vector的成員變量失效
pos = begin() + oldpos;
}
//2.當(dāng)size() < capacity()時(shí)，表明vector未滿，插入直接在pos的位置進(jìn)行插入
//需要注意的是插入是在pos指向的位置進(jìn)行插入，并且插入需要挪動(dòng)數(shù)據(jù)，
//將pos位置之后的數(shù)據(jù)全部向后挪動(dòng)一個(gè),為防止元素被改寫(xiě)，則需要從后向前進(jìn)行挪動(dòng)
iterator tail = _last;
while(tail > pos)
{
*tail = *(tail-1);
--tail;
}
//這里要注意的是挪動(dòng)數(shù)據(jù)時(shí)，因?yàn)闆](méi)有對(duì)pos位置進(jìn)行操作，所以pos位置的迭代器并沒(méi)有失效，
//但是pos位置之后的迭代器全部失效了，但在這里并沒(méi)有關(guān)系，我們并不會(huì)用到那些迭代器
*pos = value;
//插入完之后，一定要對(duì)_last指針+1，因?yàn)槿肯蚝笈矂?dòng)了一個(gè)元素
++_last;
return pos;
}
void insert(size_type n,const _Ty& value)
{
for(int i = 0;i < n; ++i)
{
insert(end(),value);
}
}
void insert(iterator f,iterator l)
{
while(f!=l)
{
insert(end(),*f);
++f;
}
}
iterator erase(iterator pos)
{
assert(pos >= _start || pos < _last);
//1.刪除pos位置的元素，就是將[pos,end()]這個(gè)區(qū)間向前挪動(dòng)一個(gè)即可
iterator it = pos + 1;
while(it != _last)
{
*(it-1) = *(it);
++it;
}
--_last;
return pos;
}
private:
iterator _start;
iterator _last;
iterator _end;
};
};
void Test1()
{
mytest::vector<int> iv;
cout << "iv.size() = " << iv.size() << endl;
cout << "iv.capacity() = " << iv.capacity() << endl;
iv.push_back(1);
iv.push_back(2);
iv.push_back(3);
iv.push_back(4);
cout << "iv.size() = " << iv.size() << endl;
cout << "iv.capacity() = " << iv.capacity() << endl;
mytest::vector<int>::iterator it = iv.begin();
while(it != iv.end())
{
cout << *it << " ";
++it;
}
cout << endl;
iv.pop_back();
iv.pop_back();
it = iv.begin();
while(it != iv.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void Test2()
{
mytest::vector<int> iv(10,2);
mytest::vector<int>::iterator it = iv.begin();
while(it != iv.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
void Test3()
{
int ar[] = {1,2,3,3,4,5};
mytest::vector<int> iv(ar,ar+6);
mytest::vector<int>::iterator it = iv.begin();
while(it != iv.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
int main()
{
// Test1();
// Test2();
Test3();
return 0;
}
到此這篇關(guān)于C++ STL vector的模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ STL vector內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++基于QWidget和QLabel實(shí)現(xiàn)圖片縮放,拉伸與拖拽
這篇文章主要為大家詳細(xì)介紹了C++如何基于QWidget和QLabel實(shí)現(xiàn)圖片縮放、拉伸與拖拽等功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2024-02-02
我們給大家?guī)?lái)了一篇關(guān)于C/C++項(xiàng)目編譯工具簡(jiǎn)單介紹的文章，大家在項(xiàng)目編譯前可以先閱讀下。2019-12-12
運(yùn)算符重載后不能改變運(yùn)算符的操作對(duì)象(操作數(shù))的個(gè)數(shù)；如："+"是實(shí)現(xiàn)兩個(gè)操作數(shù)的運(yùn)算符，重載后仍然為雙目運(yùn)算符2013-09-09
vscode實(shí)現(xiàn)本地代碼自動(dòng)同步到遠(yuǎn)程機(jī)器的步驟
這篇文章主要介紹了vscode實(shí)現(xiàn)本地代碼自動(dòng)同步到遠(yuǎn)程機(jī)器的步驟,本文分步驟給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2023-06-06
下面小編就為大家?guī)?lái)一篇淺談do {...} while (0) 在宏定義中的作用。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-12-12
今天小編就為大家分享一篇關(guān)于C++命名空間namespace的介紹與使用，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2021-09-09
C/C++通過(guò)SQLite SDK實(shí)現(xiàn)數(shù)據(jù)庫(kù)增刪改查操作
SQLite,作為一款嵌入式關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng),一直以其輕量級(jí)、零配置以及跨平臺(tái)等特性而備受青睞,本文主要介紹了C++如何通過(guò)SQLite SDK實(shí)現(xiàn)數(shù)據(jù)庫(kù)增刪改查操作,感興趣的可以了解下2023-11-11
快速掌握VC6.0中各種宏注釋?xiě)?yīng)用(附圖)
為了方便別人或自己閱讀自己的程序，注釋是堅(jiān)決不可少的,一個(gè)漂亮的程序，不是在于你應(yīng)用的技術(shù)多么高深，而是能夠把高深的技術(shù)描述的清楚易懂2013-01-01
C++ Boost Coroutine使用協(xié)程詳解
通過(guò)Boost.Coroutine，可以在C++中使用協(xié)程。協(xié)程是其他編程語(yǔ)言的一個(gè)特性，通常使用關(guān)鍵字yield來(lái)表示協(xié)程。在這些編程語(yǔ)言中，yield可以像return一樣使用2022-11-11
C++設(shè)計(jì)模式編程中的迭代器模式應(yīng)用解析
這篇文章主要介紹了C++設(shè)計(jì)模式編程中的迭代器模式應(yīng)用解析,迭代器模式注重對(duì)集合中元素的遍歷而不使其暴露,需要的朋友可以參考下2016-03-03