😎【博客主頁：你最愛的小傻瓜】😎

🤔【本文內容：C++ list容器?😍】🤔

---------------------------------------------------------------------------------------------------------------------------------

在 C++ 的數據江湖里，list 仿若一位靈動迅捷的暗衛。

它憑雙向鏈表的隱秘鎖鏈串聯元素，從無空間局促的煩憂 —— 新增元素時，只需借由?push_front?或?push_back?施展暗勁，新的節點便如暗樁般悄然嵌入。那些靜臥的元素，似暗格里的密信靜待調閱，借迭代器輕輕游走，就能探尋到某一環的機密。

當你持迭代器之匕穿梭其中，恰似指尖拂過暗衛的鎖鏈，每個元素皆有序排布，等你細究。若要對這鎖鏈重構序列，sort?函數就是絕佳的秘使，瞬間就能讓雜亂的節點規整得有條不紊。

無論是整數的密令、字符的暗語，還是自定義對象的機密情報，它都能妥善收納，宛如一座隨需而設的秘庫，讓各類數據在其中各就其位，等候編程者去調取探尋。

---------------------------------------------------------------------------------------------------------------------------------

1.list的介紹：

在之前，我們學習了vector這個容器，我們復習一下。它的優點是尾插尾刪效率高，支持隨機訪問。更詳細的看我之前的博客鏈接：vector

今天我要分享的是list，它是以鏈表形式來實現的，并是環形雙向鏈表（想要了解：順序表和鏈表）。

因為是鏈表所以不支持隨機訪問，只能是通過已知的位置迭代到想訪問的位置。但在插入和刪除這兩個方面效率更高，由于它是指針的形式來去儲存數據的，只要將鄰近的指針跟它相鏈接就行，刪除也類似。

forward_list 是單鏈表的形式，只能朝前迭代。

// list()
list<int> l;

// list (size_type n, const value_type& val = value_type())
list<int> l(5, 10);

// list (const list& x);
list<int> l1{1, 2, 3};
list<int> l2(l1);

// list (InputIterator first, InputIterator last);
// 示例1：用數組迭代器構造
int arr[] = {1, 2, 3, 4, 5};
list<int> l(arr, arr + 5);// 示例2：用其他 list 的迭代器構造
list<int> l1{1, 2, 3, 4, 5};
list<int> l2(l1.begin(), l1.end());

begin()：返回指向容器第一個元素的可修改迭代器（iterator）

end()：返回指向容器最后一個元素后一位的可修改迭代器

用途：正向遍歷并可修改元素

list<int> l{1,2,3};
for (auto it = l.begin(); it != l.end(); ++it) {*it += 10; // 修改元素：1→11，2→12，3→13
}

rbegin()：返回指向容器最后一個元素的反向迭代器（reverse_iterator）

rend()：返回指向容器第一個元素前一位的反向迭代器

用途：反向遍歷并可修改元素

list<int> l{1,2,3};
for (auto rit = l.rbegin(); rit != l.rend(); ++rit) {*rit *= 2; // 反向修改：3→6，2→4，1→2
}

3.列表元素訪問：

front()?/?back()：獲取頭部 / 尾部元素：

list<int> l{1,2,3};
l.front() = 10; // 頭部改為10：[10,2,3]
l.back() = 30;  // 尾部改為30：[10,2,30]

4.容量訪問：

empty()：判斷容器是否為空（無元素），返回?bool?值（true?表示空，false?表示非空）

list<int> l1; // 空列表
list<int> l2{1,2,3}; // 非空列表cout << (l1.empty() ? "l1為空" : "l1非空"); // 輸出：l1為空
cout << (l2.empty() ? "l2為空" : "l2非空"); // 輸出：l2非空

size()：返回元素個數：

list<int> l{1,2,3};
cout << l.size(); // 輸出：3

5.列表元素修改：

push_front(val)：在頭部添加元素

list<int> l{2,3};
l.push_front(1); // 結果：[1,2,3]

push_back(val)：在尾部添加元素

list<int> l{1,2};
l.push_back(3); // 結果：[1,2,3]

insert(pos, val)：在迭代器pos位置插入元素

list<int> l{1,3};
auto it = ++l.begin(); // 指向3的位置
l.insert(it, 2); // 結果：[1,2,3]

pop_front()：刪除頭部元素

list<int> l{1,2,3};
l.pop_front(); // 結果：[2,3]

pop_back()：刪除尾部元素

list<int> l{1,2,3};
l.pop_back(); // 結果：[1,2]

remove(val)：刪除所有值為val的元素

list<int> l{1,2,2,3};
l.remove(2); // 結果：[1,3]

erase(pos)：刪除迭代器pos指向的元素

list<int> l{1,2,3};
auto it = ++l.begin(); // 指向2
l.erase(it); // 結果：[1,3]

clear()：清空所有元素

list<int> l{1,2,3};
l.clear(); // 結果：空列表

6.操作：

