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