导航在左侧的网站欣赏,外贸营销网站制作,保定免费做网站,wordpress模板仿新版虎嗅huxiu-new主题阅前提要#xff1a;
本文主要是对list和vector的实现的补充#xff0c;以代码实现为主#xff0c;注释为辅#xff0c;如果对vector#xff0c;list底层实现感兴趣的可以自行阅读#xff0c;代码量有点大#xff0c;请大家耐心查看#xff0c;对理解语言很有帮助
本文主要是对list和vector的实现的补充以代码实现为主注释为辅如果对vectorlist底层实现感兴趣的可以自行阅读代码量有点大请大家耐心查看对理解语言很有帮助本文的实现方式并不是stl标准库中的实现但大致的思路一样
一、反向迭代器的实现
实现思想反向迭代器和正向迭代器的不同点只在于--时迭代器的移动方向不同其他的操作基本一样我们可以对正向迭代器进行封装从而得到反向迭代器代码如下
namespace zxws
{// 适配器 -- 复用//这里细节关键在于模板参数可以传任何一个容器的正向迭代器//即只要该容器的正向迭代器实现了那么反向迭代器也就实现了(这就是模板的力量)templateclass Iterator, class Ref, class Ptrstruct Reverse_iterator{Iterator _it;//这是正向迭代器typedef Reverse_iterator Self;Reverse_iterator(Iterator it):_it(it){}bool operator(const Self s){return _it s._it;}bool operator!(const Self s){return _it ! s._it;}//这个函数的实现和我们默认的rbegin()和rend()的位置有关//下面的代码实现是默认rbegin()是end() rend()是begin()Ref operator*(){Iterator cur _it;return *(--cur);}Ptr operator-(){return (operator*());}Self operator(){--_it;return *this;}Self operator--(){_it;return *this;}Self operator(int){Self tmp(_it);--_it;return tmp;}Self operator--(int){Self tmp(_it);_it;return tmp;}};
}
二、list的实现
思路本质和数据结构中的双向循环链表一样只是用C的语法实现的不同点在迭代器
代码如下
namespace zxws
{templateclass Tstruct Node {T _val;Node* _next;Node* _pre;Node(const T xT()):_val(x),_next(nullptr),_pre(nullptr){}};//正向迭代器的实现templateclass T,class Ref,class Ptrstruct Iterator {typedef NodeT Node;typedef Iterator Self;Node* node;Iterator(Node* p):node(p){}Self operator(){node node-_next;return *this;}Self operator--(){node node-_pre;return *this;}Self operator(int){Self tmp(node);node node-_next;return tmp;}Self operator--(int){Self tmp(node);node node-_pre;return tmp;}Ref operator*(){return node-_val;}Ptr operator-(){return node-_val;}bool operator(const Self tmp){return node tmp.node;}bool operator!(const Self tmp){return node ! tmp.node;}};templateclass Tclass list{public:typedef NodeT Node;typedef IteratorT, T, T* iterator;typedef IteratorT,const T,const T* const_iterator;iterator begin(){return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;//对rbegin(),rend()的位置的定义//与反向迭代器中解引用运算符的重载实现有关reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}list(){init();}void init(){_head new Node;_head-_next _head;_head-_pre _head;}~list(){clear();delete _head;_head nullptr;}void clear(){auto cur begin();while(cur!end()){cur erase(cur);}}list(const list tmp){init();for(auto x:tmp){push_back(x);}}list operator(list tmp){swap(tmp);return *this;}void swap(list tmp){std::swap(_head, tmp._head);}void push_back(const T x){insert(x, end());}void push_front(const T x){insert(x, begin());}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(const T x, iterator pos){Node* cur pos.node;Node* pre cur-_pre;Node* newnode new Node(x);newnode-_next cur;cur-_pre newnode;newnode-_pre pre;pre-_next newnode;return newnode;//类型转化}iterator erase(iterator pos){assert(pos ! end());Node* cur pos.node;Node* next cur-_next;cur-_next-_pre cur-_pre;cur-_pre-_next cur-_next;delete(cur);return next;//类型转化}private:Node* _head nullptr;};
}
三、vector的实现
思路本质和数据结构中的动态数组一样只是用C的语法实现的不同点在迭代器
namespace zxws
{template class Tclass vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}const_iterator begin() const{return _start;}iterator end(){return _finish;}const_iterator end() const{return _finish;}//,--,,!,*,-没必要写因为vector迭代器底层是指针是内置类型能够自己实现--比较大小等操作typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}vector(){}vector(const vector tmp){if (tmp.size()){_finish _start new T[tmp.capacity()];for (auto x : tmp)*(_finish) x;_end_of_storage _start tmp.capacity();}}void swap(vector tmp){std::swap(_start, tmp._start);std::swap(_finish, tmp._finish);std::swap(_end_of_storage, tmp._end_of_storage);}vector operator(vector tmp){swap(tmp);return *this;}~vector(){delete[] _start;_start nullptr;_finish nullptr;_end_of_storage nullptr;}T operator[](size_t pos){assert(pos size());return _start[pos];}const T operator[](size_t pos) const{assert(pos size());return _start[pos];}void push_back(const T x){if (_finish _end_of_storage){reserve(capacity() 0 ? 4 : capacity() * 2);}*_finish x;_finish;}void pop_back(){assert(size() 0);--_finish;}void resize(size_t n, const T x T()){if (nsize()){reserve(n);for (int i size(); i n; i)_start[i] x;}_finish _start n;}void reserve(size_t n){if (capacity() n){size_t sz size();T* tmp new T[n];for (size_t i 0; i sz; i)tmp[i] _start[i];delete[] _start;_start tmp;_finish _start sz;_end_of_storage _start n;}}iterator insert(iterator pos,const T x){assert(pos_startpos_finish);if (_finish _end_of_storage){size_t len pos - _start;reserve(capacity() 0 ? 4 : capacity() * 2);pos _start len;}iterator it _finish;while (it pos){*it *(it - 1);it--;}_finish;*pos x;return pos;}iterator erase(iterator pos){assert(pos _start pos _finish);iterator cur pos;while (cur _finish - 1){*cur *(cur 1);cur;}--_finish;return pos;}size_t size(){return _finish - _start;}size_t capacity(){return _end_of_storage - _start;}private:T* _start nullptr;T* _finish nullptr;T* _end_of_storage nullptr;};
}
