一、list簡介及用法
1. list簡介
list是可以在常數范圍內任意位置進行插入、刪除、修改操作的有順序性的容器，而且支持雙向迭代，其底層是雙鏈表結構，邏輯上連續但物理空間上不連續，只能通過指針來進行元素訪問，無法使用下標隨機訪問。在任意位置的增刪查改的實現上，list效率比vector高；在快排中，因為要取中的原因，vector支持下標隨機訪問，而list只能從開頭或者尾部逐步迭代到對應位置，而且還需要額外的空間開銷來存儲節點的信息，這使得list的排序效率比vector要低。
2. 重要接口及使用
構造函數：
迭代器iterator
capacity
元素訪問
增刪查改
注意：在vector中進行增刪操作會面臨迭代器失效的風險，而在list中增加元素操作不會造成迭代器失效問題，只有刪除操作會影響指向被刪除元素的迭代器，并且其它的迭代器不會被影響。我們可以通過接收erase函數返回值的辦法使迭代器仍然有效。
二、模擬實現
list的模擬實現有幾個要點：
- 需要模擬出雙鏈表的節點，所以我們需要構建節點結構體，這個結構體要包含節點的元素，指向前一個和后一個節點的該結構體的指針；
- 我們需要構建list的迭代器模板，這個迭代器要有非const及const類型，所以我們要用到模板，模板要有元素類型自定義，元素的const和非const的引用和指針，下面的代碼中可以看到T代表元素類型，Ref代表元素引用，Ptr代表指向元素的指針；
- 開始構建list類，其成員變量要包含哨兵位節點和代表鏈表內元素個數的size，成員函數則是實現list功能的重要接口。
list的模擬實現如下：
#pragma once
#include<iostream>
#include<list>
#include<vector>
#include<algorithm>
#include<assert.h>
#include"my_reverse_iterator.h"using namespace std;// 注意：因為物理上結構的差異，list的迭代器與vector的不一樣，需要封裝成一個結構體并且重載引用等運算符
// 通過迭代器封裝來改變迭代器的行為
// 單參數類型構造函數支持隱式類型轉換
// 迭代器結構體內部不能處理節點的創建和釋放template<class T>
struct _list_node
{typedef struct _list_node<T> list_node;list_node* _prev;list_node* _next;T _val;_list_node(const T& val = T()):_prev(nullptr),_next(nullptr),_val(val){}};template<class T, class Ref, class Ptr > //T代表數據類型，Ref用于區分const與非const迭代器，Ptr用于箭頭運算符重載返回_val
struct _list_iterator
{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self; //self代表iterator自身node* _node;_list_iterator(node* new_node):_node(new_node){}Ref operator*(){return _node->_val;}bool operator==(const self& it){return (_node == it._node);}bool operator!=(const self& it) const{return (_node != it._node);}self operator++(int) //這里不能加引用，因為返回的是temp，{self temp(*this); //采用了拷貝構造函數_node = _node->_next;return temp;}self& operator++(){_node = _node->_next;return *this;}self operator--(int) //這里不能加引用，因為返回的是temp，{self temp(*this); //采用了拷貝構造函數_node = _node->_prev;return temp;}self& operator--(){_node = _node->_prev;return *this;}Ptr operator->() //注意：這里經過特殊處理（C++標準）it->_val即可獲得值，不用it->->_val//(正常情況下返回指針得再經過解引用才能得到值){return &_node->_val; //返回地址}};template<class T>
class my_list
{
public:typedef _list_node<T> node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, T*> const_iterator;typedef my_reverse_iterator<iterator, T&, T*> reverse_iterator;typedef my_reverse_iterator<const_iterator, T&, T*> const_reverse_iterator;private:node* _head;size_t _size;public:void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;_size = 0;}my_list(){empty_init();}void clear() //刪除鏈表除哨兵位外所有元素{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~my_list(){clear();delete _head;_head = nullptr;}my_list(const my_list<T>& list) //形參必須是引用才是拷貝構造函數{empty_init();for (auto& e : list) //節省棧幀空間{push_back(e);}}void swap(my_list<T>& list){std::swap(_head, list._head);std::swap(_size, list._size);}my_list<T>& operator=(my_list<T> list){swap(list);return *this;}iterator insert(iterator pos, const T& val) //默認在pos位置前插入數據{node* new_node = new node(val);node* prev = (pos._node)->_prev;new_node->_next = pos._node;new_node->_prev = prev;(pos._node)->_prev = new_node;prev->_next = new_node;_size++;return --pos; //這里return new_node; 也可以}void push_back(const T& val){//node* new_node = new node(val); //使用了默認構造函數(系統生成，無參，全缺省)//new_node->_next = _head; //使用了賦值運算符重載//new_node->_prev = _head->_prev;//_head->_prev->_next = new_node;//_head->_prev = new_node;insert(end(), val);}void push_front(const T& val){insert(begin(), val);}iterator erase(iterator pos) //返回刪除元素的后一個元素的位置{assert(pos != end()); //注意：這里要檢查鏈表內是否只有哨兵位，不然會出問題！！！node* next = (pos._node)->_next;node* prev = (pos._node)->_prev;next->_prev = prev;prev->_next = next;//iterator temp = ++pos; //注意：pos也改變了！！！delete pos._node;pos = nullptr;_size--;return next; //函數返回值是iterator類型，為什么這里可以返回node*類型？//因為這里隱式調用了iterator的構造函數，即iterator(next)！！！//如果不希望被隱式類型轉換，那么就在構造函數前用explicit修飾//return temp;}void pop_back(){iterator temp = --end();erase(temp);}void pop_front(){erase(begin());}size_t size(){return _size;}iterator begin(){//return _head->_next; //注意，返回值的類型是iterator，用node*返回是錯誤的！return iterator(_head->_next); //采用迭代器的構造函數來返回}iterator end(){return iterator(_head);}const_iterator begin() const{//return _head->_next; //注意，返回值的類型是iterator，用node*返回是錯誤的！return const_iterator(_head->_next); //采用迭代器的構造函數來返回}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();}void print(){for (auto e : *this){cout << e << " ";}cout << endl;}
};
我們知道，list支持反向迭代，所以我們也需要模擬實現反向迭代器，以下是實現反向迭代器的一些要點：
- 構建反向迭代器只需復用正向迭代器即可，正向迭代器自加那么反向迭代器就自減；
- 在設計中，反向迭代器是正向迭代器的鏡像，rbegin指向end，rend指向begin，所以在反向迭代器解引用操作符重載中，需要讓指針自減再解引用；
- 同樣地，反向迭代器模擬實現也需要用到模板，模板要實現可以自定義是哪種迭代器(vector or list?)，const還是非const類型。類的成員變量僅有iterator _it。
如下是反向迭代器的模擬實現：
#pragma once
#include"my_list.h"template<class iterator, class ref, class ptr> //用普通迭代器來做反向迭代器，ref為類型引用，ptr是指針
class my_reverse_iterator
{
public:iterator _it;typedef my_reverse_iterator<iterator, ref, ptr> self;my_reverse_iterator(iterator it):_it(it){}ref operator*(){self temp = *this;return *(--temp._it);}self& operator++() //前置++{_it--;return *this;}self operator++(int) //后置++{iterator temp = _it;_it--;return temp;}self& operator--(){_it++;return *this;}self operator--(int){iterator temp = _it;_it++;return temp;}ptr operator->(){return &(operator*()); //直接返回解引用后內容的地址即可}bool operator!=(const self& it) const{return (_it != it._it);}
};
三、與vector對比
四、小結
本文一開始簡要介紹了list的定義和重要接口，接著進行list的模擬實現，在模擬實現內容中列出了實現的數個要點，這些要點是關于list和反向迭代器的構建思路的，最后則是總結了list和vector的不同點，使讀者可以根據需求來選擇容器。
如有錯誤，請批評指正，謝謝。
)
