往期《C++初階》回顧：

/------------ 入門基礎 ------------/
【C++的前世今生】
【命名空間 + 輸入&輸出 + 缺省參數 + 函數重載】
【普通引用 + 常量引用 + 內聯函數 + nullptr】
/------------ 類和對象 ------------/
【類 + 類域 + 訪問限定符 + 對象的大小 + this指針】
【類的六大默認成員函數】
【初始化列表 + 自定義類型轉換 + static成員】
【友元 + 內部類 + 匿名對象】
【經典案例：日期類】
/------------ 內存管理 ------------/
【內存分布 + operator new/delete + 定位new】
/------------ STL ------------/
【泛型編程 + STL簡介】
【auto關鍵字 + 范圍for循環 + 迭代器】
【string類：詳解 + 實現】
【vector容器：詳解 + 實現】

前言

🌈元氣滿滿的更新通知 🌞
hi～小伙伴們大家好呀！(ﾉ>ω<)ﾉ 我又來給大家更新日期小貼士啦！
明天就是中伏了，這意味著為期 10 天的頭伏即將結束，但三伏天還沒走完哦(>﹏<)～🔥 現在正值盛夏，我們依然處在夏季最熱的階段，大家一定要記得做好防暑措施呀～🍉（遞上冰鎮西瓜）

💻技術內容預告 ?
今天為大家帶來的內容是：【list 容器：詳解 + 實現】 📚。這可是 STL 中真正開始有挑戰性的容器啦！(??????)?? 但相信有了前面 “string + vector” 的學習鋪墊，list 對大家來說應該不算太難(｡???-)?～💪
本文依舊是長篇內容（哈哈，說 “巨制” 可談不上(? ???ω??? ?)），全文大約2w字，內容還是分為 “詳解” 和 “實現” 兩個部分。

---

? 這里溫馨提示一下： ?
實現部分在目錄里雖然只占 3 個條目，但這絕不代表它不重要！恰恰相反，這部分是全篇最核心的內容～🌟
鼠鼠我沒有把不同的接口實現單獨拆分出來，而是直接放了一整個文件的代碼 —— 主要是考慮到在 CSDN 上閱讀可能不太方便，以及拆分之后會缺失對整體的架構理解。所以大家可以直接把代碼拷走，放到自己的 VS 里細細推敲、運行調試哦～👨💻
大家不用擔心看不懂呦！(｡･ω･｡)ﾉ? 每個接口鼠鼠我都按步驟添加了注釋～📝 而且對于一些核心的設計問題，在實現內容下方還有專門的針對性解釋，相信大家一定能掌握的！(ﾉ≧?≦)ﾉ

------------標準接口介紹------------

標準模板庫中的list容器是什么樣的呢？

cplusplus網站上關于C++的list容器的介紹：list - C++ Reference

C++標準模板庫（STL）中對 list容器的介紹主要涵蓋以下兩個方面：

1. 成員函數：容器自身提供的方法（如：插入、刪除、排序），用于直接操作容器，封裝底層實現細節
2. 非成員函數重載：定義在容器外部的通用函數（如：比較、交換等），通過重載適配容器類型，提供統一操作接口

1. 常見的構造

構造函數	功能說明
list() 默認構造函數	構造一個空的 list 容器
list(size_type n, const value_type& val = value_type()) 填充構造函數	構造包含 n 個值為 val 的元素的 list 容器 （val 默認為類型默認值）
list(const list& x) 拷貝構造函數	通過拷貝另一個 list 容器 x 來初始化當前 list 容器 （深度復制元素）
list(InputIterator first, InputIterator last) 范圍構造函數	使用迭代器范圍 [first, last) 內的元素 （從 first 到 last 前一個位置）構造 list 容器
list(initializer_list<value_type> il) 初始化列表構造函數	通過初始化列表 ilist 中的元素直接構造 list 容器 （C++11 特性）

// constructing lists
#include <iostream>
#include <list>/*--------------------使用不同構造函數創建list對象--------------------*/
int main()
{/*--------------第一種構造函數：“默認”構造函數--------------*/std::list<int> first;  //創建空列表/*--------------第二種構造函數：“填充”構造函數--------------*/std::list<int> second(4, 100);   //4個值為100的元素/*--------------第三種構造函數：“范圍”構造函數--------------*/std::list<int> third(second.begin(), second.end());  //復制second的所有元素/*--------------第四種構造函數：“拷貝”構造函數--------------*/std::list<int> fourth(third);   //復制third的所有元素/*--------------第四種構造函數：“通過指針范圍”構造函數--------------*///1.使用數組初始化列表int myints[] = { 16,2,77,29 };//2.通過指針范圍構造std::list<int> fifth(myints, myints + sizeof(myints) / sizeof(int)); //myints指向首元素，myints + 4指向尾后位置//3.輸出fifth的內容std::cout << "fifth鏈表中的內容是: ";for (std::list<int>::iterator it = fifth.begin(); it != fifth.end(); ++it){std::cout << *it << ' ';}std::cout << '\n';return 0;
}

代碼案例：初始化列表（簡單的了解）

#include <iostream>
using namespace std;int main()
{/*-------------使用 auto 關鍵字可以自動推導變量il的類型-------------*/auto il1 = { 10, 20, 30 };cout << "auto il = { 10, 20, 30 }中il的類型：" << typeid(il1).name() << endl;cout << "auto il = { 10, 20, 30 }中il的大小：" << sizeof(il1) << endl; //輸出 initializer_list 對象的大小（以字節為單位）// 注意：// initializer_list 本身只包含兩個指針（指向數組的開始和結束）// 因此其大小通常是指針大小的兩倍（例如：在64位系統上是16字節）// 它并不直接包含列表中的元素，元素存儲在初始化列表創建的臨時數組中/*-------------顯式聲明一個 initializer_list 類型的變量il-------------*/// initializer_list 是 C++ 標準庫中的一種輕量級容器類型，用于表示一個“只讀的臨時值序列”// 它通常用于支持使用花括號初始化列表語法來初始化對象或傳遞參數initializer_list<int> il2 = { 10, 20, 30 };cout << "initializer_list<int> il = { 10, 20, 30 }中il的類型：" << typeid(il2).name() << endl;cout << "initializer_list<int> il = { 10, 20, 30 }中il的大小：" << sizeof(il2) << endl;return 0;
}

2. 迭代器操作

函數聲明	接口說明
begin	返回指向第一個元素的迭代器
end	返回指向末尾（最后一個元素之后）的迭代器
rbegin	返回指向反向開頭（即：最后一個元素）的反向迭代器
rend	返回指向反向末尾（即：原第一個元素之前）的反向迭代器

std::list::begin

