C++初階之list的模擬實(shí)現(xiàn)過(guò)程詳解
list的介紹
list的優(yōu)點(diǎn):
- list頭部、中間插入不再需要挪動(dòng)數(shù)據(jù),O(1)效率高
- list插入數(shù)據(jù)是新增節(jié)點(diǎn),不需要增容
list的缺點(diǎn):
- 不支持隨機(jī)訪(fǎng)問(wèn),訪(fǎng)問(wèn)某個(gè)元素效率O(N)
- 底層節(jié)點(diǎn)動(dòng)態(tài)開(kāi)辟,小節(jié)點(diǎn)容易造成內(nèi)存碎片,空間利用率低,緩存利用率低。
今天來(lái)模擬實(shí)現(xiàn)list
我們先來(lái)看看官方文檔中對(duì)于list的描述
我們先大致了解一下list的遍歷
迭代器
對(duì)于迭代器我們可以用while循環(huán)+begin()end()。同時(shí)還可以用迭代器區(qū)間。
當(dāng)然迭代器區(qū)間的方式只適用于內(nèi)存連續(xù)的結(jié)構(gòu)比如數(shù)組stringvector等
它們的原生指針就可以當(dāng)作迭代器來(lái)用。
范圍for
其實(shí)范圍for和迭代器的底層是完全一樣的,我們只有寫(xiě)好迭代器,才能用范圍for,而且這里的迭代器必須和庫(kù)里的命名一樣才可以用范圍for
我們?cè)賮?lái)了解一下有關(guān)算法函數(shù)中,我們最常用的函數(shù)
- swap
- find
- sort
我們主要看看sort函數(shù)
sort函數(shù)在官方庫(kù)中是用快排寫(xiě)的,其中快排的精髓就是三數(shù)取中的優(yōu)化操作。
sort默認(rèn)是排升序 如果想排降序需要使用functional文件中的greater()這個(gè)模板函數(shù),我們以vector來(lái)舉例。
對(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ī)訪(fǎng)問(wèn),他不是隨即迭代器。
而vector string這樣的迭代器是支持隨機(jī)訪(fǎng)問(wèn)的,所以他們用快排很有優(yōu)勢(shì)。
我們可以看到這三個(gè)函數(shù)的迭代器是不同的,它們是繼承關(guān)系,隨機(jī)的支持雙向,雙向支持單向,反過(guò)來(lái)就不行。
當(dāng)然除了這幾種迭代器,還有輸入輸出迭代器,也叫可讀可寫(xiě)迭代器,他們是最弱的迭代器,一個(gè)單向迭代器都可以支持可讀可寫(xiě)的功能。也就是說(shuō),可讀可寫(xiě)迭代器在繼承的最上端。所有人都包含了他倆。
但是雖然他們功能很弱,但他們?cè)谝恍┲匾奶匦陨嫌兄陵P(guān)重要的作用,那就是迭代器的萃取。這個(gè)和復(fù)雜,暫時(shí)不去管它們。
總結(jié)上面兩段話(huà):
當(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ù)
無(wú)符號(hào)整形最大是2^32-1,也就是42億多,對(duì)于int類(lèi)型的vector,就是42億除以4得到的值,對(duì)于list,就是42億除以三個(gè)指針的大小得到的值。
我們還知道再vector中,我們?cè)趇nsert的擴(kuò)容插入,還有erase的刪除時(shí),會(huì)導(dǎo)致迭代器失效的問(wèn)題。那么對(duì)于list我們還要去關(guān)注迭代器失效的問(wè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)然庫(kù)中還有一些我們不常用的函數(shù)
splice 接合函數(shù),把一個(gè)list的數(shù)據(jù)轉(zhuǎn)移到另一個(gè)list
這里不是拷貝,是轉(zhuǎn)移。
還有remove,找到就刪,沒(méi)找到就沒(méi)什么反應(yīng)。
unique 去重,這里又一個(gè)小小的bug,只有連續(xù)的重復(fù)數(shù)據(jù)才會(huì)刪除。
聰明的同學(xué)會(huì)反應(yīng)過(guò)來(lái),這里sort+unique可以解決這樣的問(wèn)題。當(dāng)然沒(méi)反應(yīng)過(guò)來(lái)的同學(xué)也很聰明。
這里顯然還是那個(gè)問(wèn)題,我們不建議堆鏈表進(jìn)行排序,效率是很低的。
list的成員函數(shù)是用的歸并排序。為什么不用algorithm中的sort快排呢?原因我們上文已經(jīng)解釋過(guò)了。
說(shuō)了這么多,來(lái)看看代碼吧。
先來(lái)看看頭文件吧!
#pragma once #include <iostream> #include <algorithm> #include <functional> using namespace std; namespace LL { 我們先寫(xiě)結(jié)點(diǎn)類(lèi),這里用類(lèi)模板,并且是用struct實(shí)現(xiàn),默認(rèn)內(nèi)容是公開(kāi)的,其他的類(lèi)都可以調(diào)用 template<class T> 其中結(jié)點(diǎn)類(lèi)中要有三個(gè)變量,一個(gè)存值,兩個(gè)指針 struct _list_node { T _val; _list_node<T>* _next; _list_node<T>* _prev; 結(jié)點(diǎn)類(lèi)中除了要有三個(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(const T& val = T()) :_val(val) , _next(nullptr) , _prev(nullptr) {} }; 這里實(shí)現(xiàn)迭代器類(lèi)。首先我們依舊是使用類(lèi)模板 ,我們這里給三個(gè)模板參數(shù),同時(shí)類(lèi)還是用struct來(lái)實(shí)現(xiàn) 在迭代器類(lèi)中,我們主要實(shí)現(xiàn) 1、構(gòu)造 2、解引用操作 3、!= 和== 操作 3、前置++后置++ --操作 template<class T, class Ref, class Ptr> 這里三個(gè)模板參數(shù)是什么意思呢?當(dāng)我們需要const迭代器和非const迭代器的時(shí)候我們可以根據(jù)第二個(gè)參數(shù)的不同來(lái)實(shí)例化出不同的迭代器,就不需要寫(xiě)兩個(gè)迭代器了 typedef _list_iterator<T,T&,T*> iterator; typedef _list_iterator<T,cosnt T&,const T*> const_iterator; 我們可以根據(jù)模板參數(shù)實(shí)例化出不同的迭代器。 struct _list_iterator { typedef _list_node<T> node; typedef _list_iterator<T, Ref, Ptr> self; node* _pnode; 構(gòu)造函數(shù),把node傳進(jìn)來(lái),然后把值賦給我們內(nèi)部創(chuàng)建的_pnode,總不能亂修改外部指針吧。 _list_iterator(node * node) :_pnode(node) {} 這里我們不需要實(shí)現(xiàn)拷貝構(gòu)造、operator=、析構(gòu),直接用編譯器生成的,對(duì)于內(nèi)置類(lèi)型直接進(jìn)行淺拷貝 我們發(fā)現(xiàn)淺拷貝指針對(duì)于list來(lái)說(shuō)完全沒(méi)問(wèn)題。 解引用,解引用我們返回值寫(xiě)為Ref ,這樣可以根據(jù)const和非const,并且就是引用返回可讀可修改,如果ref為const,那就不可修改只可讀。 這里不需要傳入?yún)?shù),我們直接進(jìn)行調(diào)用,返回值當(dāng)然為對(duì)應(yīng)的val引用. Ref operator * () { return _pnode->_val; } 同理的我們寫(xiě)一下這個(gè)指針解引用,這里返回值依舊用模板參數(shù),很方便啊。我們應(yīng)該返回一個(gè)地址。 Ptr operator ->() { return &(_pnode->_val); } != 和 == ,當(dāng)我們使用迭代器的時(shí)候,需要比較兩個(gè)迭代器是否相等來(lái)進(jìn)行循環(huán)條件判定,所以這是必要的。 我們這里返回值當(dāng)然是bool,參數(shù)傳入我們的迭代器,比較迭代器內(nèi)的節(jié)點(diǎn)是否相等。再加上const最好。 bool operator != (const self& s) const { return _pnode != s._pnode; } bool operator == (const self& s) const { return _pnode == s._pnode; } 接著我們實(shí)現(xiàn)前置后置++-- 前置 ++ it 我們返回值是 原迭代器 self& operator++() { _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ù)列表末尾開(kāi)始匹配的。 當(dāng)然返回值就不能返回引用了,因?yàn)檫@里我們要用臨時(shí)變量進(jìn)行返回,我們先用傳入的it拷貝構(gòu)造一個(gè)臨時(shí)迭代器。然后在進(jìn)行++操作。 因?yàn)楹笾眉蛹邮窍荣x值再++所以我們先用臨時(shí)變量保存一下之前的迭代器,再給之前的迭代器++,最后再返回未修改的臨時(shí)迭代器。 self operator++(int) { self tmp(*this); _pnode = _pnode->_next; return tmp; } self& operator--() { _pnode = _pnode->_prev; return *this; } self operator--(int) { self tmp(*this); _pnode = _pnode->_prev; return tmp; } }; 接下來(lái)我們開(kāi)始寫(xiě)list類(lèi),當(dāng)然也要用類(lèi)模板來(lái)寫(xiě),里面要實(shí)現(xiàn)1、迭代器 2、構(gòu)造 3、push_back 。我們這里的list是帶頭雙向循環(huán)列表 template <class T> class list { 我們先來(lái)實(shí)現(xiàn)一下迭代器,我們首先需要typedef 我們的迭代器 ,所以先實(shí)現(xiàn)迭代器。然后需要定義const和非const的beginend , 這里需要記住end和begin要有非const和cosnt,因?yàn)闊o(wú)法同時(shí)滿(mǎn)足可修改和可讀。比如const迭代器調(diào)用只能掉const的end,非const的迭代器雖然可以調(diào)用const的end,但是導(dǎo)致權(quán)限縮小,無(wú)法修改內(nèi)容。 typedef _list_node<T> node; public: typedef _list_iterator<T, T&, T*> iterator; typedef _list_iterator<T, const T&, const T*> const_iterator; iterator begin() //begin指頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn),end指頭結(jié)點(diǎn)。 { return iterator(_head->_next); //這里調(diào)用的是匿名構(gòu)造然后直接返回。 } const_iterator begin() const { return const_iterator(_head->_next); } iterator end() { return iterator(_head); } const_iterator end() const { return const_iterator(_head); } 構(gòu)造函數(shù),這里直接進(jìn)行頭結(jié)點(diǎn)的創(chuàng)建(自己鏈自己) list() { _head = new node(T()); 當(dāng)然可以有這種寫(xiě)法,我們用匿名構(gòu)造一個(gè)頭結(jié)點(diǎn),可以是各種類(lèi)型。這里和上文中,結(jié)點(diǎn)的構(gòu)造函數(shù)是一樣的,我們寫(xiě)一個(gè)就好了。 _head = new node; _head->_next = _head; _head->_prev = _head; } push_back 我們傳入一個(gè)要插入的值,創(chuàng)建新節(jié)點(diǎn)進(jìn)行鏈接的更新。 void push_back(const T& val) { node* newnode = new node(val); //這里因?yàn)槲覀冊(cè)诮Y(jié)點(diǎn)的構(gòu)造函數(shù)中寫(xiě)了模板參數(shù)類(lèi)型匿名構(gòu)造,可以傳任意類(lèi)型。 node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; } 拷貝構(gòu)造 1、創(chuàng)造新的頭結(jié)點(diǎn),把傳入的list循環(huán)賦值給新的頭結(jié)點(diǎn)。 list(const list<T>& l) { _head = new node; _head->_next = _head; _head->_prev = _head; const_iterator it = l.begin(); while (it != l.end()) { push_back(*it); ++it; } } insert,在指定位置插入元素,我們不用返回值,參數(shù)是pos迭代器和val 先給一個(gè)cur 存pos位置的結(jié)點(diǎn),然后定義一個(gè)我們的prev,為了之后和新節(jié)點(diǎn)鏈接。2、創(chuàng)建新節(jié)點(diǎn),更新鏈接就好了。 void insert(iterator pos, const T& val) //這里不需要用const 因?yàn)?,const迭代器對(duì)應(yīng)了constlist ,const list怎么會(huì)來(lái)插入數(shù)據(jù)呢? { node* cur = pos._pnode; node* prev = cur->_prev; node* newnode = new node(val); newnode->_next = cur; newnode->_prev = prev; prev->_next = newnode; cur->_prev = newnode; } erase ,返回下一個(gè)位置的迭代器,傳入一個(gè)pos 1、保存指向結(jié)點(diǎn),并找到前后的兩節(jié)點(diǎn) 2、更新鏈接 刪除掉當(dāng)前節(jié)點(diǎn)。3、返回迭代器。這里需要強(qiáng)轉(zhuǎn),從指針轉(zhuǎn)成迭代器類(lèi)型。 iterator erase(iterator pos) { node* cur = pos._pnode; node* prev = cur->_prev; node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return (iterator)next; } 那我們?cè)谫x值運(yùn)算符重載的時(shí)候需要先清理掉自身的結(jié)點(diǎn),所以我們實(shí)現(xiàn)一下clear clear 清空l(shuí)ist中除了頭結(jié)點(diǎn)以外的所有結(jié)點(diǎn)。很好實(shí)現(xiàn),我們循環(huán)erase就好了,erase返回下一個(gè)的迭代器,所以接收其返回值就好了。 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } 賦值運(yùn)算符重載,返回值是類(lèi)型的引用 ,參數(shù)傳入list 1、首先判斷是否給自己賦值,否則我們刪除后會(huì)發(fā)生野指針的問(wèn)題 2、條件成立我們先清除現(xiàn)在的一切,然后循環(huán)賦值。最后返回*this; list<T>& operator = (list<T>& l) { if (this != &l) { clear (); iterator it = l.begin(); while (it != l.end()) { push_back(*it); it++; } } return *this; } 析構(gòu):析構(gòu)要做的就是析構(gòu)一切,先clear,在delete 頭,并給頭賦空 ~list() { clear(); delete _head; _head = nullptr; cout << "析構(gòu)執(zhí)行成功" << endl; } 獲得第一個(gè)元素,返回一定是類(lèi)型的引用,這里應(yīng)該有兩個(gè)版本,否則當(dāng)const對(duì)象調(diào)用的時(shí)候,會(huì)無(wú)法調(diào)用。這里返回也要返回const,否則你給人家偷偷擴(kuò)大了權(quán)限。 T& front() { return _head->_next->_val; } const T& front() const { return _head->_next->_val; } 獲得最后一個(gè)元素 T& back() { return _head->_prev->_val; } const T& back() const { return _head->_prev->_val; } 交換兩個(gè)list,傳入list。我們只需要交換一下頭結(jié)點(diǎn)就可以了 void swap(list<T>& l) { ::swap(_head, l._head); } void push_back_insert(const T& val) { insert(end(), val); } void push_front_insert(const T& val) { insert(begin(), val); } void pop_front_erase() { erase(begin()); } void pop_back_erase() { erase(--end()); } 求結(jié)點(diǎn)個(gè)數(shù)循環(huán)計(jì)數(shù) size_t size() { size_t count = 0; auto it = begin(); while (it != end()) { ++it; ++count; } return count; } bool empty() { return begin() == end(); } resize ,開(kāi)辟n個(gè)空間并賦初始值,用匿名構(gòu)造賦值。 1、計(jì)算舊結(jié)點(diǎn)個(gè)數(shù),如果就空間比新的空間大,我們就刪除多余的空間2、否則就從新空間開(kāi)始給其賦初值。 void resize(size_t newsize, T& val = T()) { size_t oldsize = size(); if (oldsize > newsize) { for (int i = newsize; i < oldsize; i++) { pop_back_erase(); } } else { for (int i = oldsize; i < newsize; i++) { push_back_insert(val); } } } private: node* _head; }; }
我們來(lái)測(cè)試一下我們的函數(shù)
#include "List.h" //printlist 打印不需要返回什么,參數(shù)是一個(gè)模板參數(shù)類(lèi)型的列表 template<class Con> void PrintContainer(const Con& c) { Con::const_iterator it = c.begin(); while (it != c.end()) { cout << *it << " "; ++it; } cout << endl; } void test_list1() { cout << "list1使用pushback插入數(shù)據(jù)的打印" << endl; LL::list<int> lt1; lt1.push_back(1); lt1.push_back(2); lt1.push_back(3); lt1.push_back(4); lt1.push_back(5); lt1.push_back(6); PrintContainer(lt1); //for (auto e : lt) //{ // cout << e << " "; //} //cout << endl; //LL::list<int>::iterator it = lt.begin(); //while (it != lt.end()) //{ // (*it)++; // cout << *it << " "; // ++it; //} //cout << endl; cout << "拷貝構(gòu)造list2的打印" << endl; LL::list<int> lt2(lt1); PrintContainer(lt2); //cout << "在list2的2位置前insert一個(gè)0并打印" << endl; //LL::list<int>::iterator pos = find(lt2.begin(), lt2.end(),2); //lt2.insert(pos,0); //PrintContainer(lt2); //cout << "在list2的2位置前insert一個(gè)0并打印" << endl; //lt2.erase(pos); //PrintContainer(lt2); cout << "用list2給list3賦值,并打印" << endl; LL::list<int> lt3; lt3 = lt2; PrintContainer(lt3); cout << "獲得list3的第一個(gè)元素和最后一個(gè)元素" << endl; cout << lt3.front() <<" "; cout << lt3.back() << endl; cout << "整一個(gè)全是0的list4,并打印" << endl; LL::list<int> lt4; lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); lt4.push_back(0); PrintContainer(lt4); cout << "交換鏈表list1和list4、并打印" << endl; lt1.swap(lt4); PrintContainer(lt4); cout << "頭刪list4" << endl; lt4.pop_front_erase(); PrintContainer(lt4); cout << "頭插list4" << endl; lt4.push_front_insert(0); PrintContainer(lt4); cout << "尾刪list4" << endl; lt4.pop_back_erase(); PrintContainer(lt4); cout << "尾插list4" << endl; lt4.push_back_insert(0); PrintContainer(lt4); cout << "list4的節(jié)點(diǎn)個(gè)數(shù)" << endl; cout << lt4.size() << endl; cout << "判斷是list1是否為空鏈表" << endl; cout << lt1.empty() << endl; cout << " " << endl; cout << " " << endl; cout << " " << endl; cout << " " << endl; cout << " " << endl; cout << " " << endl; } int main() { test_list1(); return 0; }
總結(jié)
到此這篇關(guān)于C++初階之list的模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ list模擬實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++實(shí)現(xiàn)不能被繼承的類(lèi)實(shí)例分析
這篇文章主要介紹了C++實(shí)現(xiàn)不能被繼承的類(lèi)實(shí)例分析,對(duì)于C++初學(xué)者而言可以通過(guò)本文實(shí)例更好的理解類(lèi)的原理及運(yùn)用,需要的朋友可以參考下2014-08-08Visual Studio 2019創(chuàng)建C++ Hello World項(xiàng)目的方法
這篇文章主要介紹了Visual Studio 2019創(chuàng)建C++ Hello World項(xiàng)目的方法,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03C++實(shí)現(xiàn)將輸入復(fù)制到輸出的方法
這篇文章主要介紹了C++實(shí)現(xiàn)將輸入復(fù)制到輸出的方法,實(shí)例分析了C++字符串轉(zhuǎn)換及輸入輸出操作的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07C語(yǔ)言實(shí)現(xiàn)斐波那契數(shù)列(非遞歸)的實(shí)例講解
下面小編就為大家?guī)?lái)一篇C語(yǔ)言實(shí)現(xiàn)斐波那契數(shù)列(非遞歸)的實(shí)例講解。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-08-08c++ 單線(xiàn)程實(shí)現(xiàn)同時(shí)監(jiān)聽(tīng)多個(gè)端口
這篇文章主要介紹了c++ 單線(xiàn)程實(shí)現(xiàn)同時(shí)監(jiān)聽(tīng)多個(gè)端口的方法,幫助大家更好的理解和學(xué)習(xí)使用c++,感興趣的朋友可以了解下2021-03-03C++實(shí)現(xiàn)一個(gè)簡(jiǎn)易版的事件(Event)的示例代碼
之前在?windows系統(tǒng)中開(kāi)發(fā)應(yīng)用時(shí),?遇到需要進(jìn)行線(xiàn)程同步的時(shí)候幾乎都是使用的事件內(nèi)核對(duì)象?Event。本文為大家整理了C++實(shí)現(xiàn)一個(gè)簡(jiǎn)易版的事件(Event)的相關(guān)資料,需要的可以參考一下2022-11-11C語(yǔ)言16進(jìn)制與ASCII字符相互轉(zhuǎn)換
大家好,本篇文章主要講的是C語(yǔ)言16進(jìn)制與ASCII字符相互轉(zhuǎn)換,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話(huà)記得收藏一下2022-01-01