目錄
1. 節點(list_node) 的結構
2. 哨兵位頭節點
3. list容器的成員變量
4. 插入/刪除操作
4.1?插入操作(insert)
4.2?刪除操作(erase)
5. 迭代器的實現
?6. 不同迭代器和const容器的限制
7. 重載operator->
8. 迭代器失效問題
insert操作
erase操作
9. 析構函數
10. 拷貝構造函數
11. 賦值運算符重載
傳統寫法
現代寫法
12. C++11引入的列表初始化
13. 總結
C++標準庫中的list底層是雙向循環鏈表,這是一種與vector(動態數組)完全不同的數據結構,核心特點是節點獨立存儲,通過指針連接,因此在插入/刪除操作上有獨特優勢。
1. 節點(list_node) 的結構
template<class T>
struct list_node
{T _data; // 存儲節點數據list_node<T>* _prev; // 正確:指向前一個節點list_node<T>* _next; // 正確:指向后一個節點// 節點構造函數(初始化數據和指針)list_node(const T& val = T()) : _data(val), _prev(nullptr), _next(nullptr) {}
};
2. 哨兵位頭節點
曾經實現單鏈表的時候,進行尾插操作,那么我們要判斷當前鏈表是否為空,如果鏈表為空,直接插入;如果鏈表不為空,找到尾節點再插入。為了簡化邊界判斷,list中會額外創建一個哨兵位頭節點(不存儲實際數據),整個鏈表形成雙向循環結構,鏈表為空時,哨兵位的_prev和_next都指向自己。
3. list容器的成員變量
list類內部只存儲兩個核心信息:
template<class T>
class list
{
private:list_node<T>* _head; // 指向哨兵位頭節點的指針size_t _size; // 記錄有效元素個數(非必需,但方便快速獲取大小)
};
4. 插入/刪除操作
list的插入/刪除操作遠高于vector,核心原因是:只需修改指針,無需移動元素。
4.1?插入操作(insert)
//在 pos 迭代器指向的節點前插入val
iterator insert(iterator pos, const T& val)
{Node* cur = pos._node; //pos 指向的節點Node* prev = cur->_prev; //pos 前一個節點Node* newnode = new Node(val);//創建新節點//調整指針: prev newnode cur newnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;++_size; //有效元素+1 return newnode; //返回指向新節點的迭代器
}
4.2?刪除操作(erase)
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node; //要刪除的節點Node* prev = cur->_prev; //前一個節點Node* next = cur->_next; //后一個節點//調整指針: prev cur nextprev->_next = next;next->_prev = prev;delete cur; //釋放節點內存--_size; //有效元素-1return next; //返回被刪除元素的下一個有效迭代器
}
5. 迭代器的實現
list迭代器本質是節點指針的封裝,通過重載++/--運算符實現遍歷。
//普通迭代器(可修改元素)
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; } // 返回非const引用,允許修改T* operator->() { return &_node->_data; } // 返回非const指針Self& operator++() { _node = _node->_next; return *this; }Self operator++(int) { Self temp(*this); _node = _node->_next; return temp; }Self& operator--() { _node = _node->_prev; return *this; }Self operator--(int) { Self temp(*this); _node = _node->_prev; return temp; }bool operator!=(const Self& s) const { return _node != s._node; }bool operator==(const Self& s) const { return _node == s._node; }
};
實現 list 的const迭代器(const_iterator)的核心目標是:允許遍歷元素但禁止通過迭代器修改元素的值,它的實現邏輯與普通迭代器(iterator)類似,需要通過修改解引用和箭頭運算符的返回類型來限制寫操作。
- 普通迭代器(iterator):解引用返回T&,箭頭運算符返回T*,允許通過迭代器修改元素(*it = value 或 it->member = value)。
- const迭代器(const_iterator):解引用返回const T&,箭頭運算符返回const T*,僅允許讀取元素,禁止修改(*it 和 it->member 都是只讀的)。
我們有兩種方式實現它:
方式1:
直接復制普通迭代器的代碼,僅修改operator*和operator->的返回類型,其余操作(++、--、比較等)完全復用,但是這種方式代碼冗余,重復代碼太多。
//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引用/指針,禁止修改元素const T& operator*() { return _node->_data; } // 只讀const T* operator->() { return &_node->_data; } // 只讀Self& operator++() { _node = _node->_next; return *this; }Self operator++(int) { Self temp(*this); _node = _node->_next; return temp; }Self& operator--() { _node = _node->_prev; return *this; }Self operator--(int) { Self temp(*this); _node = _node->_prev; return temp; }bool operator!=(const Self& s) const { return _node != s._node; }bool operator==(const Self& s) const { return _node == s._node; } };
方式2:
用模版參數復用代碼,將普通迭代器和const迭代器的共性代碼合并到一個模版中,僅通過參數控制是否為const。
template<class T, class Ref, class Ptr> //Ref: T& 或 const T&; Ptr: T* 或 const T* 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->_data; } // Ref為const T&時,返回只讀引用Ptr operator->() { return &_node->_data; } // Ptr為const T*時,返回只讀指針// 移動操作完全復用(與是否const無關)Self& operator++() { _node = _node->_next; return *this; }Self operator++(int) { Self temp(*this); _node = _node->_next; return temp; }Self& operator--() { _node = _node->_prev; return *this; }Self operator--(int) { Self temp(*this); _node = _node->_prev; return temp; }bool operator!=(const Self& s) const { return _node != s._node; }bool operator==(const Self& s) const { return _node == s._node; } };
list容器在定義普通迭代器和const迭代器這兩種具體類型時,主動明確地把它們的具體值(比如T&或const T&)傳給list_iterator模版,從而生成了“能改”和“不能改”兩種不同功能的迭代器。在list類提供const版本的begin()和end(),用于const對象的遍歷:
template<class T> class list { private:typedef list_node<T> Node;Node* _head; // 哨兵節點size_t _size;public://1.定義普通迭代器:Ref=T& Ptr=T* typedef list_iterator<T, T&, T*> iterator;//2.定義const迭代器:Ref=const T& Ptr=const T*typedef list_iterator<T, const T&, const T*> const_iterator;// 普通迭代器接口 iterator begin() { return _head->_next; } //第一個有效節點iterator end() { return _head; } //哨兵節點(尾后位置)// const迭代器接口(供const對象使用) const_iterator begin() const { return _head->_next; } //第一個有效節點const_iterator end() const { return _head; } //哨兵節點(尾后位置)// …… 其他成員函數(構造、push_back等,省略) };
遍歷打印元素
template<class Container> void print_container(const Container& con) {typename Container:: const_iterator it = con.begin(); //auto it = con.begin();while (it != con.end()){//*it += 10; 編譯錯誤:const_iterator禁止修改元素cout << *it << " "; //可以讀取++it;}cout << endl;for (auto e : con){cout << e << " ";}cout << endl; }
?6. 不同迭代器和const容器的限制
void test_list2(){list<int> lst = { 1,2,3 };//1. 普通迭代器 list<int>::iterator it = lst.begin();*it = 10;//合法:可修改元素++it;//合法:可移動迭代器//2. const迭代器(元素不可修改的迭代器)list<int> ::const_iterator cit = lst.begin();//*cit = 20; 報錯:不能修改元素 (const_iterator特性)++cit;//合法:可移動迭代器//3. const修飾迭代器(迭代器變量本身不可修改),【實際這種迭代器幾乎不用】//情況A:const修飾普通迭代器const list<int>::iterator const_it1 = lst.begin();*const_it1 = 30;//合法:普通迭代器仍可修改元素 但只能改第一個元素,使用場景極窄!//++const_it1; //報錯:迭代器變量本身不可移動 無法修改第二個、第三個元素//情況B:const修飾const_iterator(迭代器不可移動,元素也不可修改)const list<int>::const_iterator const_it2 = lst.begin();//*const_it2 = 40; //報錯:不能修改元素 //++const_it2; //報錯:迭代器本身不可移動cout << *const_it2; //只能讀第一個元素,使用場景極窄!//4. const容器 ->"容器的狀態不可變"->而容器的狀態不僅包括內部指針,還包括其管理的元素const list<int> const_lst = { 4,5,6 };list<int>::const_iterator clst = const_lst.begin(); //const容器只能返回const迭代器//*clst = 50; //報錯:const容器元素不可修改++clst; //合法:迭代器本身可移動//const_lst.push_back(7); //報錯:容器對象狀態不可改變(包括容器長度、節點數量、節點存儲的數據等), //push_back是非const的成員函數,const容器只能調用const成員函數,添加、刪除、清空元素同樣都不可以。}
7. 重載operator->
為什么要重載operator->呢?
假設鏈表存儲自定義對象,相當于鏈表的每一個節點存儲的都是對象。
struct Person
{string name;int age;
};list<Person> people; // 存儲Person對象的鏈表
當我們用迭代器it指向鏈表中的某個Person對象時,需要訪問其成員(如name或age),如果沒有重載operator->,訪問方式會是:
list<Person> lst; lst.push_back({ "張三", 20 }); auto it = lst.begin(); //迭代器,指向第一個Person對象(*it).name; //先解引用迭代器得到Person對象,再用.訪問成員
當寫*it時,本質是調用 it.operator*(),這個函數會通過迭代器的_node找到對應的鏈表節點,返回節點中_data的引用即(Person&類型),*it等價于 “迭代器所指向節點中的Person對象。
?operator->的重載邏輯
T* operator->() {return &_node->_data; // 返回指向節點中數據的指針 }
而有了operator->重載后,訪問方式可以簡化為:
list<Person> lst; lst.push_back({ "張三", 20 }); auto it = lst.begin(); //迭代器,指向第一個Person對象it->name; //迭代器用->訪問成員(看似一步,實則兩步)編譯器會自動拆解為(it.operator->())->name
編譯器會把 it->name;?這個表達式自動拆解為兩步:
- 第一步:顯示觸發重載操作,執行 it.operator->(),得到 Person* 指針(指向節點中存儲的Person對象的指針),取名叫 p。
- 第二步:再對 p 執行 “原生 -> 操作”:p->name(這一步是隱藏的,編譯器自動補全)。
總共 2 次-> 相關操作,其中第 2 次是編譯器按標準自動隱藏執行的,目的是讓迭代器用起來和原生指針一樣簡單。
不管是標準庫還是自定義的迭代器,只要正確重載了operator->,編譯器就會自動補充第二次->,這是C++標準規定的行為,目的是讓類類型的對象可以模擬指針的->操作。
這種設計的目的是讓迭代器的用法和原生指針完全一致,降低使用成本,如果編譯器不自動補充第二次->,用戶就必須寫成( it.operator->( ) ) -> name,不僅麻煩,還會讓迭代器和原生指針的用法脫節,違背了迭代器“模擬指針”的設計初衷。
8. 迭代器失效問題
在C++中,list的迭代器失效問題和vector 等連續內存容器有顯著區別,這源于list當節點式存儲結構(非連續內存)。
insert操作
插入元素時,只會在目標位置創建新節點,并調整相鄰節點的指針,不會改變原有任何節點的內存地址,因此,所有已存在的迭代器(包括插入位置的迭代器)都不會失效。
標準庫實現insert,返回值為指向新插入元素的迭代器,插入后可直接通過返回值操作新元素。【4.1插入操作】
list<int> lst = {1, 3, 4}; auto it = lst.begin(); // 指向1的迭代器 lst.insert(++it, 2); // 在3前插入2,lst變為{1,2,3,4} // 原it仍指向3(有效),新節點2的迭代器需通過insert返回值獲取
erase操作
刪除元素時,被刪除的節點會被銷毀,指向該節點的迭代器會失效;但其它節點的內存地址沒變,因此除了被刪除節點的迭代器外,其他所有迭代器仍然有效。
erase返回指向被刪除元素的下一個元素的迭代器,避免使用已失效的迭代器。【4.2刪除操作】
//刪除偶數 std::list<int> lst = {1, 2, 3, 4}; auto it = lst.begin(); while (it != lst.end()) {if (*it % 2 == 0) {//lst.erase(it);it已失效,不能再使用,下一次判斷會導致未定義行為it = lst.erase(it); //用返回值更新it(指向被刪元素的下一個)} else {++it; // 奇數不刪除則正常移動迭代器} } // 最終lst為{1,3}
9. 析構函數
第一種實現:
~list()
{Node* current = _head->_next; //從第一個有效節點開始遍歷while (current != _head){Node* nextNode = current->_next; //先保存下一個節點delete current; //銷毀當前節點current = nextNode; //移動到下一個節點}//銷毀哨兵節點delete _head;_head = nullptr; //重置大小_size = 0;cout << "鏈表已銷毀" << endl;
}
第二種實現:復用clear() 和 erase()
~list()
{clear();delete _head; //釋放哨兵節點_head = nullptr;_size = 0;cout << "鏈表已銷毀" << endl;
}void clear()
{auto it = begin();while (it != end()){it = erase(it); //復用erase邏輯刪除單個節點}
}
10. 拷貝構造函數
在鏈表中,必須手動實現拷貝構造函數,不能依賴編譯器默認生成的默認拷貝構造函數,核心原因是:編譯器默認的拷貝構造函數是淺拷貝,僅復制指針值,導致多個鏈表共享節點內存,引發雙重釋放、野指針等問題(原鏈表和拷貝出的新鏈表會共享同一份節點內存,當其中一個鏈表析構時,導致另一個鏈表的指針變成野指針,指向已釋放的內存,若對其中一個鏈表修改,會直接影響另一個鏈表,兩個鏈表析構時,會雙重釋放導致程序崩潰)。
手動實現拷貝構造函數需要完成深拷貝:為新鏈表創建獨立的節點,確保每個鏈表擁有自己的資源。
//空初始化 (創建獨立的哨兵節點_head,形成自循環,_size為0) void empty_init() {_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0; }//拷貝構造函數 lt2(lt1) list(const list<T>& lt) {empty_init(); //初始化新鏈表的基礎結構for (auto& e : lt){push_back(e);} }
11. 賦值運算符重載
傳統寫法
//賦值運算符重載(傳統寫法)
list<T>& operator=(const list<T>& lt)
{//處理自賦值(避免釋放自身資源后無法拷貝)if (this != <){//釋放當前鏈表所有節點clear();//從lt復制元素到當前鏈表for (auto& e : lt){push_back(e);}}return *this;//返回自身引用(支持連續賦值如a=b=c)
}
現代寫法
//交換兩個鏈表的成員
void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}//賦值運算符重載(現代寫法)
//利用拷貝構造函數創建臨時副本,再交換成員變量 lt1 = lt3
list<T>& operator=(list<T> lt) //形參lt是按值傳遞,調用拷貝構造函數創建lt3的臨時副本lt
{swap(lt); //交換當前對象與臨時副本的資源return *this; //臨時副本離開作用域自動析構
}//等價寫法
//list<T>& operator=(const list<T>& lt)
//{
// list<T> tmp(lt); //顯式調用拷貝構造函數創建lt的臨時副本
// swap(tmp);
// return *this;
//}
12. C++11引入的列表初始化
C++及以后標準中引入了列表初始化,使用方式:
std::list<int> lt{ 1,2,3,4 }; //等價于std::list<int> lt = { 1,2,3,4 }; std::list<int> lt2({1,2,3,4});//顯示傳參,語法較傳統
上面代碼執行過程:
- 當編譯器看到{1,2,3,4}這個花括號初始化列表時,會自動生成一個std::initializer_list<int>類型的臨時對象,并讓它“包裹”花括號里面所有的元素。(具體操作:編譯器會在棧上創建一個臨時的int數組,存儲1,2,3,4。)
- 調用std::list里面接收initializer_list<int>參數的構造函數,將步驟1創建的臨時對象作為實參傳遞給這個構造函數。
- std::list構造函數內部會遍歷這個臨時對象,創建鏈表節點。
- 當lt構造完成后,臨時對象和它指向的臨時數組自動銷毀。
像std::list、std::vector等標準容器都專門提供了接收initializer_list<T>參數的構造函數,對于自定義實現list,我們也想用這種方式初始化,就需要添加這個構造函數,例如:
template<typename T> class list { public://接收initializer_list的構造函數 list(initializer_list<T> il) {empty_init();for (auto& e : il){push_back(e);} }……};
13. 總結
namespace cat
{//定義節點的結構template<class T>struct list_node{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& data = T()):_data(data),_next(nullptr),_prev(nullptr){}};//實現迭代器來模擬指針template<class T, class Ref, class Ptr>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node; //成員變量 _node指針變量專門用于指向鏈表中的某個節點list_iterator(Node* node):_node(node) {}Ref operator*() //返回引用 *it = 100;{return _node->_data;}Ptr operator->() {return &_node->_data;}Self& operator++()//前置++ 指針++返回指針本身,迭代器++返回迭代器本身{_node = _node->_next;return *this;}Self operator++(int) //后置++(有int占位參數):先保存當前狀態,再移動,再返回原狀態{ //后置++不能返回引用,tmp是局部臨時對象,出了作用域會銷毀,如果返回引用,會導致懸垂引用問題(引用的對象已不存在)Self temp(*this); //保存當前迭代器 調用拷貝構造函數構造temp_node = _node->next;return temp; //返回原狀態}Self& operator--() {_node = _node->prev;return *this;}Self operator--(int){Self temp(*this);_node = _node->_prev;return temp;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}};//定義鏈表template<class T>class list{private:typedef list_node<T> Node;Node* _head; //指向哨兵節點size_t _size;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){/*iterator it(_head->_next);return it;*/ return _head->_next;//返回指向第一個元素節點的迭代器,函數返回的類型(Node*)和函數聲明的返回類型(iterator對象)不匹配//iterator類有單參數構造函數,支持隱式類型轉換,自動調用構造函數將_head->next作為參數,創建一個臨時的iterator對象//等價于return iteartor(_head->next); (顯示調用構造函數)}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}//空初始化void empty_init(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}//無參構造函數list(){empty_init();}list(initializer_list<T> il) //接收initializer_list<T>參數的構造函數{empty_init();for (auto& e : il){push_back(e);}}//拷貝構造函數 lt2(lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}//賦值運算符重載(現代寫法) lt1 = lt3list<T>& operator=(list<T> lt){swap(lt);return *this;}//析構函數~list(){clear();delete _head;_head = nullptr;cout << "鏈表已銷毀" << endl;}//清除元素void clear(){auto it = begin();while (it != end()){it = erase(it);}_size = 0; }//交換兩個鏈表的成員void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);} //尾插void push_back(const T& x){insert(end(), x);}//頭插void push_front(const T& x){insert(begin(), x);}//插入數據iterator insert(iterator pos, const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);//prev newnode curnewnode->_next = cur;newnode->_prev = prev;prev->_next = newnode;cur->_prev = newnode;++_size;return newnode;//返回指向新節點的迭代器}//刪除數據iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;//prev cur nextprev->_next = next;next->_prev = prev;delete cur;--_size;return next; //返回被刪除元素的下一個有效迭代器}//尾刪void pop_back(){erase(--end());}//頭刪void pop_front(){erase(begin());}size_t size() const{return _size;}//判空bool empty() const{return _size == 0;} };template<class Container>void print_container(const Container& con){typename Container:: const_iterator it = con.begin(); //auto it = con.begin();while (it != con.end()){//*it += 10;// error!cout << *it << " ";++it;}cout << endl;for (auto e : con){cout << e << " ";}cout << endl;}void test_list(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_container(lt);list<int> lt2 = { 1,2,3,4 };//調用接收initializer_list<int>參數的構造函數list<int> lt3({ 1,2,3,4 }); //同上const list<int>& lt4{ 1,2,3 }; //lt4是臨時對象的引用print_container(lt4);}