splice（轉移）：

 list<int> l1 = {1, 2, 3};list<int> l2 = {4, 5, 6};auto it = l1.begin();advance(it, 1); // 讓 it 指向 l1 中元素 2l1.splice(it, l2); // 將 l2 中所有元素轉移到 l1 中 it 指向的位置前for (auto num : l1) {cout << num << " ";}cout << endl;// 此時 l1: 1, 4, 5, 6, 2, 3；l2 為空

remove/remove_if

list<int> l = {1, 2, 2, 3};l.remove(2); // 移除值為 2 的元素for (auto num : l) {cout << num << " ";}cout << endl; // 輸出：1 3list<int> l = {1, 2, 3, 4, 5};// 移除大于 3 的元素l.remove_if(bind(greater<int>(), placeholders::_1, 3));for (auto num : l) {cout << num << " ";}cout << endl; // 輸出：1 2 3

unique

 list<int> l = {1, 1, 2, 2, 3, 3};l.unique(); // 移除相鄰的重復元素for (auto num : l) {cout << num << " ";}cout << endl; // 輸出：1 2 3

merge

list<int> l1 = {1, 3, 5};list<int> l2 = {2, 4, 6};l1.merge(l2); // 合并兩個已排序的 listfor (auto num : l1) {cout << num << " ";}cout << endl; // 輸出：1 2 3 4 5 6

sort

list<int> l = {3, 1, 2};l.sort(); // 對 list 中的元素進行排序for (auto num : l) {cout << num << " ";}cout << endl; // 輸出：1 2 3

reverse

 list<int> l = {1, 2, 3};l.reverse(); // 反轉 list 中元素的順序for (auto num : l) {cout << num << " ";}cout << endl; // 輸出：3 2 1

一些小知識：

雙向迭代器：可雙向移動（支持++和--），功能強于單向迭代器，繼承單向迭代器操作，新增--（前置 / 后置），不支持隨機訪問（如+=n），典型容器像list、map/set。

隨機訪問迭代器：支持任意位置跳轉（隨機訪問），功能最強，繼承雙向迭代器操作，新增+=n、-=n、[]、</>等關系運算，典型容器為vector、deque、array。

單向迭代器：僅能從容器到尾單向移動，支持讀取（部分可修改），操作有++（前置 / 后置）、*（解引用讀）、->，不支持--、+=n等，典型容器如forward_list、unordered_map/unordered_set。

迭代器分類是對移動和訪問能力的標準化，理解其功能邊界，能助力正確選擇容器和算法，避免因迭代器功能不足引發編譯錯誤。

list的模擬實現（記得看注釋）:

接下來我將手把手教你們實現list(基礎版)（要建自己的命名空間域喲!!!）

第一步：

首先我們要明白list是一個雙向鏈表，所以我們先要建立一個創建結點的類：

template<class T>//模板對應著不同需求的數據
struct list_node
{list_node<T>* next;//指向下一個結點list_node<T>* prev;//指向上一個結點T _val; //存儲數據//初始化（構造函數）list_node(const T& val = T())//記得給缺省值:next(nullptr), prev(nullptr), _val(val)
};

第二步：我們要實現list類：

template<class T>
class list
{
public:typedef list_node<T> Node;//簡化名字
private:Node* _head;//哨兵位size_t _size;//計算list里面的數據個數};

第三步：完善我們的list類：

1.我們要初始化，可以寫一個函數來初始化，再將它放入構造函數里面：

void empty_node()
{_head = new Node; //申請一個結點_head->next = _head;//因為只有一個哨兵位，雙向鏈表里的方向指針，只能指向自身。_head->prev = _head;_size = 0;//記入數據多少
}
list()
{empty_node();
}

2.拷貝構造函數：要實現它，需對?list?進行插入、遍歷等操作，但由此會產生一個問題：list?的這些功能能否和?vector?一樣呢？答案顯然是否定的。因為?vector?基于數組，是連續的內存空間；而?list?底層是雙向鏈表，內存空間不連續。此時，迭代器就發揮作用了。這里用到的是雙向迭代器，它能讓我們更便捷地操作?list。雙向迭代器本質上是一個封裝好的類，專門用于對鏈表的結點（即操作對象）進行各類操作。

? 1.初始的迭代器：對于const修飾的數據無法處理(處理這個兩種方式就是用模板，還有就是再寫一個const版的迭代器)

//1.通常版
template<class T>
//template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;//簡化名稱typedef list_iterator<T> self;//簡化名稱Node* _node;//創建一個結點，來鏈接迭代器與結點之間的聯系list_iterator(Node* node)//為一些結點轉化為迭代器類類型，好操作結點，實現我們好用的方式:_node(node){}//解引用的實現：1.避免拷貝 2.支持修改操作，在一些數據里不是指針或引用，就是臨時的不會影響原數據。T& operator*(){return _node->_val;}//->訪問形式的實現：->就是對指針的。T* operator->(){return &(_node->_val);}//下面的返回值，以及代碼實現，是有一些小心思的：
//self& self 這是因為第一個前置無需擔心原數據的修改，另一個是后置要擔心原數據的修改，因為我們先要
//用到未++前的數據情況，而后再++。
//self tmp(*this)之前我們說過的迭代器初始化，在這里有體現，我們將原先的賦值拷貝給一個臨時的，再++，返回的是臨時的，這樣就實現了后置。//前置++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類型，這里傳的是迭代器引用（防拷貝），并且用了const修飾，最后的 const 表明這個成員函數不會修改當前對象的狀態。判斷兩個迭代器是否指向同一個節點bool operator!=(const self& x)const{return _node != x._node;}bool operator==(const self& x)const{return _node == x._node;}
};
//2.為了是應const類型的數據，我們可以用模板多個數據的定義。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){}//解引用的實現：1.避免拷貝 2.支持修改操作，在一些數據里不是指針或引用，就是臨時的不會影響原數據。Ref operator*(){return _node->_val;}//->訪問形式的實現：->就是對指針的。Ptr operator->(){return &(_node->_val);}//......上面的內容，沒有改變};

