第C++初階之list的模擬實(shí)現(xiàn)過程詳解我們主要看看sort函數(shù)

sort函數(shù)在官方庫中是用快排寫的，其中快排的精髓就是三數(shù)取中的優(yōu)化操作。

sort默認(rèn)是排升序如果想排降序需要使用functional文件中的greater()這個(gè)模板函數(shù)，我們以vector來舉例。

對(duì)于list，我們極度不推薦使用algorithm文件中的sort函數(shù)，上文提到了sort函數(shù)是使用的快速排序的手段進(jìn)行排序的，而其關(guān)鍵在于三數(shù)取中這樣的操作，那么三數(shù)取中這樣的操作只有在內(nèi)存連續(xù)的數(shù)據(jù)結(jié)構(gòu)中才能操作，如果給你一個(gè)head，給你一個(gè)tail，你如果能找到中間的結(jié)點(diǎn)？很明顯是很復(fù)雜的。

我們這里list迭代器是不支持隨機(jī)訪問，他不是隨即迭代器。

而vectorstring這樣的迭代器是支持隨機(jī)訪問的，所以他們用快排很有優(yōu)勢(shì)。

我們可以看到這三個(gè)函數(shù)的迭代器是不同的，它們是繼承關(guān)系，隨機(jī)的支持雙向，雙向支持單向，反過來就不行。

當(dāng)然除了這幾種迭代器，還有輸入輸出迭代器，也叫可讀可寫迭代器，他們是最弱的迭代器，一個(gè)單向迭代器都可以支持可讀可寫的功能。也就是說，可讀可寫迭代器在繼承的最上端。所有人都包含了他倆。

但是雖然他們功能很弱，但他們?cè)谝恍┲匾奶匦陨嫌兄陵P(guān)重要的作用，那就是迭代器的萃取。這個(gè)和復(fù)雜，暫時(shí)不去管它們。

總結(jié)上面兩段話：

當(dāng)我們使用迭代器遍歷的時(shí)候，我們需要知道的是，begin（）代表了第一個(gè)結(jié)點(diǎn)，end（）代表了頭結(jié)點(diǎn)。

這里再穿插一個(gè)小知識(shí)，我們?cè)俟俜轿臋n中總能看到max_size這樣的變量，

它的意義是整形的最大值除以一個(gè)節(jié)點(diǎn)的大小，也就是得出的節(jié)點(diǎn)個(gè)數(shù)

無符號(hào)整形最大是2^32-1，也就是42億多，對(duì)于int類型的vector，就是42億除以4得到的值，對(duì)于list，就是42億除以三個(gè)指針的大小得到的值。

我們還知道再vector中，我們?cè)趇nsert的擴(kuò)容插入，還有erase的刪除時(shí)，會(huì)導(dǎo)致迭代器失效的問題。那么對(duì)于list我們還要去關(guān)注迭代器失效的問題嗎？

我們?cè)賗nsert的時(shí)候，插入數(shù)據(jù)并不會(huì)影響到其他的數(shù)據(jù)的地址，只是影響鏈接的關(guān)系，所以不會(huì)引起迭代器失效

但是對(duì)于erase，當(dāng)我們刪除對(duì)應(yīng)的結(jié)點(diǎn)之后，他會(huì)變成野指針。所以我們erase的時(shí)候通常去接收它的返回值，也就是下一個(gè)結(jié)點(diǎn)的迭代器。

當(dāng)然庫中還有一些我們不常用的函數(shù)

splice接合函數(shù)，把一個(gè)list的數(shù)據(jù)轉(zhuǎn)移到另一個(gè)list

這里不是拷貝，是轉(zhuǎn)移。

還有remove，找到就刪，沒找到就沒什么反應(yīng)。

unique去重，這里又一個(gè)小小的bug，只有連續(xù)的重復(fù)數(shù)據(jù)才會(huì)刪除。

聰明的同學(xué)會(huì)反應(yīng)過來，這里sort+unique可以解決這樣的問題。當(dāng)然沒反應(yīng)過來的同學(xué)也很聰明。

這里顯然還是那個(gè)問題，我們不建議堆鏈表進(jìn)行排序，效率是很低的。

list的成員函數(shù)是用的歸并排序。為什么不用algorithm中的sort快排呢？原因我們上文已經(jīng)解釋過了。

說了這么多，來看看代碼吧。

先來看看頭文件吧！

#pragmaonce

#includeiostream

#includealgorithm

#includefunctional

usingnamespacestd;

namespaceLL

