前言：

?C++中的List容器是標準模板庫（STL）中的一種序列容器，它實現了雙向鏈表的功能。與數組（如vector）和單向鏈表相比，List容器提供了更加靈活的元素插入和刪除操作，特別是在容器中間位置進行這些操作時。

一.list的介紹及使用

1. list的介紹

• 雙向鏈表結構： list容器使用雙向鏈表來存儲元素，每個元素（節點）都包含數據部分和兩個指針，分別指向前一個元素和后一個元素。這種結構使得在鏈表的任何位置進行插入和刪除操作都非常高效，時間復雜度為O(1)。
• 動態大小： list容器的大小可以在運行時動態改變，即可以在程序運行過程中添加或移除元素。
• 不支持隨機訪問： 與vector和array等連續內存的容器不同，list不支持隨機訪問迭代器，不能直接通過索引獲取元素，而需要通過迭代器遍歷。
• 迭代器穩定性： 在list中插入或刪除元素不會導致其他迭代器失效（除了指向被刪除元素的迭代器）。這是因為它通過調整相鄰節點的指針來維護鏈表結構，而不需要移動元素或重新分配內存。

2. list的使用

list的使用參考文檔：list的文檔介紹

2.1 list的構造

構造函數	接口說明
list (size_type n, const value_type& val =value_type() )	構造的list中包含n個值為val的元素
list()	構造空的list
list (const list& x)	拷貝構造函數
list (InputIterator ?rst, InputIterator last)	用[?rst, last)區間中的元素構造list

代碼演示：

#include<list>
int main()
{list<int> l1;//構造空的l1;list<int> l2(4,100);//l2中存放4個值為100的元素list<int> l3(l2.begin(),l2.end());//用l2的[begin,end）左開右閉區間構造l3;list<int> l4(l3);//用l3拷貝構造l4// 以數組為迭代器區間構造l5int array[] = { 16,2,77,29 };list<int> l5(array, array + sizeof(array) / sizeof(int));// 列表格式初始化C++11list<int> l6{ 1,2,3,4,5 };// 用迭代器方式打印l5中的元素list<int>::iterator it = l5.begin();while (it != l5.end()){cout << *it << " ";++it;}cout << endl;// C++11范圍for的方式遍歷for (auto& e : l5)cout << e << " ";cout << endl;return 0;
}

2.2 list iterator的使用

此處，大家可暫時將迭代器理解成一個指針，該指針指向list中的某個節點。

函數聲明	接口說明
begin	返回第一個元素的迭代器
end	返回最后一個元素下一個位置的迭代器
rbegin	返回一個指向容器中最后一個元素的反向迭代器（即容器的反向起始）
rend	返回一個反向迭代器，該迭代器指向列表容器中第一個元素之前的理論元素（該元素被認為是其反向結束）。

注意：

1. begin與end為正向迭代器，對迭代器執行++操作，迭代器向后移動
2. rbegin(end)與rend(begin)為反向迭代器，對迭代器執行++操作，迭代器向前移動

代碼演示：

int main()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array + sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// list<int>::iterator it = l.begin();   // C++98中語法auto it = l.begin();                     // C++11之后推薦寫法while (it != l.end()){cout << *it << " ";++it;}cout << endl;// 使用反向迭代器逆向打印list中的元素// list<int>::reverse_iterator rit = l.rbegin();auto rit = l.rbegin();while (rit != l.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;
}

2.3 list capacity

函數聲明	接口說明
front	檢測list是否為空，是返回true，否則返回false
size	返回list中有效節點的個數

2.4 list element access

函數聲明	接口說明
front	返回list的第一個節點中值的引用
back	返回list的最后一個節點中值的引用

2.5 list modi?ers

函數聲明	接口說明
push_front	在list首元素前插入值為val的元素
pop_front	刪除list中第一個元素
push_back	在list尾部插入值為val的元素
pop_back	刪除list中最后一個元素
insert	在list position 位置中插入值為val的元素
erase	刪除list position位置的元素
swap	交換兩個list中的元素
clear	清空list中的有效元素

代碼演示：

#include<iostream>
#include<vector>
using namespace std;void PrintList(const list<int>& l)
{// 注意這里調用的是list的 begin() const，返回list的const_iterator對象for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it){cout << *it << " ";}cout << endl;
}// list插入和刪除
// push_back/pop_back/push_front/pop_front
void TestList1()
{int array[] = { 1, 2, 3 };list<int> L(array, array + sizeof(array) / sizeof(array[0]));// 在list的尾部插入4，頭部插入0L.push_back(4);L.push_front(0);PrintList(L);// 刪除list尾部節點和頭部節點L.pop_back();L.pop_front();PrintList(L);
}// insert /erase 
void TestList2()
{int array1[] = { 1, 2, 3 };list<int> L(array1, array1 + sizeof(array1) / sizeof(array1[0]));// 獲取鏈表中第二個節點auto pos = ++L.begin();cout << *pos << endl;// 在pos前插入值為4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5個值為5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)區間中的元素vector<int> v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 刪除pos位置上的元素L.erase(pos);PrintList(L);// 刪除list中[begin, end)區間中的元素，即刪除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}// resize/swap/clear
void TestList3()
{// 用數組來構造listint array1[] = { 1, 2, 3 };list<int> l1(array1, array1 + sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交換l1和l2中的元素list<int> l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 將l2中的元素清空l2.clear();cout << l2.size() << endl;
}int main()
{TestList1();TestList2();TestList3();return 0;
}

運行結果：

2.6 list的迭代器失效

?前面已經說過了，此處可以將迭代器理解為類似于指針的東西，迭代器失效即迭代器指向的節點失效了，即該節點被刪除了。因為list的底層結構為帶頭結點的雙向循環鏈表，因此在list進行插入操作時不會導致迭代器失效，只有刪除時才會失效，并且失效的是被刪除節點的迭代器，其他迭代器不會受到影響。

二.list的模擬實現

1. 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){}
};

