#pragma once
#include<assert.h>
#include<iostream>
using namespace std;
namespace aqc
{template<class T>struct list_node{list_node* _next;list_node* _prev;T _data;list_node(const T& x=T())//加const防止权限放大，用引用减少拷贝:_next(nullptr),_prev(nullptr),_data(x){}};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(node*  tmp)//BUG--函数名报错:_node(tmp){}Ref operator*()//返回值引用或const引用，不能构成重载，不好办了//，因此传第二个模板参数，在创建迭代器时确定返回的是什么{return _node->_data;}Ptr operator->()//同上，有T*和const T*{return &(_node->_data);}self& operator++(){this->_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(_node);//显示构造_node = _node->_prev;return tmp;}bool operator!=(const self& x)const{return _node != x._node;}bool operator==(const self& x){return _node == x._node;}};template<class Iterator,class Ref,class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> self;Iterator _cur;ReverseIterator(Iterator it):_cur(it){}Ref operator*()//为了保持对称的形态，rbegin对end，rend对begin，解引用时要调整一下{Iterator tmp=_cur;--tmp;return *tmp;}Ptr operator->(){return &(_cur._node->_data);}self& operator++(){--_cur;return *this;}self operator++(int){self tmp = *this;--_cur;return tmp;}self operator--(){++_cur;return *this;}bool operator!=(const self& x)const{return _cur != x._cur;}};template<class T>class list{typedef list_node<T> node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;typedef  ReverseIterator< iterator, T&, T*> reverse_iterator;typedef  ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;iterator begin(){return iterator(_head->_next);}const_iterator begin()const//不论普通链表还是const链表都可使用const迭代器{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}template<class Iterator >list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);first++;}}void swap(list<T>& lt){std::swap(_head, lt._head);}list(list<T>& lt){empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}list<int>& operator=(list<T> lt){swap(lt);return *this;}void print(){for (auto e : *this){cout << e << " ";}cout << endl;}void clear(){iterator it = begin();while (it != end()){erase(it++);//it++最终it加一，返回it没加一时的临时变量}}~list(){clear();delete _head;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void erase(iterator pos){node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;}void insert(iterator pos, const T& x){node* prev = pos._node->_prev;node* pcur = pos._node;node* new_node = new node(x);prev->_next = new_node;new_node->_prev = prev;new_node->_next = pcur;pcur->_prev = new_node;}private:node* _head;};
}

1.list是带头双向循环链表

2.list的节点设计如上，两个指针和一个T类型数据data

3.list类的成员只有哨兵节点，没有size成员，这是gcc的设计思路，在获取size时遍历获得，这样在插入和删除时不用关心size的变化

4.最重要的是迭代器，list的迭代器不再和vector与string一样是原生指针了，而是封装了结点指针的类，但要注意的是  *迭代器  返回的不是节点的引用，而是节点数据的引用T&，迭代器->成员  访问的是节点数据T的成员，编译器会先调operator->得到节点数据的地址T*，然后再->访问成员

5.迭代器有三个模板参数，这是为了实例化出迭代器和const迭代器

6.反向迭代器适配正向迭代器得到，有三个模板参数同样是为了实例化出反向迭代器和const反向迭代器