前言

近來做到一些題目，對于暴力有些卡空間，對于幾個能拿分的subtask沒個剛好都能過去，但是開的數組不一樣，都開就MLE了，我就嘗試著開同一個數組，卡的太緊，最后很多數據都MLE沒分了，一氣之下覺定學習動態開內存（順便學習一下手寫vector）

vector簡介

vector？著名STL之一，又稱動態數組，簡直就是一個數組，有點像個棧
支持壓入，彈出（push_back，pop_back）這個均攤O（1）
支持隨機尋址
然后支持erase？刪除中間一個數，可惜是O（n）的，然而跑的飛快（手寫的vector里沒寫~逃~）
其它功能基本不用

實現方式

vector尋址O（1）是因為它的內存連續，一個vector由一個數組指針（后面代碼中的Data，之后的變量也會用括號表示）、一個當前總可用存儲大小（Len），已用存儲大小（Size）
壓入元素：如果存儲的地方用完了，那么就把存儲數組開大一倍
彈出元素：如果使用的存儲占不到總存儲的1/4那么就把存儲數組減小一半

代碼

下面這份代碼里的class是首先的vector，后面是對速度的測驗

#include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<cstdlib> #include<ctime> template<typename T> class Vector {private:T* Data;int Len,Size;public:inline Vector(){Data=NULL;Len=Size=0;}inline Vector(const Vector& other){if(this==&other||!Len)return;Data=(T*)malloc(sizeof(T)*other.Len);for(register int i=0;i<other.Size;i++)Data[i]=other.Data[i];Len=other.Len,Size=other.Size;}inline T &operator[](const int x){return Data[x];}const Vector&push_back(const T x){if(Size==Len){Len=Len==0?1:Len<<1;T* newData=(T*)malloc(sizeof(T)*Len);memcpy(newData,Data,Size*sizeof(T));free(Data);Data=newData;}Data[Size++]=x;return *this;}const Vector&pop_back(){Size--;if(Size==(Len>>2)){Len=Len>>1;T* newData=(T*)malloc(sizeof(T)*Len);memcpy(newData,Data,Size*sizeof(T));free(Data);Data=newData;}return *this;}inline unsigned int size(){return Size;}inline unsigned int len(){return Len;} }; int tim; Vector<int>a,b,c,d,e; std::vector<int>A,B,C,D,E; int main() {tim=clock();for(int i=1;i<=10000000;i++)a.push_back(i);for(int i=1;i<=10000000;i++)a.pop_back();for(int i=1;i<=10000000;i++)b.push_back(i);for(int i=1;i<=10000000;i++)b.pop_back();for(int i=1;i<=10000000;i++)c.push_back(i);for(int i=1;i<=10000000;i++)c.pop_back();for(int i=1;i<=10000000;i++)d.push_back(i);for(int i=1;i<=10000000;i++)d.pop_back();for(int i=1;i<=10000000;i++)e.push_back(i);for(int i=1;i<=10000000;i++)e.pop_back();printf("My vector Cost Time：%d\n",clock()-tim);tim=clock();for(int i=1;i<=10000000;i++)A.push_back(i);for(int i=1;i<=10000000;i++)A.pop_back();for(int i=1;i<=10000000;i++)B.push_back(i);for(int i=1;i<=10000000;i++)B.pop_back();for(int i=1;i<=10000000;i++)C.push_back(i);for(int i=1;i<=10000000;i++)C.pop_back();for(int i=1;i<=10000000;i++)D.push_back(i);for(int i=1;i<=10000000;i++)D.pop_back();for(int i=1;i<=10000000;i++)E.push_back(i);for(int i=1;i<=10000000;i++)E.pop_back();printf("STL vector Cost Time：%d\n",clock()-tim);return 0; }

效率實測

首先申明，在這份代碼中，手寫vector的測試時間會偏大（但并不影響很多）
然后這里測的是5e7次push_back加上5e7次pop_back，單位毫秒（ms）
本機配置：Intel(R) Core(TM) i5-7200U CPU @ 2.50GHz 2.70GHz 64位操作系統
在不開O2的情況下，手寫的vector效率提高了很多誒，開心

然而開了O2，效率就被stl爆踩了咯

總結

如果不開O2而且要用vector那么可以考慮手寫，開O2的話那就大膽用了
然候malloc和free的使用非常方便，學會用這兩個東西也是很重要的（當然也要謹慎使用其中的功能，否則出事情后果自負），可以通過這兩個函數解決文章開頭我提到的問題

總結

以上是生活随笔為你收集整理的手写vector的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。