C++STL容器List的模擬實現

一、引言

? ? ? ? list的實現，還是比較簡單的，大家只要想著土家樓的形狀，畫出圖來就好了，不需要過多擔心。本次的博客會發出一個完整的實現List的List.hpp，以后也會這樣，主要是分段發被說孩子分段生。

二、模擬List

? ? ? ? 由于list中的結構需要特定的類型和特定的指定地址的，所以我們先要實現list中的結點和迭代器。正所謂"工欲善其事，必先利其器"。

? ? ? ? 2.1? ? ? ? List內的結點制造

?????????????????可以理解為一個包裹，用箱子包裹著的網購物品，list相當于分配的快遞線。list結點要有前后指針，肯定也要有存儲數據的類型。所以list_node中設計三個數據。

// 模版的使用。
// 可以套用任何類型，讓編譯器自己去推。
template< class T >
// 用struct是因為struct默認public訪問(也就是允許訪問任何資源)。
struct List_Node
{// 缺省參數，未傳參時，可以默認初始化_val。// _next和_prev都是nullptr，初始化好，方便list類蓋。List_Node(T val = T()):_val(val), _next(nullptr), _prev(nullptr){;}// C++11的萬能引用，等些到萬能引用會粘貼好的。template < class X >List_Node(X&& val):_val(val), _next(nullptr), _prev(nullptr){;}T _val;List_Node* _next;List_Node* _prev;
};

? ? ? ? 2.2? ? ? Iterator的模擬實現

? ? ? ? ? ? ? ? iterator迭代器是用來代替指針指向list中的地址的，所以肯定要有list結點的指針。在iterator迭代器中我們需要重載他們的運算符，重載運算符是C++的特性(operator 要重載的運算符，值得一提的是，重載的運算符不能違背運算符本身之外的操作，不然很容易報錯)。我們根據迭代器類比指針就可以知道要重載什么運算符，由于list迭代器是雙向迭代器，不支持+、-某一位置的單位距離，所以我們不能支持Self operator + ()和Self operator - ()，不僅如此還要刪除掉他們。使用delete關鍵字，令這兩個函數賦值delete，兩個函數就會停止生成。

template< class T , class Ptr , class Ref >
struct Iterator
{// 設置list中的List_Node，一個具有標識性的名字。// 封裝好一點。typedef List_Node < T > Node;// 可變性// 為了實現在list中的普通類型和const類型的迭代器。// 不用實現兩份代碼。// 在接下來的list中會講。// 最主要的原因是list的迭代器不能像vector中的迭代器直接加const。// 如果只加const，說明迭代器指向了另一個結點類型，根本無法適用。typedef Iterator < T , Ptr , Ref > Self;// 而且這樣不用寫一大串類型名。// 初始化對象。Iterator(Node* node):_node(node){;}Ref operator * (){return _node->_val;}Ptr operator -> (){return &(_node->_val);}Self& operator ++ (){_node = _node->_next;return (*this);}Self& operator -- (){_node = _node->_prev;return _node;}Self operator ++ (int){Self tmp(_node);_node = _node->_next;return tmp;}Self operator -- (int){Self tmp(_node);_node = _node->_next;return tmp;}Self& operator = (const Self& s){_node = s._node;return (*this);}// 減少拷貝，怕臨時值搗亂，無法左值引用。bool operator == (const Self& node){return _node == node._node;}bool operator != (const Self& node){return _node != node._node;}// 刪除這兩個函數，不讓這兩個函數被錯誤調用。Self& operator + (size_t i) = delete;Self& operator - (size_t i) = delete;Node* _node;
};

? ? ? ? 2.3? ? ? ? List中的基本結構和初始化函數

? ? ? ? ? ? ? ? List中一定包含著List_Node類型結點，就像快遞線上有著的包裹，回轉壽司有著壽司，土家族樓有著房間一樣。上一章我們說過如果設計一個環形的結構，不知道以哪個結點為開頭，所以我們新增一個帶頭鏈接點為開頭，避免群龍無首的事情發生。另外插入過程中，我們無法通過結點直接的運算得到插入結點總數量為多少，所以我們添加一個變量，記錄插入結點的總數量。

