一.介紹list同vector一樣都是容器list底層雙向循環(huán)鏈表由前驅(qū)指針、后繼指針和數(shù)據(jù)組成與vector不同于不是連續(xù)內(nèi)存vector是連續(xù)數(shù)組。優(yōu)點任意位置插入刪除元素時間復(fù)雜度為O1erase刪除時僅僅被刪除的節(jié)點迭代器失效其余迭代器依舊有效缺點不支持下標(biāo)訪問遍歷效率低二.list實現(xiàn)1.list構(gòu)造函數(shù)2.list iterator此處begin和end為正向迭代器反向還莫有學(xué)可進(jìn)行操作迭代器向后移。swap交換先給自己一個頭指針再把需要交換的頭指針給 給創(chuàng)建好的頭指針再把臨時對象tmp的新頭指針給原來的完成交換。為什么會有l(wèi)ist類和list iterator類list容器管整塊鏈表數(shù)據(jù)迭代器iterator專門管單個節(jié)點的訪問、遍歷分工完全不一樣必須拆成兩個類后者掌管1. 重載 * 解引用 *it 取出節(jié)點里存儲的數(shù)據(jù)T2. 重載 前置/后置自增 it 跳到下一個節(jié)點 _pNode _pNode-_pNext3. 重載 -- 自減往前遍歷上一個節(jié)點4. 重載 ! 判斷兩個迭代器是否指向同一個節(jié)點為什么要重載--相較于vector它空間是連續(xù)的1. vector迭代器本質(zhì)就是封裝的原生T*指針vector內(nèi)存連續(xù)原生指針天然支持 、 -- 、 n 、 [] 隨機偏移指針自增直接跳到下一個相鄰元素。所以不用手動重載 operator 、 operator-- 直接復(fù)用原生指針自帶的運算規(guī)則即可。2. list不能用裸指針做迭代器必須手動重載所有運算符list節(jié)點零散分布在堆上前后節(jié)點內(nèi)存地址并不挨著。單純對節(jié)點Node*做 只會走到這塊內(nèi)存后面隨機地址找不到下一個鏈表節(jié)點。只能手動寫重載一、為啥三個模板參數(shù)1. T 鏈表存的數(shù)據(jù)類型2. Ref 引用、 Ptr 指針用來一套代碼做出兩種迭代器- 普通迭代器 RefT、PtrT* 能讀寫數(shù)據(jù)- const迭代器 Refconst T、Ptrconst T* 只能讀不能改不用寫兩份重復(fù)代碼省事。3. Self 給自己這個迭代器類起短別名少寫長名字。二、各個函數(shù)為啥對應(yīng)不同類型1. Ref operator*() 解引用取值用Ref控制能不能修改元素2. Ptr operator-() 箭頭訪問成員用Ptr控制讀寫權(quán)限3. 拷貝構(gòu)造、運算符用 Self 指代迭代器本身類型書寫簡單方便鏈?zhǔn)竭\總代碼