溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章主要介紹C++中STL vector的模擬實現示例，文中介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們一定要看完！
vector是表示可變大小數組的序列容器。
就像數組一樣，vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問，和數組一樣高效。但是又不像數組，它的大小是可以動態改變的，而且它的大小會被容器自動處理。
本質講，vector使用動態分配數組來存儲它的元素。當新元素插入時候，這個數組需要被重新分配大小為了增加存儲空間。其做法是，分配一個新的數組，然后將全部元素移到這個數組。就時間而言，這是一個相對代價高的任務，因為每當一個新的元素加入到容器的時候，vector并不會每次都重新分配大小。
vector分配空間策略：vector會分配一些額外的空間以適應可能的增長，因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何，重新分配都應該是對數增長的間隔大小，以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
因此，vector占用了更多的存儲空間，為了獲得管理存儲空間的能力，并且以一種有效的方式動態增長。
與其它動態序列容器相比（deques, lists and forward_lists）， vector在訪問元素的時候更加高效，在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作，效率更低。比起lists和forward_lists統一的迭代器和引用更好。
更為詳細的可以查看vector文檔介紹。
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;
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--;
}
}iterator insert(iterator pos,const _Ty& value)
{
//1.當size()==capacity()時，表明vector已滿，再進行插入前需要進行擴容
if(size()== capacity())
{
size_type oldpos = pos - begin();
//這里需要防止一種情況：若vector為空的時候，他的capacity為0，這個時候給他直接擴容2倍是行不通的，
//因為2*0 = 0，因此就需要進行判斷
size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
reserve(newcapacity);
//這里空間發生了變化，pos迭代器會失效，因此需要重新對pos進行設置
//reserve不會使vector的成員變量失效
pos = begin() + oldpos;
}
//2.當size() < capacity()時，表明vector未滿，插入直接在pos的位置進行插入
//需要注意的是插入是在pos指向的位置進行插入，并且插入需要挪動數據，
//將pos位置之后的數據全部向后挪動一個,為防止元素被改寫，則需要從后向前進行挪動
iterator tail = _last;
while(tail > pos)
{
*tail = *(tail-1);
--tail;
}
//這里要注意的是挪動數據時，因為沒有對pos位置進行操作，所以pos位置的迭代器并沒有失效，
//但是pos位置之后的迭代器全部失效了，但在這里并沒有關系，我們并不會用到那些迭代器
*pos = value;
//插入完之后，一定要對_last指針+1，因為全部向后挪動了一個元素
++_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()]這個區間向前挪動一個即可
iterator it = pos + 1;
while(it != _last)
{
*(it-1) = *(it);
++it;
}
--_last;
return pos;
}void reserve(size_type n)
{
//若 n 的值大于vector的容量，則開辟空間
//若 n 的值小于等于，則不進行任何操作
if(n > capacity())
{
//1.新開辟一個空間
size_type oldSize = size();
_Ty* newVector = new _Ty[n];
//2.將原空間的數值賦值到新空間
if(_start)
{
//注意：這里不能使用memcpy,因為memcpy是一個淺拷貝。
//memcpy(newVector,_start,sizeof(_Ty)*size());
for(size_type i = 0; i < oldSize; ++i)
{
newVector[i] = _start[i];
}
}
//3.改變三個指針的指向
//這里直接重新給三個成員進行賦值，所以調用reserve()函數不用擔心迭代器失效的問題
_start = newVector;
_last = _start + oldSize;
_end = _start + n;
}
}
void resize(size_type n,const _Ty& value = _Ty())
{
//1.如果n的值小于等于size()的時候，則只需要將_last的指針往前移動即可
if(n <= size())
{
_last = _start + n;
return;
}
//2.如果n的值大于capacity()的時候，則需調用reserve()函數，重新設置容量大小
if(n > capacity())
{
reserve(n);
}
//若當n的值大于size()而小于capacity()的時候，只需將_last的指針往后移即可
iterator it = _last;
_last = _start + n;
while(it != _last)
{
*it = value;
++it;
}
//resize()函數也不需要擔心迭代器失效的問題
}void push_back(const _Ty& value)
{
insert(end(),value);
}
void pop_back()
{
erase(end()-1);
}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);
}#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的容量，則開辟空間
//若 n 的值小于等于，則不進行任何操作
if(n > capacity())
{
//1.新開辟一個空間
size_type oldSize = size();
_Ty* newVector = new _Ty[n];
//2.將原空間的數值賦值到新空間
if(_start)
{
//注意：這里不能使用memcpy,因為memcpy是一個淺拷貝。
//memcpy(newVector,_start,sizeof(_Ty)*size());
for(size_type i = 0; i < oldSize; ++i)
{
newVector[i] = _start[i];
}
}
//3.改變三個指針的指向
//這里直接重新給三個成員進行賦值，所以調用reserve()函數不用擔心迭代器失效的問題
_start = newVector;
_last = _start + oldSize;
_end = _start + n;
}
}
void resize(size_type n,const _Ty& value = _Ty())
{
//1.如果n的值小于等于size()的時候，則只需要將_last的指針往前移動即可
if(n <= size())
{
_last = _start + n;
return;
}
//2.如果n的值大于capacity()的時候，則需調用reserve()函數，重新設置容量大小
if(n > capacity())
{
reserve(n);
}
//若當n的值大于size()而小于capacity()的時候，只需將_last的指針往后移即可
iterator it = _last;
_last = _start + n;
while(it != _last)
{
*it = value;
++it;
}
//resize()函數也不需要擔心迭代器失效的問題
}
void push_back(const _Ty& value)
{
insert(end(),value);
}
void pop_back()
{
erase(end()-1);
}
iterator insert(iterator pos,const _Ty& value)
{
//1.當size()==capacity()時，表明vector已滿，再進行插入前需要進行擴容
if(size()== capacity())
{
size_type oldpos = pos - begin();
//這里需要防止一種情況：若vector為空的時候，他的capacity為0，
//這個時候給他直接擴容2倍是行不通的，因為2*0 = 0，因此就需要進行判斷
size_type newcapacity = (capacity() == 0)? 1 : 2*capacity();
reserve(newcapacity);
//這里空間發生了變化，pos迭代器會失效，因此需要重新對pos進行設置
//reserve不會使vector的成員變量失效
pos = begin() + oldpos;
}
//2.當size() < capacity()時，表明vector未滿，插入直接在pos的位置進行插入
//需要注意的是插入是在pos指向的位置進行插入，并且插入需要挪動數據，
//將pos位置之后的數據全部向后挪動一個,為防止元素被改寫，則需要從后向前進行挪動
iterator tail = _last;
while(tail > pos)
{
*tail = *(tail-1);
--tail;
}
//這里要注意的是挪動數據時，因為沒有對pos位置進行操作，所以pos位置的迭代器并沒有失效，
//但是pos位置之后的迭代器全部失效了，但在這里并沒有關系，我們并不會用到那些迭代器
*pos = value;
//插入完之后，一定要對_last指針+1，因為全部向后挪動了一個元素
++_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()]這個區間向前挪動一個即可
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;
}以上是“C++中STL vector的模擬實現示例”這篇文章的所有內容，感謝各位的閱讀！希望分享的內容對大家有幫助，更多相關知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
