深入解析C++ STL鏈表（List）模擬實現

一、需要實現的三個類及其成員函數接口

二、結點類的模擬實現

構造函數

三、迭代器類的模擬實現

1、迭代器類的作用

2、迭代器類模板參數說明

3、構造函數

4、前置++運算符重載

5、后置++運算符重載

6、前置 -- 運算符重載

7、后置 -- 運算符重載

8、==運算符重載

9、重載 != 運算符

10、解引用運算符的重載

11、->運算符的重載

四、List 模擬實現

1、默認成員函數

構造函數

拷貝構造函數

賦值運算符重載函數

傳統寫法

現代寫法

析構函數

2、迭代器相關函數：begin和end

3、訪問容器相關函數

front()和back()

4、插入與刪除函數

insert函數

erase 函數

push_back 和 pop_back 函數

push_front 和 pop_front 函數

5、其他函數

size

resize

clear

empty

swap

五、測試代碼

六、vector?與?list?的對比

關鍵總結：

七、為什么?list?的插入不會使迭代器失效，而刪除僅影響當前迭代器？

1、list?插入不會使迭代器失效的原因

2、list?刪除僅影響當前迭代器的原因

3、對比?vector?的迭代器失效

4、總結

一、需要實現的三個類及其成員函數接口

#define _CRT_SECURE_NO_WARNINGS 1#include <iostream>
#include <cassert>
#include <vector>namespace hmz 
{template<class T>struct _list_node{//構造函數_list_node(const T& val = T()):_val(val), _prev(nullptr), _next(nullptr){}//成員變量T _val;                 //數據域_list_node<T>* _next;   //后繼指針_list_node<T>* _prev;   //前驅指針};//模擬實現list迭代器template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;//構造函數_list_iterator(node* pnode):_pnode(pnode){}//各種運算符重載函數// 前置++self operator++(){_pnode = _pnode->_next; // 指針指向下一個結點return *this;          // 返回更新后的指針}//前置--self operator--(){_pnode = _pnode->_prev; //讓結點指針指向前一個結點return *this; //返回自減后的結點指針}// 后置++self operator++(int){self tmp(*this);       // 保存當前指針狀態_pnode = _pnode->_next; // 指針指向下一個結點return tmp;            // 返回之前的指針}//后置--self operator--(int){self tmp(*this); //記錄當前結點指針的指向_pnode = _pnode->_prev; //讓結點指針指向前一個結點return tmp; //返回自減前的結點指針}bool operator==(const self& s) const{return _pnode == s._pnode; //判斷兩個結點指針指向是否相同}bool operator!=(const self& s) const{return _pnode != s._pnode;  // 檢查兩個節點指針是否指向不同地址}Ref operator*(){return _pnode->_val; // 返回節點指針所指向節點的數據}Ptr operator->(){return &_pnode->_val; // 返回結點指針所指數據的地址}//成員變量node* _pnode; //一個指向結點的指針};//模擬實現listtemplate<class T>class list{public:typedef _list_node<T> node;typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;//默認成員函數// 構造函數list(){_head = new node;        // 創建頭節點_head->_next = _head;    // 后繼指針自指_head->_prev = _head;    // 前驅指針自指}//拷貝構造函數list(const list<T>& lt){_head = new node; //申請一個頭結點_head->_next = _head; //頭結點的后繼指針指向自己_head->_prev = _head; //頭結點的前驅指針指向自己for (const auto& e : lt){push_back(e); //將容器lt當中的數據一個個尾插到新構造的容器后面}}//傳統寫法list<T>& operator=(const list<T>& lt){if (this != &lt) //避免自己給自己賦值{clear(); //清空容器for (const auto& e : lt){push_back(e); //將容器lt當中的數據一個個尾插到鏈表后面}}return *this; //支持連續賦值}// 析構函數~list(){clear();      // 清空容器delete _head; // 釋放頭節點_head = nullptr; // 重置頭指針}//迭代器相關函數iterator begin(){// 返回頭結點下一個結點構造的普通迭代器return iterator(_head->_next);}iterator end(){// 返回頭結點構造的普通迭代器return iterator(_head);}const_iterator begin() const{// 返回頭結點下一個結點構造的const迭代器return const_iterator(_head->_next);}const_iterator end() const{// 返回頭結點構造的const迭代器return const_iterator(_head);}//訪問容器相關函數T& front(){return *begin(); // 返回首元素的引用}T& back(){return *(--end()); // 返回末元素的引用}const T& front() const{return *begin(); // 返回首元素的const引用}const T& back() const{return *(--end()); // 返回末元素的const引用}//插入、刪除函數//插入函數void insert(iterator pos, const T& x){assert(pos._pnode); //檢測pos的合法性node* cur = pos._pnode; //迭代器pos處的結點指針node* prev = cur->_prev; //迭代器pos前一個位置的結點指針node* newnode = new node(x); //根據所給數據x構造一個待插入結點//建立newnode與cur之間的雙向關系newnode->_next = cur;cur->_prev = newnode;//建立newnode與prev之間的雙向關系newnode->_prev = prev;prev->_next = newnode;}//刪除函數iterator erase(iterator pos){assert(pos._pnode); //檢測pos的合法性assert(pos != end()); //刪除的結點不能是頭結點node* cur = pos._pnode; //迭代器pos處的結點指針node* prev = cur->_prev; //迭代器pos前一個位置的結點指針node* next = cur->_next; //迭代器pos后一個位置的結點指針delete cur; //釋放cur結點//建立prev與next之間的雙向關系prev->_next = next;next->_prev = prev;return iterator(next); //返回所給迭代器pos的下一個迭代器}// 尾插操作void push_back(const T& x){insert(end(), x); // 在尾節點位置插入新元素}// 尾刪操作void pop_back(){erase(--end()); // 刪除尾節點}// 頭插操作void push_front(const T& x){insert(begin(), x); // 在鏈表頭部插入新元素}// 頭刪操作void pop_front(){erase(begin()); // 刪除鏈表首元素}//其他函數size_t size() const{size_t sz = 0; //統計有效數據個數const_iterator it = begin(); //獲取第一個有效數據的迭代器while (it != end()) //通過遍歷統計有效數據個數{sz++;it++;}return sz; //返回有效數據個數}void resize(size_t n, const T& val = T()){iterator i = begin(); //獲取第一個有效數據的迭代器size_t len = 0; //記錄當前所遍歷的數據個數while (len < n && i != end()){len++;i++;}if (len == n) //說明容器當中的有效數據個數大于或是等于n{while (i != end()) //只保留前n個有效數據{i = erase(i); //每次刪除后接收下一個數據的迭代器}}else //說明容器當中的有效數據個數小于n{while (len < n) //尾插數據為val的結點，直到容器當中的有效數據個數為n{push_back(val);len++;}}}void clear(){iterator it = begin();while (it != end())  // 逐個刪除元素{it = erase(it);}}void swap(list<T>& lt){std::swap(_head, lt._head);  // 調用全局swap函數交換頭指針}private:node* _head; //指向鏈表頭結點的指針};
}

二、結點類的模擬實現

我們經常說list在底層實現時就是一個鏈表，更準確來說，list實際上是一個帶頭雙向循環鏈表。

????????因此，我們若要實現list，則首先需要實現一個結點類。而一個結點需要存儲的信息有：數據、前一個結點的地址、后一個結點的地址，于是該結點類的成員變量也就出來了（數據、前驅指針、后繼指針）。

????????而對于該結點類的成員函數來說，我們只需實現一個構造函數即可。因為該結點類只需要根據數據來構造一個結點即可，而結點的釋放則由list的析構函數來完成。

構造函數

????????結點類的構造函數直接根據所給數據構造一個結點即可，構造出來的結點的數據域存儲的就是所給數據，而前驅指針和后繼指針均初始化為空指針即可。

//構造函數
_list_node(const T& val = T()):_val(val), _prev(nullptr), _next(nullptr)
{}

注意：?若構造結點時未傳入數據，則默認以list容器所存儲類型的默認構造函數所構造出來的值為傳入數據。

三、迭代器類的模擬實現

1、迭代器類的作用

????????在之前模擬實現string和vector時，我們并未專門實現迭代器類，那么為什么在實現list時需要單獨設計迭代器類呢？

????????原因在于string和vector的數據存儲在連續的內存空間中，通過指針的自增、自減和解引用操作就能直接訪問對應位置的數據，因此它們的迭代器可以直接使用原生指針。

????????而list的情況不同：它的各個節點在內存中的分布是隨機的，不連續的。僅靠節點指針的自增、自減和解引用操作無法正確訪問數據。

????????迭代器的核心價值在于：它讓使用者無需了解容器的底層實現細節，只需通過統一簡單的方式就能訪問容器數據。

????????由于list的節點指針無法直接滿足迭代器的要求，我們需要對其進行封裝，通過重載運算符來調整指針的行為。這樣就能像使用string和vector的迭代器一樣操作list的迭代器。例如，list迭代器的自增操作背后實際執行的是p = p->next語句，但使用者無需關心這個細節。

總結：list迭代器類本質上是對節點指針的封裝，通過運算符重載使其行為與普通指針一致（比如自增操作會自動指向下一個節點）。

2、迭代器類模板參數說明

在迭代器類的模板參數列表中，為什么需要三個模板參數？

template<class T, class Ref, class Ptr>

在list的模擬實現中，我們定義了兩個迭代器類型：

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

可以看出，Ref和Ptr分別代表引用類型和指針類型。這樣設計可以實現：

使用普通迭代器時，編譯器實例化普通迭代器對象
使用const迭代器時，編譯器實例化const迭代器對象

????????如果只使用單一模板參數，就無法有效區分普通迭代器和const迭代器的不同行為。三個模板參數的設計提供了這種區分能力。

3、構造函數

????????迭代器類實際上就是對結點指針進行了封裝，其成員變量就只有一個，那就是結點指針，其構造函數直接根據所給結點指針構造一個迭代器對象即可。

//構造函數
_list_iterator(node* pnode):_pnode(pnode)
{}

4、前置++運算符重載

????????前置++的原始功能是使數據自增并返回自增后的結果。為了讓結點指針模擬普通指針的行為，我們需要先讓結點指針指向下一個結點，然后返回更新后的指針。

// 前置++
self operator++()
{_pnode = _pnode->_next; // 指針指向下一個結點return *this;          // 返回更新后的指針
}

5、后置++運算符重載

????????后置++的實現需要先保存當前指針狀態，然后移動指針到下一個結點，最后返回之前保存的指針值。

// 后置++
self operator++(int)
{self tmp(*this);       // 保存當前指針狀態_pnode = _pnode->_next; // 指針指向下一個結點return tmp;            // 返回之前的指針
}

注：self定義為當前迭代器類型的別名：typedef _list_iterator<T, Ref, Ptr> self;

6、前置 `--` 運算符重載

對于前置 -- 運算，需要先將結點指針指向前一個結點，然后返回修改后的指針。

// 前置--
self operator--() 
{_pnode = _pnode->_prev;  // 移動指針到前一個結點return *this;            // 返回當前對象
}

7、后置 `--` 運算符重載

對于后置 -- 運算，需要先保存當前指針狀態，移動指針后再返回先前保存的值。

// 后置--
self operator--(int) 
{self tmp(*this);         // 保存當前狀態_pnode = _pnode->_prev;  // 移動指針到前一個結點return tmp;              // 返回先前保存的值
}

8、==運算符重載

????????當使用==運算符比較兩個迭代器時，實際上需要判斷它們是否指向相同位置，即比較兩個迭代器所包含的結點指針是否相同。

bool operator==(const self& s) const
{return _pnode == s._pnode;  // 比較結點指針的指向
}

9、重載 != 運算符

!= 運算符的功能與 == 運算符相反，用于判斷兩個迭代器中的節點指針是否指向不同的位置。

bool operator!=(const self& s) const
{return _pnode != s._pnode;  // 檢查兩個節點指針是否指向不同地址
}

10、解引用運算符的重載

????????解引用操作符用于獲取指針指向位置的數據內容。因此，我們直接返回當前節點指針所指向節點的數據即可。這里需要使用引用返回類型，因為解引用操作后用戶可能需要對數據進行修改。

Ref operator*()
{return _pnode->_val; // 返回節點指針所指向節點的數據
}

11、->運算符的重載

????????在某些使用迭代器的場景中，我們可能需要通過->運算符來訪問元素成員。例如當list容器存儲的是自定義類型（如日期類）時，我們可以通過迭代器直接訪問Date類的成員：

list<Date> lt;
Date d1(2021, 8, 10);
Date d2(1980, 4, 3);
Date d3(1931, 6, 29);
lt.push_back(d1);
lt.push_back(d2);
lt.push_back(d3);
list<Date>::iterator pos = lt.begin();
cout << pos->_year << endl; // 輸出第一個日期的年份

注意：使用pos->_year這種訪問方式時，需要將Date類的成員變量設為公有。

->運算符的重載實現很簡單，直接返回結點存儲數據的地址即可：（C++ 的?->?運算符要求返回指針，編譯器會自動處理?->?的嵌套調用。）

Ptr operator->()
{return &_pnode->_val; // 返回結點指針所指數據的地址
}

????????這里有一個需要注意的地方：按照重載方式，理論上使用迭代器訪問成員變量時應該有兩個->運算符。第一個箭頭是pos->調用重載的operator->返回Date指針，第二個箭頭是Date指針訪問成員變量_year。但為了提升代碼可讀性，編譯器會進行特殊處理，自動省略一個箭頭。

四、List 模擬實現

1、默認成員函數

構造函數

????????List 采用帶頭雙向循環鏈表結構。在構造 list 對象時，會先申請一個頭節點，并將該節點的前驅和后繼指針都指向自身，形成初始循環結構。

// 構造函數
list()
{_head = new node;        // 創建頭節點_head->_next = _head;    // 后繼指針自指_head->_prev = _head;    // 前驅指針自指
}

拷貝構造函數

拷貝構造函數用于根據已有list容器創建一個新對象。其實現步驟如下：

申請頭結點并初始化其指針指向自身
遍歷原容器數據，逐個執行尾插操作

實現代碼如下：

// 拷貝構造函數
list(const list<T>& lt)
{_head = new node;        // 申請頭結點_head->_next = _head;    // 初始化后繼指針_head->_prev = _head;    // 初始化前驅指針for (const auto& e : lt) // 遍歷原容器{push_back(e);        // 執行尾插操作}
}

賦值運算符重載函數

傳統寫法

這種實現方式邏輯清晰直觀：先清空原有容器，然后逐個插入新元素。

//傳統寫法
list<T>& operator=(const list<T>& lt)
{if (this != &lt) //避免自己給自己賦值{clear(); //清空容器for (const auto& e : lt){push_back(e); //將容器lt當中的數據一個個尾插到鏈表后面}}return *this; //支持連續賦值
}

現代寫法

????????現代實現方式代碼更簡潔：通過編譯器機制，故意不使用引用傳參，讓編譯器自動調用list的拷貝構造函數生成臨時對象，然后調用swap函數完成原容器與臨時對象的交換。

list<T>& operator=(list<T> lt) // 參數使用傳值方式，自動調用拷貝構造
{swap(lt); // 交換容器內容return *this; // 支持鏈式賦值
}

????????現代寫法的優勢在于：通過參數傳值創建臨時副本后交換內容，原容器數據會隨著臨時對象銷毀而自動清理，代碼更加簡潔高效。

析構函數

在對象銷毀時，首先調用 clear 函數清空容器數據，然后釋放頭節點，最后將頭指針置空。

// 析構函數
~list()
{clear();      // 清空容器delete _head; // 釋放頭節點_head = nullptr; // 重置頭指針
}

2、迭代器相關函數：begin和end

begin和end函數的功能如下：

begin()返回指向第一個有效數據的迭代器
end()返回指向最后一個有效數據下一個位置的迭代器

對于帶頭雙向循環鏈表list來說：

第一個有效數據的迭代器是通過頭結點下一個結點的地址構造的
end()返回的迭代器是通過頭結點地址構造的（因為最后一個結點的next指針指向頭結點）

iterator begin()
{// 返回頭結點下一個結點構造的普通迭代器return iterator(_head->_next);
}iterator end()
{// 返回頭結點構造的普通迭代器return iterator(_head);
}

同時需要提供const版本的重載：

const_iterator begin() const
{// 返回頭結點下一個結點構造的const迭代器return const_iterator(_head->_next);
}const_iterator end() const
{// 返回頭結點構造的const迭代器return const_iterator(_head);
}

3、訪問容器相關函數

front()和back()

????????front()和back()函數分別用于獲取容器中的首元素和末元素。實現時直接返回首元素和末元素的引用即可。

T& front()
{return *begin(); // 返回首元素的引用
}T& back()
{return *(--end()); // 返回末元素的引用
}

為保證const對象的正確訪問，需要重載const版本：

const T& front() const
{return *begin(); // 返回首元素的const引用
}const T& back() const
{return *(--end()); // 返回末元素的const引用
}

4、插入與刪除函數

insert函數

insert函數用于在指定迭代器位置前插入新節點。

函數流程：

通過迭代器獲取當前節點指針cur
通過cur獲取前驅節點指針prev
根據輸入值x創建新節點
建立新節點與當前節點的雙向鏈接
建立新節點與前驅節點的雙向鏈接

//插入函數
void insert(iterator pos, const T& x)
{assert(pos._pnode); //檢測pos的合法性node* cur = pos._pnode; //迭代器pos處的結點指針node* prev = cur->_prev; //迭代器pos前一個位置的結點指針node* newnode = new node(x); //根據所給數據x構造一個待插入結點//建立newnode與cur之間的雙向關系newnode->_next = cur;cur->_prev = newnode;//建立newnode與prev之間的雙向關系newnode->_prev = prev;prev->_next = newnode;
}

erase 函數

erase 函數用于刪除指定迭代器位置的節點。

該函數執行以下操作：

獲取目標節點指針 cur
定位前驅節點 prev 和后繼節點 next
釋放當前節點內存
重建前后節點的雙向鏈接關系

//刪除函數
iterator erase(iterator pos)
{assert(pos._pnode); //檢測pos的合法性assert(pos != end()); //刪除的結點不能是頭結點node* cur = pos._pnode; //迭代器pos處的結點指針node* prev = cur->_prev; //迭代器pos前一個位置的結點指針node* next = cur->_next; //迭代器pos后一個位置的結點指針delete cur; //釋放cur結點//建立prev與next之間的雙向關系prev->_next = next;next->_prev = prev;return iterator(next); //返回所給迭代器pos的下一個迭代器
}

push_back 和 pop_back 函數

? ? push_back 和 pop_back 函數分別用于在鏈表尾部進行插入和刪除操作。通過復用已有的 insert 和 erase 函數，我們可以簡潔地實現這兩個功能：

push_back 在頭節點前插入新節點
pop_back 刪除頭節點前的一個節點

// 尾插操作
void push_back(const T& x)
{insert(end(), x); // 在尾節點位置插入新元素
}// 尾刪操作
void pop_back()
{erase(--end()); // 刪除尾節點
}

push_front 和 pop_front 函數

同樣地，我們可以復用 insert 和 erase 函數來實現頭部的插入和刪除操作：

push_front 在第一個有效節點前插入新節點
pop_front 刪除第一個有效節點

// 頭插操作
void push_front(const T& x)
{insert(begin(), x); // 在鏈表頭部插入新元素
}// 頭刪操作
void pop_front()
{erase(begin()); // 刪除鏈表首元素
}

5、其他函數

size

size函數用于獲取容器中有效數據的個數。由于list是鏈表結構，需要通過遍歷統計元素數量。

size_t size() const
{size_t sz = 0;  // 計數器初始化為0const_iterator it = begin();  // 獲取起始迭代器while (it != end())  // 遍歷整個鏈表{sz++;it++;}return sz;  // 返回元素總數
}

擴展：可以考慮添加一個成員變量size來記錄當前元素數量，避免每次遍歷。

resize

resize函數的實現規則：

擴容處理：當容器當前有效數據量小于指定值n時，持續在尾部插入新節點，直至數據量達到n。
縮容處理：當容器當前有效數據量大于n時，僅保留前n個有效數據，后續節點將被釋放。

優化實現建議：

避免直接調用size函數獲取當前數據量，防止重復遍歷
采用遍歷計數法：設置變量len記錄已遍歷節點數量
- 當len≥n時終止遍歷，釋放后續節點
- 當遍歷完所有節點時（len<n），持續進行尾插操作直至數據量達到n

注意事項：

此方法確保只需單次遍歷即可完成調整操作
有效平衡了執行效率和內存管理需求

void resize(size_t n, const T& val = T())
{iterator i = begin(); //獲取第一個有效數據的迭代器size_t len = 0; //記錄當前所遍歷的數據個數while (len < n&&i != end()){len++;i++;}if (len == n) //說明容器當中的有效數據個數大于或是等于n{while (i != end()) //只保留前n個有效數據{i = erase(i); //每次刪除后接收下一個數據的迭代器}}else //說明容器當中的有效數據個數小于n{while (len < n) //尾插數據為val的結點，直到容器當中的有效數據個數為n{push_back(val);len++;}}
}

clear

clear函數用于清空容器，我們通過遍歷的方式，逐個刪除結點，只保留頭結點即可。

void clear()
{iterator it = begin();while (it != end())  // 逐個刪除元素{it = erase(it);}
}

empty

????????empty函數用于判斷容器是否為空，我們直接判斷該容器的begin函數和end函數所返回的迭代器，是否是同一個位置的迭代器即可。（此時說明容器當中只有一個頭結點）

bool empty() const
{return begin() == end();  // 判斷起始和結束迭代器是否相同
}

swap

????????swap函數用于交換兩個容器，list容器當中存儲的實際上就只有鏈表的頭指針，我們將這兩個容器當中的頭指針交換即可。

void swap(list<T>& lt)
{std::swap(_head, lt._head);  // 調用全局swap函數交換頭指針
}

注意：使用std::顯式指定調用std命名空間的swap函數，避免與成員函數沖突。

五、測試代碼

void TestList() {// 測試默認構造函數和push_backhmz::list<int> l1;assert(l1.size() == 0);assert(l1.begin() == l1.end());l1.push_back(1);l1.push_back(2);l1.push_back(3);assert(l1.size() == 3);assert(*l1.begin() == 1);assert(*(--l1.end()) == 3);// 測試front和backassert(l1.front() == 1);assert(l1.back() == 3);// 測試迭代器遍歷std::vector<int> v;for (auto it = l1.begin(); it != l1.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 1, 2, 3 }));// 測試拷貝構造函數hmz::list<int> l2(l1);assert(l2.size() == 3);v.clear();for (auto it = l2.begin(); it != l2.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 1, 2, 3 }));// 測試賦值運算符hmz::list<int> l3;l3 = l1;assert(l3.size() == 3);v.clear();for (auto it = l3.begin(); it != l3.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 1, 2, 3 }));// 測試push_front和pop_frontl3.push_front(0);assert(l3.front() == 0);assert(l3.size() == 4);l3.pop_front();assert(l3.front() == 1);assert(l3.size() == 3);// 測試pop_backl3.pop_back();assert(l3.back() == 2);assert(l3.size() == 2);// 測試insertauto it = l3.begin();++it;l3.insert(it, 5);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 1, 5, 2 }));// 測試eraseit = l3.begin();++it;it = l3.erase(it);assert(*it == 2);assert(l3.size() == 2);// 測試resize增大l3.resize(4, 10);assert(l3.size() == 4);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 1, 2, 10, 10 }));// 測試resize縮小l3.resize(2);assert(l3.size() == 2);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 1, 2 }));// 測試clearl3.clear();assert(l3.size() == 0);assert(l3.begin() == l3.end());// 測試swaphmz::list<int> l4;l4.push_back(7);l4.push_back(8);l4.push_back(9);l3.swap(l4);assert(l3.size() == 3);assert(l4.size() == 0);v.clear();for (auto num : l3) {v.push_back(num);}assert(v == std::vector<int>({ 7, 8, 9 }));// 測試const迭代器const hmz::list<int> l5(l3);v.clear();for (auto it = l5.begin(); it != l5.end(); ++it) {v.push_back(*it);}assert(v == std::vector<int>({ 7, 8, 9 }));std::cout << "All list tests passed!" << std::endl;
}int main() {TestList();return 0;
}

六、`vector`?與?`list`?的對比

對比項	vector	list
底層結構	動態順序表（一段連續空間）	帶頭結點的雙向循環鏈表
隨機訪問	支持，效率 O(1)	不支持，效率 O(N)
插入和刪除	任意位置效率低（需搬移元素），時間復雜度 O(N)；增容可能導致額外開銷	任意位置效率高（無需搬移元素），時間復雜度 O(1)
空間利用率	連續空間，內存碎片少，空間及緩存利用率高	節點動態開辟，易產生內存碎片，空間及緩存利用率低
迭代器類型	原生態指針（通常為指針或隨機訪問迭代器）	對節點指針的封裝（雙向迭代器）
迭代器失效	插入可能因擴容使所有迭代器失效；刪除時當前迭代器需重新賦值	插入不失效；刪除僅影響當前迭代器
使用場景	需高效存儲、頻繁隨機訪問，插入刪除操作較少	需頻繁插入刪除，不依賴隨機訪問

關鍵總結：

vector：適合隨機訪問密集、內存緊湊的場景，但插入/刪除（尤其非尾部）性能較差。
list：適合頻繁插入/刪除的場景，但隨機訪問效率低且內存開銷較大。

七、為什么?`list`?的插入不會使迭代器失效，而刪除僅影響當前迭代器？

????????這是由于?list?的底層結構是雙向鏈表，其內存管理和元素訪問方式與?vector（動態數組）有本質區別。

1、`list`?插入不會使迭代器失效的原因

在?list?中，插入新元素時：

不涉及內存重新分配：
- vector?在插入時可能需要擴容（重新分配內存+拷貝元素），導致所有迭代器失效。
- 但?list?的節點是?動態分配?的，插入新元素只需修改相鄰節點的指針，不會影響其他節點的內存地址。
插入操作僅修改局部指針：
- 例如，在節點?A?和?B?之間插入?X，只需：
```
A.next = &X;
X.prev = &A;
X.next = &B;
B.prev = &X;
```
- 其他節點的地址不變，因此所有現有迭代器仍然有效。

??結論：list?插入操作不會導致任何迭代器失效（包括?end()）。

2、`list`?刪除僅影響當前迭代器的原因

在?list?中，刪除元素時：

僅釋放當前節點的內存：
- 例如，刪除節點?X（位于?A?和?B?之間）：
```
A.next = &B;
B.prev = &A;
delete &X;  // 釋放 X 的內存
```
- 只有?X?的迭代器失效，其他節點（如?A、B）的迭代器不受影響。
不涉及數據搬移：
- vector?刪除元素后，后面的元素會前移，導致后面的迭代器全部失效。
- 但?list?是鏈表，刪除一個節點?不會影響其他節點的位置。

??錯誤示例（導致未定義行為）：

std::list<int> lst = {1, 2, 3, 4};
auto it = lst.begin();
++it; // it 指向 2
lst.erase(it); // 刪除 2
std::cout << *it; // ? it 已失效，訪問會導致未定義行為！

??正確做法（返回新迭代器）：

it = lst.erase(it); // it 現在指向 3（刪除后的下一個元素）

3、對比?`vector`?的迭代器失效

操作	`vector`	`list`
插入	可能擴容，所有迭代器失效	不會失效
刪除	被刪元素后的所有迭代器失效	僅當前迭代器失效

4、總結

list?插入不失效：因為鏈表動態分配節點，插入只修改指針，不改變已有元素的內存地址。
list?刪除僅當前失效：因為只釋放當前節點，其他節點不受影響。
vector?插入/刪除可能失效：由于內存重新分配或元素搬移，導致迭代器失效。

這種差異使得?list?在頻繁插入/刪除的場景下更安全，而?vector?在隨機訪問時更高效。