C++ vector及實(shí)現(xiàn)自定義vector以及allocator和iterator方式
簡介
作用：vector是一個(gè)能夠存放任意類型的 動(dòng)態(tài)數(shù)組 ，能夠增加和壓縮數(shù)據(jù)。
vector是表示可以改變大小的數(shù)組的序列容器。
與數(shù)組一樣，vector對元素使用連續(xù)的存儲位置，這意味也可以使用指向其元素的常規(guī)指針上的偏移量來訪問它們的元素，并且與在數(shù)組中一樣高效。
但是與數(shù)組不同，它們的大小可以動(dòng)態(tài)變化，容器會自動(dòng)處理它們的存儲。
在內(nèi)部，vector 使用個(gè)動(dòng)態(tài)分配的數(shù)組來存儲它們的元素。這個(gè)數(shù)組可能需要重新分配，以便在插入新元素時(shí)增大大小，這意味著分配一個(gè)新數(shù)組并將所有元素移動(dòng)到其中。就處理時(shí)間而言，這是一項(xiàng)相對昂貴的任務(wù)，因此，向量不會在每次向容器添加元素時(shí)重新分配。
相反，vector 容器可以分配一些 額外的存儲空間以適應(yīng)可能的增長 ， 因此容器的實(shí)際容量可能大于嚴(yán)格需要的存儲容量(即容器的大小)。
對于不同的插入位置，可以在不同的時(shí)間間隔內(nèi)實(shí)現(xiàn)不同的插入策略，但只能在不同的位置上實(shí)現(xiàn)內(nèi)存大小的平衡。
因此，與array相比，向量消耗更多的內(nèi)存，以 換取管理存儲和以高效方式動(dòng)態(tài)增長 的能力。與其他動(dòng)態(tài)序列容器( deques 、 list 和 forward_list )相比，vectors 可以非常高效地訪問其元素(就像數(shù)組一樣)，并相對高效地從其末尾添加或刪除元素。
對于涉及在結(jié)尾以外的位置插入或刪除元素的操作，它們的性能比其他操作差，迭代器和引用的一致性也不如list 和forward_list。
注意 ：
使用時(shí)有以下的注意事項(xiàng)：
- 1.如果你要表示的向量長度較長（需要為向量內(nèi)部保存很多數(shù)），容易導(dǎo)致內(nèi)存泄漏，而且效率會很低；
- 2.Vector作為函數(shù)的參數(shù)或者返回值時(shí)，需要注意它的寫法：
double Distance(vector<int>&a, vector<int>&b)
其中的“ & ”絕對不能少?。。?/p>
- 3.建立一個(gè)vector，int為數(shù)組元素的數(shù)據(jù)類型，test為動(dòng)態(tài)數(shù)組名
簡單的使用方法如下：
vector<int>test;//建立一個(gè)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); - 使用下標(biāo)訪問元素，cout<<
vec[0]<<endl;記住下標(biāo)是從0開始的。 - 使用迭代器訪問元素
vector<int>::iterator it; for(it=vec.begin();it!=vec.end();it++) cout<<*it<<endl;
- 插入元素： vec.insert(vec.begin()+i,a);在第i+1個(gè)元素前面插入a;
- 刪除元素： vec.erase(vec.begin()+2);刪除第3個(gè)元素
- 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)體要定義為全局的，否則會出錯(cuò)
算法
1.逆序排列： 使用 reverse 將元素翻轉(zhuǎn)：需要頭文件 #include<algorithm> 、 reverse(vec.begin(),vec.end()); 將元素翻轉(zhuǎn)，即逆序排列！
2.sort排序：同樣需要引入頭文件 #include<algorithm> ，sort(vec.begin(),vec.end());(默認(rèn)是按升序排列,即從小到大).
若想降序排列，就必須重寫排序比較函數(shù)按降序排列，定義排序比較函數(shù)：
bool Comp(const int &a,const int &b)
{
return a>b;
}調(diào)用時(shí)： 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
//若要輸出第一個(gè)元素，則會報(bào)錯(cuò)
return 0;
}輸出的三種方式
vector<float> vecClass; int nSize = vecClass.size();
方法1：下標(biāo)訪問
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：迭代器訪問，但是輸出某一個(gè)指定數(shù)值時(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;
}再來看一個(gè)例子，應(yīng)用實(shí)例：
#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個(gè)數(shù)據(jù)，都為0
vector<int> vecc(10, 23);//有10個(gè)數(shù)據(jù)，每個(gè)數(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迭代器，要比指針安全。當(dāng)越界時(shí)，會有檢查
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的基本使用后，我們來對這一容器進(jìn)行深層次的理解：
初步
vector會分配一些額外的存儲空間，以適應(yīng)可能的增長，容量要大于元素個(gè)數(shù)。
.size_type max_size() const {} //返回可容納的最大元素個(gè)數(shù)
size_type clear() {} //僅清除元素，未清除空間
void shrink_to_fit() {} //當(dāng)不清除數(shù)量clear()時(shí)，調(diào)用此函數(shù)縮小內(nèi)存shrink_to_fit會將容量調(diào)整與元素個(gè)數(shù)相等。
插入
vec.insert(it, 23); //在第一個(gè)元素位置插入23
vec.insert(it, 10, 23); //在第一個(gè)元素位置插入10個(gè)23
vec.insert(it, ar, ar+n) //算頭不算尾，可以插入整個(gè)數(shù)組
vec.insert(it, {1,2,3,4,5,6}) //插入一個(gè)列表元素刪除
it = vec.begin(); vec.erase(it); //刪除首元素 vec.erase(it, it+5); //連續(xù)刪除
空間預(yù)留
reserver函數(shù)用來給vector預(yù)分配存儲區(qū)大小,即 capacity 的值，但是沒有給這段內(nèi)存進(jìn)行初始化。reserve的參數(shù)n是推薦預(yù)分配內(nèi)存的大小，實(shí)際分配的可能等于或大于這個(gè)值。
當(dāng)調(diào)用函數(shù)時(shí)，n的值如果大于capacity的值，就會重新分配內(nèi)存，使得capacity的值會大于n。這樣，當(dāng)調(diào)用 push_ back 函數(shù)便得size超過原來的默認(rèn)分配的capacity值時(shí)避免了內(nèi)存重分配開銷。
需要注意的是: reserve 函數(shù)分配出來的內(nèi)存空間未初始化對象，只是表示vector可以利用這部分內(nèi)存空間，但vector不能有效地訪問這些內(nèi)存空間，如訪問的時(shí)候就會出現(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);
對于下面這個(gè)vector，我們來看看使用resize會發(fā)生什么？
vector<int> vec {12,23,34,5,4,55,67}①當(dāng)n小于當(dāng)前size()值時(shí)候，vector首先會減少size()值保存前n個(gè)元素，然后將超出n的元素刪除.
eg: vec.resize(5, 100), 則不會把100插入，并且會刪除至5個(gè)元素。
②當(dāng)n大于當(dāng)前size()值時(shí)候，vector會插入相應(yīng)數(shù)量的元素使得size()值達(dá)到n，并對這些元素進(jìn)行初始化，如果調(diào)用上面的第二個(gè)resize函數(shù)，指定val，vector會用val來初始化這些新插入的元素。 eg: vec.resize(15,100)
③當(dāng)n大于capacity()值的時(shí)候，會自動(dòng)分配重新分配內(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ù)，都會使前期的迭代器失效 ，必須對迭代器 再次 初始化或者賦值。
了解了這些之后，我們就來實(shí)現(xiàn)一個(gè)自己的vector：在STL中，我們可以查看系統(tǒng)自帶的vector的實(shí)現(xiàn)，主要包含了三個(gè)指針：
- 指向數(shù)組起始位置的指針；
- 指向數(shù)組中最后一個(gè)有效元素位置的后繼位置；
- 指向數(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()//容器的二倍擴(kuò)容操作接口
{
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;
}
};但是上述代碼還是存在一些問題：
- 對于一個(gè)容器來說，里面存放的數(shù)據(jù)類型可以是系統(tǒng)自帶的默認(rèn)類型，比如：int、char等等，也可以是自己定義的class XXX類型。
- 對于默認(rèn)類型來說，我們上面的代碼是沒有問題的（可以自行驗(yàn)證），但是對于自定義類型來說，就會出現(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類型實(shí)例化一下這個(gè)容器：
int main()
{
vector<Test> vec;
return 0;
}結(jié)果如下：
我們會發(fā)現(xiàn)，我只是定義了一個(gè)空的容器，但是它卻自動(dòng)添加了十個(gè)對象。
解決上述問題的方法：Allocator空間配置器
系統(tǒng)自帶的vector中：
可以看到，系統(tǒng)的實(shí)現(xiàn)，除了數(shù)據(jù)類型外，還有一個(gè) allocator 。而這個(gè)，就是解決問題的辦法了！我們再來回過頭看看問題，其實(shí)問題主要出在了構(gòu)造函數(shù)的new上：我們都知道new這個(gè)關(guān)鍵字會完成兩項(xiàng)任務(wù)：
- 開辟空間
- 數(shù)據(jù)初始化（對自定義類型來說就調(diào)用構(gòu)造函數(shù)）
可問題是，我們既然選擇把它作為容器，那么就只需要它提供一個(gè)場所（空間），至于這個(gè)場所里存放什么數(shù)據(jù)，是由程序員來決定的，不應(yīng)該由容器來擅作主張。
那么，問題的關(guān)鍵就在于將 開辟空間 和 構(gòu)造對象 分離開。析構(gòu)函數(shù)也不應(yīng)該做上述delete操作，而是將 有效內(nèi)存釋放 即可，應(yīng)該將 釋放空間 和 析構(gòu)對象 分離開。
因此，空間配置器應(yīng)該有以下四個(gè)功能：
- 內(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++標(biāo)準(zhǔn)庫的allocator實(shí)現(xiàn)一樣
template<typename T>
struct Allocator
{
T* allocate(size_t size) // 負(fù)責(zé)內(nèi)存開辟
{
return (T*)malloc(sizeof(T) * size);
}
void deallocate(void* p) // 負(fù)責(zé)內(nèi)存釋放
{
free(p);
}
void construct(T* p, const T& val) // 在指定內(nèi)存上負(fù)責(zé)對象構(gòu)造
{
new (p) T(val); // 定位new
}
void destroy(T* p) // 負(fù)責(zé)對象析構(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ù)組的有效元素進(jìn)行析構(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ù)組的有效元素進(jìn)行析構(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() // 容器的二倍擴(kuò)容
{
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;
}
};我們接下來實(shí)現(xiàn)以下vector容器的迭代器：
注意事項(xiàng) ：
迭代器一般實(shí)現(xiàn)成容器的嵌套類型；因?yà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++()//迭代器的前置++運(yùn)算符重載，不用后置++的原因是不用產(chǎn)生臨時(shí)量
{
_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的底層原理也是通過容器的迭代器來實(shí)現(xiàn)容器遍歷
{
cout<<val<<" ";
}
cout<<endl;
return 0;
}
總結(jié)
以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。
相關(guān)文章
本文主要介紹了C++?Date類的具體使用(構(gòu)建,重載等)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-07-07
這篇文章主要介紹了C++線程池的簡單實(shí)現(xiàn)方法,包括了線程操作函數(shù)及相關(guān)屬性的用法,需要的朋友可以參考下2014-09-09
OpenCV透視變換應(yīng)用之書本視圖矯正+廣告屏幕切換
透視變換是指利用透視中心、像點(diǎn)、目標(biāo)點(diǎn)三點(diǎn)共線的條件，按透視旋轉(zhuǎn)定律使承影面繞跡線旋轉(zhuǎn)某一角度，破壞原有的投影光線束，仍能保持承影面上投影幾何圖形不變的變換。本文將為大家介紹兩個(gè)OpenCV透視變換應(yīng)用，需要的可以參考一下2022-08-08
這篇文章主要介紹了C語言對磁盤文件進(jìn)行快速排序簡單實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-06-06
C++調(diào)用python(執(zhí)行py文件)的全過程
這篇文章主要給大家介紹了關(guān)于C++調(diào)用python(執(zhí)行py文件)的相關(guān)資料,文中通過圖文以及實(shí)例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2021-12-12
C++編程中的const關(guān)鍵字常見用法總結(jié)
這篇文章主要介紹了C++編程中的const關(guān)鍵字常見用法總結(jié),const關(guān)鍵字的使用是C++入門學(xué)習(xí)中的基礎(chǔ)知識,需要的朋友可以參考下2015-11-11
這篇文章主要為大家詳細(xì)介紹了C語言課程設(shè)計(jì)之停車場管理問題，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
本篇文章主要介紹了C++中的friend函數(shù)詳細(xì)解析，對初學(xué)c++的人有一定的幫助，有需要的可以了解一下。2016-11-11
STL區(qū)間成員函數(shù)及區(qū)間算法總結(jié)
這篇文章主要匯總介紹了STL區(qū)間成員函數(shù)及區(qū)間算法，有需要的小伙伴可以參考下。2015-07-07
c++實(shí)現(xiàn)圖像像素計(jì)算的示例詳解
我們知道每張圖像都能夠用矩陣來表示,矩陣中每個(gè)元素的值表示了圖像中每個(gè)像素值,像素值的大小就對應(yīng)著圖像的亮暗,本文主要來和大家介紹一下C++進(jìn)行圖像像素計(jì)算的相關(guān)知識,感興趣的可以了解下2023-12-12