C++學習之STL學習：list的模擬實現

? ? ? ? 在上一篇學習了list的使用后，在本篇我們將通過模擬實現的方式深入了解list的底層運作原理。

? ? ? ? 作者的個人gitee：樓田莉子 (riko-lou-tian) - Gitee.com

? ? ? ? 感興趣的讀者可以看一看

目錄

前置準備

? ? ? ? 結點的定義

????????鏈表類的定義

迭代器?

????????普通迭代器

????????const迭代器?

? ? ? ? list中關于迭代器的聲明?

? ? ? ? 誤區：

相關函數

????????push_back

? ? ? ? insert

? ? ? ? erase

源代碼

前置準備

? ? ? ? 結點的定義

? ? ? ? 我們需要定義一個結點的類（參考之前雙向鏈表那篇博客：數據結構學習之雙向循環鏈表-CSDN博客），因為這個類中的成員我們都想要訪問，如果想要方便寫的話，可以用struct（struct中默認為公開），并且用命名空間封裝

namespace Boogiepop
{template<class T>//當我們不需要也不想要讓訪問限定符限制的時候//可以用struct來定義類，而不是用classstruct list_node{T _data;			//數據list_node<T>* _next;//指向下一個節點的指針list_node<T>* _prev;//指向前一個節點的指針};
}

? ? ? ? 同時因為list模擬實現中使用了模板，所以函數的定義也只能在.h文件中（）?

? ? ? ? 同時切記，模板只能給對應的類或函數使用，是“一次性”的，想再次使用一樣的模板必須重新定義

????????鏈表類的定義

template<class T>
class list
{typedef list_node<T> node;
public://構造函數list(){_head = new node;_head->_next = _head;_head->_prev = _head;}
private:node* _head;		//指向頭節點的指針};

迭代器?

????????雙鏈表迭代器相關圖解：

?????????迭代器用node*封裝無法達到預期行為；用類封裝node*重載運算符，就可以控制迭代器的行為。

? ? ? ? 迭代器行為模擬的是普通指針訪問數組的行為

????????普通迭代器

	//迭代器template<class T,class Ref>//當我們不需要也不想要讓訪問限定符限制的時候//可以用struct來定義類，而不是用class//普通迭代器struct _list_iterator{typedef list_node<T> node;typedef _list_iterator<T, Ref> Self;node* _node;//構造迭代器_list_iterator(node* node) :_node(node){}//解引用不是結點//用引用返回可以修改這個數值T& operator*(){return _node->_data;}////不能實現，因為const list_iterator對象才能調用這個重載////但是在這種情況下const list_iterator對象不能調用++和--//const T& operator*()const//{//	return _node->_data;//}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){_list_iterator<T,Ref> tmp (*this);//淺拷貝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp (*this);//淺拷貝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node!= it._node; }bool operator==(const Self& it)const{return _node == it._node;}};

????????const迭代器?

