本文主要介紹list 的常用接口的使用實例具體的看官方文檔list文檔接著簡單模擬實現一個list更好的了解底層。1.list 的使用有了前面vector的使用再看list的使用就會比較簡單list底層是一個帶頭節點的雙向循環鏈表。1.1list的構造構造函數常用的接口代碼示例listint l1; listint l2(5, 1); listint l3(l2.begin(), l2.end()); listint l4(l3); listint l5 { 1,2,3,4,5 };賦值運算符重載常用接口代碼示例在已經有上面的構造l4 l5; l3 { 1,2,3,4,5 };析構函數的理解就比較簡單自己調用即可。1.2 list iterator 的使用這里暫時理解他底層還是指針該指針指向list的某個節點。說明上面四個迭代器都實現了const版本在調用的時候自動調用。begin與end為正向迭代器對迭代器執行操作迭代器向后移動。rbegin(end)與rend(begin為反向迭代器對迭代器執行操作迭代器向前移動。代碼示例auto it l5.begin(); while (it ! l5.end()) { cout (*it) ; it; } cout endl; auto rit l5.rbegin(); while (rit ! l5.rend()) { cout (*rit) ; rit; }1.3 list capacity1.4 list element access1.5 list modifiers上面函數接口直說明了一種情況還有更多的修改操作對應的看文檔。代碼示例:給出對應具體接口的使用情況// 創建listint容器l1包含3個元素每個元素初始值為1即 l1 {1,1,1} listint l1(3, 1); // 創建listint容器l2列表初始化元素為 1,2,3,4,5 listint l2 { 1,2,3,4,5 }; // assign區間賦值用l2的[begin,end)區間元素替換l1全部原有元素 //l1.assign(l2.begin(), l2.end()); // assign填充賦值把l1全部元素替換為5個1 //l1.assign(5, 1); // assign初始化列表賦值用{1,2,3,4,5}替換l1全部元素 //l1.assign({ 1,2,3,4,5 }); // 在l1容器尾部插入元素2 l1.push_back(2); // 在l1容器尾部插入元素2 l1.push_back(2); // 在l1容器頭部插入元素10 l1.push_front(10); // 在l1容器頭部插入元素10 l1.push_front(10); // 刪除l1容器尾部的一個元素 l1.pop_back(); // 刪除l1容器尾部的一個元素 l1.pop_back(); // 刪除l1容器頭部的一個元素 l1.pop_front(); // 刪除l1容器頭部的一個元素 l1.pop_front(); // find算法在l2的begin到end范圍內查找值等于3的迭代器位置pos auto pos find(l2.begin(), l2.end(), 3); // insert在迭代器pos位置前面插入單個元素100 //l2.insert(pos, 100); // insert在pos位置前面插入2個值為100的元素 //l2.insert(pos, 2,100); // insert在pos位置前面插入[l1.begin(), l1.end())區間內所有元素 //l2.insert(pos, l1.begin(), l1.end()); // insert在pos位置前面插入初始化列表{100,100}中的元素 //l2.insert(pos, { 100,100 }); // erase刪除迭代器pos指向的單個元素 //l2.erase(pos); // erase刪除[pos, l2.end())區間內所有元素 //l2.erase(pos, l2.end()); // swap交換l2和l1兩個list容器的全部內容效率很高只交換內部指針 //l2.swap(l1); // resize把l2容器大小調整為10多出的新位置填充值1 //l2.resize(10, 1); // resize把l2容器大小調整為2多余尾部元素直接刪除 //l2.resize(2); // clear清空l2容器所有元素size變為0 //l2.clear(); // splice拼接把整個l1容器所有元素移動到l2的pos迭代器位置之前l1變為空 //l2.splice(pos,l1); // splice拼接把l1中l1.begin()指向的單個元素移動到l2的pos位置之前 //l2.splice(pos, l1,l1.begin()); // remove刪除l2容器中所有值等于3的元素list自帶成員函數不是算法 //l2.remove(3); // reverselist成員函數反轉容器內部元素順序 l2.reverse(); // 獲取l2的起始迭代器 auto it l2.begin(); // 迭代遍歷迭代器不等于尾后迭代器就繼續循環 while (it ! l2.end()) { // 輸出迭代器指向的元素值后面跟空格 cout (*it) ; // 迭代器向后移動一位指向下一個元素 it; } // 輸出換行 cout endl;1.6迭代器失效的問題前面說過此處大家可將迭代器暫時理解成類似于指針迭代器失效即迭代器所指向的節點的無效即該節點被刪除了。因為list的底層結構為帶頭結點的雙向循環鏈表因此在list中進行插入時是不會導致list的迭代器失效的只有在刪除時才會失效并且失效的只是指向被刪除節點的迭代器其他迭代器不會受到影響。2.list 的模擬實現有了上面對list的使用基礎接下來模擬實現STL list的底層邏輯復刻源代碼的核心架構鏈表節點泛型迭代器雙向循環鏈表核心接口拷貝構造賦值重載析構函數有助于更好的了解底層。2.1 list底層存儲結構STLlist本質是帶頭結點的雙向循環鏈表存在一個哨兵頭結點head不存儲有效數據統一空鏈表和非空鏈表的操作邏輯。最后一個節點的next指向headhead的prev指向最后一個節點形成閉環。每個節點包含數據域、前驅指針、后繼指針。2.2整體代碼架構分析本次模擬實現分為三大核心架構1.list_node節點結構體封裝鏈表節點數據和指針2.list_iterator迭代器結構體封裝鏈表迭代器實現遍歷、加減、解引用等操作3.list容器類封裝鏈表所有對外接口、構造析構、增刪查改、拷貝賦值2.3鏈表節點list_node節點是鏈表的最小存儲單元采用泛型設計支持存儲任意類型數據。每個節點保存數據、前驅節點指針、后繼節點指針。template class T struct list_node { // 數據域 T _data; // 后繼節點指針 list_nodeT* _next; // 前驅節點指針 list_nodeT* _prev; // 構造函數初始化數據指針置空 list_node(const T x T()) :_data(x) , _next(nullptr) , _prev(nullptr) { } };采用默認構造參數T()支持無參創建節點適配空節點初始化場景。2.4迭代器list_iteratorlist 的迭代器和 vector 完全不同vector 迭代器是原生指針而 list 迭代器是封裝節點指針的自定義類型。因為鏈表節點不連續無法通過指針偏移實現遍歷必須封裝迭代器行為。采用三模板參數設計同時支持普通迭代器和 const 迭代器T節點數據類型Ref:數據引用類型T/const TPtr:數據指針類型T* / const T*template class T,class Ref,class Ptr struct list_iterator { // 類型重定義簡化代碼 typedef list_nodeT Node; typedef list_iteratorT, Ref,Ptr Self; // 迭代器本質封裝一個節點指針 Node* _node; // 構造函數通過節點指針構造迭代器 list_iterator(Node* node) :_node(node) { } // 解引用返回節點數據引用 Ref operator*() { return _node-_data; } // - 重載返回數據指針支持迭代器-成員訪問 Ptr operator-() { return (_node-_data); } // 前置指向后繼節點 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 it) { return _node ! it._node; } bool operator(const Self it) const { return _node it._node; } };迭代器的移動本質是節點指針的跳轉operator-重載支持it-xxx訪問自定義類型成員符合 STL 規范區分前置/后置自增自減適配不同遍歷場景2.5list容器核心類容器類對外提供所有接口封裝底層節點和迭代器對用戶屏蔽底層指針操作符合STL std::list 使用方式。1.類型從定義和迭代器接口為了后續接口使用的方便對接點類型typedef,同時保持迭代器接口的一致性對普通迭代器結構體typedef成iterator,const迭代器結構體typedef成const_iteratortemplate class T class list { typedef list_nodeT Node; public: // 普通迭代器、const迭代器類型重定義 typedef list_iteratorT,T,T* iterator; typedef list_iteratorT, 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); } }2.初始化和構造函數空鏈表初始化是核心創建哨兵頭結點讓頭結點自環next和prev都指向自身。// 空鏈表初始化 void empty_init() { _head new Node; _head-_next _head; _head-_prev _head; } // 默認構造 list() { empty_init(); } // 拷貝構造深拷貝 list(const listT lt) { empty_init(); // 遍歷原鏈表逐個尾插數據 for (const auto e : lt) { push_back(e); } } // 初始化列表構造支持 list{1,2,3,4} list(initializer_listT il) { empty_init(); for (const auto e : il) { push_back(e); } }構造函數主要實現了 默認構造拷貝構造和初始化列表構造拷貝構造實現深拷貝新鏈表獨立開辟節點和原鏈表內存完全隔離避免淺拷貝析構重復釋放問題上面復用的接口push_back在后面會給出具體代碼。3.賦值重載采用傳值交換法實現賦值重載代碼簡潔且天然解決自賦值問題。// 交換兩個鏈表的頭結點指針 void swap(listT lt) { std::swap(_head, lt._head); } // 賦值重載現代寫法 listT operator(listT lt) { swap(lt); return *this; }原理傳入參數為臨時拷貝交換當前對象和臨時對象的頭指針當前對象接管臨時對象的有效數據臨時對象析構時自動釋放舊數據。4.析構函數和清空鏈表接口// 清空所有有效節點 void clear() { auto it begin(); while (it ! end()) { iterase(it); } } // 析構函數 ~list() { // 清空有效節點 clear(); // 釋放哨兵頭結點 delete _head; _head nullptr; }5.核心的增刪接口插入insert和刪除(erase)接口的實現和數據結構的雙向循環鏈表的實現一樣修改對應的指針即可。所有頭尾插入刪除接口全部復用insert和erase核心接口減少代碼冗余統一邏輯。// 任意位置插入節點 iterator insert(iterator pos, const T val) { Node* cur pos._node; // 創建新節點 Node* newnode new Node(val); // 調整指針指向 newnode-_next cur; newnode-_prev cur-_prev; cur-_prev-_next newnode; cur-_prev newnode; return iterator(newnode); } // 任意位置刪除節點 iterator erase(iterator pos) { Node* cur pos._node; Node* next cur-_next; // 跳過當前節點重構鏈表連接 cur-_prev-_next cur-_next; cur-_next - _prev cur-_prev; // 釋放節點內存 delete cur; // 返回下一個有效迭代器 return iterator(next); } // 尾插 void push_back(const T x) { insert(end(), x); } // 頭插 void push_front(const T x) { insert(begin(), x); } // 尾刪 void pop_back() { erase(--end()); } // 頭刪 void pop_front() { erase(begin()); }本次模擬實現list的底層原理更好的理解的list 的底層邏輯同時厘清了自定義迭代器的實現原理對比原生指針。3.模擬實現的完整代碼#pragma once namespace gxy { // 鏈表節點結構體 template class T struct list_node { T _data; list_nodeT* _next; list_nodeT* _prev; list_node(const T x T()) :_data(x) ,_next(nullptr) , _prev(nullptr) { } }; // 迭代器結構體 template class T,class Ref,class Ptr struct list_iterator { typedef list_nodeT Node; typedef list_iteratorT, Ref,Ptr Self; Node* _node; list_iterator(Node* node) :_node(node) { } Ref operator*() { return _node-_data; } Ptr operator-() { return (_node-_data); } 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 it) { return _node ! it._node; } bool operator(const Self it) const { return _node it._node; } }; // list 容器類 template class T class list { typedef list_nodeT Node; public: typedef list_iteratorT,T,T* iterator; typedef list_iteratorT, 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_init() { _head new Node; _head-_next _head; _head-_prev _head; } list() { empty_init(); } list(const listT lt) { empty_init(); for (const auto e : lt) { push_back(e); } } list(initializer_listT il) { empty_init(); for (const auto e : il) { push_back(e); } } void swap(listT lt) { std::swap(_head, lt._head); } listT operator(listT lt) { swap(lt); return *this; } ~list() { clear(); delete _head; _head nullptr; } void clear() { auto it begin(); while (it ! end()) { iterase(it); } } bool empty() { return begin() end(); } void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } iterator insert(iterator pos, const T val) { Node* cur pos._node; Node* newnode new Node(val); newnode-_next cur; newnode-_prev cur-_prev; cur-_prev-_next newnode; cur-_prev newnode; return iterator(newnode); } iterator erase(iterator pos) { Node* cur pos._node; Node* next cur-_next; cur-_prev-_next cur-_next; cur-_next - _prev cur-_prev; delete cur; return iterator(next); } private: Node* _head; }; }