2.迭代器的訪問：
?

template<class T>
class list
{
public:typedef list_node<T> Node;//簡化名字typedef list_iterator<T, T&, T*> iterator;//模板實例化typedef list_iterator<const T, const T&, const T*> const_iterator;//模板實例化
//iterator()這個是為了改為迭代器類類型好訪問iterator begin(){return iterator(_head->next);}const_iterator begin()const{return const_iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}//................
}

3.拷貝構造函數的實現：

list(const list<T>& it)
{empty_node();//初始化for (auto& e : it)//一個個插入數據{push_back(e);//尾插}
}void push_back(const T& x)
{insert(end(), x);//用insert來實現尾插
}iterator insert(iterator pos, const T& x)//第一個參數迭代器類類型，用來訪問。
{//申請前（prev）中（prev）以及新結點 三個結點 而插入就是再prev與cur中間。修改他們的前后指針指向。Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(x);prev->next = newnode;cur->prev = newnode;newnode->next = cur;newnode->prev = prev;++_size;//計入增加大小return newnode;//返回值是迭代器，指向新建的結點。方便后續操作。以及避免迭代器失效的問題
}

第四步：

erase函數以及插入，刪除函數和重載=和析構函數：

在鏈表的刪除操作（erase）中，會導致迭代器失效，具體情況如下：

• 被刪除節點的迭代器失效原因：鏈表迭代器是對節點指針的封裝，刪除操作里，被刪除節點會被delete釋放內存，指向該節點的迭代器所關聯的指針就成了野指針（指向已釋放內存），野指針無法安全訪問和使用，所以這個迭代器徹底失效。
• 注意事項：刪除操作后，被刪除節點的迭代器絕對不能再使用（如解引用、遞增等），否則會引發未定義行為（程序崩潰、數據錯誤等）。
• erase函數的應對：erase函數會返回被刪除節點的下一個節點的迭代器，以此替代失效的迭代器，保障后續操作（如繼續遍歷）的安全性。

void swap(list<T>& it)//用庫里面的swap函數進行交換，傳的是list類的引用
{std::swap(_head, it._head);std::swap(_size, it._size);
}
//重載賦值就是將list的類里面的成員變量給賦值過去
list<T>& operator=(list<T> it)
{swap(it);return *this;
}
//銷毀就是要前（prev）中（我們要刪的）后（next）三個指針，我們銷毀就是將原先指向cur的給改成prev和next之間的關系，返回的是下一個結點
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete cur;--_size;return next;
}void push_front(const T& x)
{insert(begin(), x);
}
//為什么要-- 這是因為尾刪的數據在哨兵位的前面（end（）返回的是哨兵位）
void pop_back()
{erase(--end());
}void pop_front()
{erase(begin());
}//通過迭代器的遍歷來進行，由于erase的是返回下一個結點的，所以不需要像我們之前的++遍歷下去
void clear()
{iterator it = begin();while (it != end()){it = erase(it);}_size = 0;
}~list()
{clear();delete _head;_head = nullptr;
}
//計算數據多少
size_t size()const
{return _size;
}

終于結束了！！！

list模擬完整代碼：

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
namespace xin
{template<class T>struct list_node{list_node<T>* next;list_node<T>* 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;}Ptr 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& x)const{return _node != x._node;}bool operator==(const self& x)const{return _node == x._node;}};template<class T>class list{public:typedef list_node<T> Node;typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<const T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->next);}const_iterator begin()const{return const_iterator(_head->next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}void empty_node(){_head = new Node;_head->next = _head;_head->prev = _head;_size = 0;}list(){empty_node();}void swap(list<T>& it){std::swap(_head, it._head);std::swap(_size, it._size);}list<T>& operator=(list<T> it){swap(it);return *this;}list(const list<T>& it){empty_node();for (auto& e : it){push_back(e);}}void push_back(const T& x){insert(end(), x);}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(x);prev->next = newnode;cur->prev = newnode;newnode->next = cur;newnode->prev = prev;++_size;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete cur;--_size;return next;}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}~list(){clear();delete _head;_head = nullptr;}size_t size()const{return _size;}private:Node* _head;size_t _size;};
}

list與vector的對比：

??總結

相信堅持下來的你一定有了滿滿的收獲。那么也請老鐵們多多支持一下，點點關注，收藏，點贊。??