	//const迭代器template<class T,class Ref>//當我們不需要也不想要讓訪問限定符限制的時候//可以用struct來定義類，而不是用classstruct _list_const_iterator{typedef list_node<T> node;typedef _list_const_iterator<T, Ref> Self;node* _node;//構造迭代器_list_const_iterator(node* node) :_node(node){}//解引用不是結點//用引用返回可以修改這個數值const Self& operator*(){return _node->_data;}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){Self tmp(*this);//淺拷貝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp(*this);//淺拷貝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}};

? ? ? ? list中關于迭代器的聲明?

//鏈表
template<class T>
class list
{typedef list_node<T> node;
public://普通迭代器typedef _list_iterator<T,Ref> iterator;//const迭代器typedef const _list_iterator<T,Ref> const_iterator;//返回迭代器iterator begin(){return iterator(_head->_next);}//返回迭代器iterator end(){return iterator(_head);}//其余部分在此處省略。。。。。。
}

?測試：

void test1()
{Boogiepop::list<int> list;list.push_back(1);list.push_back(2);list.push_back(3);list.push_back(4);list.push_back(5);Boogiepop::list<int>::iterator it = list.begin();while (it != list.end()){cout << *it << " ";++it;}cout<<endl;
}

? ? ? ? 普通迭代器可以修改指向的內容，const迭代器不可以修改指向的內容

? ? ? ? 誤區：

? ? ? ? 1、

? ? ? ? 這么寫是不對的，這樣迭代器本身無法修改,無法進行++和--

typedef const iterator const_iterator;

? ? ? ? string和vector可以這么干是因為const修飾的指向的內容?

? ? ? ? 但是list只能重新搞一個類型實現

?????????2、還有這種情況，寫重載能否實現？答案是不能

T& operator*()
{return _node->_data;
}
const T& operator*()const
{return _node->_data;
}

? ? ? ? 因為：

T& operator*()
{return _node->_data;
}
//不能實現，因為const list_iterator對象才能調用這個重載
//但是在這種情況下const list_iterator對象不能調用++和--
const T& operator*()const
{return _node->_data;
}

????????

相關函數

????????push_back

void push_back(const T&x)
{node* new_node = new node(x);//頭結點node* tail=_head->_prev;//尾節點tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;
}

? ? ? ? insert

void insert(iterator pos, const T& x)
{node* cur = pos._node;node*new_node = new node(x);node*prev = cur->_prev;//prev  new_node  curprev->_next = new_node;new_node->_next = cur;cur->_prev = new_node;new_node->_prev = prev;
}

? ? ? ? erase

iterator erase(iterator pos)
{node* cur=pos._next;node*prev=cur->_prev;node*next=cur->_next;prev->_next=next;next->_prev=prev;delete cur;return iterator(next);//也可以這么寫return next
}

源代碼

list.h

#pragma once
#include<iostream>
using namespace std;
namespace Boogiepop
{//節點template<class T>//當我們不需要也不想要讓訪問限定符限制的時候//可以用struct來定義類，而不是用classstruct list_node{T _data;			//數據list_node<T>* _next;//指向下一個節點的指針list_node<T>* _prev;//指向前一個節點的指針//構造函數list_node(const T& x = T()) :_data(x), _next(nullptr), _prev(nullptr){}};//迭代器template<class T, class Ref>//當我們不需要也不想要讓訪問限定符限制的時候//可以用struct來定義類，而不是用class//普通迭代器struct _list_iterator{typedef list_node<T> node;typedef _list_iterator<T, Ref> Self;node* _node;//構造迭代器_list_iterator(node* node) :_node(node){}//解引用不是結點//用引用返回可以修改這個數值T& operator*(){return _node->_data;}////不能實現，因為const list_iterator對象才能調用這個重載////但是在這種情況下const list_iterator對象不能調用++和--//const T& operator*()const//{//	return _node->_data;//}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){_list_iterator<T, Ref> tmp(*this);//淺拷貝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp(*this);//淺拷貝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}};//const迭代器template<class T, class Ref>//當我們不需要也不想要讓訪問限定符限制的時候//可以用struct來定義類，而不是用class//普通迭代器struct _list_const_iterator{typedef list_node<T> node;typedef _list_const_iterator<T, Ref> Self;node* _node;//構造迭代器_list_const_iterator(node* node) :_node(node){}//解引用不是結點//用引用返回可以修改這個數值const Self& operator*(){return _node->_data;}//迭代器++//前置++Self& operator++(){_node = _node->_next;return *this;}//后置Self& operator++(int){Self tmp(*this);//淺拷貝_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->prev;return *this;}//后置--Self& operator--(int){Self tmp(*this);//淺拷貝_node = _node->prev;return *this;}//返回是否相等bool operator!=(const Self& it)const{return _node != it._node;}bool operator==(const Self& it)const{return _node == it._node;}};//鏈表template<class T, class Ref>class list{typedef list_node<T> node;typedef _list_iterator<T, Ref> Self;typedef _list_const_iterator<T, Ref> const_Self;public://普通迭代器typedef _list_iterator<T, Ref> iterator;//const迭代器typedef const _list_iterator<T, Ref> const_iterator;//返回迭代器iterator begin(){return iterator(_head->_next);}//返回迭代器iterator end(){return iterator(_head);}//構造函數list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//拷貝構造函數list(const list<T>& lt){_head = new node;_head->_next = _head;_head->_prev = _head;for (const auto& x : lt){push_back(x);}}//花括號初始化list(initializer_list<T> il){_head = new node;_head->_next = _head;_head->_prev = _head;for (const auto& x : lt){push_back(x);}}//=運算符重載list<T>& operator=(const list<T>& lt){if (this != &lt){clear();for (const auto& x : lt){push_back(x);}}return *this;}//析構函數//釋放結點~list(){clear();delete _head;_head = nullptr;}void push_back(const T& x){node* new_node = new node(x);//頭結點node* tail = _head->_prev;//尾節點tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;}//交換數據void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//插入元素void insert(iterator pos, const T& x){node* cur = pos._node;node* new_node = new node(x);node* prev = cur->_prev;//prev  new_node  curprev->_next = new_node;new_node->_next = cur;cur->_prev = new_node;new_node->_prev = prev;}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}iterator erase(iterator pos){node* cur = pos._next;node* prev = cur->_prev;node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;return iterator(next);//也可以這么寫return next}//返回鏈表大小size_t size()const{}private:node* _head;		//指向頭節點的指針};
};

? ? ? ?

????????提示：類的模板沒有實例化不能去類模板中找后面的東西編譯器無法區分const_iterator 是嵌套內類還是靜態成員變量，typename是告訴編譯器確認過是類型

????????本期內容就到這里，感興趣的可以點個贊謝謝

封面圖自取：?

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

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

相關文章

不引入變量 異或交換的缺點

不引入變量 異或交換的缺點

文章目錄選擇排序正確代碼交換兩個數位置的方法引入中間變量不引入中間變量&#xff0c;使用異或的方法錯誤原因優化代碼選擇排序正確代碼 // 數組中交換i和j位置的數public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}// 選擇排…
閱讀更多...
VS Code中使用Git的方法：環境配置與Git操作

VS Code中使用Git的方法：環境配置與Git操作

本文介紹在Windows電腦的VS Code中&#xff0c;配置Git環境并使用Git命令、功能的方法。 1 環境部署 首先&#xff0c;我們需要分別安裝Git環境與VS Code軟件。這里需要注意&#xff0c;即使是在VS Code中使用Git&#xff0c;也需要我們首先在電腦上單獨配置好Git的環境&#…
閱讀更多...
在 Windows 上安裝和運行 Apache Kafka

在 Windows 上安裝和運行 Apache Kafka

Apache Kafka是一款開源應用程序&#xff0c;用于實時處理海量數據流。Apache Kafka 是一個發布-訂閱消息系統。消息系統允許您在進程、應用程序和服務器之間發送消息。廣義上講&#xff0c;Apache Kafka 是一款可以定義主題并進行進一步處理的軟件。 下載和安裝 Apache Kafk…
閱讀更多...
【嵌入式電機控制#8】編碼器測速實戰

【嵌入式電機控制#8】編碼器測速實戰

一、編碼器測速重要參數有刷電機編碼器參數&#xff08;其他的后面會慢慢提及&#xff0c;也可以在某寶看&#xff09;1. 編碼器分辨率&#xff08;PPR&#xff09;2. 編碼器工作電壓 3. 電機減速比 例如 30&#xff1a;1 指的就是電機減速軸轉1圈&#xff0c;編碼器轉30圈。注…
閱讀更多...
在C#中，可以不實例化一個類而直接調用其靜態字段

在C#中，可以不實例化一個類而直接調用其靜態字段

這是因為靜態成員&#xff08;static members&#xff09;屬于類本身&#xff0c;而不是類的實例。這是靜態成員的核心特性1. 靜態成員屬于類&#xff0c;而非實例當用static關鍵字修飾字段、方法或屬性時&#xff0c;這些成員會綁定到類級別&#xff0c;而不是實例級別。它們在…
閱讀更多...
Win11 安裝 Visual Studio（保姆教程 - 更新至2025.07）

Win11 安裝 Visual Studio（保姆教程 - 更新至2025.07）

Visual Studio 安裝&#xff08;保姆教程 - 更新至2025.07&#xff09; 前言安裝須知安裝過程1. 下載安裝包2. 安裝3. 注冊4. 創建桌面快捷方式 前言 本教程針對 非計算機相關專業的小白用戶 &#xff0c;手把手教你如何基于 win11 操作系統 安裝 Visual Studio 2022。安裝搭載…
閱讀更多...
工商銀行杭州軟開校招面經分享

工商銀行杭州軟開校招面經分享

近年來，央國企成為了很多求職者的首選，無論是校招還是社招。不過，在選擇央國企的時候，還是盡量要選擇壟斷性或者盈利多的。 昨天看到一份 2024 年中國企業 500 強榜單中提到的最賺錢的十家央國企的名單，給大家分享一下。 排名企業名稱成立時間主要業務描述2024年營收（萬…
閱讀更多...
李宏毅genai筆記：推理

李宏毅genai筆記：推理

0 思考越多效果越好 可以把算力投入在training的時候&#xff0c;也可以投入在testing上面 連起來的線表示表現是差不多的&#xff0c;越高分&#xff08;越右上方&#xff09;越好 同樣-1000分&#xff0c;可以訓練時候用力較少&#xff0c;test的時候多用點算力 但是training…
閱讀更多...
使用SSH隧道連接遠程主機

使用SSH隧道連接遠程主機

概述 SSH（Secure Shell 的縮寫）是一種網絡協議，通過使用身份驗證機制，是兩臺計算機進行加密通信。 SSH 主要用途是登錄服務器，還可以作為加密通信的中介，充當兩臺服務器之間的通信加密跳板，這個功能稱為端口轉發（port forwarding），又稱 SSH 隧道（tunnel）。 端口…
閱讀更多...
數據結構---鏈表理解（二）

數據結構---鏈表理解（二）

文章目錄 二、鏈表2.1 鏈表初始化2.2 單鏈表2.2.1 單鏈表---頭插法2.2.2 單鏈表---單鏈表遍歷2.2.3 單鏈表---尾插法2.2.4 單鏈表---在指定位置插入數據2.2.5 單鏈表---刪除指定位置節點2.2.6 單鏈表---獲取鏈表長度2.2.7 單鏈表---釋放鏈表 二、鏈表 暫時到這一步你就理解為&a…
閱讀更多...
Playnite使用指北 —— 一個優秀的本地化游戲管理工具

Playnite使用指北 —— 一個優秀的本地化游戲管理工具

為何我們使用 Playnite&#xff1f; 首先我們需要知道 Playnite 是什么&#xff0c;如果你有過用 emby 等管理過電影影視的經驗&#xff0c;你可能會對這種工具感到熟悉&#xff1a; Playnite 是一個開源的本地化的游戲管理軟件&#xff0c;可以實現多平臺的管理&#xff08;S…
閱讀更多...
時間與空間復雜度詳解：算法效率的度量衡

時間與空間復雜度詳解：算法效率的度量衡

一、為什么需要復雜度分析&#xff1f; 想象你正在開發一個手機通訊錄應用&#xff0c;需要實現聯系人搜索功能。你有兩種算法可以選擇&#xff1a; // 算法A&#xff1a;線性搜索 public Contact linearSearch(List<Contact> contacts, String name) {for (Contact c …
閱讀更多...
408第三季part2 - 計算機網絡 - 交換機

408第三季part2 - 計算機網絡 - 交換機

理解 題目 如果你這么做 那你完了&#xff0c;因為這種叫存儲轉發 直通只轉目的地址 b 再次理解 A發數據到交換機里想給B 然后交換表會記錄A的MAC地址和端口 然后因為交換表找不到B&#xff0c;所以A會把BCD全部肘一遍&#xff08;廣播&#xff09;&#xff0c;最終只有B會…
閱讀更多...
從零開始開發純血鴻蒙應用之探析倉頡語言與ArkTS的差異

從零開始開發純血鴻蒙應用之探析倉頡語言與ArkTS的差異

探析倉頡語言與ArkTS的差異 〇、前言一、IDE 的支持程度不同二、內置組件的使用方式不同三、頁面路由實現方式的不同四、總結 〇、前言 截止到本文發布的日期為止&#xff0c;鴻蒙官方所推薦的開發原生鴻蒙應用的語言&#xff0c;有兩種&#xff0c;分別是擴展自 Typescript 的…
閱讀更多...
Cursor/VScode ,點擊運行按鈕，就打開新的終端，如何設置為在當前終端運行文件而不是重新打開終端----一招搞定篇

Cursor/VScode ,點擊運行按鈕，就打開新的終端，如何設置為在當前終端運行文件而不是重新打開終端----一招搞定篇

我發現就是&#xff0c;我運行.py&#xff0c;點擊完運行按鈕&#xff0c;就給我重新打開一個終端&#xff0c;然后新的終端是在base環境中的&#xff0c;就跟麻煩 還得在當前終端輸入python3 test.py 來運行文件。能不能修改。1、打開cursor或者vscode 。 同時按下 ctrlshiftp…
閱讀更多...
【STM32實踐篇】：I2C驅動編寫

【STM32實踐篇】：I2C驅動編寫

文章目錄I2C 物理層I2C 協議層1. 數據有效性2. 起始和停止信號3. 應答響應4. 總線的尋址方式5. 數據傳輸5.1 主機向從機發送數據5.2 主機由從機中讀數據5.3 I2C通信復合格式I2C 驅動編寫1. 配置 SCL 和 SDA2. I2C起始信號和停止信號3. 等待從設備應答4. 主機發送ACK和NACK信號5…
閱讀更多...
ragflow本地部署教程linux Ubuntu系統

ragflow本地部署教程linux Ubuntu系統

以下是一份在 Ubuntu 系統上本地部署 RAGFlow 的詳細教程。 一、基礎環境準備 1.硬件要求 –CPU ≥ 4核 –RAM ≥ 16 GB –磁盤空間 ≥ 50 GB&#xff08;建議 SSD&#xff09; 2.系統配置 更新系統 sudo apt update && sudo apt upgrade -y 設置內核參數&#xff…
閱讀更多...
[netty5: WebSocketClientHandshaker WebSocketClientHandshakerFactory]-源碼分析

[netty5: WebSocketClientHandshaker WebSocketClientHandshakerFactory]-源碼分析

在閱讀這篇文章前&#xff0c;推薦先閱讀以下內容&#xff1a; [netty5: WebSocketFrame]-源碼分析[netty5: WebSocketFrameEncoder & WebSocketFrameDecoder]-源碼解析 WebSocketClientHandshakerFactory WebSocketClientHandshakerFactory 是用于根據 URI 和協議版本創…
閱讀更多...
4.2 如何訓練?個 LLM

4.2 如何訓練?個 LLM

?般??&#xff0c;訓練?個完整的 LLM 需要經過圖1中的三個階段——Pretrain、SFT 和 RLHF。 4.2.1 Pretrain 預訓練任務與架構 任務類型&#xff1a;采用因果語言模型&#xff08;CLM&#xff09;&#xff0c;通過預測下一個 token 進行訓練&#xff0c;與傳統預訓練模型…
閱讀更多...
Qt中的QObject::moveToThread方法詳解

Qt中的QObject::moveToThread方法詳解

一、QObject::moveToThread方法QObject::moveToThread()是Qt框架中一個非常重要的功能&#xff0c;它允許改變QObject及其子對象的線程關聯性。這個功能在多線程編程中特別有用&#xff0c;可以將耗時操作移到工作線程執行&#xff0c;避免阻塞主線程/GUI線程。基本用法void QO…
閱讀更多...
最新文章

Copyright @ 2022~2023