list的作用

list是c++的stl庫提供的鏈表容器，鏈表作為我們熟知的數據結構之一，其與順序表相比，在任意位置插入刪除方面具有絕對的優勢，但在隨機讀取方面不如順序表，兩者屬于互補關系，stl中的list底層是用雙向鏈表實現的，以實現反向迭代器的反向讀取，stl中還有forward_list，它是由單向鏈表實現的。

list的接口

構造函數

//默認構造
explicit list (const allocator_type& alloc = allocator_type());
//指定鏈表初始化大小和鏈表初始化的值
explicit list (size_type n, const value_type& val = value_type(),const allocator_type& alloc = allocator_type());
//使用迭代器進行構造           
template <class InputIterator>list (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
//拷貝構造
list (const list& x);

四種構造方式都較為常用

賦值運算符重載

list& operator= (const list& x);

重載了來鏈表復制，代碼更加易讀。

迭代器相關

      iterator begin();
const_iterator begin() const;iterator end();
const_iterator end() const;reverse_iterator rbegin();
const_reverse_iterator rbegin() const;reverse_iterator rend();
const_reverse_iterator rend() const;const_iterator cbegin() const noexcept;const_iterator cend() const noexcept;const_reverse_iterator crbegin() const noexcept;const_reverse_iterator crend() const noexcept;

由于鏈表是非連續性容器，所以迭代器還是很實用的。

size

size_type size() const;

返回鏈表尺寸。

empty

bool empty() const;

鏈表判空。

front

      reference front();
const_reference front() const;

返回對鏈表第一個元素的引用。

back

      reference back();
const_reference back() const;

返回對鏈表最后一個元素的引用。

assign

template <class InputIterator>void assign (InputIterator first, InputIterator last);//迭代器初始化
void assign (size_type n, const value_type& val);//指定初始化大小和內容

重新初始化鏈表。

push_front

void push_front (const value_type& val);

頭插。

pop_front

void pop_front();

頭刪。

push_back

void push_back (const value_type& val);

尾插。

pop_back

void pop_back();

尾刪。

insert

//插入一個
iterator insert (iterator position, const value_type& val);//插入一段
void insert (iterator position, size_type n, const value_type& val);//插入迭代器表示的一段
template <class InputIterator>void insert (iterator position, InputIterator first, InputIterator last);

插入函數，鏈表的插入函數效率很高。

erase

iterator erase (iterator position);//刪除一個
iterator erase (iterator first, iterator last);//刪除一段

刪除函數，鏈表的刪除函數效也很高。

swap

void swap (list& x);

交換函數，交換兩個鏈表。

resize

void resize (size_type n, value_type val = value_type());

重新指定鏈表的大小，如果n大于鏈表此時的size，就擴充到n大小，然后將擴充后的節點的值初始化成指定內容（缺省為0）；如果n小于鏈表此時的size，就減小到n大小，然后刪除并銷毀超出的部分。

clear

void clear();

清空鏈表。

splice

void splice (iterator position, list& x);//轉移一整個
void splice (iterator position, list& x, iterator i);//轉移指定位置的元素
void splice (iterator position, list& x, iterator first, iterator last);//轉移指定的一段。

將鏈表中的元素轉移到另一個鏈表中，position是插入位置。

remove

void remove (const value_type& val);

刪除鏈表中所有與給定值相等的元素。

remove_if

template <class Predicate>void remove_if (Predicate pred);

刪除鏈表中所有Predicate pred返回true的元素的函數，這允許我們刪除滿足特定復雜條件的元素。

unique

void unique();
template <class BinaryPredicate>void unique (BinaryPredicate binary_pred);

這個函數可以讓鏈表中等于特定值或滿足特定條件的元素唯一，與remove和remove_if函數類似，只不過他們是全部刪除，unique是要留一個。

merge

  void merge (list& x);
template <class Compare>void merge (list& x, Compare comp);

將兩個已經滿足一定順序的鏈表合并為一個滿足這個順序的新鏈表，默認順序是升序，也就是說合并兩個升序鏈表時可以用第一個函數，其他的都需要寫仿函數。

sort

void sort();默認升序
template <class Compare>void sort (Compare comp);//自定義

list自己的排序函數。

reverse

void reverse();

list自己的反轉函數。

關系運算符重載（非成員函數）

template <class T, class Alloc>bool operator== (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator!= (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator<  (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator<= (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator>  (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);
template <class T, class Alloc>bool operator>= (const list<T,Alloc>& lhs, const list<T,Alloc>& rhs);

list的模擬實現

#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>using namespace std;namespace jiunian
{// List的節點類template<class T>struct ListNode{ListNode(const T& val = T()) :_pPrev(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPrev;ListNode<T>* _pNext;T _val;};//List的迭代器類template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &(_pNode->_val);}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self& operator++(int){Self tmp(*this);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPrev;return *this;}Self& operator--(int){Self tmp(*this);_pNode = _pNode->_pPrev;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;};//list類template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;public:///// List的構造 list(){CreateHead();}list(int n, const T& value = T()){CreateHead();while(n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*(first++));}}list(const list<T>& l){CreateHead();for (auto& e : l){push_back(e);}}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin()const{return _pHead->_pNext;}const_iterator end()const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _pHead == _pHead->_pNext;//size == 0;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPrev->_val;}const T& back()const{return _pHead->_pPrev->_val;}// List Modifyvoid push_back(const T& val){ insert(end(), val); }void pop_back() {erase(--end()); }void push_front(const T& val){insert(begin(), val); }void pop_front() {erase(begin()); }// 在pos位置前插入值為val的節點iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);newnode->_pPrev = pos._pNode->_pPrev;newnode->_pNext = pos._pNode;pos._pNode->_pPrev->_pNext = newnode;pos._pNode->_pPrev = newnode;++_size;return newnode;}//iterator insert(iterator pos, const T& x)//{//    Node* cur = pos._pNode;//    Node* prev = cur->_pPrev;//    Node* newnode = new Node(x);//    prev->_pNext = newnode;//    newnode->_pNext = cur;//    cur->_pPrev = newnode;//    newnode->_pPrev = prev;//    //++_size;//    return newnode;//}// 刪除pos位置的節點，返回該節點的下一個位置iterator erase(iterator pos){pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;iterator ret = pos._pNode->_pNext;delete pos._pNode;--_size;return ret;}void clear(){iterator cur = begin();while (cur != end()){cur = erase(cur);}_size = 0;}void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPrev = _pHead;}PNode _pHead;size_t _size = 0;};
}

對于list這種存儲不連續的容器，其迭代器的實現就不能像string和vector一樣直接對指針進行封裝，雖然對于迭代器來說，其底層的實現離不開指針，但其還是有別于string和vector的。

結點類

在對于迭代器進行說明之前，我還是要先介紹一下鏈表的結點類，結點是組成鏈表的基本單位，是需要單獨封裝的。

// List的節點類
template<class T>
struct ListNode
{ListNode(const T& val = T()) :_pPrev(nullptr),_pNext(nullptr),_val(val){}ListNode<T>* _pPrev;ListNode<T>* _pNext;T _val;
};

由于我們創建的是一個雙向帶頭鏈表，所以一個節點要給一個指針指向前一個結點，也要給一個指針指向后一個節點，再者因為ListNode中的成員之后都要被list類頻繁使用，所以我們直接將類定義成struct，因為struct的元素在不加訪問限定符的情況下都是默認共有的（兼容c語言）。最后我們為這個類寫上構造函數就完成了。

迭代器類

//List的迭代器類
template<class T, class Ref, class Ptr>
struct ListIterator
{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}Ref operator*(){return _pNode->_val;}Ptr operator->(){return &(_pNode->_val);}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self tmp(*this);_pNode = _pNode->_pNext;return tmp;}Self& operator--(){_pNode = _pNode->_pPrev;return *this;}Self& operator--(int){Self tmp(*this);_pNode = _pNode->_pPrev;return tmp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return _pNode == l._pNode;}PNode _pNode;
};

之后就是迭代器的說明了，在有了對于string和vector的實現經驗之后，其實對于list這個類本身的實現已經很輕松了，因為stl庫中的容器之間是有很強的共性的，實現的思路大差不差，但對于list的迭代器還是有所不同的，因為list要實現不連續內存容器的隨機訪問。首先我們看向這個類所給的模板參數，有三個，這其實是一個令人疑惑的點，因為通常來說我們只需要給一個模板參數說明迭代器指向的節點中的val是什么類型不就行了，但這里所給的參數有足足三個，這里直接理解是理解不同的，我們不妨先往下看。

typedef的妙用

typedef ListNode<T>* PNode;
typedef ListIterator<T, Ref, Ptr> Self;

這兩句代碼我想要單獨拎出來講，如果我們有一些閱讀源碼的經歷，我們會發現寫源碼的那些大佬會經常性的使用typedef，一層套一層，看起來像是脫褲子放屁，但其實不然，比如這里，假如我們不使用typedef，那會阻礙我們書寫代碼嗎？答案是不會的，typedef無非只是個替換，不使用無非只是麻煩一點，多寫幾個模板參數實例化的事（其實省事這一點就足以成為我們使用它的理由了），但倘若我們書寫完代碼之后因為某些原因要改變ListNode或ListIterator的模板參數數量或者模板參數名就麻煩了，我們要把之前寫ListNode和ListIterator都寫一遍，如果代碼量巨大，那將是一場噩夢，但倘若我們用了typedef，不僅書寫時就省了事，書寫之后萬一要對typedef的內容進行更改也是很輕松的，只要把typedef的地方一改其他地方都會改。說到底，這樣寫本質上降低了代碼之間的關聯度（耦合度），我們作為代碼學習者，可能會從某些地方聽說過高內聚低耦合的概念，高內聚低耦合就是指盡量使一個模塊的代碼專注于完成單一任務，且模塊與模塊之間的關聯度盡可能地低。我們這里使用typedef就大大地降低了代碼之間的關聯度，這樣一處代碼的修改帶來的連鎖反應會盡可能地小，這是我們在書寫代碼時要時刻注意的。

*運算符重載

Ref operator*()
{return _pNode->_val;
}

這段代碼是對于*的運算符重載這不難看出，但是我們看想這個函數的返回值，只是我們之前所說的三個模板參數中的第二個，我們仔細想想，倘若這里不使用模板參數，我們應該寫什么呢？當然是_val類型的引用，解引用運算符之后的變量更改會影響原指針指向的數，所以要用引用。但為什么要用模板參數呢，這時我們看向list類的這一段，

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

對于迭代器來說，不僅有普通迭代器，還有const版的，而普通迭代器和const迭代器除了*和->運算符重載不一樣之外，其他的都是一致的，所以我們通過傳三個參數的方式成功偷了一波懶，一個類干了別人兩個類干的事，剩下的事由編譯器來完成。

->運算符重載

Ptr operator->()
{return &(_pNode->_val);
}

這個函數可以訪問_val的對象成員（前提是_val得有對象成員，沒有用不到），這個函數筆者在一開始理解時非常困惑，因為筆者認為迭代器視為指向鏈表結點的指針，而->被用來在使用指針的情況下訪問對象元素，所以這個->是用來訪問系欸但元素的，也就是_val、_pPrev和_pNext，但事實上不是，這里迭代器不應該被看作為一個指向結點的指針，而應該看作為一個指向_val的指針，因為我是在實現這個類的基礎之上去理解這個迭代器的，我先入為主了，最為使用者來說，我并不清楚list類的底層如何實現，我也就不用會知道list其實有一個前置的類叫ListNode，也并不知道ListNode中有三個元素_val、_pPrev和_pNext，在使用者看來，迭代器就是指向容器元素本身，使用->訪問的就是元素這個對象本身的元素（前提是有元素）。理解了這個函數本身的作用之后，我們看向這個函數的返回值，返回值類型使用了單獨的模板參數，這在前一個解引用運算符重載中講過了，這里也是如此，

typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T*> const_iterator;

這里的Ptr指的T*（或const T*）。我們再看向返回值本身，_pNode->_val取地址，這個函數返回之后會發生什么呢，假如我們寫了以下代碼

std::cout << it->a << std::endl;

it->使用運算符重載返回了一個指針，那代碼就變成了一個指針和一個元素中間沒有運算符，這因該是會報錯的操作，但這里是會正常編譯通過的，因為c++在這里又做了特殊處理給這兩個變量中間加上了一個->，所以時候事實上來說代碼應該是這樣的

std::cout << it->->a << std::endl;//演示一下，事實上會報錯

可以看出c++為了增加代碼可讀性還是做出了很多妥協的。

++、–運算符重載

Self& operator++()
{_pNode = _pNode->_pNext;return *this;
}Self operator++(int)
{Self tmp(*this);_pNode = _pNode->_pNext;return tmp;
}Self& operator--()
{_pNode = _pNode->_pPrev;return *this;
}Self& operator--(int)
{Self tmp(*this);_pNode = _pNode->_pPrev;return tmp;
}

之后還要說明的就是迭代器的++和–的運算符重載，因為之前我們也說過，list是內存不連續的容器，所以++和–運算符都不能直接以指針++和–的形式實現，而是使用ListNode中_pPrev和_pNext指針來實現迭代，至于前置++（–）和后置++（–）的書寫區別，之前的文章也講過，因為它們是單參運算符，無法通過位置識別從而進行不同的操作，所以c++特別規定++（–）運算符重載時在參數列表多加上int的是后置++（–），沒加的是前置++（–）。

list類

template<class T>
class list
{typedef ListNode<T> Node;typedef Node* PNode;
public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;
public:///// List的構造 list(){CreateHead();}list(int n, const T& value = T()){CreateHead();while(n--){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*(first++));}}list(const list<T>& l){CreateHead();for (auto& e : l){push_back(e);}}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin()const{return _pHead->_pNext;}const_iterator end()const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _pHead == _pHead->_pNext;//size == 0;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPrev->_val;}const T& back()const{return _pHead->_pPrev->_val;}// List Modifyvoid push_back(const T& val){ insert(end(), val); }void pop_back() {erase(--end()); }void push_front(const T& val){insert(begin(), val); }void pop_front() {erase(begin()); }// 在pos位置前插入值為val的節點iterator insert(iterator pos, const T& val){Node* newnode = new Node(val);newnode->_pPrev = pos._pNode->_pPrev;newnode->_pNext = pos._pNode;pos._pNode->_pPrev->_pNext = newnode;pos._pNode->_pPrev = newnode;++_size;return newnode;}//iterator insert(iterator pos, const T& x)//{//    Node* cur = pos._pNode;//    Node* prev = cur->_pPrev;//    Node* newnode = new Node(x);//    prev->_pNext = newnode;//    newnode->_pNext = cur;//    cur->_pPrev = newnode;//    newnode->_pPrev = prev;//    //++_size;//    return newnode;//}// 刪除pos位置的節點，返回該節點的下一個位置iterator erase(iterator pos){pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;iterator ret = pos._pNode->_pNext;delete pos._pNode;--_size;return ret;}void clear(){iterator cur = begin();while (cur != end()){cur = erase(cur);}_size = 0;}void swap(list<T>& l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPrev = _pHead;}PNode _pHead;size_t _size = 0;
};

list類的實現就比較公式化了，值得一說的就幾個，下面一一講解。

CreateHead（頭節點創建）

void CreateHead()
{_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPrev = _pHead;
}

首先是CreateHead()，這個函數被用于創建頭節點，我們實現的list的底層是帶頭雙向鏈表，頭節點是必須的，這個函數在很多成員函數中都會用到，所以單獨封裝并放進private訪問限定符中限制外部訪問。函數實現思路也很簡單，new一個節點出來，指針首尾相連就行。

insert

iterator insert(iterator pos, const T& val)
{Node* newnode = new Node(val);newnode->_pPrev = pos._pNode->_pPrev;newnode->_pNext = pos._pNode;pos._pNode->_pPrev->_pNext = newnode;pos._pNode->_pPrev = newnode;++_size;return newnode;
}

之后是insert函數，insert函數可以被反復復用到一些成員函數之中，十分方便。實現思路就是創建一個節點插入pos迭代器指向的節點的前面，接一下指針就行，之后返回新插入的結點防止迭代器失效。

erase

iterator erase(iterator pos)
{pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;iterator ret = pos._pNode->_pNext;delete pos._pNode;--_size;return ret;
}

erase函數也可以被復用到一些成員函數之中，非常方便，實現思路就是將pos指向的結點的前一個和后一個相接之后刪除這個結點，之后返回原本pos指向的結點的下一個結點。

賦值運算符重載

list<T>& operator=(list<T> l)
{swap(l);return *this;
}

賦值運算符重載，這里我們故意不用引用，這樣傳過來的參數就是拷貝構造好的需要被賦值成的對象，直接交換，由于臨時變量的生命周期出了作用域就沒了，所以正好把之前的對象的銷毀，完美完成交換。