【C++學習手札】模擬實現list

?

?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ???????????????🎬慕斯主頁：修仙—別有洞天

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?????????????????? ??今日夜電波：リナリア—まるりとりゅうが

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 0:36━━━━━━?💟──────── 3:51
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ????🔄 ? ?? ? ? ? ?? ? ???

??????????????????????????????????????💗關注👍點贊🙌收藏您的每一次鼓勵都是對我莫大的支持😍

目錄

一、list實際的底層原理

二、list的模擬實現

? ? ? ? ?寫在前面

各層封裝的實現

????????節點類

? ? ? ? 迭代器類?

? ? ? ? list類?

list類詳解?

? ? ? ? 迭代器實現

list的修改操作

? ? ? ? Insert?

????????erase

????????swap?

? ? ? ? 復用操作（push_back/front、pop_back/front、clear）

list的構造

? ? ? ? 建立頭節點

????????構造函數

? ? ? ? 拷貝構造和‘=’重載

? ? ? ? 析構函數?

list的空間管理

list的訪問相關

三、整體代碼?

一、list實際的底層原理

????????C++的STL庫中的list是使用帶頭的雙向循環鏈表實現的。list中存儲的每個元素包含了兩個指針，一個指向前一個節點，一個指向后一個節點，這樣就可以方便地在list中進行插入和刪除操作，這些操作的時間復雜度都是O(1)。

?????????大致的結構如下：?

? ? ? ? ?如多大家對于這個數據結構不太熟悉的話，不妨看看作者之前寫的一篇關于帶頭雙向循環鏈表的文章：🌀【數據結構】—C語言實現雙向鏈表（超詳細!）?

二、list的模擬實現

? ? ? ? ?寫在前面

? ? ? ? list的底層雖然是帶頭雙向循環鏈表，但是對于它的實際實現不只是簡單的鏈表而已，當然了，我們肯定會有鏈表的數據結構。但是，這個“結構”，經過了三層的封裝才得以實現，分別是：??第一層：list的節點類

? ? ? ? ? ? ? ? 第二層：list的迭代器類

? ? ? ? ? ? ? ? 第三層：list類

????????本文目前只實現正向的迭代器，反向迭代器會在后面的文章統一vector、string、list一起實現。

各層封裝的實現

?????????節點類

? ? ? ? 主要是包括：對于兩個雙向指針的定義以及數據的定義，再是通過初始化列表對于節點的初始化。

    // List的節點類template<class T>struct ListNode{ListNode(const T& val = T())//通過初始化列表初始化值:_val(val), _pPre(nullptr), _pNext(nullptr){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};

? ? ? ? 迭代器類?

? ? ? ? ?迭代器實際上是對于指針進行操作，因此我們實例化并且重新命名了節點類的指針PNode,由于迭代器分為是否常量正向迭代器，對此我們額外定義了兩個模板參數Ref、Ptr用于控制其中重載運算符 T& operator*() 和?T* operator->()。后面的list類中會有體現。在迭代器中，其中，operator*和operator->返回指向節點的指針，operator++和operator--實現前后綴++/--運算符，operator==和operator!=用來比較兩個迭代器是否指向同一個節點。

    //List的迭代器類template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}T& operator*(){return _pNode->_val;}T* operator->(){return &*this;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp(*this);_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self temp(*this);_pNode = _pNode->_pPre;return temp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return !(*this != l);}private:PNode _pNode;};

? ? ? ? list類?

? ? ? ? 這里先給出主要的封裝，具體的實現后面詳解。可以看到我們又對于節點類進行了實例化并且重新命名，并且定義了一個數據變量。下面是重點了：我們對于迭代器類也進行了實例化并且重新命名，特別是對于上面我們所提到的Ref和Ptr是有做變動的注意看：對于是否常量正向迭代器分別做出了如下定義：T&, T*和const T&, const T*。這里所這的一些變動也是為了后續簡化代碼，避免我們因為動靜態多一份代碼。

????????請結合上面我們迭代器類中我們所提到的operator==和operator!=理解。

class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;//普通迭代器重命名typedef ListIterator<T, const T&, const T*> const_iterator;//靜態迭代器重命名public://...private:PNode _pHead;};

list類詳解?

