#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反向迭代器