// 無參構造
List()
{_lt = new Node();_lt->_next = _lt;_lt->_prev = _lt;
}// 初始化列表構造，就把它當做數組就行了。
// 另外initializer_list是C++11的內容，使用時記得調好編譯器選項。
List(initializer_list<T> lt)
{_lt = new Node();for (auto& e : lt){Emplace_back(e);}
}Node* _lt;
size_t _n;

? ? ? ? 2.4? ? ? ? size()函數和empty()函數

? ? ? ? ? ? ? ? List不像Vector和String一樣有capacity(）有著空間大小，只要有_n就行了。根據_n我們可以判斷List中是否存在數據以及插入數據有多少個。

size_t size()
{return _n;
}bool empty()
{return _n == 0;
}

? ? ? ? 2.5? ? ? ? Insert()和Erase()函數

? ? ? ? ? ? ? ? Insert()函數和Erase()函數都是在指定位置插入刪除。

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

? ? ? ? ? ? ? ? 我們先從插入開始講起。插入只需要將pos位置上的結點(我們將這個結點設為結點A)和要pos位置之前(_prev)的結點(我們將這個結點設為結點B)和該位置的結點的_prev、_next指針做修改就可以了。由圖可知讓結點A(pos)的_prev指針指向新結點的地址，結點B(--pos上的結點)的_next指針指向新結點的地址，再讓新結點的_prev指向結點B，_next指針指向結點A。

? ? ? ? ? ? ? ? 講完插入，就要將刪除了。刪除就更簡單了，將要刪除結點pos之前的位置和要刪除結點之后的位置直接相連。再將pos上的結點delete掉，返回現在處于pos位置上的結點，也就是pos位置上的下一個結點。

????????另外為什么需要返回插入、刪除位置上新結點？

? ? ? ? 是為了更新迭代器顯示的pos位置上的結點避免訪問出現錯誤，那為什么不直接在函數內修改pos呢？

? ? ? ? 這個主要是出于有些迭代器不需要去修改，這個只能讓用戶去進行決定，比如說insert(begin())，begin()需要修改內部的指針嗎？況且有時候這是一份吃力不討好的工作，畢竟拷貝也是有效率犧牲的。其前面也提到過C++追求極致的效率，是不可能損害效率的。

iterator Insert(iterator pos , const T& val)
{// 前節點Node* prev = ((pos._node)->_prev);// 后節點Node* next = pos._node;// 新插入節點。Node* tmp = new Node (val);// 新節點插入tmp->_next = next;tmp->_prev = prev;// 前節點更新next（記錄下一個節點的地址。）prev->_next = tmp;// 后節點節點更新prev（記錄上一個節點的地址。）next->_prev = tmp;// 更新結點個數。++_n;return iterator(tmp);
}// 按照STL的思想，應該是返回后一個位置，因為返回刪除后該位置的指針，后一個位置已經頂替了該位置的指針。
iterator Erase(iterator pos)
{// 判斷是否存在數據。assert(empty());// 刪除位置不能為確定位置的頭結點。assert(pos != End());// 前節點Node* prev = ((pos._node)->_prev);// 后節點Node* next = (pos._node)->_next;// 刪除該節點。next->_prev = prev;prev->_next = next;pos._node->_next = pos._node->_prev = nullptr;delete pos._node;// 更新結點個數。--_n;// 構建匿名對象(方便返回)，相當于調用一個Iterator的初始化函數。return iterator(next);
}

? ? ? ? 2.6????????begin()函數和end()函數

? ? ? ? ? ? ? ? begin()指明List中的起始位置(當List中沒有結點時，會等于end())，所以begin()應返回的是定位的頭結點。end()可以設為定位頭結點本身。

		iterator begin(){return iterator(_lt->_next);}iterator end(){return iterator(_lt);}

? ? ? ? 2.7? ? ? ? push_back()函數和pop_back()函數????????

? ? ? ? ? ? ? ?至于這個就更簡單了，代碼應該講究能復用時就復用，這樣能提高代碼的健壯性?，畢竟改代碼只用改一個地方還是改幾個地方還是很便捷的，最重要的是使代碼變得簡潔，以后用的時候也好用。所以我們直接復用insert和erase。

void push_back(T val)
{Insert(end(),val);
}void pop_back()
{Erase(end());
}

????????2.8? ? ? ? emplace()函數和empalce_back()函數????????

? ? ? ? ? ? ? ? 這個我保證C++11的時候絕對會講。到時候放個鏈接在這里。

三、全部代碼

#include <iostream>
#include <initializer_list>
#include <cassert>
using namespace std;namespace Link_List
{template< class T >struct List_Node{List_Node(T val = T()):_val(val), _next(nullptr), _prev(nullptr){;}template < class X >List_Node(X&& val):_val(val), _next(nullptr), _prev(nullptr){;}T _val;List_Node* _next;List_Node* _prev;};template< class T , class Ptr , class Ref >struct Iterator{typedef List_Node < T > Node;typedef Iterator < T , Ptr , Ref > Self;Iterator(Node* node):_node(node){;}Ref operator * (){return _node->_val;}Ptr operator -> (){return &(_node->_val);}Self& operator ++ (){_node = _node->_next;return (*this);}Self& operator -- (){_node = _node->_prev;return _node;}Self operator ++ (int){Self tmp(_node);_node = _node->_next;return tmp;}Self operator -- (int){Self tmp(_node);_node = _node->_next;return tmp;}// 減少拷貝，怕臨時值搗亂，無法左值引用。bool operator == (const Self& node){return _node == node._node;}bool operator != (const Self& node){return _node != node._node;}// 刪除這兩個函數，不讓這兩個函數被錯誤調用。Self& operator + (size_t i) = delete;Self& operator - (size_t i) = delete;Node* _node;};template < class T > class List{public:typedef List_Node < T > Node;typedef Iterator < T  , T* , T& > iterator;typedef Iterator < T, const T*, const T& > Const_Iterator;List(){_lt = new Node();_lt->_next = _lt;_lt->_prev = _lt;}List(initializer_list<T> lt){// 設計一個帶頭結點。_lt = new Node();_lt->_next = _lt;_lt->_prev = _lt;for (auto& e : lt){Emplace_back(e);}}~List(){size_t n = _n;for(int i = 0;i < n;++i){Erase(begin());}//cout << endl;//cout << _n << ":" << n << endl;//iterator it = Begin();//while (it != End())//{//	cout << *it << endl;//	++it;//}delete _lt;_lt = nullptr;}iterator begin(){return iterator(_lt->_next);}iterator end(){return iterator(_lt);}iterator Insert(iterator pos , const T& val){// 前節點Node* prev = ((pos._node)->_prev);// 后節點Node* next = pos._node;// 新插入節點。Node* tmp = new Node (val);// 新節點插入tmp->_next = next;tmp->_prev = prev;// 前節點更新next（記錄下一個節點的地址。）prev->_next = tmp;// 后節點節點更新prev（記錄上一個節點的地址。）next->_prev = tmp;// 更新結點個數。++_n;return iterator(tmp);}// 按照STL的思想，應該是返回后一個位置，因為返回刪除后該位置的指針，后一個位置已經頂替了該位置的指針。iterator Erase(iterator pos){// 判斷是否存在數據。// assert()不滿足則觸發。// 本質是一種檢查。// 例如assert(false);常常被拿來做防御式編程assert(size());// 刪除位置不能為確定位置的頭結點。assert(pos != end());// 前節點Node* prev = ((pos._node)->_prev);// 后節點Node* next = (pos._node)->_next;// 刪除該節點。next->_prev = prev;prev->_next = next;pos._node->_next = pos._node->_prev = nullptr;delete pos._node;// 更新結點個數。--_n;// 構建匿名對象(方便返回)，相當于調用一個Iterator的初始化函數。return iterator(next);}size_t size(){return _n;}bool empty(){return _n == 0;}void push_back(T val){Insert(end(),val);}void pop_back(){Erase(end());}iterator add(iterator it){return it;}// 接收參數包的類型，參數包不是單純相同類型的集成。template < class X , class... ARGS >// 參數包后面...是展開的意思。// 前面則類似聲明的意思。iterator add(iterator pos, X&& val, ARGS&&... args){iterator it = Insert(pos , val);return add(it, args...);}template < class... ARGS >iterator Emplace(iterator cit, ARGS&&... args){iterator it (cit);return add(it,args...);}template < class... ARGS >void Emplace_back(ARGS&&... args){Emplace(end(),args...);}private:Node* _lt = nullptr;size_t _n;};// 測試Insert函數void test01(){List < int > lt;for (int i = 0; i < 13; ++i){lt.push_back(i);}//lt.Erase(lt.begin());//lt.Erase(lt.end());}void test02(){List < int > lt = { 1,2,3,4,5,6,7 };for (auto& e : lt){std::cout << e << " ";}std::cout << std::endl;}void test03(){//List < int > lt = { 11121,131,0321 ,1311,33,113,1321 };List < int > lt;int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };for (int i = 0; i < sizeof(a) / sizeof(int); ++i){lt.push_back(a[i]);}List<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';++it;}cout << endl;}
}int main()
{Link_List::test02();return 0;
}

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

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

相關文章

區塊鏈 + 域名Web3時代域名投資的新風口（上）

區塊鏈 + 域名Web3時代域名投資的新風口（上）

關于Dynadot Dynadot是通過ICANN認證的域名注冊商&#xff0c;自2002年成立以來&#xff0c;服務于全球108個國家和地區的客戶&#xff0c;為數以萬計的客戶提供簡潔&#xff0c;優惠&#xff0c;安全的域名注冊以及管理服務。 Dynadot平臺操作教程索引&#xff08;包括域名郵…
閱讀更多...
電子電氣架構 --- 軟件會給汽車帶來哪些變化？

電子電氣架構 --- 軟件會給汽車帶來哪些變化？

我是穿拖鞋的漢子，魔都中堅持長期主義的汽車電子工程師。 老規矩，分享一段喜歡的文字，避免自己成為高知識低文化的工程師： 做到欲望極簡，了解自己的真實欲望，不受外在潮流的影響，不盲從，不跟風。把自己的精力全部用在自己。一是去掉多余，凡事找規律，基礎是誠信；二是…
閱讀更多...
在rtthread中，互斥量不能在中斷服務例程中使用？以及線程多次持有互斥量的情況怎么理解？

在rtthread中，互斥量不能在中斷服務例程中使用？以及線程多次持有互斥量的情況怎么理解？

互斥鎖的所有權&#xff1a;互斥量的狀態只有兩種&#xff0c;開鎖或閉鎖&#xff08;兩種狀態值&#xff09;。當有線程持有它時&#xff0c;互斥量處于閉鎖狀態&#xff0c;由這個線程獲得它的所有權。相反&#xff0c;當這個線程釋放它時&#xff0c;將對互斥量進行開鎖&…
閱讀更多...
力扣32:最長有效括號

力扣32:最長有效括號

力扣32:最長有效括號題目思路代碼題目 給你一個只包含 ‘(’ 和 ‘)’ 的字符串&#xff0c;找出最長有效&#xff08;格式正確且連續&#xff09;括號 子串 的長度。 左右括號匹配&#xff0c;即每個左括號都有對應的右括號將其閉合的字符串是格式正確的&#xff0c;比如 “…
閱讀更多...
機器學習實例應用

機器學習實例應用

K最近鄰算法K近鄰算法(KNN,k-Nearest Neighbor),每個樣本都可以用它的最接近的K個鄰近值來代表。算法說明&#xff1a;①輸入沒有標簽的新數據&#xff0c;將新數據的每個特征與樣本集中數據對應的特征進行比較&#xff0c;然后算法提取樣本集中特征最相似數據&#xff08;最近…
閱讀更多...
力扣 hot100 Day77

力扣 hot100 Day77

連做了幾個動態規劃的中等題&#xff0c;還是比較有套路的&#xff0c;這里只簡要分析一下最長遞增子序列&#xff0c;設定dp[i]為以nums[i]結尾的最長子序列&#xff0c;遞推公式就好推了乘積最大子數組&#xff0c;和上面類似&#xff0c;但考慮到負負得正&#xff0c;所以需…
閱讀更多...
深入解析RabbitMQ與AMQP-CPP：從原理到實戰應用

深入解析RabbitMQ與AMQP-CPP：從原理到實戰應用

一、RabbitMQ安裝 1.安裝 RabbitMQ sudo apt install rabbitmq-serverRabbitMQ 的簡單使用 # 啟動服務 sudo systemctl start rabbitmq-server.service # 查看服務狀態 sudo systemctl status rabbitmq-server.service # 安裝完成的時候默認有個用戶 guest &#xff0c;但是權限…
閱讀更多...
（論文速讀）ViDAR：視覺自動駕駛預訓練框架

（論文速讀）ViDAR：視覺自動駕駛預訓練框架

論文題目&#xff1a;Visual Point Cloud Forecasting enables Scalable Autonomous Driving&#xff08;視覺點云預測實現可擴展的自動駕駛&#xff09; 會議&#xff1a;CVPR2024 摘要&#xff1a;與對通用視覺的廣泛研究相比&#xff0c;可擴展視覺自動駕駛的預訓練很少被探…
閱讀更多...
《Unity Shader入門精要》學習筆記二

《Unity Shader入門精要》學習筆記二

1、基礎光照&#xff08;1&#xff09;看世界的光模擬真實的光照環境來生成一張圖像&#xff0c;需要考慮3種物理現象。光線從光源中被發射出來。光線和場景中的一些物體相交&#xff1a;一些光線被物體吸收了&#xff0c;而另一些光線被散射到其他方向攝像機吸收了一些光&…
閱讀更多...
Windchill 11.0使用枚舉類型自定義實用程序實現生命周期狀態管理

Windchill 11.0使用枚舉類型自定義實用程序實現生命周期狀態管理

一、Enumerated Type Customization Utility 枚舉類型自定義實用程序，可用于添加或編輯枚舉類型的值，在Windchill 12.0+中可直接在類型和屬性管理中編輯，如下圖所示，而在Windchill 11.0中只能通過windchill shell啟動程序，下面將詳細介紹Windchill 11.0中啟動并使用枚舉類…
閱讀更多...
UGUI源碼剖析（10）：總結——基于源碼分析的UGUI設計原則與性能優化策略

UGUI源碼剖析（10）：總結——基于源碼分析的UGUI設計原則與性能優化策略

UGUI源碼剖析&#xff08;第十章&#xff09;&#xff1a;總結——基于源碼分析的UGUI設計原則與性能優化策略 本系列文章對UGUI的核心組件與系統進行了深入的源代碼級分析。本章旨在對前述內容進行系統性總結&#xff0c;提煉出UGUI框架最核心的設計原則&#xff0c;并基于這些…
閱讀更多...
STM32N6引入NPU，為邊緣AI插上“隱形的翅膀”

STM32N6引入NPU，為邊緣AI插上“隱形的翅膀”

2025年的春天格外特別。伴隨著人形機器人、DeepSeek的強勢刷屏&#xff0c;AI成了最有前景的賽道。萬物皆可AI&#xff0c;萬物也在尋覓用上AI或者讓AI“轉正”的“aha moment”。 幫助機器更好地“思考”&#xff0c;讓更多的AI走向邊緣&#xff0c;是AI發展的重要趨勢之一。…
閱讀更多...
演練：使用VB開發多智能體協作的榮格八維分析器

演練：使用VB開發多智能體協作的榮格八維分析器

在大語言模型高速發展的時代&#xff0c;我們面對困難的語義分析任務&#xff0c;通過構建智能體進行處理是一個流行趨勢。本文將介紹如何使用 Visual Basic .NET 開發一個多智能體協作系統&#xff0c;用于分析聊天記錄中特定人物的榮格八維人格類型。 本文使用 CC-BY-NC-SA …
閱讀更多...
llamafactory使用qlora訓練

llamafactory使用qlora訓練

llamafactory使用qlora訓練 1.環境搭建 conda create -n qlora python3.10 -y conda activate qlora# 克隆LLaMA-Factory倉庫 git clone https://github.com/hiyouga/LLaMA-Factory.git# 進入倉庫目錄 cd LLaMA-Factory# 切換到0.9.4版本 git checkout v0.9.4pip install -e .2…
閱讀更多...
模型微調/量化技術整理

模型微調/量化技術整理

一、模型微調技術1.模型微調簡介大模型微調(Fine-tuning)&#xff0c;是指在已經預訓練好的大語言模型基礎上&#xff08;基座模型&#xff09;&#xff0c;使用特定的數據集進行進一步訓練&#xff0c;讓模型適應特定任務或領域。通常LLM的預訓練是無監督的&#xff0c;但微調…
閱讀更多...
實踐筆記-VSCode與IDE同步問題解決指南；程序總是進入中斷服務程序。

實踐筆記-VSCode與IDE同步問題解決指南；程序總是進入中斷服務程序。

一、VSCode 修改文件后&#xff0c;IDE 未同步如果你在 VSCode 中異步修改了項目文件內容&#xff0c;但 S32DS 或 Keil&#xff08;等集成開發環境&#xff09;中的項目沒有同步更新&#xff0c;有兩個解決方法&#xff1a;檢查文件是否已保存&#xff1a;確保 VSCode 中修改的…
閱讀更多...
C#WPF實戰出真汁04--登錄功能實現

C#WPF實戰出真汁04--登錄功能實現

1、登錄功能實現要點對于登錄系統&#xff0c;應該注意幾個要點&#xff1a;用戶認證流程設計&#xff0c;密碼存儲與驗證&#xff0c;會話管理&#xff0c;防暴力破解措施&#xff0c;錯誤處理與提示2、登錄功能的視圖模型首先在xaml文件中必須指定該頁面使用的視圖模型&#…
閱讀更多...
鴻蒙入門簡化版

鴻蒙入門簡化版

第一步&#xff1a; 首先下載DEVStudio https://developer.huawei.com/consumer/cn/deveco-studio/ 第二步&#xff1a; 了解基本的ArkTs語言 https://developer.huawei.com/consumer/cn/doc/harmonyos-guides/introduction-to-arkts 第三步 &#xff1a; 教學視頻有兩個途徑&a…
閱讀更多...
day25｜學習前端js

day25｜學習前端js

函數聲明&#xff0c;被提升&#xff08;hoisting&#xff09;。函數表達式必須先定義才能用。對象解構&#xff0c;按屬性名數組解構按順序點運算符. 對象.屬性名哪些可迭代&#xff08;可以被for..of循環的東西&#xff09;&#xff1a;array&#xff0c;string&#xff0c;m…
閱讀更多...
quic協議與應用開發

quic協議與應用開發

quic為什么出現&#xff1f;quic主要是為了解決TCP協議的局限性而提出的&#xff0c;具體來說是要解決如下問題&#xff1a;1. 加密連接建立時間長TCP協議是傳輸層協議&#xff0c;而TLS是會話層協議&#xff0c;在Linux等主流操作系統中TCP在內核實現而TLS一般在用戶態實現&am…
閱讀更多...
最新文章

Copyright @ 2022~2023