C++之List模擬實現

目錄

list的邏輯結構

構造函數

拷貝構造函數

賦值運算符重載

返回迭代器的初始位置

返回迭代器的最終位置

?元素的插入

頭插

尾插?

刪除元素

頭刪

尾刪

清空整個鏈表

析構函數

正向迭代器?

反向迭代器

整體代碼?

?上期我們學寫了list的基本操作，本期我們將學習list的模擬實現。

list的邏輯結構

list是一個帶頭結點的雙向循環鏈表。

構造函數

	list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}

?這是一個無參的構造函數。

        template<class inputiterator>list(inputiterator begin, inputiterator end){_head = new Node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}}

這是用迭代器區間進行初始化的構造函數。

		list(int n, const T& data = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;while (n != 0){push_back(data);n--;}}

?初始化鏈表的n個節點，使它們的每個結點的數據為data的值。

拷貝構造函數

	    list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}

這是拷貝構造函數的現代寫法，通過使用迭代器區間構造函數構造了一個list的臨時對象，然后交換了臨時對象和當前對象的頭結點指針，前提是得保證當前結點的頭指針不為空，不然到時候調用析構函數時會將同一空間釋放兩次，導致出錯。

賦值運算符重載

	    list<T>& operator= (const list<T>lt){std:swap(_head,lt._head);return *this;}

?先通過拷貝構造函數生成了一個臨時對象，然后再交換了臨時對象和當前對象的頭結點指針。

返回迭代器的初始位置

	iterator begin(){return  iterator(_head->_next);}

迭代器的初始位置就是頭結點的下一位置。

返回迭代器的最終位置

        iterator end(){return iterator(_head);}

迭代器的最終位置為最后一個元素的下一位置，即頭結點的位置。

?元素的插入

		iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}

?表示在當前位置之前插入一個元素，但是當前位置必須為迭代器類型。

元素的插入會導致迭代器失效嗎？
不會，因為插入元素之后會及時更改迭代器中節點指針的指向。?

頭插

        void push_front(const T& x){insert(begin(), x);}

在頭節點之前插入元素，復用了插入函數。?

尾插?

	    void push_back(const T& x){insert(end(), x);}

在最后一個元素的后面插入元素，復用了插入函數。

