一、list 类的模拟实现

iterator 和 const_iterator 除了下述不同外，其他代码基本一模一样：

iterator 调用 operator* / operator-> 返回 T& / T*
const_iterator 调用 operator* / operator-> 返回 const T& / const T*

为了减少代码冗余，创建一个公有的模板，并增加两个模板参数，在调用时通过传递不同的模板参数从而得到 iterator 和 const_iterator

reverse_iterator 和 const_reverse_iterator 通过封装 iterator 实现

list 类常用接口模拟实现：

//test.cpp
#include "list.h"int main()
{//starrycat::list_test5();starrycat::list_reverse_iterator_test();return 0;
}//iterator.h
#pragma oncenamespace starrycat
{template<class Iterator, class Ref, class Ptr>class __list_reverse_iterator{typedef __list_reverse_iterator<Iterator, Ref, Ptr> self;public:__list_reverse_iterator<Iterator, Ref, Ptr>() {}__list_reverse_iterator<Iterator, Ref, Ptr>(Iterator iter) : _cur(iter) {}//rbegin() 底层返回 end()，rend() 底层返回 begin()//因此在访问元素时，需要访问当前迭代器的前一个位置 Ref operator*(){Iterator tmp = _cur;return *--tmp;}Ptr operator->(){Iterator tmp = _cur;return (--tmp).operator->();}self& operator++(){--_cur;return *this;}self operator++(int){Iterator tmp = _cur;--_cur;return tmp;}self& operator--(){++_cur;return *this;}self operator--(int){Iterator tmp = _cur;++_cur;return tmp;}bool operator==(const self& s) { _cur == s._cur; }bool operator!=(const self& s) { _cur != s._cur; }private:Iterator _cur;};
}//list.h
#pragma once#include "iterator.h"
#include <iostream>
#include <assert.h>
#include <algorithm>using std::cout;
using std::endl;namespace starrycat
{//带头双向链表结点template<class T>struct __list_node{__list_node<T>* _prev;__list_node<T>* _next;T _data;};//迭代器template<class T, class Ref, class Ptr>struct __list_iterator{typedef __list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;//成员node* _node;//默认构造函数__list_iterator<T, Ref, Ptr>(){}//构造函数__list_iterator<T, Ref, Ptr>(node* node): _node(node){}//解引用重载Ref operator*(){return _node->_data;}//->重载都需要这样玩Ptr operator->(){return &(_node->_data);}//前置++重载self& operator++(){_node = _node->_next;return *this;}//后置++重载self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//前置--重载self& operator--(){_node = _node->_prev;return *this;}//后置--重载self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator==(const self& s) const{return _node == s._node;}bool operator!=(const self& s) const{return _node != s._node;}};//带头双向链表template<class T>class list{public:typedef __list_node<T> node;typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef __list_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;void empty_Init(){_head = new node;_head->_next = _head;_head->_prev = _head;}//默认构造函数list(){empty_Init();}//迭代器区间构造template<class InputIterator>list(InputIterator first, InputIterator last){empty_Init();while (first != last){push_back(*first);++first;}}void swap(list<T>& lt){std::swap(_head, lt._head);}list(const list<T>& lt){empty_Init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}list<T>& operator=(list<T> lt){swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}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);}reverse_iterator rbegin(){return end();}const_reverse_iterator rbegin() const{return end();}reverse_iterator rend(){return begin();}const_reverse_iterator rend() const{return begin();}bool empty() const{return _head->_next == _head;}size_t size() const{size_t result = 0;node* cur = _head->_next;while (cur != _head){++result;cur = cur->_next;}return result;}T& front(){return _head->_next->_data;}const T& front() const{return _head->_next->_data;}T& back(){return _head->_prev->_data;}const T& back() const{return _head->_prev->_data;}void push_front(const T& x){//node* _head_next = _head->_next;//node* new_node = new node;//new_node->_data = x;//_head->_next = new_node;//new_node->_prev = _head;//new_node->_next = _head_next;//_head_next->_prev = new_node;insert(begin(), x);}void pop_front(){//assert(!empty());//node* del = _head->_next;//node* _head_new_next = del->_next;//_head->_next = _head_new_next;//_head_new_next->_prev = _head;//delete del;erase(begin());}void push_back(const T& x){//node* tail = _head->_prev;//node* new_node = new node;//new_node->_data = x;//tail->_next = new_node;//new_node->_prev = tail;//new_node->_next = _head;//_head->_prev = new_node;insert(end(), x);}void pop_back(){//assert(!empty());//node* del = _head->_prev;//node* new_tail = del->_prev;//new_tail->_next = _head;//_head->_prev = new_tail;//delete del;erase(--end());}iterator insert(iterator pos, const T& x){node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node;new_node->_data = x;prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;return pos;}iterator erase(iterator pos){node* del = pos._node;node* prev = del->_prev;node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;return next;}private:node* _head;};void Print1(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){//(*it) *= 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;}void list_test1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::iterator it = lt.begin();while (it != lt.end()){(*it) *= 10;cout << *it << " ";++it;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;Print1(lt);}struct A{int _a1;int _a2;//构造函数A(int a1 = 0, int a2 = 0): _a1(a1), _a2(a2){}};void Print2(const list<A>& lt){list<A>::const_iterator it = lt.begin();while (it != lt.end()){//it->_a1 *= 2;//it->_a2 *= 2;cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;}void list_test2(){list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));list<A>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " " << (*it)._a2 << endl;//-> 都需要这样玩//it->_a1 编译器默认解释为 it->->_a1 <==> it.operator->()->_a1;it->_a1 *= 10;it->_a2 *= 10;cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;Print2(lt);}void list_test3(){list<int> lt;cout << "empty:" << lt.empty() << endl;cout << "size:" << lt.size() << endl;lt.push_front(1);lt.push_front(2);lt.push_front(3);lt.push_front(4);for (auto e : lt){cout << e << " ";}cout << endl;cout << "empty:" << lt.empty() << endl;cout << "size:" << lt.size() << endl;lt.pop_front();lt.pop_front();//lt.pop_front();//lt.pop_front();//lt.pop_front();for (auto e : lt){cout << e << " ";}cout << endl;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.pop_back();lt.pop_back();//lt.pop_back();//lt.pop_back();//lt.pop_back();//lt.pop_back();for (auto e : lt){cout << e << " ";}cout << endl;lt.front() *= 10;lt.back() *= 100;for (auto e : lt){cout << e << " ";}cout << endl;}void list_test4(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;//list<int>::iterator pos = std::find(lt.begin(), lt.end(), 2); errlt.insert(++lt.begin(), 20);for (auto e : lt){cout << e << " ";}cout << endl;lt.erase(++lt.begin());for (auto e : lt){cout << e << " ";}cout << endl;}void list_test5(){list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt2(lt1.begin(), lt1.end());for (auto e : lt1){cout << e << " ";}cout << endl;list<int> lt3(lt2);for (auto e : lt3){cout << e << " ";}cout << endl;lt3.clear();for (auto e : lt3){cout << e << " ";}cout << endl;lt3 = lt2;for (auto e : lt2){cout << e << " ";}cout << endl;for (auto e : lt3){cout << e << " ";}cout << endl;}void Print3(const list<int>& lt){list<int>::const_reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){//*rit *= 2;cout << *rit << " ";++rit;}cout << endl;}void Print4(const list<A>& lt){list<A>::const_reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){//rit->_a1 *= 10;//rit->_a2 *= 10;cout << rit->_a1 << " " << rit->_a2 << endl;++rit;}cout << endl;}void list_reverse_iterator_test(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){*rit *= 2;cout << *rit << " ";++rit;}cout << endl;Print3(lt);list<A> ltA;ltA.push_back(A(1, 1));ltA.push_back(A(2, 2));ltA.push_back(A(3, 3));ltA.push_back(A(4, 4));list<A>::reverse_iterator ritA = ltA.rbegin();while (ritA != ltA.rend()){ritA->_a1 *= 10;ritA->_a2 *= 10;cout << ritA->_a1 << " " << ritA->_a2 << endl;++ritA;}cout << endl;Print4(ltA);}
}