? ? ? ? 在C++中我們通常會進行各類函數的復用，以減少代碼量和增加可讀性。對此，我們盡量做到復用。

? ? ? ? ?迭代器實現

? ? ? ? 返回頭以及尾的迭代器，注意區分動靜態?。

        // List Iteratoriterator begin(){return iterator(_pHead->_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin()const{return const_iterator(_pHead->_pNext);}const_iterator end()const{return const_iterator(_pHead);}

?list的修改操作

? ? ? ? Insert?

? ? ? ? ?實現在pos位置前插入值為val的節點，開辟空間->保存原位置節點->新節點的前指針指向原節點的前一個節點->后節點指向原節點->該邊原節點的前一個節點的后指針指向，指向新節點->原節點的前指針指向新節點->返回性節點的迭代器。

// 在pos位置前插入值為val的節點iterator insert(iterator pos, const T& val){PNode pNewNode = new Node(val);PNode pCur = pos._pNode;pNewNode->_pPre = pCur->_pPre;pNewNode->_pNext = pCur;pNewNode->_pPre->_pNext = pNewNode;pCur->_pPre = pNewNode;return iterator(pNewNode);}

?????????erase

?????????刪除pos位置的節點，返回該節點的下一個位置，保存刪除j節點，保存原節點的下一個節點（用于返回）->一些列刪除解鏈接操作->返回原節點的下一個節點的迭代器

        // 刪除pos位置的節點，返回該節點的下一個位置iterator erase(iterator pos){PNode pDel = pos._pNode;PNode pRet = pDel->_pNext;pDel->_pPre->_pNext = pDel->_pNext;pDel->_pNext->_pPre = pDel->_pPre;delete pDel;return iterator(pRet);}

????????swap?

        void swap(list<T>& l){pNode tmp = _pHead;_pHead = l._pHead;l._pHead = tmp;}

? ? ? ? ?復用操作（push_back/front、pop_back/front、clear）

        void push_back(const T& val){ insert(end(), val);}void pop_back(){ erase(--end()); }void push_front(const T& val) { insert(begin(), val); }void pop_front() { erase(begin());}void clear(){iterator p = begin();while (p != end()){p = erase(p);}_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}

?list的構造

? ? ? ? ?建立頭節點

? ? ? ? 因為我們在構造、?拷貝等很多的場景中都會用到對于頭結點的初始化，對此額外寫一個函數用于減少代碼量。

        void CreateHead(){_pHead = new Node;_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}

?????????構造函數

? ? ? ? 實現無參、含參初始化、迭代器構造。

        // List的構造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}

? ? ? ? 拷貝構造和‘=’重載

        list(const list<T>& l){CreateHead();list<T> temp(l.begin(), l.end());this->swap(temp);}list<T>& operator=(const list<T> l){this->swap(l);return *this;}

? ? ? ? 析構函數?

        ~list(){clear();delete _pHead;_pHead = nullptr;}

?list的空間管理

        size_t size()const{size_t size = 0;ListNode* p = _pHead->_pNext;while (p != _pHead){size++;p = p->_pNext;}return size;}bool empty()const{return size() == 0;}

list的訪問相關

? ? ? ? 主要還是要區分是否為動靜態相關。

        T& front(){assert(!empty());return _pHead->_pNext->_val;}const T& front()const{assert(!empty());return _pHead->_pNext->_val;}T& back(){assert(!empty());return _pHead->_pPre->_val;}const T& back()const{assert(!empty());return _pHead->_pPre->_val;}

三、整體代碼?