// list::begin
#include <iostream>
#include <list>int main()
{/*-----------第一階段：使用“數組初始化列表 + 范圍構造”創建一個list容器-----------*/int myints[] = { 75,23,65,42,13 };std::list<int> mylist(myints, myints + 5);/*-----------第二階段：使用“正向迭代器”遍歷整個list容器-----------*/std::cout << "mylist中的內容是:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

std::list::end

std::list::rbegin

// list::rbegin/rend
#include <iostream>
#include <list>int main()
{/*----------第一階段：創建一個list的容器并進行初始化----------*/std::list<int> mylist;for (int i = 1; i <= 5; ++i) mylist.push_back(i);std::cout << "mylist backwards:";for (std::list<int>::reverse_iterator rit = mylist.rbegin(); rit != mylist.rend(); ++rit){std::cout << ' ' << *rit;}std::cout << '\n';return 0;
}

std::list::rend

3. 容量的操作

函數聲明	接口說明
size()	返回list中有效節點的個數（即：元素數量）
empty()	檢測list是否為空，若為空返回 true，否則返回 false

std::list::size

// list::size
#include <iostream>
#include <list>int main()
{std::list<int> mylist;std::cout << "初始狀態的mylist的size為：" << mylist.size() << '\n';for (int i = 0; i < 10; i++) mylist.push_back(i);std::cout << "尾插10個節點之后的size為：" << mylist.size() << '\n';mylist.insert(mylist.begin(), 10, 100);std::cout << "再在下標為10的位置插入10個節點后的size為：" << mylist.size() << '\n';mylist.pop_back();std::cout << "尾刪一個節點之后的size為：" << mylist.size() << '\n';return 0;
}

std::list::empty

// list::empty
#include <iostream>
#include <list>int main()
{std::list<int> mylist;int sum(0); //使用“直接初始化”進行初始化，等同于：int sum = 0;for (int i = 1; i <= 10; ++i){mylist.push_back(i);}while (!mylist.empty()){sum += mylist.front();mylist.pop_front();}std::cout << "從1加到的10的和為: " << sum << '\n';return 0;
}

4. 訪問的操作

函數聲明	接口說明
front()	返回 list 第一個節點的值的引用（不進行空容器檢查）
back()	返回 list 最后一個節點的值的引用（不進行空容器檢查）

std::list::front

// list::front
#include <iostream>
#include <list>int main()
{std::list<int> mylist;mylist.push_back(77);mylist.push_back(22);std::cout << "初始狀態下的mylist.front()是：" << mylist.front() << '\n';mylist.front() -= mylist.back();std::cout << "經過操作現在mylist.front()是：" << mylist.front() << '\n';return 0;
}

std::list::back

// list::back
#include <iostream>
#include <list>int main()
{std::list<int> mylist;mylist.push_back(10);while (mylist.back() != 0){mylist.push_back(mylist.back() - 1);}std::cout << "mylist的內容是:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

4. 修改的操作

函數聲明	接口說明
clear()	清空 list 中的有效元素
swap(other_list)	交換當前 list 和 other_list 的所有元素
push_front(val)	在 list 頭部插入值為 val 的元素
push_back(val)	在 list 尾部插入值為 val 的元素
insert(position, val)	在指定迭代器 position 位置前插入值為 val 的元素
pop_front()	刪除 list 的第一個元素（不返回被刪除元素）
pop_back()	刪除 list 的最后一個元素（不返回被刪除元素）
erase(position)	刪除 position位置的元素（返回指向下一個元素的迭代器）

std::list::clear

int main()
{std::list<int> mylist;std::list<int>::iterator it;mylist.push_back(100);mylist.push_back(200);mylist.push_back(300);std::cout << "mylist的內容是：";for (it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}  std::cout << '\n';mylist.clear();mylist.push_back(1101);mylist.push_back(2202);std::cout << "經過clear再尾插兩個節點后，mylist的內容是：";for (it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

std::list::swap

// swap lists
#include <iostream>
#include <list>int main()
{std::list<int> first(3, 100);   //使用“填充構造函數”創建出一個有三個100的鏈表 firststd::list<int> second(5, 200);  //使用“填充構造函數”創建出一個有五個200的鏈表 secondfirst.swap(second);std::cout << "first鏈表中的內容是:";for (std::list<int>::iterator it = first.begin(); it != first.end(); it++)std::cout << ' ' << *it;std::cout << '\n';std::cout << "second鏈表中的內容是:";for (std::list<int>::iterator it = second.begin(); it != second.end(); it++)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

std::list::push_front

// list::push_front
#include <iostream>
#include <list>int main()
{std::list<int> mylist(2, 100);   //使用“填充構造函數”初始化一個有兩個100的鏈表mylistmylist.push_front(200);mylist.push_front(300);std::cout << "mylist中的內容是：";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it)std::cout << ' ' << *it;std::cout << '\n';return 0;
}

std::list::push_back

代碼示例1：push_back接口函數的使用

// list::push_back
#include <iostream>
#include <list>int main()
{std::list<int> mylist;int myint;std::cout << "請輸入一些整數（輸入 0 結束）:\n";do {std::cin >> myint;mylist.push_back(myint);} while (myint);std::cout << "mylist中存儲節點的個數為：" << mylist.size();return 0;
}

代碼示例2：push_back和emplace_back的區別

int main()
{/*------------------第一階段：創建一個“存儲內置類型變量”的list容器------------------*/list<int> lt1;//1.使用push_back進行尾插lt1.push_back(1);//2.使用emplace_back進行尾插//注意：區別 C++11新特性：就地構造，避免臨時對象（對基本類型效果相同）lt1.emplace_back(2);  lt1.emplace_back(3);lt1.emplace_back(4);for (auto it : lt1){cout << it << " ";}cout << endl; /*------------------第二階段：創建一個“存儲自定義類型變量”的list容器------------------*/list<A> lt2;              /*------------展示：push_back接口函數的使用------------*/cout << "=============展示：push_back接口函數的使用=============" << endl;cout << "情況1：" << endl;// 情況1：先構造對象，再push_back（調用1次構造+1次拷貝構造）A aa1(1, 1);                // 顯式構造A對象（調用構造函數）lt2.push_back(aa1);         // 尾插已構造的對象（調用拷貝構造）cout << "情況2：" << endl;// 情況2：直接push_back臨時對象（調用1次構造）lt2.push_back(A(2, 2));     // 尾插臨時對象（直接構造，效率更高）// 錯誤示例：push_back僅接受單個參數//lt2.push_back(3, 3);      // 錯誤！push_back僅接受單個參數/*------------展示：emplace_back接口函數的使用------------*/cout << "=============展示：emplace_back接口函數的使用=============" << endl;cout << "情況1：" << endl;// 情況1：emplace_back“已有對象”（等價于push_back，調用1次拷貝構造）A aa2(1, 1);lt2.emplace_back(aa2);      // 尾插對象（調用拷貝構造，等價于push_back(aa1)）cout << "情況2：" << endl;// 情況2：emplace_back“臨時對象”（與push_back臨時對象效果相同）lt2.emplace_back(A(2, 2));  // 尾插臨時對象（直接構造）cout << "情況3：" << endl;// C++11特性：emplace_back可直接傳遞構造參數，避免臨時對象// 情況3：emplace_back的核心優勢：直接傳遞構造參數（調用1次構造，無拷貝）lt2.emplace_back(3, 3);     // 無需創建臨時對象，直接在容器內存中構造對象return 0;
}

std::list::insert

// inserting into a list
#include <iostream>
#include <list>
#include <vector>int main()
{std::list<int> mylist;std::list<int>::iterator it;// set some initial values:for (int i = 1; i <= 5; ++i) mylist.push_back(i); it = mylist.begin();++it;      //注意：現在的迭代器指向節點2   /*-----------使用list容器的：“普通的指定位置插入”操作-----------*/mylist.insert(it, 10);                        // 1 10 2 3 4 5//                                                    ^//進行完“普通的指定位置插入”插入之后，it迭代器還是指向2/*-----------使用list容器的：“填充指定插入”操作-----------*/mylist.insert(it, 2, 20);                      // 1 10 20 20 2 3 4 5--it;                  //                                  ^//進行完“填充指定插入”操作之后，it迭代器還是指向2，但是--后現在的it迭代器指向第二個20//所以下面的“迭代器范圍插入”操作是在20的前面插入兩個30/*-----------使用list容器的：“迭代器范圍指定插入”操作-----------*/std::vector<int> myvector(2, 30);  //使用vector容器的“填充構造函數”初始化一個有兩個30的vector容器mylist.insert(it, myvector.begin(), myvector.end());  //使用list容器的“迭代器范圍指定插入”為list容器進行賦值// 1 10 20 30 30 20 2 3 4 5//                ^//進行完“迭代器范圍指定插入”操作之后，it迭代器還是指向20std::cout << "mylist中的內容是:";for (it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

std::list::pop_front

// list::pop_front
#include <iostream>
#include <list>int main()
{std::list<int> mylist;mylist.push_back(100);mylist.push_back(200);mylist.push_back(300);std::cout << "彈出 mylist 中的元素:";while (!mylist.empty()){std::cout << ' ' << mylist.front();mylist.pop_front();}std::cout << "\n最終mylist中節點的個數是：" << mylist.size() << '\n';return 0;
}

std::list::pop_back

// list::pop_back
#include <iostream>
#include <list>int main()
{std::list<int> mylist;int sum(0);mylist.push_back(100);mylist.push_back(200);mylist.push_back(300);while (!mylist.empty()){sum += mylist.back();mylist.pop_back();}std::cout << "mylist中所有節點的和為：" << sum << '\n';return 0;
}

std::list::erase

// erasing from list
#include <iostream>
#include <list>int main()
{/*-------------第一步：定義第一個list容器，并定義兩個迭代器-------------*/std::list<int> mylist;std::list<int>::iterator it1, it2;/*-------------第二步：對list容器的進行賦值-------------*/for (int i = 1; i < 10; ++i){mylist.push_back(i * 10);}/*-------------第三步：對list迭代器的進行賦值-------------*/// 10  20 30 40 50 60 70  80 90it1 = it2 = mylist.begin(); // ^^advance(it2, 6);            // ^                   ^++it1;                      //      ^              ^/*-------------第四步：使用list的erase接口-------------*//*-------使用list容器的：“普通的指定迭代器刪除”操作-------*///1.刪除it1指向的節點it1 = mylist.erase(it1);   // 10 30 40 50 60 70 80 90//    ^           ^//1.刪除it2指向的節點it2 = mylist.erase(it2);   // 10 30 40 50 60 80 90//    ^           ^++it1;                      //       ^        ^--it2;                      //       ^     ^/*-------使用list容器的：“迭代器范圍刪除”操作-------*/mylist.erase(it1, it2);     // 10 30 60 80 90//        ^//注：刪除[it1, it2)范圍內的元素(左閉右開區間)，即刪除40、50，但不刪除60std::cout << "mylist中的內容是:";for (it1 = mylist.begin(); it1 != mylist.end(); ++it1){std::cout << ' ' << *it1;}std::cout << '\n';return 0;
}

5. 其他的操作

函數聲明	接口說明
splice	將元素從一個 list 轉移到另一個 list
remove	刪除所有等于指定值的元素
remove_if	刪除滿足特定條件的元素（需傳入判斷條件）
unique	刪除相鄰的重復元素（可自定義去重規則）
merge	合并兩個已排序的 list（合并后仍保持有序）
sort	對 list 中的元素進行排序（可自定義排序規則）
reverse	反轉 list 中元素的順序

std::list::splice

// splicing lists
#include <iostream>
#include <list>int main()
{/*----------------第一階段：定義兩個“list的容器” + “list的迭代器”----------------*/std::list<int> mylist1, mylist2;std::list<int>::iterator it;/*----------------第二階段：為兩個list容器進行初始化----------------*/for (int i = 1; i <= 4; ++i){mylist1.push_back(i);      // mylist1: 1 2 3 4}for (int i = 1; i <= 3; ++i){mylist2.push_back(i * 10);   // mylist2: 10 20 30}/*----------------第三階段：為list的迭代器進行初始化----------------*/it = mylist1.begin();++it;                         //it -> 2（現在it指向的mylist1的節點2）/*----------------第四階段：展示splice接口函數的三種使用方式----------------*//*---------第一種使用方式：“整個列表”的拼接操作---------*/mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)           //注：將mylist2的所有元素轉移到mylist1的it位置前//注意: it 仍然指向2（轉移后成為第5個元素）/*---------第二種使用方式：“單個元素”的拼接操作---------*/mylist2.splice(mylist2.begin(), mylist1, it);  // mylist1: 1 10 20 30 3 4// mylist2: 2//注：將mylist1中it指向的元素(2)轉移到mylist2的開頭//注意: 轉移后it失效，因為原位置元素已被移除/*---------第三種使用方式：“元素范圍”的拼接操作---------*/it = mylist1.begin();std::advance(it, 3);           //it -> 30（現在it指向的mylist1的節點30）mylist1.splice(mylist1.begin(), mylist1, it, mylist1.end()); // mylist1: 30 3 4 1 10 20//注：將mylist1中[it, end)的元素轉移到自身開頭，轉移范圍: [30, end)，即30, 3, 4std::cout << "mylist1中的內容是:";for (it = mylist1.begin(); it != mylist1.end(); ++it) {std::cout << ' ' << *it;}std::cout << '\n';std::cout << "mylist2中的內容是:";for (it = mylist2.begin(); it != mylist2.end(); ++it){std::cout << ' ' << *it;}   std::cout << '\n';return 0;
}

std::list::remove

// remove from list
#include <iostream>
#include <list>int main()
{/*----------第一階段：使用“數組初始化列表 + 范圍構造”創建一個list容器----------*/int myints[] = { 17,89,7,14 };std::list<int> mylist(myints, myints + 4);/*----------第二階段：使用remove刪除list容器中“指定值”的節點----------*/mylist.remove(89);  //remove()會遍歷整個列表，刪除所有等于給定值的元素std::cout << "mylist中的內容是:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

std::list::remove_if

// list::remove_if
#include <iostream>
#include <list>//1. 函數對象（謂詞）：判斷數值是否為個位數（小于 10）
bool single_digit(const int& value) 
{ return (value < 10); 
}//2. 函數對象（謂詞）：判斷數值是否為奇數
struct is_odd 
{bool operator() (const int& value)  //注意：用結構體實現，需重載 operator()，使其能像函數一樣被調用{ return (value % 2) == 1; }
};int main()
{/*------------第一階段：使用“數組初始化列表 + 范圍構造”創建一個list容器------------*/int myints[] = { 15,36,7,17,20,39,4,1 };std::list<int> mylist(myints, myints + 8);//mylist：15 36 7 17 20 39 4 1/*------------第二階段：使用remove刪除list容器中“滿足條件”的節點------------*///1.第一次調用 remove_if：傳入函數名 single_digit 作為條件mylist.remove_if(single_digit);           //mylist：15 36 17 20 39//2.第二次調用 remove_if：傳入 is_odd 結構體的臨時對象 is_odd()mylist.remove_if(is_odd());               //mylist：36 20std::cout << "mylist中的內容是:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;} std::cout << '\n';return 0;
}

std::list::unique

// list::unique
#include <iostream>
#include <cmath>
#include <list>//1. 二元謂詞（函數形式）：判斷兩個浮點數的整數部分是否相同
bool same_integral_part(double first, double second)  //注意：用于 unique 的自定義去重邏輯，接收兩個 double 參數，返回 bool
{return (int(first) == int(second));
}//2. 二元謂詞（函數對象/仿函數形式）：判斷兩個浮點數的差值是否小于 5.0
struct is_near  //注意：用結構體實現，需重載 operator()，使對象能像函數一樣被調用
{bool operator() (double first, double second) {return (fabs(first - second) < 5.0); //用 fabs 計算絕對值，判斷差值是否小于 5.0}
};int main()
{/*------------第一階段：使用“數組初始化列表 + 范圍構造”創建一個list容器------------*/double mydoubles[] = { 12.15,  2.72, 73.0, 12.77, 3.14, 12.77, 73.35, 72.25, 15.3, 72.25 };std::list<double> mylist(mydoubles, mydoubles + 10);/*------------第二階段：展示unique不同的使用方法------------*///1.首先對list容器進行排序mylist.sort();             // 2.72,  3.14, 12.15, 12.77, 12.77,// 15.3,  72.25, 72.25, 73.0,  73.35//2.然后再使用unique刪除相鄰的重復元素/*----------第一種：“無參數”版本的unique----------*/mylist.unique();           // 2.72,  3.14, 12.15, 12.77// 15.3,  72.25, 73.0,  73.35/*----------第二種：“帶二元謂詞參數”版本的unique----------*/mylist.unique(same_integral_part);  // 2.72,  3.14, 12.15// 15.3,  72.25, 73.0mylist.unique(is_near());           //  2.72, 12.15, 72.25//  傳入 is_near() 臨時對象，刪除“差值小于 5.0”的連續元素//  邏輯：遍歷 list，若相鄰元素差值 < 5.0，則視為“重復”并刪除//  執行過程（基于上一步結果）：//  - 2.72 和 3.14：差值 0.42 < 5 → 刪除 3.14 → 保留 2.72//  - 2.72 和 12.15：差值 9.43 ≥ 5 → 保留 12.15//  - 12.15 和 15.3：差值 3.15 < 5 → 刪除 15.3 → 保留 12.15//  - 12.15 和 72.25：差值 60.1 ≥ 5 → 保留 72.25//  - 72.25 和 73.0：差值 0.75 < 5 → 刪除 73.0 → 保留 72.25//  最終內容：2.72, 12.15, 72.25std::cout << "mylist中的內容是:";for (std::list<double>::iterator it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

std::list::merge

// list::merge
#include <iostream>
#include <list>//自定義比較函數：僅比較浮點數的整數部分
bool mycomparison(double first, double second) //用于 merge 的自定義排序邏輯
{return (int(first) < int(second));
}int main()
{/*------------------第一階段：創建兩個list容器并進行初始化------------------*/std::list<double> first, second;first.push_back(3.1);first.push_back(2.2);first.push_back(2.9);second.push_back(3.7);second.push_back(7.1);second.push_back(1.4);/*------------------第二階段：展示merge不同的使用方法------------------*///1.首先對兩個list容器進行排序first.sort();  // sort 后 first： 2.2, 2.9, 3.1second.sort(); // sort 后 second：1.4, 3.7, 7.1/*----------使用“無自定義比較器”的merge操作----------*/first.merge(second); // 執行后 first：1.4, 2.2, 2.9, 3.1, 3.7, 7.1 // second 變為空（元素已被轉移）/*----------使用“帶自定義比較器”的merge操作----------*/second.push_back(2.1);first.merge(second, mycomparison);std::cout << "first鏈表中的內容是:";for (std::list<double>::iterator it = first.begin(); it != first.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

std::list::sort

代碼示例1：sort接口函數的使用

// list::sort
#include <iostream>
#include <list>
#include <string>
#include <cctype>//自定義比較函數：不區分大小寫的字符串比較
bool compare_nocase(const std::string& first, const std::string& second)
{unsigned int i = 0;while ((i < first.length()) && (i < second.length())) //只要兩個字符串中有一個字符串已經遍歷完畢while循環就結束{if (tolower(first[i]) < tolower(second[i])) return true; //注意：轉換為小寫后比較（不區分大小寫的字符串的比較）else if (tolower(first[i]) > tolower(second[i])) return false;++i;}return (first.length() < second.length()); //注意：如果所有已比較字符都相同，則較短的字符串排在前面
}int main()
{/*------------------第一階段：創建兩個list容器并進行初始化------------------*/std::list<std::string> mylist;std::list<std::string>::iterator it;mylist.push_back("one");mylist.push_back("two");mylist.push_back("Three"); //注意：插入三個字符串，包含大小寫不同的情況/*------------------第二階段：展示sort不同的使用方法------------------*//*----------使用“無自定義比較器”的sort操作----------*/// 第一次排序：使用默認比較（字典序，區分大小寫）// 默認規則下，大寫字母排在小寫字母之前// 排序結果：Three, one, twomylist.sort();std::cout << "使用“無自定義比較器”的sort排序后mylist中的內容是:";for (it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';/*----------使用“帶自定義比較器”的sort操作----------*/// 第二次排序：使用自定義比較函數 compare_nocase// 自定義規則：不區分大小寫，僅按字母順序和長度排序// 排序結果：one, Three, twomylist.sort(compare_nocase);std::cout << "使用“帶自定義比較器”的sort排序后mylist中的內容是:";for (it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

代碼示例2：sort接口函數的使用

#include <iostream>
#include <list>
using namespace std;int main()
{list<int> mylist;mylist.push_back(1);mylist.push_back(20);mylist.push_back(3);mylist.push_back(5);mylist.push_back(4);mylist.push_back(5);mylist.push_back(6);cout << "排序后mylist中的內容是:";for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){cout << ' ' << *it;}cout << '\n';/*---------------使用sort“默認的升序排序”---------------*///mylist.sort();  //sort() 方法使用元素類型的 operator< 進行比較/*---------------使用sort結合“仿函數實現：升序+降序”---------------*/// less<int> ls;        // 升序仿函數（默認）// greater<int> gt;     // 降序仿函數mylist.sort(greater<int>());   // 傳入降序仿函數，鏈表排序為: 20 6 5 5 4 3 1//注意：greater<int>() 返回一個函數對象，定義 a > b 的比較規則cout << "排序后mylist中的內容是:";for (list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){cout << ' ' << *it;}return 0;
}

std::list::reverse

// reversing list
#include <iostream>
#include <list>
#include <algorithm>int main()
{/*------------------第一階段：創建一個list容器并進行初始化------------------*/std::list<int> mylist;for (int i = 1; i < 10; ++i){mylist.push_back(i);}std::cout << "反轉前mylist中的內容是:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';/*------------------第二階段：展示list容器的兩種反轉方法------------------*//*-----------使用“list容器的成員函數”進行反轉-----------*///mylist.reverse(); //注意事項：//1.直接修改鏈表結構，交換每個節點的前后指針//2.時間復雜度 O(n)，高效且不需要額外空間/*-----------調用“STL中的反轉算法”進行反轉-----------*/reverse(mylist.begin(), mylist.end());//注意事項：//1.需要包含 <algorithm> 頭文件//2.此方法不適用于 list，因為 std::reverse 要求隨機訪問迭代器//3.而 list 僅提供雙向迭代器，編譯時會報錯std::cout << "反轉后mylist中的內容是:";for (std::list<int>::iterator it = mylist.begin(); it != mylist.end(); ++it){std::cout << ' ' << *it;}std::cout << '\n';return 0;
}

------------模擬實現展示------------

list容器存儲結構的設計

在 C++ 標準模板庫（STL）中，list容器的底層實現依托于數據結構中的 雙向鏈表，更具體地說，它采用的是帶頭節點的雙向循環鏈表結構。

• 這種設計使得 list 在元素插入、刪除等操作上具備高效性，且能靈活支持雙向遍歷。

---

具體來看，帶頭節點的雙向循環鏈表結構包含以下核心特點：

• 雙向性：每個節點除了存儲數據本身外，還包含兩個指針，這使得從任意節點出發都能便捷地向前或向后訪問其他節點。
  • 一個指向其前一個節點（前驅指針）
  • 一個指向其后一個節點（后繼指針）
• 循環性：鏈表的最后一個節點的后繼指針會指向頭節點，而頭節點的前驅指針則指向最后一個節點，形成一個閉環。
  • 避免了傳統非循環鏈表中 “尾節點后繼為空” 的邊界判斷問題
  • 簡化了鏈表操作的邏輯
• 頭節點：鏈表中存在一個不存儲實際數據的頭節點（哨兵節點），它作為鏈表的起始標記，統一了空鏈表與非空鏈表的操作方式。
  • 無論是插入、刪除還是遍歷，都無需額外處理鏈表為空的特殊情況
  • 提升了實現的簡潔性和魯棒性

正是基于這種底層結構，list容器能夠在任意位置以常數時間復雜度$O(1)$完成元素的插入和刪除操作（只需調整節點指針指向）

同時支持雙向迭代器遍歷，成為處理頻繁插入刪除場景的理想選擇。

/************************** 任務2.1：list節點類的定義 **************************/
template <class T>
struct list_node
{/*--------------------成員變量--------------------*///1.存儲數據//2.指向前一個節點的指針 //3.指向下一個節點的指針T _data;				list_node<T>* _prev;  //注意：類型是“類類型的指針”，但是list類又是模板類，所以類型應該是；list_node<T>*list_node<T>* _next;   /*--------------------成員函數：全缺省默認構造函數--------------------*/};

/************************** 任務2.3：list類的定義 **************************/template <class T>
class list
{
private:/*--------------------------第一部分：定義類型別名--------------------------*///重命名“list節點”的類型：list_node<T> ---> Nodetypedef list_node<T> Node;/*--------------------------第二部分：定義成員變量--------------------------*/Node* _head; //頭節點指針（指向不存儲有效數據的哨兵節點）size_t _size; //鏈表中有效元素的個數public:/*--------------------------第一部分：定義類型別名--------------------------*//*--------------------第一種情況：當我們使用的是“單模板參數 + 兩個迭代器模板”*/////1.重命名“普通迭代器（可讀可寫）”的類型：list_iterator<T> ---> iterator//typedef list_iterator<T> iterator;////2.重命名“常量迭代器（只讀）”的類型：list_iterator<T> ---> const_iterator//typedef list_const_iterator<T> cont_iterator;/*--------------------第二種情況：當我們使用的是“三模板那參數 + 一個迭代器模板”*///1.重命名“普通迭代器（可讀可寫）”的類型：list_iterator<T,T&,T*> ---> iteratortypedef list_iterator<T, T&, T*> iterator;//2.重命名“常量迭代器（只讀）”的類型：list_iterator<T,const T&, const T*> ---> const_iteratortypedef list_iterator<T, const T&, const T*> const_iterator;/*--------------------------第二部分：定義迭代器接口--------------------------*//*--------------------------第三部分：構造/賦值/析構--------------------------*//*--------------------------第四部分：容量相關的操作--------------------------*//*--------------------------第五部分：增刪改查的修改操作--------------------------*/};

頭文件：list.h

#pragma once//任務1：包含需要的頭文件
#include <iostream>
#include <assert.h>
#include <algorithm>
using namespace std;//任務2：定義自定義命名空間mySpace//任務2.1：實現list節點的類模板//任務2.2：實現list迭代器的類模板//任務2.3：實現list的類模板//任務2.4：實現print_container的函數模板namespace mySpace
{/************************** 任務2.1：list節點類的定義 **************************//*** @brief 雙向鏈表節點類* @tparam T 節點存儲的數據類型*		包含數據域_data，前驅指針_prev，后繼指針_next*		構造函數支持默認初始化，方便空節點創建*/template <class T>struct list_node{/*--------------------成員變量--------------------*/T _data;				//存儲數據list_node<T>* _prev;	//指向前一個節點的指針 ---> 注意：類型是“類類型的指針”，但是list類又是模板類，所以類型應該是；list_node<T>*list_node<T>* _next;    //指向下一個節點的指針/*--------------------成員函數：全缺省默認構造函數--------------------*/list_node(const T& data = T()) :  //注意：list_node類有三個成員變量，但是傳參時只傳一個，另外兩個用初始化列表的nullptr進行初始化_data(data),_prev(nullptr),_next(nullptr){}};/************************** 任務2.2：list迭代器類的定義 **************************//*** @brief 雙向鏈表迭代器模板（支持普通引用和指針）* @tparam T 迭代器操作的數據類型* @tparam Ref 數據的引用類型（T& 或 const T&）* @tparam Ptr 數據的指針類型（T* 或 const T*）*		實現迭代器的基本操作：解引用、指針運算符、自增自減、比較運算*/template <class T, class Ref, class Ptr>struct list_iterator{/*--------------------定義類型別名--------------------*///1.重命名“list節點”的類型：list_node<T> ---> Nodetypedef list_node<T> Node;//2.重命名“list迭代器”的類型：list_iterator<T,Ref,Ptr> ---> Selftypedef list_iterator<T, Ref, Ptr> Self;/*--------------------定義成員變量--------------------*/Node* _node; //迭代器內部存儲的節點指針，指向當前位置/*--------------------定義成員函數--------------------*///1.實現：“有參構造函數”list_iterator(Node* node) :_node(node){}//2.實現：“解引用運算符重載函數”Ref operator*()  //注意：返回節點數據的引用{return _node->_data;}//3.實現：“指針運算符重載函數”Ptr operator->() //注意：返回節點數據的指針{return &_node->_data;}//4.實現：“前置自增運算符的重載函數”Self& operator++() //注意：移動到下一個節點，返回自身引用{_node = _node->_next;return *this;}//5.實現：“前置自減運算符的重載函數”Self& operator--()  //注意：移動到前一個節點，返回自身引用{_node = _node->_prev;return *this;}//6.實現：“后置自增運算符的重載函數”Self operator++(int){//1.首先復制當前迭代器狀態Self tmp(*this);//2.其次移動到下一個位置_node = _node->_next;//3.最后返回舊位置的迭代器return tmp;}//7.實現：“后置自減運算符的重載函數”Self operator--(int){//1.首先復制當前迭代器狀態Self tmp(*this);//2.其次移動到前一個節點_node = _node->_prev;//3.最后返回舊位置的迭代器return tmp;}//8.實現：“等號運算符的重載函數”bool operator==(const Self& lt) const{return _node == lt._node;  //比較節點指針地址}//9.實現：“不等號運算符的重載函數”bool operator!=(const Self& lt) const{return _node != lt._node;}};///*--------------------------“非常量”迭代器的實現--------------------------*///template<class T>//struct list_iterator//{//	/*--------------------定義類型別名--------------------*///	//1.重命名“list節點”的類型：list_node<T> ---> Node//	typedef list_node<T> Node;//	//2.重命名“list迭代器”的類型：list_iterator<T> ---> Self//	typedef list_iterator<T> Self;//	/*--------------------定義成員變量--------------------*///	Node* _node;//	/*--------------------定義成員函數--------------------*///	//1.實現：“有參構造函數”//	list_iterator(Node* node)//		:_node(node)//	{}//	//2.實現：“*運算符的重載函數”//	T& operator*()//	{//		return _node->_data;//	}//	//3.實現：“->運算符的重載函數”//	T* operator->()//	{//		return &_node->_data;//	}//	//4.實現：“前置++運算符的重載函數”//	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	//5.實現：“前置--運算符的重載函數”//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	//6.實現：“后置++運算符的重載函數”//	Self operator++(int)//	{//		Self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	//7.實現：“后置--運算符的重載函數”//	Self& operator--(int)//	{//		Self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	//8.實現：“==運算符的重載函數”//	bool operator==(const Self& lt) const//	{//		return _node == lt._node;//	}//	//9.實現：“!=運算符的重載函數”//	bool operator!=(const Self& lt) const//	{//		return _node != lt._node;//	}//};///*--------------------------“常量”迭代器的實現--------------------------*///template<class T>//struct list_const_iterator//{//	/*--------------------定義類型別名--------------------*///	//1.重命名“list節點”的類型：list_node<T> ----> Node//	typedef list_node<T> Node;//	//2.重命名：“list迭代器”的類型：list_const_iterator<T> ---> Self//	typedef list_const_iterator<T> Self;//	/*--------------------定義類型別名--------------------*///	Node* _node;//	/*--------------------定義類型別名--------------------*///	//1.實現：“有參構造函數”//	list_const_iterator(Node* node)//		:_node(node)//	{}//	//2.實現“*運算符的重載函數”//	const T& operator*()//	{//		return _node->_data;//	}//	//3.實現：“->運算符的重載函數”//	const T* operator->()//	{//		return &_node->_data;//	}//	//3.實現：“前置++運算符的重載函數”//	Self& operator++()//	{//		_node = _node->_next;//		return *this;//	}//	//4.實現：“前置--運算符的重載函數”//	Self& operator--()//	{//		_node = _node->_prev;//		return *this;//	}//	//5.實現：“后置++運算符的重載函數”//	Self operator++(int)//	{//		Self tmp(*this);//		_node = _node->_next;//		return tmp;//	}//	//6.實現：“后置--運算符的重載函數”//	Self& operator--(int)//	{//		Self tmp(*this);//		_node = _node->_prev;//		return tmp;//	}//	//8.實現：“==運算符的重載函數”//	bool operator==(const Self& lt) const//	{//		return _node == lt._node;//	}//	//9.實現：“!=運算符的重載函數”//	bool operator!=(const Self& lt) const//	{//		return _node != lt._node;//	}//};/************************** 任務2.3：list類的定義 **************************//*** @brief 雙向循環鏈表模板類*		實現雙向循環鏈表的基本功能：插入、刪除、遍歷、拷貝構造、賦值運算符等*		使用帶頭結點的循環鏈表結構，頭節點不存儲有效數據，方便邊界處理*/template <class T>class list{private:/*--------------------------第一部分：定義類型別名--------------------------*///重命名“list節點”的類型：list_node<T> ---> Nodetypedef list_node<T> Node;/*--------------------------第二部分：定義成員變量--------------------------*/Node* _head; //頭節點指針（指向不存儲有效數據的哨兵節點）size_t _size; //鏈表中有效元素的個數public:/*--------------------------第一部分：定義類型別名--------------------------*//*--------------------第一種情況：當我們使用的是“單模板參數 + 兩個迭代器模板”*/////1.重命名“普通迭代器（可讀可寫）”的類型：list_iterator<T> ---> iterator//typedef list_iterator<T> iterator;////2.重命名“常量迭代器（只讀）”的類型：list_iterator<T> ---> const_iterator//typedef list_const_iterator<T> cont_iterator;/*--------------------第二種情況：當我們使用的是“三模板那參數 + 一個迭代器模板”*///1.重命名“普通迭代器（可讀可寫）”的類型：list_iterator<T,T&,T*> ---> iteratortypedef list_iterator<T, T&, T*> iterator;//2.重命名“常量迭代器（只讀）”的類型：list_iterator<T,const T&, const T*> ---> const_iteratortypedef list_iterator<T, const T&, const T*> const_iterator;/*--------------------------第二部分：定義迭代器接口--------------------------*///1.實現：“返回指向首元節點的普通迭代器” ----> 頭節點指向的第一個有效節點iterator begin(){///*---------方法一：有名對象---------*///iterator it = (_head->_next);//return it;///*---------方法二：匿名對象---------*///return iterator(_head->_next);/*---------方法三：隱式轉換---------*/return _head->_next;}//2.實現：“返回指向尾后位置的普通迭代器” ---> 頭節點iterator end(){return _head;}//3.實現：“返回指向首元節點的常量迭代器”const_iterator begin()const{return _head->_next;//return const_iterator(_head->_next);  // 顯式構造 const_iterator}//4.實現：“返回指向尾后位置的常量迭代器”const_iterator end()const{return _head;//return const_iterator(_head);  // 顯式構造 const_iterator}/*--------------------------第三部分：構造/賦值/析構--------------------------*///1.實現：“空鏈表初始化函數”void empty_init(){//1.動態創建list的頭節點_head = new Node;//2.初始化list的元素數量為0_size = 0;//3.初始化list的前驅后繼指針//3.1：初始化_prev指針 ---> 頭節點的next指向自己，構成空循環_head->_prev = _head;//3.2：初始化_next指針 ---> 頭節點的prev指向自己，構成空循環_head->_next = _head;}//2.實現：“默認構造函數”list(){empty_init();}//3.實現：“初始化列表構造函數”list(initializer_list<T> il){//1.首先初始化空鏈表empty_init();//2.循環遍歷初始化列表for (auto& it : il){//3.尾插遍歷的到的每一個元素push_back(it);}}//4.實現：“拷貝構造函數”list(const list<T>& lt){//1.初始化空鏈表empty_init();//2.遍歷原鏈表，逐個尾插元素  ---> （利用push_back實現深拷貝）for (auto& it : lt){push_back(it);}}//5.實現：“賦值運算符重載函數”list<T>& operator=(list<T> lt) //使用現代寫法{swap(lt);      //交換當前對象與臨時對象的數據return *this;  //返回當前對象（臨時對象會自動析構，釋放原資源）}//6.實現：“析構函數”~list(){//1.檢查if (_head){//2.清理clear();//3.釋放delete _head;//4.置空_head = nullptr;}}/*--------------------------第四部分：容量相關的操作--------------------------*/size_t size()const{return _size;}bool empty()const{return _size == 0;}/*--------------------------第五部分：增刪改查的修改操作--------------------------*///1.實現：“清空鏈表的操作”void clear()  //注意：釋放所有有效節點，不會釋放內存空間，保留頭節點{//1.獲取首元節點的迭代器auto it = begin();//2.使用迭代器循環遍歷每個節點并將其刪除掉（除了頭節點）while (it != end()){it = erase(it);   //注意：刪除當前節點，并獲取下一個節點的迭代器}}//2.實現：“交換兩個鏈表的函數”void swap(list<T>& lt){//1.交換頭節點指針std::swap(_head, lt._head);//2.交換鏈表的元素的個數std::swap(_size, lt._size);}//3.實現：“尾插操作的函數”void push_back(const T& x){/*-----------方法一：直接在list的尾部插入一個節點----------*//*-----------------第一步：創建一個節點-----------------*///Node* newNode = new Node(x);///*-----------------第二步：找到和插入節點相關的節點-----------------*/////2.1：頭節點：我們不用特意的找，已經擁有指向list頭節點的指針：_head////2.2：原尾節點：//Node* tail = _head->_prev;///*-----------------第三步：調整指針將新節點插入到：tail和_head之間-----------------*///tail->_next = newNode;//newNode->_prev = tail;//newNode->next = _head;//_head->_prev = newNode;///*------------第四步：更新節點的個數------------*///++_size;/*-----------方法二：間接調用insert在list的尾部插入一個節點----------*/insert(end(), x);	//在尾后位置（頭節點前）插入新元素}//4.實現：“頭插操作的函數”void push_front(const T& x){insert(begin(), x);  //在首元節點前插入新元素}//5.實現：“在指定位置之前插入節點的函數”iterator insert(iterator pos, const T& x){/*------------第一步：創建要插入的節點------------*/Node* newNode = new Node(x);/*------------第二步：找到和插入節點相關的節點------------*///2.1：獲取插入位置的節點Node* last = pos._node;//2.2：獲取插入位置之前的節點Node* first = last->_prev;/*------------第三步：調整指針將新節點插入到：first和last之間------------*/first->_next = newNode;newNode->_prev = first;newNode->_next = last;last->_prev = newNode;/*------------第四步：更新節點的個數并返回“新節點的迭代器”------------*/++_size;return iterator(newNode);}//6.實現：“尾刪操作的函數”void pop_back(){erase(--end());  //end()指向頭節點，--end()指向最后一個元素}//7.實現：“頭刪操作的函數”void pop_front(){erase(begin());  //直接刪除首元節點}//8.實現：“刪除指定位置的節點的函數”iterator erase(iterator pos){/*------------第一步：斷言檢查，不能刪除end()位置的節點的頭節點------------*/assert(pos != end());/*------------第二步：找到和刪除節點相關的節點------------*///2.1：獲取要刪除節點的前驅節點Node* first = pos._node->_prev;//2.2：獲取要刪除節點的后繼節點Node* last = pos._node->_next;/*------------第三步：調整前驅和后繼的指針，跳過待刪除節點------------*/first->_next = last;last->_prev = first;/*------------第四步：釋放待刪除節點------------*/delete pos._node;/*------------第五步：更新節點的個數并返回“后繼節點的迭代器”------------*/--_size;return iterator(last);}};/************************** 任務2.4：實現print_container的函數模板 **************************/template<class Container>void print_container(const Container& con){/*--------------方法一：使用迭代器進行遍歷list容器--------------*///1.首先定義一個常量迭代器typename Container::const_iterator it = con.begin();//2.然后再使用迭代器循環遍歷這個容器while (it != con.end()){//2.1：打印遍歷到的每個節點的值cout << *it << " ";//2.2：讓迭代器進行自增++it;}cout << endl;/*//--------------方法二：使用范圍for循環遍歷list容器--------------for (auto& it : con){cout << it << " ";}cout << endl;*/}}

/*-------------測試：list的“初始化列表”和“隱式類型轉換”的功能-------------*/
/*** 測試常量鏈表的遍歷* 接收一個常量list引用，驗證在只讀條件下能否正確遍歷元素*/
void func(const list<int>& lt) 
{// 調用打印函數，使用迭代器遍歷容器元素print_container(lt);
}void test_list5() 
{cout << "==========測試：list的“初始化列表”和“隱式類型轉換”的功能==========" << endl;// 直接構造方式：使用初始化列表顯式構造list對象// 調用list的initializer_list構造函數，將大括號內的元素依次插入鏈表list<int> lt1({ 1,2,3,4,5,6 });// 傳遞給接受常量引用的函數，驗證常量迭代器是否正常工作func(lt1);// 隱式類型轉換方式1：拷貝初始化// 使用賦值語法，但實際調用initializer_list構造函數// 編譯器自動將右側的初始化列表轉換為list<int>臨時對象，再拷貝構造lt2// 注意：如果list未定義initializer_list構造函數，此語句將無法編譯list<int> lt2 = { 1,2,3,4,5,6,7,8 };// 隱式類型轉換方式2：直接綁定到常量引用// 右側的初始化列表先轉換為list<int>臨時對象// 再將該臨時對象的生命周期延長到常量引用lt3的作用域// 臨時對象的生命周期將持續到當前代碼塊結束const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };// 測試函數調用時的隱式轉換// 實參直接使用初始化列表，編譯器自動轉換為list<int>臨時對象// 傳遞給接受常量引用的函數參數// 等價于 func(list<int>({1,2,3,4,5,6}));func({ 1,2,3,4,5,6 });// 驗證原始列表內容未被修改print_container(lt1);
}

測試文件：test.cpp

#include "list.h"namespace mySpace
{/************************** 測試用結構體 **************************/struct AA{int _a1 = 1;        // 成員變量，默認初始化為1int _a2 = 1;        // 成員變量，默認初始化為1};/************************** 測試函數 **************************//*-------------測試：list的“基本”的功能-------------*/void test_list01(){cout << "==========測試：list中存儲自定義類型的變量==========" << endl;list<AA> lt;lt.push_back(AA());lt.push_back(AA());lt.push_back(AA());lt.push_back(AA());cout << "使用迭代器遍歷list容器" << endl;//1.定義指向的list首元節點的迭代器list<AA>::iterator it = lt.begin();  //注意：迭代器類型的前面的域限定：list<AA>//2.使用迭代器循環遍歷整個list容器while (it != lt.end()){//1.訪問/*-----------第一種：使用“.運算符”訪問結構體成員-----------*///cout << (*it)._a1 << "," << (*it)._a2 << endl;/*-----------第二種：使用“->運算符”訪問結構體成員-----------*/cout << it->_a1 << "," << it->_a2 << endl;/*-----------第三種：使用“operator->()重載函數”訪問結構體成員-----------*///cout << it.operator->()->_a1 << "," << it.operator->()->_a2 << endl;//2.移動++it;}cout << endl;}/*-------------測試：list的“迭代器”的功能-------------*/void test_list02(){cout << "==========測試：list的“迭代器”的功能==========" << endl;list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << "鏈表初始內容為：" << endl;print_container(lt);cout << "使用迭代器遍歷并修改使每個元素都+10后：" << endl;list<int>::iterator it = lt.begin();while (it != lt.end()){*it += 10;cout << *it << " ";++it;}cout << endl;cout << "使用范圍for遍歷鏈表" << endl;for (auto e : lt){cout << e << " ";}cout << endl;}/*-------------測試：list的“插入和刪除”的功能-------------*/void test_list03(){cout << "==========測試：list的“插入和刪除”的功能==========" << endl;list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout << "鏈表初始內容為：" << endl;print_container(lt);/*----------------第一種的情況：list的頭插----------------*/cout << "在鏈表的首元節點的位置處插入10，然后再將原先的第一個元素+100后：" << endl;list<int>::iterator it = lt.begin();lt.insert(it, 10);   //注意：insert操作后迭代器不失效*it += 100;print_container(lt);/*----------------第二種的情況：list的任意插----------------*///1.獲取首元節點的迭代器it = lt.begin();//2.定義偏移量int k = 3;//3.使用while循環進行偏移while (k--){++it;   //移動迭代器到第4個元素（索引3，鏈表從0開始計數）}cout << "在索引為3的位置處插入30后：" << endl;lt.insert(it, 30);print_container(lt);cout << "刪除鏈表的中值為偶數的節點后：" << endl;it = lt.begin();while (it != lt.end()){if (*it % 2 == 0)  //注意：erase操作后迭代器失效，需正確處理{it = lt.erase(it);  //刪除偶數，返回下一個元素的迭代器}else{++it;}}print_container(lt);}/*-------------測試：list的“拷貝和賦值”的功能-------------*/void test_list04(){cout << "==========測試：list的“拷貝和賦值”的功能==========" << endl;list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);cout << "鏈表lt1為：" << endl;print_container(lt1);/*---------拷貝構造---------*/cout << "使用lt1拷貝構造的鏈表lt2為：" << endl;list<int> lt2(lt1);print_container(lt2);/*---------賦值操作---------*/list<int> lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);cout << "鏈表lt3為：" << endl;print_container(lt3);cout << "用lt3為鏈表lt1賦值后lt1為：" << endl;lt1 = lt3;print_container(lt1);}/*-------------測試：list的“初始化列表”的功能-------------*//*** 測試常量鏈表的遍歷*/void func(const list<int>& lt){print_container(lt);}void test_list05(){cout << "==========測試：list的“初始化列表”的功能==========" << endl;/*----------------直接構造方式：使用初始化列表顯式構造list對象----------------*/cout << "直接構造方式：list<int> lt1({ 1,2,3,4,5,6 });" << endl;list<int> lt1({ 1,2,3,4,5,6 });  //調用list的initializer_list構造函數，將大括號內的元素依次插入鏈表func(lt1);  //傳遞給接受常量引用的函數，驗證常量迭代器是否正常工作/*----------------隱式類型轉換方式1：拷貝初始化----------------*/cout << "隱式類型轉換方式1：list<int> lt2 = { 1,2,3,4,5,6,7,8 };" << endl;list<int> lt2 = { 1,2,3,4,5,6,7,8 };/** 使用賦值語法，但實際調用initializer_list構造函數*       1.編譯器自動將右側的初始化列表轉換為list<int>臨時對象*       2.再拷貝構造lt2*/func(lt2);/*----------------隱式類型轉換方式2：直接綁定到常量引用----------------*/cout << "隱式類型轉換方式2：const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };" << endl;const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };/**    1.右側的初始化列表先轉換為list<int>臨時對象*    2.再將該臨時對象的生命周期延長到常量引用lt3的作用域* 注：臨時對象的生命周期將持續到當前代碼塊結束*/func(lt3);//測試函數調用時的隱式轉換cout << "測試函數調用時的隱式轉換：func({ 1,2,3,4,5,6 })" << endl;func({ 1,2,3,4,5,6 });/**    1.實參直接使用初始化列表，編譯器自動轉換為list<int>臨時對象*    2.傳遞給接受常量引用的函數參數* 注：等價于 func(list<int>({1,2,3,4,5,6}));*/cout << "使用print_container函數分別打印這三個鏈表：" << endl;print_container(lt1);print_container(lt2);print_container(lt3);}
}/************************** 主函數：測試入口 **************************/
int main() 
{mySpace::test_list01();mySpace::test_list02();mySpace::test_list03();mySpace::test_list04();mySpace::test_list05();return 0;
}

運行結果：

------------核心問題深究------------

一、迭代器失效問題

1. list容器中哪些操作會導致迭代器失效？

在 C++ 中，list 是基于雙向鏈表實現的容器，其迭代器失效情況相對簡單，主要與刪除操作相關，插入操作一般不會導致迭代器失效 。

---

1. 刪除操作（erase）

當使用 list 的 erase 成員函數刪除元素時，僅指向被刪除節點的迭代器會失效，其他迭代器不受影響 。

• 核心原理：list 的底層是雙向鏈表，節點通過指針連接。

  • 刪除一個節點時，只會斷開該節點與前后節點的鏈接，其他節點的位置和指針不受影響。
  • 因此，只有指向被刪除節點的迭代器會因為所指節點被銷毀而失效，指向其他節點的迭代器仍能正常使用。

• 使用示例：

   list<int> mylist = {1, 2, 3, 4};auto it = mylist.begin(); // it 指向 1mylist.erase(it); // 刪除 1，it 失效// 此時，指向 2、3、4 的迭代器仍有效auto it2 = mylist.begin(); // it2 指向 2，可正常使用
  

• 解決方法：erase 函數會返回被刪除節點的后繼節點的迭代器，可利用該返回值更新失效的迭代器，繼續遍歷或操作

   list<int> mylist = {1, 2, 3, 4};auto it = mylist.begin();while (it != mylist.end()) {// 先通過 it++ 保存下一個節點的迭代器，再刪除當前節點it = mylist.erase(it); // it 現在指向被刪除節點的后繼，可繼續循環}
  

---

2. 插入操作（insert、push_front、push_back 等）

由于 list 是鏈表結構，插入新節點時，只需調整相鄰節點的指針，不會移動其他節點的位置

因此，插入操作不會導致任何迭代器失效（包括指向插入位置附近節點的迭代器）

• 使用示例：

  list<int> mylist = {1, 3, 4};
  auto it = mylist.begin();++it; // it 指向 3// 在 3 前插入 2，it 仍指向 3（節點 3 未被移動，指針未變）
  mylist.insert(it, 2); 
  // 遍歷結果：1 2 3 4，所有迭代器（包括原來指向 3 的 it）都有效
  

---

3. 清空操作 （clear）

• clear 會刪除 list 中所有元素，所有指向該 list 元素的迭代器都會失效（因為沒有元素可指向了）
• 調用 clear 后，若再使用之前的迭代器，會導致未定義行為

---

4. 賦值 / 交換操作 （assign、swap 等）

• assign：會替換 list 的內容，原 list 所有元素被刪除，原迭代器全部失效，需重新獲取新 list 的迭代器。
• swap：交換兩個 list 的內容后，原 list 的迭代器會指向另一個 list 的元素（邏輯上 “轉移” 了指向），若原 list 被銷毀或內容改變，需注意迭代器的有效性。

案例一：erase造成的迭代器失效

#include <iostream>
#include <list>
using namespace std;// 錯誤示例：迭代器失效問題
void TestListIterator01()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> lt(array, array + sizeof(array) / sizeof(array[0]));auto it = lt.begin();while (it != lt.end()){lt.erase(it);++it; //未定義行為：對失效迭代器進行遞增操作//錯誤分析：// erase會刪除it指向的節點，并使it失效// 失效的迭代器不能再進行++操作}
}// 正確示例：處理迭代器失效
void TestListIterator02()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> lt(array, array + sizeof(array) / sizeof(array[0]));auto it = lt.begin();while (it != lt.end()){/*-------方法1：利用后置++的特性-------*///lt.erase(it++);//正確分析：// it++ 返回舊值（當前有效迭代器）// erase刪除舊值指向的節點// it 被遞增為下一個有效節點/*-------方法2：顯式接收erase返回的迭代器-------*///it = lt.erase(it); // erase返回下一個有效迭代器}
}int main()
{//TestListIterator01();TestListIterator02();return 0;
}

二、反向迭代器實現問題

通過前面的例子可知：

• 反向迭代器的 ++ 操作，對應正向迭代器的 -- 操作
• 反向迭代器的 -- 操作，對應正向迭代器的 ++ 操作

基于此，反向迭代器的實現可借助正向迭代器來完成，具體來說：

反向迭代器內部可包含一個正向迭代器，通過對該正向迭代器的接口進行封裝、調整邏輯，就能實現反向迭代器的功能 。

//反向迭代器適配器：將正向迭代器轉換為反向迭代器
template<class Iterator>
class ReverseListIterator
{
private:Iterator _it;  //底層維護的正向迭代器public:/*--------------------------第一部分：定義類型別名--------------------------*///1.重命名“list正向迭代器中的引用類型”：Iterator::Ref ---> Reftypedef typename Iterator::Ref Ref;//2.重命名“list正向迭代器的指針類型”：Iterator::Ptr ---> Ptrtypedef typename Iterator::Ptr Ptr;//3.重命名“list反向迭代器”的類型：ReverseListIterator ---> Selftypedef ReverseListIterator<Iterator> Self;//注意：//1.此處typename的作用是明確告訴編譯器，Ref是“Iterator類中的類型”，而不是“靜態成員變量”//2.否則編譯器編譯時就不知道Ref是Iterator中的類型還是靜態成員變量//3.因為靜態成員變量也是按照 “類名::靜態成員變量名” 的方式訪問的/*--------------------------第二部分：定義成員變量--------------------------*///1.實現：“有參數構造函數”ReverseListIterator(Iterator it) : _it(it)  //用正向迭代器初始化反向迭代器{}//2.實現：“*運算符的重載函數”Ref operator*()  //注意：返回當前位置前一個元素的引用（反向迭代器的特性）{//1.創建臨時迭代器Iterator temp(_it);//2.前移一位（注意：這是正向迭代器的--）--temp;  //3.返回臨時迭代器的解引用return *temp; }//3.實現：“->運算符的重載函數”Ptr operator->()  //注意：返回當前位置前一個元素的指針{ return &(operator*());  //復用解引用運算符，取地址}//4.實現：“前置++運算符的重載函數”Self& operator++()  //（反向迭代器遞增 = 正向迭代器遞減）{--_it;   //注意：調整底層正向迭代器向前移動return *this;}//5.實現：“前置--運算符的重載函數”Self& operator--()  //（反向迭代器遞減 = 正向迭代器遞增）{++_it;   //注意：調整底層正向迭代器向后移動return *this;}//6.實現：“后置++運算符的重載函數”Self operator++(int){Self temp(*this);--_it;  //注意：（底層正向迭代器遞減）return temp;}//7.實現：“后置--運算符的重載函數”Self operator--(int) {Self temp(*this);++_it;  //注意：（底層正向迭代器遞增）return temp;}//8.實現：“==運算符的重載函數”bool operator==(const Self& lt) const{return _it == lt._it;  //比較底層正向迭代器}//8.實現：“!=運算符的重載函數”bool operator!=(const Self& lt) const { return _it != lt._it;  //比較底層正向迭代器}
};

三、vector和list的選擇問題

1. STL中的容器分為哪些種類？

C++ STL（標準模板庫）中的容器主要分為以下 三大類 ，每類都有獨特的特性和適用場景：

序列容器（Sequence Containers）

• vector（動態數組）
• list（雙向鏈表）
• deque（雙端隊列）
• forward_list（單向鏈表，C++11 新增）
• array（C++11 新增，固定大小數組）

---

關聯容器（Associative Containers）

• 基于紅黑樹（有序）
  • set（有序集合）
  • multiset（有序多重集合）
  • map（有序鍵值對映射）
  • multimap（有序多重鍵值對映射）
• 基于哈希表（無序)
  • unordered_set（無序集合）
  • unordered_multiset（無序多重集合）
  • unordered_map（無序鍵值對映射）
  • unordered_multimap（無序多重鍵值對映射）

---

容器適配器（Container Adapters）

• stack（棧，LIFO：后進先出）
• queue（隊列，FIFO：先進先出）
• priority_queue（優先隊列）

一、序列容器

序列容器：是元素按插入順序存儲，強調 “線性排列”，支持位置相關的插入、訪問操作。

---

1. vector（動態數組）：底層是動態分配的連續內存

• 優勢：
  • 尾部插入/刪除高效（push_back/pop_back 為 O(1) ）
  • 支持隨機訪問（通過下標 [] 或 at()，時間復雜度 O(1) ）
• 劣勢：
  • 中間和頭部插入/刪除 效率低（需移動元素，O(n) ）
  • 擴容時可能觸發內存重新分配（拷貝舊數據）
• 適用場景：需頻繁隨機訪問、尾部操作
  • 例如：存儲一組可按索引快速查詢的數據（如：游戲存檔列表）

---

2. list（雙向鏈表）：底層是雙向鏈表，節點通過指針連接，非連續內存

• 優勢：
  • 任意位置插入/刪除高效（只需調整指針，O(1) ）
  • 內存按需分配（無需預分配或擴容）
• 劣勢：
  • 不支持隨機訪問（需遍歷查找，O(n) ）
  • 額外存儲指針增加內存開銷
• 適用場景：需頻繁插入 / 刪除
  • 例如：實現 Undo/Redo 歷史記錄、鏈表結構的業務邏輯

---

3. deque（雙端隊列）：底層是分段連續內存，邏輯上視為連續，實際由多個緩沖區拼接

• 優勢：
  • 頭部和尾部插入/刪除高效（push_front/pop_front、push_back/pop_back 均為 O(1) ）
  • 也支持隨機訪問（但效率略低于 vector ）
• 劣勢：
  • 中間插入/刪除仍需移動元素（O(n) ），
  • 內存管理比 vector 復雜
• 適用場景：需頻繁在頭尾操作數據
  • 例如：實現隊列（queue 適配器默認用 deque 做底層）

---

4. forward_list（單向鏈表，C++11 新增）：底層是單向鏈表，僅支持正向遍歷

• 優勢：
  • 任意位置插入/刪除操作（除尾部外）效率與 list 相當
  • 比 list 更節省內存（少一個指針）
• 劣勢：
  • 不支持反向遍歷（無 rbegin/rend ）
  • 尾部操作需遍歷到末尾（效率低）
• 適用場景：內存敏感且只需正向遍歷的場景
  • 例如：簡單的單向鏈表結構

---

5. array（C++11 新增，固定大小數組）：底層是靜態數組（大小編譯期確定，不可擴容）

• 優勢：
  • 類型安全（替代原生數組）
  • 支持隨機訪問
  • 無動態擴容開銷
• 劣勢：
  • 大小固定（初始化后無法改變）
• 適用場景：需固定大小數組且希望用 STL 風格接口
  • 例如： begin/end 、迭代器等的場景

---

二、關聯容器

關聯容器：是元素按鍵自動排序或哈希組織，強調 “高效查找”，通常用于快速查詢、去重等場景。

• 常用容器底層多基于紅黑樹或哈希表

---

1. 基于紅黑樹（有序）

• set（有序集合）：存儲唯一鍵（key），按 key 自動按升序排序（默認用 < 比較，可自定義）
  • 核心特性：插入時自動去重，查找、插入、刪除均為 O(logn)（紅黑樹保證平衡）
  • 適用場景：需自動排序、去重的集合
    • 例如：存儲學生學號，保證無重復
• multiset（有序多重集合）：類似 set，但允許鍵重復（插入重復鍵時會保留，按序排列）
  • 核心特性：查找、插入、刪除仍為 O(logn)
  • 適用場景：需保留重復元素但需有序的場景
    • 例如：統計詞頻后按詞頻排序

++++++++++++++++++++++++++++++++++++++++++++

• map（有序鍵值對映射）：存儲唯一鍵值對（key-value ），按 key 自動升序排序
  • 核心特性：key 唯一，通過 key 查找 value 高效（O(logn) ）
  • 適用場景：常用于字典、配置映射等場景
    • 例如：存儲學生學號→姓名
• multimap（有序多重鍵值對映射）：類似 map，但允許鍵 key 重復（同一個 key 可對應多個 value ）
  • 核心特性：按 key 排序，查找、插入為 O(log n) ，
  • 適用場景：適用于一對多映射
    • 例如：存儲日期→當日事件列表

---

2. 基于哈希表（無序，C++11 新增，前綴 unordered_ ）

• unordered_set（無序集合）：底層是哈希表，存儲唯一鍵，不保證有序
  • 核心特性：平均查找、插入、刪除為 O(1)（哈希沖突時退化為 O(n) ），比 set 更高效（無需排序開銷）
  • 適用場景：需去重但無需排序的場景
    • 例如：統計網頁關鍵詞，只需存在性判斷
• unordered_multiset（無序多重集合）：類似 unordered_set，但允許鍵 key 重復

++++++++++++++++++++++++++++++++++++++++++++

• 核心特性：插入、查找平均 O(1)
• unordered_map（無序鍵值對映射）：底層是哈希表，存儲唯一 key-value，不保證有序
  • 核心特性：通過 key 查找 value 平均 O(1) ，是實際開發中替代 map 的高頻選擇
  • 適用場景：需去重但無需排序的場景
    • 例如：緩存系統、快速鍵值查詢
• unordered_multimap（無序多重鍵值對映射）：類似 unordered_map，但允許鍵 key 重復
  • 核心特性：平均操作 O(1)

三、容器適配器

容器適配器：是基于上述容器（序列容器為主）封裝接口，屏蔽部分功能、突出特定行為，簡化常用場景的使用。

---

1. stack（棧，LIFO：后進先出）：底層默認基于 deque（也可指定 vector 或 list ）

• 封裝接口：
  • push（入棧，默認調 push_back ）
  • pop（出棧，默認調 pop_back ）
  • top（訪問棧頂，默認調 back ）
• 適用場景：需后進先出邏輯
  • 例如：函數調用棧模擬、表達式求值

---

2. queue（隊列，FIFO：先進先出）：底層默認基于 deque（也可指定 list ）

• 封裝接口：
  • push（入隊，默認調 push_back ）
  • pop（出隊，默認調 pop_front ）
  • front/back（訪問隊首 / 隊尾）
• 適用場景：需先進先出邏輯
  • 例如：任務隊列、消息隊列

---

3. priority_queue（優先隊列）：底層默認基于 vector（用堆算法維護，邏輯上是完全二叉樹）

• 核心特性：元素按 “優先級” 自動排序（默認大頂堆，最大元素優先出隊；可自定義比較規則）
• 封裝接口：
  • push（插入后調整堆，O(log n) ）
  • pop（彈出堆頂，O(log n) ）
  • top（訪問堆頂，O(1) ）
• 適用場景：需按優先級處理任務
  • 例如：操作系統進程調度、事件驅動框架

2. STL容器怎么選？

總結（選型簡易指南）

• 隨機訪問 + 尾部操作 → vector
• 任意位置插入 / 刪除 → list
• 頭尾高效操作 → deque

---

• 自動排序 + 唯一鍵/鍵值對 → set/map
• 高效查找（無需排序） + 唯一鍵/鍵值對 → unordered_set/unordered_map

---

• 特定邏輯（棧 / 隊列 / 優先隊列） → 對應適配器（stack/queue/priority_queue ）

3. vector和list的核心差異有什么？

總結：分類對比展示 vector 和 list 的核心差異：

對比維度	vector（動態數組）	list（雙向鏈表）
底層結構	動態數組 （連續內存空間）	雙向帶頭循環鏈表 （非連續內存空間，節點包含前驅 / 后繼指針）
隨機訪問支持	支持 （通過下標 operator[] 或迭代器 +n，時間復雜度 $O(1)$）	不支持 （需從頭遍歷，時間復雜度 $O(n)$）
插入/刪除效率	尾部插入/刪除：$O(1)$（平均） 中間/頭部：$O(n)$（需移動元素）	任意位置插入 / 刪除：$O(1)$ （僅需修改指針，無需移動元素）
空間利用率	連續內存不易產生碎片，空間利用率高 緩存友好	節點動態開辟易產生碎片，空間利用率低 緩存友好度差
迭代器實現	直接使用原生態指針（如 T*）	對節點指針封裝（需維護雙向鏈表的 prev/next）
迭代器失效	插入可能觸發擴容 → 所有迭代器失效 插入/刪除非尾部元素時，后續迭代器失效	插入操作不會使其他迭代器失效 僅刪除操作會使指向被刪節點的迭代器失效
典型使用場景	1.元素需在內存中連續存儲 2.需頻繁隨機訪問 3.對插入/刪除效率要求低	1.需頻繁插入/刪除 2.無需隨機訪問 3.數據量動態變化且不確定大小

------------代碼片段剖析------------

片段一：list迭代器的模板參數為什么是三個？

template <class T, class Ref, class Ptr>
struct list_iterator
{/*--------------------定義類型別名--------------------*///1.重命名“list節點”的類型：list_node<T> ---> Nodetypedef list_node<T> Node;//2.重命名“list迭代器”的類型：list_iterator<T,Ref,Ptr> ---> Selftypedef list_iterator<T, Ref, Ptr> Self;/*--------------------定義成員變量--------------------*/Node* _node; //迭代器內部存儲的節點指針，指向當前位置/*--------------------定義成員函數--------------------*///1.實現：“有參構造函數”list_iterator(Node* node) :_node(node){}
}

在 C++ 標準庫中，list容器的迭代器模板參數設計為三個（通常是：T, Ref, Ptr），主要是為了支持 常量迭代器 和 非常量迭代器 的區分。

這種設計允許通過模板參數的不同組合，讓同一套迭代器代碼同時服務于普通迭代器和常量迭代器，避免代碼冗余。

---

核心原因解析：

1. 分離值類型、引用類型和指針類型

• 普通迭代器：需要返回T&和T*（可修改元素）
• 常量迭代器：需要返回const T&和const T*（不可修改元素）

通過三個模板參數，可以靈活指定引用和指針的常量性：

• Ref = T&，Ptr = T* 時，是普通迭代器。
• Ref = const T&，Ptr = const T* 時，是常量迭代器。

---

2. 避免代碼重復

如果不使用三個參數，需要為普通迭代器和常量迭代器分別編寫兩套幾乎完全相同的代碼

如下面使用傳統方式實現普通/常量迭代器的代碼中，list_iterator和list_const_iterator存在大量重復，但是通過模板參數化Ref和Ptr，可以復用同一套迭代器實現

/*----------------------傳統方式（代碼冗余）----------------------*/
// 普通迭代器
template <class T>
struct list_iterator 
{T& operator*() { /*...*/ }T* operator->() { /*...*/ }
};// 常量迭代器
template <class T>
struct list_const_iterator 
{const T& operator*() { /*...*/ }const T* operator->() { /*...*/ }
};/*----------------------模板參數優化方式----------------------*/
template <class T, class Ref, class Ptr>
struct list_iterator 
{Ref operator*()  // 可能是 T& 或 const T&{ return _node->_data; }  Ptr operator->() // 可能是 T* 或 const T*{ return &_node->_data; } 
};

---

3. 實現容器的const_iterator

當容器對象被聲明為const時，調用begin()/end()應返回常量迭代器：

const list<int> clst;auto it = clst.begin();  // 必須返回const_iterator

通過三個參數的模板設計，容器可以根據自身是否為const來實例化不同的迭代器類型：

template <typename T>
class list
{
public://using iterator = list_iterator<T, T&, T*>;//using const_iterator = list_iterator<T, const T&, const T*>;//1.重定義普通迭代器的類型：list_iterator<T, T&, T*> ---> iteratortypedef list_iterator<T, T&, T*> iterator;//2.重定義常量迭代器的類型：list_iterator<T, const T&, const T*> ---> const_iteratortypedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(head->_next);}const_iterator begin() const  // 關鍵：返回const_iterator{return const_iterator(head->_next);}
};

1. 為什么不能只用一個模板參數？

如果只使用T作為模板參數，迭代器內部無法區分返回值的常量性：

template <class T>
struct list_iterator
{T& operator*() // 無法適配const T&{return _node->_data;}
};

此時：若要支持常量迭代器，必須單獨編寫一個list_const_iterator類，導致代碼冗余。

---

總結：

三個模板參數的設計是 C++ 標準庫中實現迭代器的經典技巧。

通過分離值類型、引用類型和指針類型，在保持代碼復用的同時，優雅地區分 普通迭代器和常量迭代器。

這種設計使容器能夠根據使用場景自動選擇正確的迭代器類型，提供一致且安全的接口。

片段二：為什么要實現空鏈表的初始化函數?

//1.實現：“空鏈表初始化函數”
void empty_init()
{//1.動態創建list的頭節點_head = new Node;//2.初始化list的元素數量為0_size = 0;//3.初始化list的前驅后繼指針//3.1：初始化_prev指針 ---> 頭節點的next指向自己，構成空循環_head->_prev = _head;//3.2：初始化_next指針 ---> 頭節點的prev指向自己，構成空循環_head->_next = _head;
}//2.實現：“默認構造函數”
list()
{empty_init();
}//3.實現：“初始化列表構造函數”
list(initializer_list<T> il)
{//1.首先初始化空鏈表empty_init();//2.循環遍歷初始化列表for (auto& it : il){//3.尾插遍歷的到的每一個元素push_back(it);}
}//4.實現：“拷貝構造函數”
list(const list<T>& lt)
{//1.初始化空鏈表empty_init();//2.遍歷原鏈表，逐個尾插元素  ---> （利用push_back實現深拷貝）for (auto& it : lt){push_back(it);}
}

在實現雙向循環鏈表時，空鏈表初始化函數（如：empty_init()）的設計是一種常見的代碼復用策略，之所以使用它主要出于以下幾個原因：

---

1. 避免構造函數代碼重復

• 多個構造函數（如：默認構造函數、初始化列表構造函數、拷貝構造函數）都需要將鏈表初始化為空狀態。

• 如果不抽取公共邏輯，每個構造函數都要重復實現相同的初始化代碼。

  // 示例：若不使用empty_init()，默認構造函數需重復實現初始化
  list() 
  {_head = new Node;_size = 0;_head->_prev = _head;_head->_next = _head;
  }// 初始化列表構造函數也需重復相同代碼
  list(initializer_list<T> il) 
  {_head = new Node;_size = 0;_head->_prev = _head;_head->_next = _head;// ...后續代碼
  }
  

總結：通過抽取empty_init()，所有構造函數只需調用該函數一次，減少代碼冗余。

---

2. 保證初始化邏輯一致性

鏈表的空狀態有嚴格的定義：

• 頭節點的_prev和_next指針必須指向自身，形成循環
• 元素數量_size必須為 0

若分散在多個構造函數中實現，可能因疏忽導致某個構造函數的初始化邏輯不完整（如：忘記設置循環指針），引發難以調試的錯誤。

集中到一個函數中實現可以確保所有構造函數的初始化行為一致。

---

3. 便于維護和修改

如果后續需要調整空鏈表的初始化方式（如：添加新的成員變量初始化），只需修改empty_init()一處，而不必改動所有構造函數。

// 假設后續添加了一個新的成員變量_alloc用于內存分配
void empty_init() 
{_head = new Node;_size = 0;_alloc = std::allocator<T>();  // 新增初始化邏輯_head->_prev = _head;_head->_next = _head;
}

---

4. 支持拷貝操作的正確實現

• 在拷貝構造函數中，必須先將新對象初始化為空鏈表，再逐個插入原鏈表的元素：
• 若不調用empty_init()，直接插入元素會導致未初始化的頭節點指針指向隨機內存，引發崩潰。

list(const list<T>& lt) 
{empty_init();  // 關鍵：先初始化為空鏈表for (auto& it : lt) {push_back(it);}
}

片段三：怎么處理依賴名稱問題？

template<class Container>
void print_container(const Container& con)
{/*--------------方法一：使用迭代器進行遍歷list容器--------------*///1.首先定義一個常量迭代器typename Container::const_iterator it = con.begin();//2.然后再使用迭代器循環遍歷這個容器while (it != con.end()){//2.1：打印遍歷到的每個節點的值cout << *it << " ";//2.2：讓迭代器進行自增++it;}cout << endl;
}

在 C++ 模板編程中：

typename關鍵字：用于告訴編譯器某個 嵌套名稱 是一個類型，而非靜態成員或枚舉值

• 所以上面的代碼中，typename Container::const_iterator it 必須使用 typename

原因如下：

1. 依賴名稱與非依賴名稱的區分

在模板中，編譯器處理依賴名稱時需要特殊規則。

依賴名稱是指依賴于模板參數的名稱，例如：

• Container：是模板參數
• Container::const_iterator：是依賴于 Container 的嵌套名稱（所以這里的Container::const_iterator就是依賴名稱）

編譯器在實例化模板前，無法確定 Container::const_iterator 是一個類型、靜態成員變量還是枚舉值

---

2. 默認假設與顯式類型聲明

C++ 標準規定，默認情況下，依賴名稱不被視為類型

因此：如果不使用 typename，編譯器會將 Container::const_iterator 解釋為一個值（如：靜態變量或枚舉），而非類型。

Container::const_iterator it;           // 錯誤：默認假設const_iterator是靜態成員
typename Container::const_iterator it;  // 正確：顯式聲明const_iterator是類型

---

3. 編譯器實例化時的解析需求

模板在編譯時分為兩個階段：

1. 定義階段：編譯器只檢查語法，不實例化模板。此時無法確定 Container::const_iterator 的性質。
2. 實例化階段：當模板被調用（如：print_container(list<int>)）時，編譯器才知道 Container 的具體類型。

總結：使用 typename 是為了在定義階段解決類型解析的歧義，確保編譯通過。

---

4. 例外情況

• 只有當嵌套名稱是依賴類型時，才需要 typename ，例如：

template <typename T>
struct Example 
{static const int value = 42;  // 靜態成員變量typedef T type;               // 類型別名void func() {type x;        //不需要typename，因為type不依賴其他模板參數，type是Example的成員T::type* ptr;  //需要typename，因為T::type是依賴于模板參數 T 的嵌套名稱，編譯器默認不認為它是類型}
};

---

總結：

在上面的代碼中，typename Container::const_iterator it 的 typename 是必需的，因為：

• Container::const_iterator 是依賴于模板參數 Container 的嵌套名稱。
• 編譯器默認不將依賴名稱視為類型，需用 typename 顯式聲明。
• 這一規則確保模板在實例化前能正確解析類型，避免編譯錯誤。