文章目錄引入一、先看節(jié)點和遍歷邊界1.1 一個數(shù)據(jù)節(jié)點兩個方向1.2 空鏈表并不是沒有任何節(jié)點二、節(jié)點指針為什么需要包裝2.1 原始指針的操作與我們要的操作不同2.2 先忽略 const理解最小實現(xiàn)骨架三、逐個拆解運算符重載3.1 operator*返回引用才能修改真實元素3.2 operator-讓箭頭指向元素而不是節(jié)點3.3 前置 改變自身返回自身引用3.4 后置 保存舊副本再改變自身3.5 -- 同理但移動條件不同3.6 比較的是位置不是元素數(shù)值四、通過三個模板參數(shù)生成兩種迭代器4.1 為什么只用 T 不夠4.2 在 list 中填入兩組類型4.3 為什么不能簡單換成 list_iterator const T 4.4 begin / end 的 const 重載把類型連接到容器五、const 的三個位置含義各不相同六、節(jié)點操作和資源管理6.1 insert保存前驅(qū)再接上四條連接6.2 erase先保存后繼再刪除當(dāng)前節(jié)點6.3 拷貝構(gòu)造與賦值重載七、小結(jié)續(xù)接上篇list 的使用把節(jié)點、位置和操作聯(lián)系起來的綜合敘述上代碼倉庫《list測試與模擬實現(xiàn)》引入在學(xué)習(xí)了解過前面的容器后構(gòu)造、析構(gòu)、深拷貝和交換這些基礎(chǔ)操作已經(jīng)基本熟練不必再次深入。對于list與之前容器的最大不同之處就是其迭代器的實現(xiàn)同一個節(jié)點指針被包裝成類對象后怎樣獲得*it、it-成員、it這些表達(dá)式的含義怎樣復(fù)用移動邏輯卻讓不同迭代器獲得不同訪問權(quán)限一、先看節(jié)點和遍歷邊界1.1 一個數(shù)據(jù)節(jié)點兩個方向templateclassTstructlist_Node{T _data;list_NodeT*_next;list_NodeT*_prev;list_Node(constTxT()):_data(x),_next(nullptr),_prev(nullptr){}};list_Nodeint的_data是 元素數(shù)據(jù)兩個連接指向相同類型的節(jié)點。構(gòu)造全新的節(jié)點時先保存元素再將連接初始化為空只有插入鏈表后連接才代表真正的前后關(guān)系。1.2 空鏈表并不是沒有任何節(jié)點_head指向哨兵。空鏈表時_head-_next _head、_head-_prev _head元素數(shù)量為 0。非空時哨兵next指向首數(shù)據(jù)節(jié)點prev指向尾數(shù)據(jù)節(jié)點。因此begin包裝的是_head-_nextend包裝_head空鏈表中二者相等。哨兵節(jié)點的存在讓尾插能復(fù)用insert(end(),x)但end 只是邊界不允許讀取哨兵的_data。二、節(jié)點指針為什么需要包裝2.1 原始指針的操作與我們要的操作不同假設(shè)Node* p指向保存 10 的節(jié)點表達(dá)式原始 Node 指針希望迭代器提供的含義*p/*it整個節(jié)點對象元素 10 的引用p/it指針?biāo)阈g(shù)試圖前進(jìn)一個Node沿當(dāng)前節(jié)點的next找到后繼p-.../it-...訪問節(jié)點成員訪問元素對象的成員相等比較比較地址比較是否表示同一個節(jié)點位置節(jié)點各自分配不構(gòu)成供p做數(shù)組遍歷的連續(xù)Node數(shù)組。雙向鏈表節(jié)點內(nèi)存并不是連續(xù)的因此對原始的節(jié)點指針直接既不能表達(dá)“沿鏈接前進(jìn)”也不能拿計算出的地址當(dāng)作后繼節(jié)點訪問。所以需要一個類把節(jié)點指針存進(jìn)去再給操作定義合理的含義。這就是迭代器包裝。迭代器不擁有節(jié)點不在析構(gòu)時釋放節(jié)點vector 迭代器就是原生指針內(nèi)存連續(xù)直接指針?biāo)阈g(shù)即可。list 迭代器類封裝包裝節(jié)點指針重載operator內(nèi)部執(zhí)行_node _node-_next。2.2 先忽略 const理解最小實現(xiàn)骨架templateclassTstructsimple_iterator{list_NodeT*_node;simple_iterator(list_NodeT*p):_node(p){}Toperator*()const{return_node-_data;}simple_iteratoroperator(){_node_node-_next;return*this;}};it是迭代器對象it._node是它記錄的地址。復(fù)制it通常只是復(fù)制這個地址所以auto another it得到獨立的迭代器對象但兩者最初指向同一元素。隨后another改變another的地址成員不改變it也不復(fù)制鏈表。三、逐個拆解運算符重載以下代碼中的Self表示當(dāng)前這一種迭代器類型Ref表示解引用返回類型Ptr表示箭頭返回類型。3.1 operator*返回引用才能修改真實元素Refoperator*(){return_node-_data;}普通迭代器的Ref表示的是T。表達(dá)式*it調(diào)用it.operator*()返回節(jié)點里那個T對象的引用。因此*it 8能夠改變真實元素.如果返回T得到的是元素副本不能提供正常的可寫迭代器語義而且對復(fù)雜的類還可能發(fā)生一些不必要的復(fù)制。3.2 operator-讓箭頭指向元素而不是節(jié)點Ptroperator-(){return_node-_data;}當(dāng)元素是簡單的一個類 A有成員變量int _a1此時希望寫的是it-_a1而不是暴露_node-_data._a1。返回_node-_data得到元素指針編譯器對箭頭重載繼續(xù)應(yīng)用箭頭訪問最終將會通過這個真實指針來訪問成員。真實過程等價于//it 指向有效 A 元素。it-_a1;it.operator-()-_a1;(*it)._a1;3.3 前置 改變自身返回自身引用//前置Selfoperator(){_node_node-_next;return*this;}it調(diào)用無額外參數(shù)的operator。第一句沿鏈接改變it保存的地址第二句返回it自身的引用所以結(jié)果代表的是新位置。這里容易混淆的是*it與*this*itit是類對象調(diào)用重載operator*得到元素引用。*thisthis是指向當(dāng)前迭代器對象的真實指針使用內(nèi)置解引用得到的是迭代器對象本身。所以return *this不會遞歸調(diào)用元素解引用也不返回節(jié)點數(shù)據(jù)。正好匹配上了Self。3.4 后置 保存舊副本再改變自身//后置Selfoperator(int){Selftmp(*this);_node_node-_next;returntmp;}it調(diào)用帶int占位參數(shù)的版本。這個int只用于讓編譯器區(qū)分前置與后置沒有其它特殊含義。假設(shè)it指向 10next是 20執(zhí)行auto old it;Self old *this復(fù)制迭代器把“指向 10”的地址保存到另一個對象。修改it的地址使it指向 20。按值返回old使表達(dá)式結(jié)果仍表示原來的 10。3.5 – 同理但移動條件不同//前置--Selfoperator--(){_node_node-_prev;return*this;}//后置--Selfoperator--(int){Selftmp(*this);_node_node-_prev;returntmp;}前置--返回自身引用后置--返回舊副本。都沿prev移動。非空鏈表的end有最后一個元素作前驅(qū)所以可以先復(fù)制end再--begin沒有接口意義上的前驅(qū)所以不能--begin。寫法相應(yīng)成員調(diào)用改變 it 嗎返回什么itit.operator()是沿next改變后的it自身引用itit.operator(0)是沿next修改前的獨立副本--itit.operator--()是沿prev改變后的it自身引用it--it.operator--(0)是沿prev修改前的獨立副本3.6 比較的是位置不是元素數(shù)值booloperator!(constSelfs)const{return_node!s._node;}booloperator(constSelfs)const{return_nodes._node;}兩個節(jié)點都保存 5元素值相等但迭代器不相等。若錯誤地比較_data重復(fù)元素的存在就會破壞遍歷。不要隨意比較來自不同容器的迭代器。公開的接口只保證其規(guī)定比較域內(nèi)的行為。四、通過三個模板參數(shù)生成兩種迭代器4.1 為什么只用 T 不夠如果iterator始終返回T通過const容器仍能修改元素違背只讀訪問要求。若始終返回const T普通容器也失去可寫迭代器。初始做法是可以復(fù)制兩份類一份返回可寫類型一份返回只讀類型但其中、--、比較的代碼完全一樣造成了大量的代碼冗余而且如果后續(xù)需要修改的話還要改兩遍。下面則通過三個模板參數(shù)的配合實現(xiàn)了兩種迭代器的返回templateclassT,classRef,classPtrstructlist_iterator{typedeflist_NodeTNode;typedeflist_iteratorT,Ref,PtrSelf;//...T決定節(jié)點內(nèi)的元素類型Ref決定operator*返回什么Ptr決定operator-返回什么。鏈表的移動沿Node的鏈接進(jìn)行不依賴Ref與Ptr因此兩種可以共用。4.2 在 list 中填入兩組類型templateclassTclasslist{public:typedeflist_NodeTNode;typedeflist_iteratorT,T,T*iterator;typedeflist_iteratorT,constT,constT*const_iterator;//...這是代碼實現(xiàn)的核心下面暫時把T代為int參數(shù)或成員普通迭代器只讀迭代器完整類型list_iteratorint,int,int*list_iteratorint,const int,const int*TintintRefintconst intPtrint*const int*Nodelist_Nodeintlist_Nodeint_nodelist_Nodeint*list_Nodeint*解引用可修改元素的引用只讀元素引用/--修改迭代器的位置同樣可以修改迭代器的位置4.3 為什么不能簡單換成 list_iterator const T 如果把const放到節(jié)點的 T 上Node就會變成list_Nodeconst int它和list_Nodeint是兩種不同節(jié)點類型。我們要的不是把節(jié)點結(jié)構(gòu)換掉而是讓同一批節(jié)點得到不同的元素訪問接口。T 不變Ref 與 Ptr 加const正好表達(dá)這個需求。4.4 begin / end 的 const 重載把類型連接到容器iteratorbegin(){returniterator(_head-_next);}iteratorend(){returniterator(_head);}const_iteratorbegin()const{returnconst_iterator(_head-_next);}const_iteratorend()const{returnconst_iterator(_head);}非const容器調(diào)用非const begin得到iteratorconst容器只能調(diào)用const begin得到const_iterator。兩者都包裝同一個位置只是返回類型不同。五、const 的三個位置含義各不相同寫法能移動迭代器嗎能通過它修改元素嗎iterator it能能const_iterator cit能不能const iterator fixed不能能const const_iterator fixed_cit不能不能第三行最容易誤解const iterator只是一個不能改變地址成員的迭代器對象相當(dāng)于關(guān)注“位置固定”它的Ref仍然是T因此正常解引用仍能寫元素。const_iterator的類型則改變了Ref與Ptr相當(dāng)于關(guān)注“訪問只讀”?？梢灶惐戎羔樒胀╟onst_iterator的接口權(quán)限近似const T*而const iterator則近似與T* const。六、節(jié)點操作和資源管理6.1 insert保存前驅(qū)再接上四條連接//指定位置前插入數(shù)據(jù)iteratorinsert(iterator pos,constTx){Node*curpos._node;Node*newNodenewNode(x);cur-_prev-_nextnewNode;newNode-_prevcur-_prev;newNode-_nextcur;cur-_prevnewNode;_size;returnnewNode;}insert(end(), x)是尾插insert(begin(), x)是頭插?？真湵頃rprev和cur都是哨兵仍使用同一套步驟。6.2 erase先保存后繼再刪除當(dāng)前節(jié)點//刪除指定位置數(shù)據(jù)iteratorerase(iterator pos){assert(pos!end());Node*prevpos._node-_prev;Node*nextpos._node-_next;prev-_nextnext;next-_prevprev;deletepos._node;--_size;returnnext;}刪除以后不能再讀取cur-next所以提前保存next。assert則防止誤刪end6.3 拷貝構(gòu)造與賦值重載//初始化頭節(jié)點voidempty_init(){_headnewNode();_head-_prev_head;_head-_next_head;_size0;}//構(gòu)造函數(shù)list(){empty_init();}//拷貝構(gòu)造list(constlistTlt){empty_init();for(autoe:lt){push_back(e);}}//拷貝交換voidswap(listTlt){std::swap(_head,lt._head);std::swap(_size,lt._size);}listoperator(listTlt){swap(lt);return*this;}這里的賦值重載種按值參數(shù)other是副本不是源對象的引用。交換后本對象取得復(fù)制內(nèi)容other取得本對象舊節(jié)點函數(shù)結(jié)束時清理舊節(jié)點。自賦值也先復(fù)制再交換不會提前清空源。(與之前的string和vector一樣)七、小結(jié)理解這份實現(xiàn)時可以一直沿著同一個問題往下問這個表達(dá)式修改的是迭代器的位置、節(jié)點的連接還是節(jié)點中的元素分清這三層再把返回類型與模板參數(shù)對應(yīng)起來list的迭代器就不再是一組難記的符號。對照資料list 總覽與接口splice節(jié)點轉(zhuǎn)移、重載版本與時間復(fù)雜度merge有序歸并前提、源容器清空規(guī)則unique / remove / sortlist 專屬成員函數(shù)迭代器、引用失效規(guī)則與常見陷阱