#pragma once
#include<iostream>
#include<assert.h>using namespace std;namespace lt
{// List的節點類template<class T>struct ListNode{ListNode(const T& val = T())//通過初始化列表初始化值:_val(val), _pPre(nullptr), _pNext(nullptr){}ListNode<T>* _pPre;ListNode<T>* _pNext;T _val;};//List的迭代器類template<class T, class Ref, class Ptr>class ListIterator{typedef ListNode<T>* PNode;typedef ListIterator<T, Ref, Ptr> Self;public:ListIterator(PNode pNode = nullptr):_pNode(pNode){}ListIterator(const Self& l):_pNode(l._pNode){}T& operator*(){return _pNode->_val;}T* operator->(){return &*this;}Self& operator++(){_pNode = _pNode->_pNext;return *this;}Self operator++(int){Self temp(*this);_pNode = _pNode->_pNext;return temp;}Self& operator--(){_pNode = _pNode->_pPre;return *this;}Self& operator--(int){Self temp(*this);_pNode = _pNode->_pPre;return temp;}bool operator!=(const Self& l){return _pNode != l._pNode;}bool operator==(const Self& l){return !(*this != l);}private:PNode _pNode;};//list類template<class T>class list{typedef ListNode<T> Node;typedef Node* PNode;public:typedef ListIterator<T, T&, T*> iterator;//普通迭代器重命名typedef ListIterator<T, const T&, const T*> const_iterator;//靜態迭代器重命名public:///// List的構造list(){CreateHead();}list(int n, const T& value = T()){CreateHead();for (int i = 0; i < n; ++i){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last){CreateHead();while (first != last){push_back(*first);++first;}}list(const list<T>& l){CreateHead();list<T> temp(l.begin(), l.end());this->swap(temp);}list<T>& operator=(const list<T> l){this->swap(l);return *this;}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return iterator(_pHead->_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin()const{return const_iterator(_pHead->_pNext);}const_iterator end()const{return const_iterator(_pHead);}///// List Capacitysize_t size()const{size_t size = 0;ListNode* p = _pHead->_pNext;while (p != _pHead){size++;p = p->_pNext;}return size;}bool empty()const{return size() == 0;}// List AccessT& front(){assert(!empty());return _pHead->_pNext->_val;}const T& front()const{assert(!empty());return _pHead->_pNext->_val;}T& back(){assert(!empty());return _pHead->_pPre->_val;}const T& back()const{assert(!empty());return _pHead->_pPre->_val;}// List Modifyvoid push_back(const T& val){ insert(end(), val);}void pop_back(){ erase(--end()); }void push_front(const T& val) { insert(begin(), val); }void pop_front() { erase(begin());}// 在pos位置前插入值為val的節點iterator insert(iterator pos, const T& val){PNode pNewNode = new Node(val);PNode pCur = pos._pNode;pNewNode->_pPre = pCur->_pPre;pNewNode->_pNext = pCur;pNewNode->_pPre->_pNext = pNewNode;pCur->_pPre = pNewNode;return iterator(pNewNode);}// 刪除pos位置的節點，返回該節點的下一個位置iterator erase(iterator pos){PNode pDel = pos._pNode;PNode pRet = pDel->_pNext;pDel->_pPre->_pNext = pDel->_pNext;pDel->_pNext->_pPre = pDel->_pPre;delete pDel;return iterator(pRet);}void clear(){iterator p = begin();while (p != end()){p = erase(p);}_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}void swap(list<T>& l){pNode tmp = _pHead;_pHead = l._pHead;l._pHead = tmp;}private:void CreateHead(){_pHead = new Node;_pHead->_pPre = _pHead;_pHead->_pNext = _pHead;}PNode _pHead;};
};

