一、list的介紹及使用

• list是可以在常數范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
• list的底層是雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節點中，在節點中通過指針指向其前一個元素和后一個元素。
• list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡單高效。
• 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進行插入、移除元素的執行效率更好。
• 與其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的隨機訪問，比如：要訪問list的第6個元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時間開銷；list還需要一些額外的空間，以保存每個節點的相關聯信息(對于存儲類型較小元素的大list來說這可能是一個重要的因素)

list文檔

list是雙向帶頭鏈表

注意：

在閱讀list文檔時會發現list有自己sort函數

因為list的迭代器屬于雙向迭代器，而std算法庫里的sort是使用隨機迭代器的，所以list不適合用std算法庫里的sort。但是list的sort底層是歸并排序效率比不過算法庫里的sort，如果遇到少量數據可以使用list的sort，遇到大量數據可以將list的數據放到vector中使用std算法庫的sort排序。

類似于長方形的性質可以用在正方形上，反之不行。

二、list的模擬實現

list的模擬實現重點在于list的迭代器實現，list的迭代器是個自定義類型

list的迭代器使用了三個模板參數

namespace List
{template<class T>struct list_node{list_node* _next;list_node* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};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* node):_node(node){}Ref operator*(){return _node->_val;}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 it) const{return _node == it._node;}bool operator!=(const self it) const{return _node != it._node;}Ptr operator->(){return &_node->_val;}};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;list():_size(0){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(size_t n, const T& val = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;while (n--) {push_back(val);}}list(const list<T>& lt):_size(0){_head = new Node;_head->_next = _head;_head->_prev = _head;for (auto e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}const_iterator cbegin() const{return _head->_next;}const_iterator cend() const{return _head;}iterator erase(iterator pos){assert(pos != _head);Node* prev = pos._node->_prev;Node* next = pos._node->_next;prev->_next = next;next->_prev = prev;_size--;delete pos._node;return next;}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = pos._node->_prev;Node* NewNode = new Node(x);cur->_prev = NewNode;prev->_next = NewNode;NewNode->_next = cur;NewNode->_prev = prev;NewNode->_val = x;_size++;return NewNode;}void push_back(const T& x){ //Node* tail = new Node;//tail->_val = x;//_head->_prev->_next = tail;//tail->_prev = _head->_prev;//_head->_prev = tail;//tail->_next = _head;//_size++;insert(end(), x);}void pop_back(){erase(_head->_prev);}void push_front(const T& x){insert(_head->_next, x);}void pop_front(){erase(_head->_next);}size_t size(){return _size;}void clear(){for (size_t i = _size; i > 0; --i){pop_back();}_size = 0;}void swap(list& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}private:Node* _head;size_t _size;};}

單參數的構造函數支持隱式類型的轉化

->運算符重載? 可以用于訪問結構體成員變量的成員變量

嚴格來說，it->->_a1 這樣寫才符合語法要求；因為運算符重載要求可讀性，所以編譯器特殊處理，省略了一個->。

注意：

類模板在類里面寫時，既可以寫類名也可以寫類型