我們先寫結(jié)點(diǎn)類，這里用類模板，并且是用struct實(shí)現(xiàn)，默認(rèn)內(nèi)容是公開的,其他的類都可以調(diào)用

templateclassT

其中結(jié)點(diǎn)類中要有三個(gè)變量，一個(gè)存值，兩個(gè)指針

struct_list_node

T_val;

_list_nodeT*_next;

_list_nodeT*_prev;

結(jié)點(diǎn)類中除了要有三個(gè)變量，還需要有一個(gè)構(gòu)造函數(shù)。當(dāng)我們定義一個(gè)新結(jié)點(diǎn)的時(shí)候，進(jìn)行構(gòu)造函數(shù)初始化

我們這里的參數(shù)是一個(gè)缺省的val值，其中缺省參數(shù)給的是匿名構(gòu)造函數(shù)。最好以const接收。

_list_node(constTval=T())

:_val(val)

,_next(nullptr)

,_prev(nullptr)

這里實(shí)現(xiàn)迭代器類。首先我們依舊是使用類模板，我們這里給三個(gè)模板參數(shù)，同時(shí)類還是用struct來實(shí)現(xiàn)

在迭代器類中，我們主要實(shí)現(xiàn)1、構(gòu)造2、解引用操作3、！=和==操作3、前置++后置++--操作

templateclassT,classRef,classPtr這里三個(gè)模板參數(shù)是什么意思呢當(dāng)我們需要const迭代器和非const迭代器的時(shí)候我們可以根據(jù)第二個(gè)參數(shù)的不同來實(shí)例化出不同的迭代器，就不需要寫兩個(gè)迭代器了

typedef_list_iteratorT,T,T*iterator;

typedef_list_iteratorT,cosntT,constT*const_iterator;我們可以根據(jù)模板參數(shù)實(shí)例化出不同的迭代器。

struct_list_iterator

typedef_list_nodeTnode;

typedef_list_iteratorT,Ref,Ptrself;

node*_pnode;

構(gòu)造函數(shù)，把node傳進(jìn)來，然后把值賦給我們內(nèi)部創(chuàng)建的_pnode,總不能亂修改外部指針吧。

_list_iterator(node*node)

:_pnode(node)

這里我們不需要實(shí)現(xiàn)拷貝構(gòu)造、operator=、析構(gòu)，直接用編譯器生成的，對(duì)于內(nèi)置類型直接進(jìn)行淺拷貝

我們發(fā)現(xiàn)淺拷貝指針對(duì)于list來說完全沒問題。

解引用，解引用我們返回值寫為Ref，這樣可以根據(jù)const和非const，并且就是引用返回可讀可修改，如果ref為const，那就不可修改只可讀。

這里不需要傳入?yún)?shù)，我們直接進(jìn)行調(diào)用，返回值當(dāng)然為對(duì)應(yīng)的val引用.

Refoperator*()

return_pnode-_val;

同理的我們寫一下這個(gè)指針解引用，這里返回值依舊用模板參數(shù)，很方便啊。我們應(yīng)該返回一個(gè)地址。

Ptroperator-()

return(_pnode-_val);

！=和==，當(dāng)我們使用迭代器的時(shí)候，需要比較兩個(gè)迭代器是否相等來進(jìn)行循環(huán)條件判定，所以這是必要的。

我們這里返回值當(dāng)然是bool，參數(shù)傳入我們的迭代器，比較迭代器內(nèi)的節(jié)點(diǎn)是否相等。再加上const最好。

booloperator!=(constselfs)const

return_pnode!=s._pnode;

booloperator==(constselfs)const

return_pnode==s._pnode;

接著我們實(shí)現(xiàn)前置后置++--

前置++it我們返回值是原迭代器

selfoperator++()

_pnode=_pnode-_next;

return*this;

后置++it，我們需要進(jìn)行傳參，第一個(gè)參數(shù)就是默認(rèn)的this，第二個(gè)參數(shù)為0

it++--it.operator++(it,0);我們可以缺省掉第二個(gè)參數(shù)，因?yàn)槟J(rèn)是從參數(shù)列表末尾開始匹配的。

當(dāng)然返回值就不能返回引用了，因?yàn)檫@里我們要用臨時(shí)變量進(jìn)行返回,我們先用傳入的it拷貝構(gòu)造一個(gè)臨時(shí)迭代器。然后在進(jìn)行++操作。

因?yàn)楹笾眉蛹邮窍荣x值再++所以我們先用臨時(shí)變量保存一下之前的迭代器，再給之前的迭代器++，最后再返回未修改的臨時(shí)迭代器。

selfoperator++(int)

selftmp(*this);

_pnode=