????????????????????????感謝你耐心的看到這里?( ′･?･` )比心，如有哪里有錯誤請踢一腳作者o(╥﹏╥)o！?

????????????????????????????????? ? ? ?

?????????????????????????????????????????????????????????????????????????給個三連再走嘛~??

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/165848.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/165848.shtml
英文地址，請注明出處：http://en.pswp.cn/news/165848.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

聊聊httpclient的staleConnectionCheckEnabled

聊聊httpclient的staleConnectionCheckEnabled

序 本文主要研究一下httpclient的staleConnectionCheckEnabled staleConnectionCheckEnabled org/apache/http/client/config/RequestConfig.java public class RequestConfig implements Cloneable {public static final RequestConfig DEFAULT new Builder().build();pr…
閱讀更多...
【ARM 嵌入式 編譯 Makefile 系列 18 -- Makefile 中的 export 命令詳細介紹】

【ARM 嵌入式 編譯 Makefile 系列 18 -- Makefile 中的 export 命令詳細介紹】

文章目錄 Makefile 中的 export 命令詳細介紹Makefile 使用 export導出與未導出變量的區別示例&#xff1a;導出變量以供子 Makefile 使用 Makefile 中的 export 命令詳細介紹 在 Makefile 中&#xff0c;export 命令用于將變量從 Makefile 導出到由 Makefile 啟動的子進程的環…
閱讀更多...
qgis添加wms服務

qgis添加wms服務

例如添加geoserver的wms服務 左右瀏覽器-WMS/WMTS-右鍵-新建連接 URL添加geoserver的wms地址 http://{ip}:{port}/geoserver/{workspace}/wms 展開wms目錄&#xff0c;雙擊相應圖層即可打開
閱讀更多...
Spark---基于Yarn模式提交任務

Spark---基于Yarn模式提交任務

Yarn模式兩種提交任務方式 一、yarn-client提交任務方式 1、提交命令 ./spark-submit --master yarn --class org.apache.spark.examples.SparkPi ../examples/jars/spark-examples_2.11-2.3.1.jar 100 或者 ./spark-submit --master yarn–client --class org.apache.s…
閱讀更多...
三菱PLC應用[集錦]

三菱PLC應用[集錦]

三菱PLC應用[集錦] 如何判斷用PNP還是NPN的個人工作心得 10&#xff5e;30VDC接近開關與PLC連接時&#xff0c;如何判斷用PNP還是NPN的個人工作心得: 對于PLC的開關量輸入回路。我個人感覺日本三菱的要好得多&#xff0c;甚至比西門子等赫赫大名的PLC都要實用和可靠&#xff01…
閱讀更多...
vulnhub4

vulnhub4

靶機地址: https://download.vulnhub.com/admx/AdmX_new.7z 信息收集 fscan 掃一下 ┌──(kali?kali)-[~/Desktop/Tools/fscan] └─$ ./fscan_amd64 -h 192.168.120.138 ___ _ / _ \ ___ ___ _ __ __ _ ___| | __ / /_\/____/ __|/ …
閱讀更多...
LeetCode | 622. 設計循環隊列

LeetCode | 622. 設計循環隊列

LeetCode | 622. 設計循環隊列 OJ鏈接 思路&#xff1a; 我們這里有一個思路&#xff1a; 插入數據&#xff0c;bank往后走 刪除數據&#xff0c;front往前走 再插入數據&#xff0c;就循環了 那上面這個方法可行嗎&#xff1f; 怎么判斷滿&#xff0c;怎么判斷空&#xff1…
閱讀更多...
模電知識點總結（二）二極管

模電知識點總結（二）二極管

系列文章目錄 文章目錄 系列文章目錄二極管二極管電路分析方法理想模型恒壓降模型折線模型小信號模型高頻/開關 二極管應用整流限幅/鉗位開關齊納二極管變容二極管肖特基二極管光電器件光電二極管發光二極管激光二極管太陽能電池 二極管 硅二極管&#xff1a;死區電壓&#xf…
閱讀更多...
今年注冊電氣工程師考試亂象及就業前景分析

今年注冊電氣工程師考試亂象及就業前景分析

1、注冊電氣工程師掛靠價格 # 2011年以前約為5萬一年&#xff0c;2011年開始強制實施注冊電氣執業制度&#xff0c;證書掛靠價格開始了飛漲&#xff0c;2013年達到巔峰&#xff0c;供配電15萬一年&#xff0c;發輸變電20-25萬一年&#xff0c;這哪里是證書&#xff0c;簡直就是…
閱讀更多...
Docker kill 命令

Docker kill 命令

docker kill&#xff1a;殺死一個或多個正在運行的容器。 語法&#xff1a; docker kill [OPTIONS] CONTAINER [CONTAINER...]OPTIONS說明&#xff1a; -s&#xff1a;向容器發送一個信號 描述&#xff1a; docker kill子命令會殺死一個或多個容器。容器內的主進程被發送S…
閱讀更多...
C語言數組的距離（ZZULIOJ1200:數組的距離）

C語言數組的距離（ZZULIOJ1200:數組的距離）

題目描述 已知元素從小到大排列的兩個數組x[]和y[]&#xff0c; 請寫出一個程序算出兩個數組彼此之間差的絕對值中最小的一個&#xff0c;這叫做數組的距離 。 輸入&#xff1a;第一行為兩個整數m, n(1≤m, n≤1000)&#xff0c;分別代表數組f[], g[]的長度。第二行有m個元素&a…
閱讀更多...
如何在Simulink中使用syms？換個思路解決報錯：Function ‘syms‘ not supported for code generation.

如何在Simulink中使用syms？換個思路解決報錯：Function ‘syms‘ not supported for code generation.

問題描述 在Simulink中的User defined function使用syms函數&#xff0c;報錯simulink無法使用外部函數。 具體來說&#xff1a; 我想在Predefined function定義如下符號函數作為輸入信號&#xff0c;在后續模塊傳入函數參數賦值&#xff0c;以實現一次定義多次使用&#xf…
閱讀更多...
014:MyString

014:MyString

題目 描述 補足MyString類&#xff0c;使程序輸出指定結果 #include <iostream> #include <string> #include <cstring> using namespace std; class MyString {char * p; public:MyString(const char * s) {if( s) {p new char[strlen(s) 1];strcpy(p,…
閱讀更多...
最小二乘線性回歸

最小二乘線性回歸

? 線性回歸&#xff08;linear regression&#xff09;&#xff1a;試圖學得一個線性模型以盡可能準確地預測實際值的輸出。 以一個例子來說明線性回歸&#xff0c;假設銀行貸款會根據 年齡 和 工資 來評估可放款的額度。即&#xff1a; ? 數據&#xff1a;工資和年齡&…
閱讀更多...
python將模塊進行打包

python將模塊進行打包

模塊名稱為&#xff1a;my_module 目錄結構&#xff1a; my_modulemy_module__init__.pymy_module_main.pysetup.pypython setup.pu sdist bdist_wheel生成tar.gz包和whl文件用于安裝 """ python setup.py sdist bdist_wheel """from setuptoo…
閱讀更多...
LeeCode前端算法基礎100題（2）- 最多水的容器

LeeCode前端算法基礎100題（2）- 最多水的容器

一、問題詳情&#xff1a; 給定一個長度為 n 的整數數組 height 。有 n 條垂線&#xff0c;第 i 條線的兩個端點是 (i, 0) 和 (i, height[i]) 。 找出其中的兩條線&#xff0c;使得它們與 x 軸共同構成的容器可以容納最多的水。 返回容器可以儲存的最大水量。 說明&#xff1a;…
閱讀更多...
案例025:基于微信小程序的移動學習平臺的設計與實現

案例025:基于微信小程序的移動學習平臺的設計與實現

文末獲取源碼 開發語言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 數據庫&#xff1a;mysql 5.7 開發軟件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序開發軟件&#xff1a;HBuilder X 小程序…
閱讀更多...
[C++歷練之路]優先級隊列||反向迭代器的模擬實現

[C++歷練之路]優先級隊列||反向迭代器的模擬實現

W...Y的主頁 &#x1f60a; 代碼倉庫分享&#x1f495; &#x1f354;前言&#xff1a; 在C的宇宙中&#xff0c;優先隊列似乎是一座巨大的寶庫&#xff0c;藏匿著算法的珍寶。而就在這片代碼的天空下&#xff0c;我們不僅可以探索優先隊列的神奇&#xff0c;還能夠揭開反向迭…
閱讀更多...
shutil和fileinput模塊：文件操作的最佳實踐

shutil和fileinput模塊：文件操作的最佳實踐

在Python中&#xff0c;shutil和fileinput模塊是處理文件和輸入/輸出(I/O)操作的有力工具。shutil模塊提供了一種在Python中操作文件的高級接口&#xff0c;而fileinput模塊則允許我們輕松地讀取多個輸入流。 shutil模塊 shutil模塊是Python的標準庫之一&#xff0c;提供了很…
閱讀更多...
【【Linux系統下常用指令學習 之 二 】】

【【Linux系統下常用指令學習 之 二 】】

Linux系統下常用指令學習 之 二 文件查詢和搜索 文件的查詢和搜索也是最常用的操作&#xff0c;在嵌入式 Linux 開發中常常需要在 Linux 源碼文件中查詢某個文件是否存在&#xff0c;或者搜索哪些文件都調用了某個函數等等。 1、命令 find find 命令用于在目錄結構中查找文件…
閱讀更多...
最新文章

Copyright @ 2022~2023