閱前提要：

本文主要是對list和vector的實現(xiàn)的補充，以代碼實現(xiàn)為主，注釋為輔，如果對vector，list底層實現(xiàn)感興趣的可以自行閱讀，代碼量有點大，請大家耐心查看，對理解語言很有幫助（本文的實現(xiàn)方式并不是stl標(biāo)準(zhǔn)庫中的實現(xiàn)，但大致的思路一樣）

一、反向迭代器的實現(xiàn)

實現(xiàn)思想：反向迭代器和正向迭代器的不同點只在于++，--時迭代器的移動方向不同，其他的操作基本一樣，我們可以對正向迭代器進行封裝，從而得到反向迭代器，代碼如下

namespace zxws
{// 適配器 -- 復(fù)用//這里細(xì)節(jié)關(guān)鍵在于模板參數(shù)可以傳任何一個容器的正向迭代器，//即只要該容器的正向迭代器實現(xiàn)了，那么反向迭代器也就實現(xiàn)了(這就是模板的力量)template<class Iterator, class Ref, class Ptr>struct 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;}//這個函數(shù)的實現(xiàn)和我們默認(rèn)的rbegin()和rend()的位置有關(guān)//下面的代碼實現(xiàn)是默認(rèn)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的實現(xiàn)

思路：本質(zhì)和數(shù)據(jù)結(jié)構(gòu)中的雙向循環(huán)鏈表一樣，只是用C++的語法實現(xiàn)的，不同點在迭代器

代碼如下

namespace zxws
{template<class T>struct Node {T _val;Node* _next;Node* _pre;Node(const T& x=T()):_val(x),_next(nullptr),_pre(nullptr){}};//正向迭代器的實現(xiàn)template<class T,class Ref,class Ptr>struct Iterator {typedef Node<T> 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;}};template<class T>class list{public:typedef Node<T> Node;typedef Iterator<T, T&, T*> iterator;typedef Iterator<T,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_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//對rbegin(),rend()的位置的定義//與反向迭代器中解引用運算符的重載實現(xiàn)有關(guān)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;//類型轉(zhuǎn)化}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;//類型轉(zhuǎn)化}private:Node* _head = nullptr;};
}

三、vector的實現(xiàn)

思路：本質(zhì)和數(shù)據(jù)結(jié)構(gòu)中的動態(tài)數(shù)組一樣，只是用C++的語法實現(xiàn)的，不同點在迭代器

namespace zxws
{template <class T>class 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迭代器底層是指針，是內(nèi)置類型，能夠自己實現(xiàn)++，--，比較大小等操作typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_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 (n>size()){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>=_start&&pos<=_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;};
}

?