手寫了一個動態申請內存的數組，更準確的說是一個本來應該是塊鏈，最后由于太耗時間了變成數組的東西。
由于太懶了，編譯需要用c++11或以上。
兩個參數分別是元素類型和塊大小S。申請內存以塊為單位，很明顯如果塊大小是\(O(n)\)那么就是數組，如果塊大小是\(O(1)\)那么就是鏈表。
各種操作的復雜度跟數組沒啥區別，有可能乘上一個\(O(n/S)\)，畢竟我太懶了。
重載了許多構造函數，重載了迭代器，應該可以支持大部分stl算法，冒號遍歷應該也沒有問題。

結果慢的飛起，被vector卡爆了，目前還不知有個毛用。
有bug嗎？我也不知道，暫且可以過一些題。
曾經有過內存泄漏的bug，不過現在應該不會了。

namespace container{template<class T,size_t BLOCK_SIZE>class myarray{struct period{T* a;period* ne=NULL;period(){//slow but safea=new T[BLOCK_SIZE]();}period(const T &v){a=new T[BLOCK_SIZE](v);}~period(){delete []a;}};period *Be;size_t Sz;class iterator{period *ip;size_t pos;myarray *po;public:typedef random_access_iterator_tag iterator_category;typedef T value_type;typedef T* pointer;typedef T& reference;typedef ptrdiff_t difference_type;iterator():ip(nullptr),pos(0),po(nullptr){}iterator(const iterator &it){(*this)=it;}iterator(period * const &ip,const size_t &pos,myarray * const &po):ip(ip),pos(pos),po(po){}bool operator !=(const iterator &it) const{return ip!=it.ip||pos!=it.pos;}bool operator ==(const iterator &it) const{return ip==it.ip&&pos==it.pos;}iterator operator ++(){if (++pos==BLOCK_SIZE&&ip->ne!=NULL){ip=ip->ne;pos=0;}return *this;}const iterator operator ++(int){iterator tmp(*this);if (++pos==BLOCK_SIZE&&ip->ne!=NULL){ip=ip->ne;pos=0;}return tmp;}iterator operator --(){if (pos){--pos;return (*this);}period *tBe=po->Be;while (tBe->ne!=ip) tBe=tBe->ne;ip=tBe;pos=BLOCK_SIZE-1;return (*this);}const iterator operator --(int){iterator tmp(*this);if (pos){--pos;return tmp;}period *tBe=po->Be;while (tBe->ne!=ip) tBe=tBe->ne;ip=tBe;pos=BLOCK_SIZE-1;return tmp;}iterator operator +(const size_t &len) const{//ip!=NULL BUGif (BLOCK_SIZE>pos+len) return iterator(ip,pos+len,po);size_t tmp=len-(BLOCK_SIZE-1-pos);if (ip->ne==NULL) return iterator(ip,BLOCK_SIZE,po);period *tip=ip->ne;while (tmp>BLOCK_SIZE){if (tip->ne==NULL) return iterator(tip,BLOCK_SIZE,po);tip=tip->ne;tmp-=BLOCK_SIZE;}return iterator(tip,tmp-1,po);}iterator operator +=(const size_t &len){return ((*this)=(*this)+len);}size_t operator -(const iterator &it) const{//onlyif (ip==it.ip) return pos-it.pos;period *tmp=it.ip->ne;size_t ret=BLOCK_SIZE-it.pos;while (tmp!=ip){ret+=BLOCK_SIZE;tmp=tmp->ne;}return ret+pos;}iterator operator -(const size_t &len) const{return (po->begin()+((*this)-(po->begin())-len));}iterator operator -=(const size_t &len){return ((*this)=(*this)-len);}bool operator <(const iterator &it) const{//same fatherreturn ((*this)-po->begin())<(it-(po->begin()));}bool operator <=(const iterator &it) const{//same fatherreturn ((*this)-po->begin())<=(it-(po->begin()));}T & operator *() const{return ip->a[pos];}};public:typedef T value_type;typedef T& reference;typedef const T& const_reference;typedef size_t size_type;myarray(){Be=NULL;Sz=0;}myarray(const size_t &sz){construct(sz);}myarray(const size_t &sz,const T &v){construct(sz,v);}~myarray(){myfree(Be);}myarray(const myarray &rhs){if (this==&rhs) return;construct(rhs.size());auto j=begin();for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);}myarray(const initializer_list<T> &args){construct(args.size());auto j=begin();for (auto it=args.begin(); it!=args.end(); ++it) *(j++)=(*it);}myarray& operator =(const myarray &rhs){if (this==&rhs) return (*this);myfree(Be);construct(rhs.size());auto j=begin();for (auto it=rhs.begin(); it!=rhs.end(); ++it) *(j++)=(*it);return *this;}void myfree(period * const &Be){period *tBe=Be,*tmp;while (tBe!=NULL){tmp=tBe->ne;delete tBe;tBe=tmp;}}void construct(const size_t &sz){Be=new period();//slow but safeSz=sz;size_t tSz=sz;period *tBe=Be;while (tSz>BLOCK_SIZE){tBe=(tBe->ne=new period);tSz-=BLOCK_SIZE;}}void construct(const size_t &sz,const T &v){Be=new period(v);Sz=sz;size_t tSz=sz;period *tBe=Be;while (tSz>BLOCK_SIZE){tBe=(tBe->ne=new period);tSz-=BLOCK_SIZE;}}iterator begin() const{return iterator(Be,0,(myarray*)this);}iterator end() const{//Slow And Dangerousif (Be==NULL) return iterator(NULL,0,(myarray*)this);period *tBe=Be;while (tBe->ne!=NULL) tBe=tBe->ne;return iterator(tBe,((int)Sz-1)%(int)BLOCK_SIZE+1,(myarray*)this);}void push_back(const T &v){if (Be==NULL){Be=new period;Be->a[Sz++]=v;return;}period *tBe=Be;while (tBe->ne!=NULL) tBe=tBe->ne;size_t tSz=(Sz++)%BLOCK_SIZE;if (tSz==0) tBe=(tBe->ne=new period);tBe->a[tSz]=v;}void pop_back(){if ((--Sz)%BLOCK_SIZE) return;if (Sz==0){delete Be;Be=NULL;return;}period *tBe=Be;while (tBe->ne->ne!=NULL) tBe=tBe->ne;delete tBe->ne;tBe->ne=NULL;}T& operator [](const size_t &pos) const{size_t tpos=pos;for (period* i=Be; i!=NULL; i=i->ne)if (tpos<BLOCK_SIZE) return i->a[tpos];else tpos-=BLOCK_SIZE;throw;}T& front() const{//unusualreturn Be->a[0];}T& back() const{return *(--end());}size_t size() const{return Sz;}bool empty() const{return Sz==0;}void swap(myarray &arr){std::swap(Be,arr.Be);std::swap(Sz,arr.Sz);}template<class U>struct iterator_traits{typedef typename U::value_type value_type;typedef typename U::iterator_category iterator_category;typedef typename U::difference_type difference_type;typedef typename U::pointer pointer;typedef typename U::reference reference;};}; } template<class T=int,size_t BLOCK_SIZE=32> using arr=container::myarray<T,BLOCK_SIZE>;

轉載于:https://www.cnblogs.com/Yuhuger/p/10546728.html

總結

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

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