刪除元素

		iterator erase(iterator pos){//前提是不能刪除掉頭結點assert(pos != end());Node* prev =pos._node->_prev;Node* next = pos._node->_next;delete pos._node;pos._node = nullptr;prev->_next = next;next->_prev = prev;return iterator(next);}

刪除某一位置之后，返回的是當前位置的下一位置的迭代器。?

元素的刪除會導致迭代器失效嗎？
會，因為刪除掉當前位置之后，當前迭代器的節點指針會被釋放。迭代器的節點都被釋放了，所以迭代器自然會失效。

頭刪

     	void pop_back(){erase(--end());}

尾刪

	    void pop_back(){erase(--end());}

清空整個鏈表

		void clear(){iterator it = begin();while (it != end()){erase(it);it++;}}

刪除除頭結點之外的所有節點。?

析構函數

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

析構函數會清空整個鏈表的信息，所以頭結點指針也會被釋放。

正向迭代器?

正向迭代器，其實就是從前往后進行鏈表元素的遍歷。

	template<class T,class Ref,class Ptr>struct list_iterator{typedef ListNode<T> Node;typedef list_iterator<T, Ref, Ptr> self;//構造函數list_iterator<T,Ref,Ptr>(Node* node):_node(node){}//解引用操作Ref operator*()    {return _node->_data;}//->操作，返回迭代器中的節點指針指向的數據的地址Ptr operator->(){return  &_node->_data;}//前置++self& operator++(){_node = _node->_next;return *this;}//后置++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//前置--self& operator--(){_node = _node->_prev;return *this;}//后置--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}//賦值運算符重載，淺拷貝self& operator=(const self& iterator){_node = iterator._node;return *this;}//判斷是否相等bool operator ==(const self& iterator) const{return _node == iterator._node;}bool operator !=(const self& iterator) const{return _node != iterator._node;}Node* _node;};

list的迭代器和vector的迭代器是不同的，vector的迭代器類型是指針類型，即內置類型。而list的迭代器類型是自定義類型。

反向迭代器

反向迭代器即從后往前進行鏈表元素的遍歷。

namespace yjd {template<class iterator,class Ref,class Ptr>class reverse_iterator{public:typedef reverse_iterator<iterator, Ref, Ptr> self;//構造函數reverse_iterator(iterator it):_it(it){}//解引用操作Ref operator*(){iterator prev = _it;return *(--prev);}//->Ptr operator->(){iterator prev = _it;return &(--prev);}//++self& operator++(){_it--;return *this;}//--self& operator--(){_it++;return *this;}//判斷是否相等bool  operator!=(const self & rit) const{return  _it != rit._it;}private:iterator _it;};}

正向迭代器和返現迭代器的開始和結束位置剛好是相對的。反向迭代器的本質仍然是正向迭代器。反向迭代器的++為正向迭代器的--。

雖然說返現迭代器的開始和結束如圖如上圖所示，但是我們真正在訪問的時候并不是訪問所示位置的元素，而是訪問其前一個位置的元素，比如要訪問rbgin位置的元素，則要讓正向迭代器進行--訪問最后一個位置的元素。?

整體代碼?

list.h

#pragma once
#include<assert.h>
#include"reverse_iterator.h"
namespace yjd 
{//節點類型template<class T>struct ListNode {ListNode* _next;ListNode* _prev;T _data;ListNode(const T& data=T()):_next(nullptr),_prev(nullptr),_data(data){}};//鏈表的迭代器類型template<class T,class Ref,class Ptr>struct list_iterator{typedef ListNode<T> Node;typedef list_iterator<T, Ref, Ptr> self;//構造函數list_iterator<T,Ref,Ptr>(Node* node):_node(node){}//解引用操作Ref operator*()    {return _node->_data;}//->操作，返回迭代器中的節點指針指向的數據的地址Ptr operator->(){return  &_node->_data;}//前置++self& operator++(){_node = _node->_next;return *this;}//后置++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//前置--self& operator--(){_node = _node->_prev;return *this;}//后置--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}//賦值運算符重載，淺拷貝self& operator=(const self& iterator){_node = iterator._node;return *this;}//判斷是否相等bool operator ==(const self& iterator) const{return _node == iterator._node;}bool operator !=(const self& iterator) const{return _node != iterator._node;}Node* _node;};//鏈表類型template<class T>class list {typedef ListNode<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;typedef reverse_iterator<iterator, T&, T*> reverse_iterator;typedef reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//構造函數list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}//構造函數，迭代器區間進行構造template<class inputiterator>list(inputiterator begin, inputiterator end){_head = new Node;_head->_next = _head;_head->_prev = _head;while (begin != end){push_back(*begin);++begin;}}//拷貝構造list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;list<T> tmp(lt.begin(), lt.end());std::swap(_head, tmp._head);}//賦值運算符重載list<T>& operator= (const list<T>lt){std:swap(_head,lt._head);return *this;}//構造函數n個datalist(int n, const T& data = T()){_head = new Node;_head->_next = _head;_head->_prev = _head;while (n != 0){push_back(data);n--;}}//尾插//void push_back(const T& data)//{//	Node* newnode = new Node(data);//	Node* tail = _head->_prev;//	tail->_next = newnode;//	newnode->_prev = tail;//	newnode->_next = _head;//	_head->_prev = newnode;//}// //rbeginreverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}//rendreverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}//beginiterator begin(){return  iterator(_head->_next);}//enditerator end(){return iterator(_head);}//beginconst_iterator begin() const{return  const_iterator(_head->_next);}//endconst_iterator end() const{return const_iterator(_head);}//元素的插入,在pos位置之前插入元素iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return iterator(newnode);}//list的頭插和尾插，可以復用insert,插入元素之后我們更改的是節點的指針，所以不會涉及到迭代器失效void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){insert(end(), x);}//鏈表刪除某一位置元素，刪除某一位置的元素，迭代器會失效嗎？會失效，因為刪除掉元素之后，會釋放節點的指針，節點的指針都被釋放了，迭代器自然也就沒有意義了iterator erase(iterator pos){//前提是不能刪除掉頭結點assert(pos != end());Node* prev =pos._node->_prev;Node* next = pos._node->_next;delete pos._node;pos._node = nullptr;prev->_next = next;next->_prev = prev;return iterator(next);}//list的尾刪頭刪void pop_back(){erase(--end());}void pop_front(){erase(begin());}//list整個的刪除，這個刪除是刪除所有的有效的節點void clear(){iterator it = begin();while (it != end()){erase(it);it++;}}//析構函數~list(){clear();delete _head;_head = nullptr;}private:Node* _head;};}

reverse_iterator.h

#pragma oncenamespace yjd {template<class iterator,class Ref,class Ptr>class reverse_iterator{public:typedef reverse_iterator<iterator, Ref, Ptr> self;//構造函數reverse_iterator(iterator it):_it(it){}//解引用操作Ref operator*(){iterator prev = _it;return *(--prev);}//->Ptr operator->(){iterator prev = _it;return &(--prev);}//++self& operator++(){_it--;return *this;}//--self& operator--(){_it++;return *this;}//判斷是否相等bool  operator!=(const self & rit) const{return  _it != rit._it;}private:iterator _it;};}

以上便是list模擬實現的所有知識點。

本期內容到此結束^_^

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

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

相關文章

蘇東坡傳-讀書筆記十一

蘇東坡傳-讀書筆記十一

蘇東坡對寫作與風格所表示的意見最為清楚。他說做文章“大略如行云流水&#xff0c;初無定質&#xff0c;但常行于所當行&#xff0c;常止于所不可不止。文理自然&#xff0c;姿態橫生。孔子曰&#xff1a;‘言之不文&#xff0c;行而不遠。’又曰&#xff1a;‘辭達而已矣。’…
閱讀更多...
【cocos creator】2.4.x實現簡單3d功能，點擊選中，旋轉，材質修改，透明材質

【cocos creator】2.4.x實現簡單3d功能，點擊選中，旋轉，材質修改，透明材質

demo下載：（待審核） https://download.csdn.net/download/K86338236/89527924 const {ccclass, property } = cc._decorator;const enum box_color {NORMAL = 0,DASHED_LINE = 1,//虛線TRANSLUCENT = 2,//半透明 }@ccclass export default class main extends cc.Component {…
閱讀更多...
STC32G/F/8H通用無刷電機驅動板

STC32G/F/8H通用無刷電機驅動板

STC32G/F/8H通用無刷電機驅動板 &#x1f4cc;相關篇《低成本STC32G8K64驅動控制BLDC開源入門學習方案》 ?該驅動板是在上一版的基礎上改版而來。這里的STC32G/F/8H所指的是封裝型號為-LQFP48的STC32G8K64、STC32G12K128、STC32F12K54、STC8H8K64U。是一款兼容有感和無感設計的…
閱讀更多...
數據結構--樹和二叉樹的一些知識點總結

數據結構--樹和二叉樹的一些知識點總結

樹是n個結點的有限集&#xff0c;當n0時&#xff0c;稱為空樹。樹是一種遞歸的數據結構&#xff0c;樹作為一種邏輯結構同時也是一種分層的結構結點的深度是從根開始自頂向下累加&#xff1b;結點的高度是從葉結點自底向上累加由于樹中的分支是有向的&#xff0c;即從雙親指向孩…
閱讀更多...
【Java算法】二分查找 下

【Java算法】二分查找 下

&#x1f525;個人主頁&#xff1a; 中草藥 &#x1f525;專欄&#xff1a;【算法工作坊】算法實戰揭秘 一.山脈數組的峰頂索引 題目鏈接&#xff1a;852.山脈數組的峰頂 ? 算法原理 這段代碼實現了一個查找山峰數組中峰值索引的算法。山峰數組是一個先遞增后遞減的數組&…
閱讀更多...
玩具營銷是如何拿捏成年人錢包？

玩具營銷是如何拿捏成年人錢包？

好像現在的成年人逐漸熱衷于偏向年輕化&#xff0c;問問題會好奇“尊嘟假嘟”&#xff0c;飯量上的“兒童套餐”&#xff0c;娃娃機前排長隊......而最突出的莫過于各類各式的玩具不斷收割當代年輕人&#xff0c;除去常給大朋友們小朋友們送去玩具福利的“麥、肯”雙門&#xf…
閱讀更多...
激光干涉儀可以完成哪些測量：全面應用解析

激光干涉儀可以完成哪些測量：全面應用解析

在高端制造領域&#xff0c;精度是衡量產品質量的關鍵指標之一。激光干涉儀作為一項高精度測量技術&#xff0c;其應用廣泛&#xff0c;對于提升產品制造精度具有重要意義。 線性測量&#xff1a;精確定位的基礎 激光干涉儀采用邁克爾遜干涉原理&#xff0c;實現線性測量。該…
閱讀更多...
AlphaGo 的傳奇故事

AlphaGo 的傳奇故事

文章目錄 一、說明二、AlphaGo 傳奇&#xff08;一&#xff09;&#xff1a;游戲規則三、AlphaGo 傳奇(二)&#xff1a;它是如何運作的&#xff1f;四、AlphaGo 傳奇&#xff08;三&#xff09;&#xff1a;史詩般的戰斗和人工智能的未來 一、說明 1997 年&#xff0c;IBM 的“…
閱讀更多...
卷積神經網絡之ResNet50遷移學習

卷積神經網絡之ResNet50遷移學習

數據準備 下載狗與狼分類數據集&#xff0c;數據來自ImageNet&#xff0c;每個分類有大約120張訓練圖像與30張驗證圖像。使用download接口下載數據集&#xff0c;并自動解壓到當前目錄。 全是小狗的圖片 另一邊全是狼的圖片 加載數據集 狼狗數據集提取自ImageNet分類數據集&a…
閱讀更多...
2-3個月的幼貓能吃主食凍干嗎？第一次吃哪款主食凍干比較好

2-3個月的幼貓能吃主食凍干嗎？第一次吃哪款主食凍干比較好

2-3個月的幼貓能吃凍干嗎&#xff1f;一般來說&#xff0c;幼貓在2-3個月左右的離乳期就可以吃凍干了。需要注意的&#xff0c;一個是要認準主食凍干&#xff0c;零食凍干會讓貓貓從小就挑食&#xff0c;以后就更不好糾正了。而且離乳期的貓貓沒有了母乳的保護&#xff0c;免疫…
閱讀更多...
Open3D 點對面的ICP算法配準（精配準）

Open3D 點對面的ICP算法配準（精配準）

目錄 一、概述 1.1核心思想 1.2實現步驟 二、代碼實現 2.1關鍵函數 2.2完整代碼 三、實現效果 3.1原始點云 3.2配準后點云 3.3計算數據 一、概述 基于點對面的ICP&#xff08;Iterative Closest Point&#xff09;配準算法是ICP的一種變體&#xff0c;它通過最小化源…
閱讀更多...
【Ty CLI】一個開箱即用的前端腳手架

【Ty CLI】一個開箱即用的前端腳手架

目錄 資源鏈接基礎命令模板創建命令幫助選擇模板開始創建開發模板 開發背景npm 發布流程問題記錄模板創建超時 更新日志 資源鏈接 文檔&#xff1a;https://ty.cli.vrteam.top/ 源碼&#xff1a;https://github.com/bosombaby/ty-cli 基礎命令 1. npm 全局安裝 npm i ty-cli…
閱讀更多...
Zabbix Sia Zabbix 邏輯漏洞（CVE-2022-23134）

Zabbix Sia Zabbix 邏輯漏洞（CVE-2022-23134）

前言 CVE-2022-23134是一個中等嚴重度的漏洞&#xff0c;影響Zabbix Web前端。這個漏洞允許未經身份驗證的用戶訪問setup.php文件的某些步驟&#xff0c;這些步驟通常只對超級管理員開放。利用這個漏洞&#xff0c;攻擊者可以通過跳過某些步驟來重新配置Zabbix前端&#xff0c…
閱讀更多...
gazebo仿真環境中加入livox mid360

gazebo仿真環境中加入livox mid360

https://github.com/Livox-SDK/livox_laser_simulation 功能包適用于ubuntu18.04 gazebo9的可以直接編譯運行。在ubutun20.04 的系統下gazebo是11版本，需要做一些修改 CMakeLists.txt文件中的 add_compile_options(-std=c++11) 改為 add_compile_options(-std=c++17)fatal er…
閱讀更多...
二一、搭建自已的語言大模型

二一、搭建自已的語言大模型

1. 配置langchain環境 使用conda創建一個虛擬環境，基于 Python3.10，并在虛擬環境內安裝項目的依賴。注意，大模型對gpu有一定的要求，否則速度會奇慢無比。 conda create -n langchain python=3.10 conda env list conda activate langchain # 拉取倉庫 $ git clone ht…
閱讀更多...
Redis-Jedis連接池\RedisTemplate\StringRedisTemplate

Redis-Jedis連接池\RedisTemplate\StringRedisTemplate

Redis-Jedis連接池\RedisTemplate\StringRedisTemplate 1. Jedis連接池1.1 通過工具類1.1.1 連接池&#xff1a;JedisConnectionFactory&#xff1a;1.1.2 test&#xff1a;&#xff08;代碼其實只有連接池那里改變了&#xff09; 2. SpringDataRedis&#xff08;lettuce&#…
閱讀更多...
終于弄明白了什么是EI！

終于弄明白了什么是EI！

EI是Engineering Index的縮寫&#xff0c;中文意為“工程索引”&#xff0c;是由美國工程信息公司(Engineering Information, Inc.)編輯出版的著名檢索工具。它始創于1884年&#xff0c;擁有超過一個世紀的歷史&#xff0c;是全球工程界最權威的文獻檢索系統之一。EI雖然名為“…
閱讀更多...
十五、小型電腦沒有數字鍵及insert，怎么解決IDEA快速插入getset構造這些方法

十五、小型電腦沒有數字鍵及insert，怎么解決IDEA快速插入getset構造這些方法

&#x1f33b;&#x1f33b;目錄 一、小型電腦沒有數字鍵及insert&#xff0c;怎么解決IDEA快速插入getset構造這些方法 一、小型電腦沒有數字鍵及insert&#xff0c;怎么解決IDEA快速插入getset構造這些方法 解決&#xff1a; 1.winR打開搜索 2.osk回車 屏幕就出現了這樣的一…
閱讀更多...
CC7利用鏈分析

CC7利用鏈分析

分析版本 Commons Collections 3.2.1 JDK 8u65 環境配置參考JAVA安全初探(三):CC1鏈全分析 分析過程 CC7,6,5都是在CC1 LazyMap利用鏈(引用)的基礎上。 只是進入到LazyMap鏈的入口鏈不同。 CC7這個鏈有點繞&#xff0c;下面順著分析一下利用鏈。 入口類是Hashtable&…
閱讀更多...
前端入門知識分享：如何在HTML或CSS文件中引用CSS文件。

前端入門知識分享：如何在HTML或CSS文件中引用CSS文件。

閱讀提示&#xff1a;本文僅僅僅適用于剛剛接觸HTML和CSS的小白從業者&#xff0c;新人愛好者。自覺身份不符的老鳥們&#xff0c;盡快繞行吧&#xff01; 什么是CSS&#xff1f;什么是CSS文件。 CSS&#xff0c;全稱為Cascading Style Sheets&#xff08;層疊樣式表&#xff…
閱讀更多...
最新文章

Copyright @ 2022~2023