目錄
一、實現框架
二、list_node節點類的模擬實現
節點構造函數
三、list_iterator迭代器的模擬實現
迭代器類的模板參數說明
構造函數
*運算符重載
++運算符的重載
--運算符的重載
==運算符的重載
!=運算符的重載
list的模擬實現
默認成員函數
構造函數
拷貝構造函數
賦值運算符重載函數
析構函數
迭代器相關函數
begin和end
插入、刪除函數
push_back
insert
erase
push_front
pop_back
pop_front
size
swap
clear
一、實現框架
namespace lzg
{//模擬實現list當中的結點類template<class T>struct list_node{//成員變量T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T x& = T()):_data(x),_next(nullptr),_prev(nullptr){}};//模擬實現list迭代器//這里寫的一種是模板，最后由編譯器實例化對應的類型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*();Ptr operator->();Self& operator++();Self& operator--();Self operator++(int);Self operator--(int);bool operator!=(const Self& s);bool operator==(const Self& s);};template<class T>class list{typedef list_node<T> Node;public://迭代器有兩種(const和非const)，通過傳遞的參數(有無const)來實例化對應迭代器typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//初始化空的帶哨兵位的雙向循環鏈表void list_empty();list();//默認構造函數(調用list_empty();)list(const list<T>& lt);//拷貝構造函數list(size_t n, const T& val = T());//初始化n個值為val的鏈表list<T>& operator=(list<T> lt); //賦值重載~list(); //析構//迭代器相關函數iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;//鏈表的操作函數void push_front(const T& x);void pop_front();void pop_back();void push_back(const T& x);iterator insert(iterator pos, const T& val);iterator erase(iterator pos);void clear();void swap(list<T>& tmp);size_t size();private:Node* _head;size_t _size;};}二、list_node節點類的模擬實現
list的底層是帶頭雙向循環鏈表
因此，我們若要實現list，則首先需要實現一個結點類。而一個結點需要存儲的信息有：數據、前一個結點的地址、后一個結點的地址，于是該結點類的成員變量也就出來了（數據、前驅指針、后繼指針）
而對于該結點類的成員函數來說，我們只需實現一個構造函數即可。因為該結點類只需要根據數據來構造一個結點即可，而結點的釋放則由list的析構函數來完成。
節點構造函數
list_node(const T x& = T()):_data(x),_next(nullptr),_prev(nullptr)
{}傳值時利用匿名構造來實現，這樣節點就能存儲任意類型的值
三、list_iterator迭代器的模擬實現
在之前string和vector中模擬實現迭代器我們都是在類里面完成的，并沒有單獨拎出來封裝成一個類，這是因為在前兩者中，物理地址空間是連續的可以完成自增自減，但鏈表不一樣，兩個節點的地址不是連續的不能通過+1來實現從一個節點到另一個節點的操作。
你可能還會問，那么為什么不在list里面封裝形成一個內部類，這也是不合理的，這樣會
?降低靈活性?：難以共享迭代器實現細節（如const和非const迭代器）
增加耦合?：迭代器實現與特定容器綁定
模板特化困難?：不利于針對不同迭代器類別進行優化
迭代器類的模板參數說明
這里我們所實現的迭代器類的模板參數列表當中為什么有三個模板參數？
template<class T, class Ref, class Ptr>
我們是仿照c++底層源碼實現的，Ref是reference(引用)的縮寫，Ptr是pointer(指針)的縮寫
我們在list中typedef了兩種迭代器
typedef _list_iterator<T, T&, T*> iterator;
typedef _list_iterator<T, const T&, const T*> const_iterator;
傳遞的形參沒有加const(<T, T&, T*> )也就是對應普通迭代器( iterator;)
加上了const修飾那么就是const迭代器 (const_iterator）
可以理解我們寫的是一個迭代器模板，通過傳遞的參數不同由編譯器幫我們實例化出是普通迭代器還是const迭代器，如果不用Ref和Ptr我們就要寫兩種迭代器并且它們是高度相似的
構造函數
迭代器類實際上就是對結點指針進行了封裝，其成員變量就只有一個，那就是結點指針，其構造函數直接根據所給結點指針構造一個迭代器對象即可。
list_iterator(Node* node):_node(node)
{}*運算符重載
當我們使用解引用操作符時，是想得到該位置的數據內容。因此，我們直接返回當前結點指針所指結點的數據即可，但是這里需要使用引用返回，因為解引用后可能需要對數據進行修改。
Ref operator*()
{return _node->_data;//訪問節點中存儲的數據
}
->運算符重載
Ptr operator->()
{return &_node->_data;
}++運算符的重載
typedef list_iterator<T, Ref, Ptr> Self;
前置++
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)
{return _node == s._node;
}!=運算符的重載
可以復用==，也可以看兩個迭代器的指針指向是否不同
bool operator!=(const Self& s)
{return _node != s._node;
}四、list的模擬實現
默認成員函數
構造函數
list是一個帶頭雙向循環鏈表，在構造一個list對象時，直接申請一個頭結點，并讓其前驅指針和后繼指針都指向自己即可。
void list_empty()
{_size = 0;_head = new Node();_head->_next = _head;_head->_prev = _head;
}list()
{list_empty();
}拷貝構造函數
拷貝構造函數就是根據所給list容器，拷貝構造出一個新對象。對于拷貝構造函數，我們先調用list_empty函數把鏈表初始化為空，再通過復用push_back函數一個個尾插到新構造的容器后面即可。
//lt2(lt1)
list(const list<T>& lt)
{list_empty();for (auto& e : lt){push_back(e);//將容器lt當中的數據一個個尾插到新構造的容器后面}
}賦值運算符重載函數
對自定義類型傳值傳參要調用對應的拷貝構造函數，我們通常加上&(引用)是為了減少傳值傳參帶來的拷貝冗余，但是我們這里故意不用引用，那么lt就是lt1的拷貝，通過交換lt來實現賦值，這樣把lt1賦值給了lt2，并且我們交換的是lt(lt1的拷貝)并不會影響lt的數據，并且出函數時，臨時對象lt會自動析構
// lt2=lt1
list<T>& operator=(list<T> lt)
{ swap(lt); return *this;
}析構函數
//析構函數
~list()
{clear(); //清理容器delete _head; //釋放頭結點_head = nullptr; //頭指針置空
}
clear的實現在后面，并且clear也是復用erase函數
迭代器相關函數
begin和end
begin函數返回的是第一個有效數據的迭代器，end函數返回的是最后一個有效數據的下一個位置的迭代器。
由于返回類型是iterator (list_iterator<T,T&,T*>) 如果寫出return?_head->_next，編譯器不會自動將指針轉為自定義類類型，這里我們用迭代器的匿名構造返回地址
iterator begin()
{return iterator(_head->_next);
}iterator end()
{return iterator(_head);
}當然，還需要重載一對用于const對象的begin函數和end函數
const_iterator begin() const
{ return const_iterator(_head->_next);
}
const_iterator end() const
{return const_iterator(_head);
}
插入、刪除函數
push_back
畫圖后操作一目了然,完成insert函數后就能復用
void push_back(const T& x)
{/*Node* new_node = new Node(x);Node* tail = _head->_prev;tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;*/insert(end(), x);
}insert
iterator insert(iterator pos, const T& val)
{Node* cur = pos._node; //pos是一個類需要的是里面的_node值Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curnewnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;prev->_next = newnode;_size++;return iterator(newnode);
}erase
iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;//prev del nextprev->_next = next;next->_prev = prev;delete del;_size--;return iterator(next);
}push_front
void push_front(const T& x)
{insert(begin(), x);
}pop_back
void pop_back()
{erase(--end());
}pop_front
void pop_front()
{erase(begin());
}size
為了方便在list中我們還定義了_size來表明鏈表中插入節點的個數，并且在上面insert和erase函數中都更新了對_size的操作，所以我們直接返回就行了
size_t size()
{return _size;
}swap
交換兩個鏈表的哨兵位節點就能交換兩個鏈表
void swap(list<T>& tmp)
{swap(_head,tmp._head);swap(_size, tmp._size);
}clear
clear函數用于清空容器，我們通過遍歷的方式，逐個刪除結點，只保留頭結點即可。
void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}
--Java版)
