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