2. list的成員變量

template<class T>
class list
{typedef list_node<T> Node;
public://成員函數
private:Node* _head; //哨兵位的頭節點
};

?沒有用訪問限定符限制的成員class默認是私有的，struct默認是公有的，如果一個類既有公有也有私有就用class，全部為公有一般用struct。這不是規定，只是個慣例。

3.list迭代器相關問題

簡單分析：
&emsp； 這里不能像以前一樣給一個結點的指針作為迭代器，如果it是typedef的節點的指針，it解引用得到的是節點，不是里面的數據，但是我們期望it解引用是里面的數據，++it我們期望走到下一個節點去，而list中++走不到下一個數據，因為數組的空間是連續的，++可以走到下一個數據。但是鏈表達不到這樣的目的。所以原身指針已經無法滿足這樣的行為，怎么辦呢？這時候我們的類就登場了
?用類封裝一下節點的指針，然后重載運算符，模擬指針。
例如：

reference operator*()const
{return (*node).data;
}
self& opertor++()
{node = (link_type)((*node).next);return *this;
}

3.1 普通迭代器

template<class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*() //用引用返回可以讀數據也可以修改數據{return _node->_data;}T* operator->(){return &_node->_data;}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};

3.2 const迭代器

const迭代器在定義的時候不能直接定義成typedef const list_iterator<T> const_iterator,const迭代器的本質是限制迭代器指向的內容不能被修改，而前面的這種寫法限制了迭代器本身不能被修改，所以迭代器就不能進行++操作。那該怎能辦呢？答案是我們可以實現一個單獨的類：

template<class T>
struct list_const_iterator
{typedef list_node<T> Node;typedef list_const_iterator<T> Self;Node* _node;list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_data; //返回這個數據的別名，但是是const別名，所以不能被修改}const T* operator->(){return &_node->_data; //我是你的指針，const指針}Self& operator++(){_node = _node->_next;return *this;}Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tmp(*this);_node = _node->_next;return tmp;}Self operator--(int){Self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const Self& s){return _node != s._node;}
};

普通法迭代器與const迭代器的區別就是：普通迭代器可讀可寫，const迭代器只能讀
上面是我們自己實現的普通迭代器和const迭代器，用兩個類，并且這兩個類高度相似，下來就讓我們一起看一看庫里面是怎么實現的吧！

我們可以看到庫里面是寫了兩個模板，讓編譯器去生成對應的類。其本質上也是寫了兩個類，只不過是讓編譯器去生成對應的類。

迭代器不需要我們自己寫析構函數、拷貝構造函數、賦值運算符重載函數，因為這里要的是淺拷貝，例如我把一個迭代器賦值給另外一個迭代器，就是期望兩個迭代器指向同一個節點，這里用淺拷貝即可，拷貝給你我們兩個迭代器就指向同一個節點。

4. list的成員函數

4.1 list的空初始化

void empty_init() //空初始化
{_head = new Node();_head->_next = _head;_head->_prev = _head;
}

4.2 push_back

//普通版本
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版本insert(end(),x);

4.3 構造函數

list_node(const T& x = T()):_data(x), _next(nullptr), _prev(nullptr)
{}

4.4 insert

iterator insert(iterator position; const T& val)
{Node* cur = pos._node;Node* newnode = new Node(val);Node* prev = cur->_prev;//prev newnode curprev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);
}

4.4 erase

iterator erase(iterator pos)
{assert(pos != end());Node* del = pos._node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;return iterator(next);
}

4.5 push_front

void push_front(const T& x)
{insert(begin(), x);
}

4.6 pop_front

void pop_front()
{erase(begin());
}

4.7 pop_back

void pop_back()
{erase(--end());
}

4.8 clear

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

4.8 析構函數

~list()
{clear();delete _head;_head = nullptr;
}

4.9 swap

void swap(list<T>& tmp)
{std::swap(_head, tmp._head);//交換哨兵位的頭節點
}

4.10 賦值運算符重載

//現代寫法
//lt2=lt3
//list<T>& operator=(list<T> lt)
list& operator=(list lt) //不加模板參數
{swap(lt);//交換就是交換哨兵位的頭節點return *this;
}//lt3傳給lt去調用拷貝構造，所以lt就和lt3有一樣大的空間一樣大的值，lt2很想要，也就是/this想要，lt2之前的數據不想要了，交換給lt,此時lt2就和lt3有一樣大的空間一樣大的值，
//lt出了作用域就被銷毀了

構造函數和賦值運算符重載函數的形參和返回值類型可以只寫類名 list，不需要寫模板參數，這種寫法在類里面可以不加，只能在類里面可以這樣寫，類外面是不行的，一般情況下加上好一點。

---

最后想說：

本章我們STL的List就介紹到這里，下期我將介紹關于stack和queue的有關知識，如果這篇文章對你有幫助，記得點贊，評論+收藏 ，最后別忘了關注作者，作者將帶領你探索更多關于C++方面的問題。