C++ vector及實現(xiàn)自定義vector以及allocator和iterator方式
簡介
作用：vector是一個能夠存放任意類型的 動態(tài)數(shù)組 ，能夠增加和壓縮數(shù)據(jù)。
vector是表示可以改變大小的數(shù)組的序列容器。
與數(shù)組一樣，vector對元素使用連續(xù)的存儲位置，這意味也可以使用指向其元素的常規(guī)指針上的偏移量來訪問它們的元素，并且與在數(shù)組中一樣高效。
但是與數(shù)組不同，它們的大小可以動態(tài)變化，容器會自動處理它們的存儲。
在內(nèi)部，vector 使用個動態(tài)分配的數(shù)組來存儲它們的元素。這個數(shù)組可能需要重新分配，以便在插入新元素時增大大小，這意味著分配一個新數(shù)組并將所有元素移動到其中。就處理時間而言，這是一項相對昂貴的任務(wù)，因此，向量不會在每次向容器添加元素時重新分配。
相反，vector 容器可以分配一些 額外的存儲空間以適應(yīng)可能的增長 ， 因此容器的實際容量可能大于嚴格需要的存儲容量(即容器的大小)。
對于不同的插入位置，可以在不同的時間間隔內(nèi)實現(xiàn)不同的插入策略，但只能在不同的位置上實現(xiàn)內(nèi)存大小的平衡。
因此，與array相比，向量消耗更多的內(nèi)存，以 換取管理存儲和以高效方式動態(tài)增長 的能力。與其他動態(tài)序列容器( deques 、 list 和 forward_list )相比，vectors 可以非常高效地訪問其元素(就像數(shù)組一樣)，并相對高效地從其末尾添加或刪除元素。
對于涉及在結(jié)尾以外的位置插入或刪除元素的操作，它們的性能比其他操作差，迭代器和引用的一致性也不如list 和forward_list。
注意 ：
使用時有以下的注意事項：
- 1.如果你要表示的向量長度較長（需要為向量內(nèi)部保存很多數(shù)），容易導(dǎo)致內(nèi)存泄漏，而且效率會很低；
- 2.Vector作為函數(shù)的參數(shù)或者返回值時，需要注意它的寫法：
double Distance(vector<int>&a, vector<int>&b)
其中的“ & ”絕對不能少?。?！
- 3.建立一個vector，int為數(shù)組元素的數(shù)據(jù)類型，test為動態(tài)數(shù)組名
簡單的使用方法如下：
vector<int>test;//建立一個vector test.push_back(1); test.push_back(2);//把1和2壓入vector，這樣test[0]就是1,test[1]就是2
基本操作
- 頭文件#include.
- 創(chuàng)建vector對象，
vector<int> vec; - 尾部插入數(shù)字：vec.
push_back(a); - 使用下標訪問元素，cout<<
vec[0]<<endl;記住下標是從0開始的。 - 使用迭代器訪問元素
vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++) cout<<*it<<endl;
- 插入元素： vec.insert(vec.begin()+i,a);在第i+1個元素前面插入a;
- 刪除元素： vec.erase(vec.begin()+2);刪除第3個元素
- vec.erase(vec.begin()+i,vec.end()+j);刪除區(qū)間[i,j-1];區(qū)間從0開始
- 向量大小:vec.size();
- 清空:vec.clear();
注意 ：
vector的元素不僅僅可以是int,double,string,還可以是結(jié)構(gòu)體，但是要注意：結(jié)構(gòu)體要定義為全局的，否則會出錯
算法
1.逆序排列： 使用 reverse 將元素翻轉(zhuǎn)：需要頭文件 #include<algorithm> 、 reverse(vec.begin(),vec.end()); 將元素翻轉(zhuǎn)，即逆序排列！
2.sort排序：同樣需要引入頭文件 #include<algorithm> ，sort(vec.begin(),vec.end());(默認是按升序排列,即從小到大).
若想降序排列，就必須重寫排序比較函數(shù)按降序排列，定義排序比較函數(shù)：
bool Comp(const int &a,const int &b)
{
return a>b;
}調(diào)用時： sort(vec.begin(),vec.end(),Comp) ，這樣就降序排序。
3.拷貝，例如：a中的從a.begin()（包括它）到a.end()（不包括它）的元素復(fù)制到b中，從b.begin()+1的位置（包括它）開始復(fù)制，覆蓋掉原有元素
copy(a.begin(),a.end(),b.begin()+1);
4.預(yù)留容量： reserve()
int main()
{
vector<int> vec;
vec.reserve(100); //預(yù)留100的容量
cout<<vec.size()<<" "<<vec.capacity()<<endl;
// 0 100
//若要輸出第一個元素，則會報錯
return 0;
}輸出的三種方式
vector<float> vecClass; int nSize = vecClass.size();
方法1：下標訪問
for(int i=0;i<nSize;i++)
{
cout<<vecClass[i]<<" ";
}
cout<<endl; 方法2： .at(i) 訪問
for(int i=0;i<nSize;i++)
{
cout<<vecClass.at(i)<<" ";
}
cout<<endl; 方法3：迭代器訪問，但是輸出某一個指定數(shù)值時不方便
for(vector<float>::iterator it = vecClass.begin();it!=vecClass.end();it++)
{
cout<<*it<<" ";
}
cout<<endl; 二維使用
#include "stdafx.h"
#include <cv.h>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
using namespace std;
int out[3][2] = { 1, 2,
3, 4,
5, 6 };
vector <int*> v1;
v1.push_back(out[0]);
v1.push_back(out[1]);
v1.push_back(out[2]);
cout << v1[0][0] << endl;//1
cout << v1[0][1] << endl;//2
cout << v1[1][0] << endl;//3
cout << v1[1][1] << endl;//4
cout << v1[2][0] << endl;//5
cout << v1[2][1] << endl;//6
return 0;
}再來看一個例子，應(yīng)用實例：
#include<vector>
void ForwardPrint(const vector<int> &ar) //ar為引用，為了防止改變設(shè)置const
{
vector<int> :: const_iterator it = ar.begin(); //迭代器也要加上const
for(; it != ar.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
int main()
{
int ar[] = {12,23,34,45,56,67,78,89,90,100};
int n = sizeof(ar) / sizeof(ar[0]);
vector<int> veca;
vector<int> vecb(10); //有10個數(shù)據(jù)，都為0
vector<int> vecc(10, 23);//有10個數(shù)據(jù)，每個數(shù)都是23
vector<int> vecd(ar, ar+n);//算頭不算尾，將ar中的數(shù)據(jù)從12到100存入vecd中
vector<int> vece = {12,23,34,45,56,67,78,89,90,100}; //數(shù)組形式將值存入vece中 ; vs2019 C11
vector<int> vecf {12,23,34,45,56,67,78,89,90,100};
vector<int> :: iterator it = vece.begin(); //it迭代器，要比指針安全。當越界時，會有檢查
for(; it != vece.end(); it++)
{
*it += 10; //也可以通過迭代器改變vector中的值
cout<< *it <<endl;
}
//逆向迭代器，逆向打印
vector<int>:: reverse_iterator rit = vecf.rbegin();
for(; it != vecf.rend(); it++)
{
cout<<*rit<<" ";
}
ForwardPrint(vece);
return 0;
}了解了vector的基本使用后，我們來對這一容器進行深層次的理解：
初步
vector會分配一些額外的存儲空間，以適應(yīng)可能的增長，容量要大于元素個數(shù)。
.size_type max_size() const {} //返回可容納的最大元素個數(shù)
size_type clear() {} //僅清除元素，未清除空間
void shrink_to_fit() {} //當不清除數(shù)量clear()時，調(diào)用此函數(shù)縮小內(nèi)存shrink_to_fit會將容量調(diào)整與元素個數(shù)相等。
插入
vec.insert(it, 23); //在第一個元素位置插入23
vec.insert(it, 10, 23); //在第一個元素位置插入10個23
vec.insert(it, ar, ar+n) //算頭不算尾，可以插入整個數(shù)組
vec.insert(it, {1,2,3,4,5,6}) //插入一個列表元素刪除
it = vec.begin(); vec.erase(it); //刪除首元素 vec.erase(it, it+5); //連續(xù)刪除
空間預(yù)留
reserver函數(shù)用來給vector預(yù)分配存儲區(qū)大小,即 capacity 的值，但是沒有給這段內(nèi)存進行初始化。reserve的參數(shù)n是推薦預(yù)分配內(nèi)存的大小，實際分配的可能等于或大于這個值。
當調(diào)用函數(shù)時，n的值如果大于capacity的值，就會重新分配內(nèi)存，使得capacity的值會大于n。這樣，當調(diào)用 push_ back 函數(shù)便得size超過原來的默認分配的capacity值時避免了內(nèi)存重分配開銷。
需要注意的是: reserve 函數(shù)分配出來的內(nèi)存空間未初始化對象，只是表示vector可以利用這部分內(nèi)存空間，但vector不能有效地訪問這些內(nèi)存空間，如訪問的時候就會出現(xiàn)越界現(xiàn)象，導(dǎo)致程序崩潰。 改變?nèi)萜鞔笮?resize函數(shù)重新分配大小，改變?nèi)萜鞯拇笮。⑶覄?chuàng)建對象。
void resize(const size_type Newsize); void resize(const size_type Newsize, const T& x);
對于下面這個vector，我們來看看使用resize會發(fā)生什么？
vector<int> vec {12,23,34,5,4,55,67}①當n小于當前size()值時候，vector首先會減少size()值保存前n個元素，然后將超出n的元素刪除.
eg: vec.resize(5, 100), 則不會把100插入，并且會刪除至5個元素。
②當n大于當前size()值時候，vector會插入相應(yīng)數(shù)量的元素使得size()值達到n，并對這些元素進行初始化，如果調(diào)用上面的第二個resize函數(shù)，指定val，vector會用val來初始化這些新插入的元素。 eg: vec.resize(15,100)
③當n大于capacity()值的時候，會自動分配重新分配內(nèi)存存儲空間。
迭代器
vector<int> ::iterator it = vec.begin(); vec.push_back(); //前期的迭代器已失效 vec.pop_back(); //也會導(dǎo)致失效 cout<<*it<<endl; vec.insert(it, 23); cout<<*it<<endl; //迭代器失效
只要插入或刪除數(shù)據(jù)，都會使前期的迭代器失效 ，必須對迭代器 再次 初始化或者賦值。
了解了這些之后，我們就來實現(xiàn)一個自己的vector：在STL中，我們可以查看系統(tǒng)自帶的vector的實現(xiàn)，主要包含了三個指針：
- 指向數(shù)組起始位置的指針；
- 指向數(shù)組中最后一個有效元素位置的后繼位置；
- 指向數(shù)組空間的后繼位置。
代碼如下：
template<class T>
class vector
{
public:
vector(int size = 10)
{
_first = new T[size];
_last = _first;
_end = _first + size;
}
~vector()
{
delete[] _first;
_first = _last = _end = nullptr;
}
vector(const vector<T> &rhs)//防止淺拷貝的拷貝構(gòu)造
{
int size = rhs._end - rhs._first;
_first = new T[size];
//拷貝有效元素
int len = rhs._last - rhs._first;
for(int i = 0;i<len;++i)
{
_first[i] = rhs._first[i];
}
_last = _first + len;
_end = _first + size;
}
vector<T>& operator=(const vector<T> &rhs)
{
if(this == &rhs)
{
return *this;
}
delete[] _first;
int size = rhs._end - rhs._first;
_first = new T[size];
int len = rhs._last - rhs._first;
for(int i = 0;i<len;++i)
{
_first[i] = rhs._first[i];
}
_last = _first + len;
return *this;
}
void push_back(const T &val)
{
if(full())
expand();
*_last++ = val;
}
void pop_back()
{
if(empty())
return;
--_last;
}
T back()const//返回容器末尾的元素的值
{
return *(_last -1);
}
bool full()const{return _last == _end;}
bool empty()const{return _first == _last;}
int size()const{return _last - _first;}
T & operator[](int index)
{
if(index < 0 || index >= size())
{
throw "OutofRangeException";
}
return _first[index];
}
private:
T* _first; //數(shù)組起始位置
T* _last; //指向數(shù)組中有效元素的后繼位置
T* _end; //指向數(shù)組空間的后繼位置
void expand()//容器的二倍擴容操作接口
{
int size = _end - _first;
T *ptmp = new T[2*size];
for(int i = 0;i < size;++i)
{
ptmp[i] = _first[i];
}
delete[] _first;
_first = ptmp;
_last = _first + size;
_end = _first +2*size;
}
};但是上述代碼還是存在一些問題：
- 對于一個容器來說，里面存放的數(shù)據(jù)類型可以是系統(tǒng)自帶的默認類型，比如：int、char等等，也可以是自己定義的class XXX類型。
- 對于默認類型來說，我們上面的代碼是沒有問題的（可以自行驗證），但是對于自定義類型來說，就會出現(xiàn)問題：
比如我們加上自己定義的簡單類型，分別給構(gòu)造函數(shù)、析構(gòu)函數(shù)、拷貝構(gòu)造函數(shù)都加上打印信息：
class Test
{
public:
Test() { cout << "Test()" << endl; }
~Test() { cout << "~Test()" << endl; }
Test(const Test&) { cout << "Test(const Test&)" << endl; }
};接下來用test類型實例化一下這個容器：
int main()
{
vector<Test> vec;
return 0;
}結(jié)果如下：
我們會發(fā)現(xiàn)，我只是定義了一個空的容器，但是它卻自動添加了十個對象。
解決上述問題的方法：Allocator空間配置器
系統(tǒng)自帶的vector中：
可以看到，系統(tǒng)的實現(xiàn)，除了數(shù)據(jù)類型外，還有一個 allocator 。而這個，就是解決問題的辦法了！我們再來回過頭看看問題，其實問題主要出在了構(gòu)造函數(shù)的new上：我們都知道new這個關(guān)鍵字會完成兩項任務(wù)：
- 開辟空間
- 數(shù)據(jù)初始化（對自定義類型來說就調(diào)用構(gòu)造函數(shù)）
可問題是，我們既然選擇把它作為容器，那么就只需要它提供一個場所（空間），至于這個場所里存放什么數(shù)據(jù)，是由程序員來決定的，不應(yīng)該由容器來擅作主張。
那么，問題的關(guān)鍵就在于將 開辟空間 和 構(gòu)造對象 分離開。析構(gòu)函數(shù)也不應(yīng)該做上述delete操作，而是將 有效內(nèi)存釋放 即可，應(yīng)該將 釋放空間 和 析構(gòu)對象 分離開。
因此，空間配置器應(yīng)該有以下四個功能：
- 內(nèi)存開辟
allocate（底層調(diào)用malloc）； - 內(nèi)存釋放
deallocate（底層調(diào)用free）； - 對象構(gòu)造
construct（調(diào)用構(gòu)造函數(shù)）； - 對象析構(gòu)
destroy（調(diào)用析構(gòu)函數(shù)）。
// 定義容器的空間配置器，和C++標準庫的allocator實現(xiàn)一樣
template<typename T>
struct Allocator
{
T* allocate(size_t size) // 負責內(nèi)存開辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void* p) // 負責內(nèi)存釋放
{
free(p);
}
void construct(T* p, const T& val) // 在指定內(nèi)存上負責對象構(gòu)造
{
new (p) T(val); // 定位new
}
void destroy(T* p) // 負責對象析構(gòu)
{
p->~T(); // ~T()代表了T類型的析構(gòu)函數(shù)
}
};于是，修改我們之前的vector如下：
template<typename T, typename Alloc = Allocator<T>>
class vector
{
public:
vector(int size = 10)
{
// 需要把內(nèi)存開辟和對象構(gòu)造分開處理
_first = _allocator.allocate(size);
_last = _first;
_end = _first + size;
}
~vector()
{
// 析構(gòu)容器有效的元素，然后釋放_first指針指向的堆內(nèi)存
for (T* p = _first; p != _last; ++p)
{
_allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進行析構(gòu)操作
}
_allocator.deallocate(_first); // 釋放堆上的數(shù)組內(nèi)存
_first = _last = _end = nullptr;
}
vector(const vector<T>& rhs)
{
int size = rhs._end - rhs._first;
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;
for (int i = 0; i < len; ++i)
{
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
}
vector<T>& operator=(const vector<T>& rhs)
{
if (this == &rhs)
return *this;
for (T* p = _first; p != _last; ++p)
{
_allocator.destroy(p); // 把_first指針指向的數(shù)組的有效元素進行析構(gòu)操作
}
_allocator.deallocate(_first);
int size = rhs._end - rhs._first;
_first = _allocator.allocate(size);
int len = rhs._last - rhs._first;
for (int i = 0; i < len; ++i)
{
_allocator.construct(_first + i, rhs._first[i]);
}
_last = _first + len;
_end = _first + size;
return *this;
}
void push_back(const T& val) // 向容器末尾添加元素
{
if (full())
expand();
_allocator.construct(_last, val);
_last++;
}
void pop_back() // 從容器末尾刪除元素
{
if (empty())
return;
// 不僅要把_last指針--，還需要析構(gòu)刪除的元素
--_last;
_allocator.destroy(_last);
}
T back()const // 返回容器末尾的元素的值
{
return *(_last - 1);
}
bool full()const { return _last == _end; }
bool empty()const { return _first == _last; }
int size()const { return _last - _first; }
T & operator[](int index)
{
if(index < 0 || index >= size())
{
throw "OutofRangeException";
}
return _first[index];
}
private:
T* _first; // 指向數(shù)組起始的位置
T* _last; // 指向數(shù)組中有效元素的后繼位置
T* _end; // 指向數(shù)組空間的后繼位置
Alloc _allocator; // 定義容器的空間配置器對象
void expand() // 容器的二倍擴容
{
int size = _end - _first;
T* ptmp = _allocator.allocate(2 * size);
for (int i = 0; i < size; ++i)
{
_allocator.construct(ptmp + i, _first[i]);
}
for (T* p = _first; p != _last; ++p)
{
_allocator.destroy(p);
}
_allocator.deallocate(_first);
_first = ptmp;
_last = _first + size;
_end = _first + 2 * size;
}
};我們接下來實現(xiàn)以下vector容器的迭代器：
注意事項 ：
迭代器一般實現(xiàn)成容器的嵌套類型；因為不同的容器在其底層的數(shù)據(jù)結(jié)構(gòu)是不一樣的，由此我們迭代的方式也就不一樣。
//迭代器
class iterator
{
public:
iterator(T* p = nullptr):_ptr(p){}
bool operator!=(const iterator &it)const
{
return _ptr != it._ptr;
}
void operator++()//迭代器的前置++運算符重載，不用后置++的原因是不用產(chǎn)生臨時量
{
_ptr++;
}
T & operator*()
{
return *_ptr;
}
const T & operator*()const
{
return *_ptr;
}
private:
T* _ptr;
};
//需要給容器提供begin和end方法
iterator begin(){return iterator (_first);}
iterator end(){return iterator (_end);}使用正常：
int main()
{
vector<int>vec;
for(int i = 0;i<20;++i)
{
vec.push_back(rand()%100+1);
}
int size = vec.size();
for(int i = 0;i<size;++i)
{
cout<<vec[i]<<" ";
}
cout<<endl;
cout<<"----------------------------------------------------------"<<endl;
vector<int>::iterator it = vec.begin();
for(;it != vec.end();++it)
{
cout<<*it<<" ";
}
cout<<endl;
cout<<"----------------------------------------------------------"<<endl;
for(int val:vec)//foreach的底層原理也是通過容器的迭代器來實現(xiàn)容器遍歷
{
cout<<val<<" ";
}
cout<<endl;
return 0;
}
總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
在本篇文章里小編給大家整理了一篇關(guān)于c/c++內(nèi)存分配大小實例講解內(nèi)容，有需要的朋友們可以跟著學(xué)習(xí)參考下。2021-11-11
關(guān)于C++多重繼承下虛表結(jié)構(gòu)的問題
這篇文章主要介紹了C++ 多重繼承下虛表結(jié)構(gòu)的問題，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-09-09
C++相較于Java，Python 并沒有提供的字符串分割的函數(shù)split，因此需要自己進行編寫，本文主要介紹了C++如何切割String對象的方法，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-05-05
所謂容器，就是可以承載，包含元素的一個器件，它是STL六大組件之一，是容器、算法、迭代器中最重要也是最核心的一部分2022-10-10
AT&T 匯編是一種和intel匯編在語法上完全不同的匯編語言，為避免混淆intel語法，本文只介紹AT&T匯編，AT&T的第一個特點就是每個寄存器名前必須加‘%’,立即數(shù)前必須加‘$’2019-02-02
這篇文章主要介紹了C語言關(guān)鍵字union的定義和使用詳解,本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-02-02
C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換
這篇文章主要介紹的是C++類結(jié)構(gòu)體與json相互轉(zhuǎn)換，json字符串一般使用的是開源的類庫Newtonsoft.Json，方法十分簡潔，下面就隨小編一起看下面文章內(nèi)容吧2021-09-09
C語言中feof函數(shù)和ferror函數(shù)示例詳解
在C語言中feof函數(shù)用于檢查文件流的結(jié)束標志,判斷文件在讀取時是否已經(jīng)到達了文件的末尾,這篇文章主要給大家介紹了關(guān)于C語言中feof函數(shù)和ferror函數(shù)的相關(guān)資料,需要的朋友可以參考下2024-09-09
這篇文章主要為大家詳細介紹了C語言實現(xiàn)通訊錄系統(tǒng)程序，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-06-06
許多在Windows平臺上使用OpenCV的開發(fā)者可能會在使用findContours 函數(shù)時,遇到令人頭疼的程序崩潰問題,本文將深入剖析此問題的潛在原因,并提供一個更可靠的定制化實現(xiàn)方案,感興趣的朋友一起看看吧2025-05-05