list 的實現

目錄

list

結點類

結點類的構造函數

list的尾插尾刪

list的頭插頭刪

迭代器

++運算符重載

--運算符重載

==和!= 運算符重載

* 和 -> 運算符重載

?list 的insert

list的erase

list

list實際上是一個帶頭雙向循環鏈表,要實現list,則首先需要實現一個結點類,而一個結點需要存儲的信息為:數據、前驅指針、后繼指針

而對于該結點類的成員函數來說,我們只需實現一個構造函數即可,因為該結點類只需要根據數據來構造一個結點即可,而結點的釋放則由list的析構函數來完成,

結點類

結點類的基本結構：

	template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _date;ListNode(const T& pos = T()){_next = nullptr;_prev = nullptr;_date = pos;}};

這里用struct 的原因是因為ListNode 的?每個成員變量都會被頻繁調用。

用struct則不需要封裝了。

結點類的構造函數

構造函數直接根據所給數據構造一個結點即可,構造出來的結點的數據域存儲的就是所給數據,而前驅指針和后繼指針均初始化為空指針即可

		ListNode(const T& pos = T()){_next = nullptr;_prev = nullptr;_date = pos;}

list的尾插尾刪

	template<class T>class list{public:typedef ListNode<T> node;	list():_head(new node){_head->_next = _head;_head->_prev = _head;}void push_back(const T& x){node* head = _head;node* tail = _head->_prev;node* p = new node(x);tail->_next = p;p->_prev = tail;p->_next = head;head->_prev = p;}void pop_back(){assert(_head != _head->_next);node* head = _head;node* tail = head->_prev;node* newtail = tail->_prev;newtail->_next = head;head->_prev = newtail;delete[] tail;}private:node* _head;};

list的頭插頭刪

	template<class T>class list{public:	typedef ListNode<T> node;list():_head(new node){_head->_next = _head;_head->_prev = _head;}void push_front(const T& x){node* newnode = new node(x);node* head = _head;node* tail = _head->_next;head->_next = newnode;newnode->_prev = head;newnode->_next = tail;tail->_prev = newnode;}void pop_front(){assert(_head != _head->_next);node* head = _head;node* tail = _head->_next;head->_next = tail->_next;tail->_next->_prev = head;delete[]tail;}private:node* _head;};

迭代器

迭代器有兩種實現方式,具體應根據容器底層數據結構實現：

  1. 原生態指針,比如：vector和string ->物理空間是連續的，因為string和vector對象都將其數據存儲在了一塊連續的內存空間,我們通過指針進行自增、自減以及解引用等操作,就可以對相應位置的數據進行一系列操作,因此string和vector當中的迭代器就是原生指針。
  2. .將原生態指針進行封裝,因迭代器使用形式與指針完全相同,因此在自定義的類中必須實現以下方法：

指針可以解引用,迭代器的類中必須重載operator*()
指針可以通過->訪問其所指空間成員,迭代器類中必須重載oprator->()
指針可以++向后移動,迭代器類中必須重載operator++()與operator++(int)
至于operator--()/operator--(int) 是否需要重載,根據具體的結構來抉擇,雙向鏈表可
以向前 移動,所以需要重載,如果是forward_list就不需要重載–
迭代器需要進行是否相等的比較,因此還需要重載operator==()與operator!=()
但是對于list來說,其各個結點在內存當中的位置是隨機的,并不是連續的,我們不能僅通過結點指針的自增、自減以及解引用等操作對相應結點的數據進行操作,

總結：list的迭代器 實際上就是對結點指針進行了封裝,對其各種運算符進行了重載,使得結點指針的各種行為看起來和普通指針一樣,（例如,對結點指針自增就能指向下一個結點 p = p->next）

	template<class T1, class T2>struct Reverse_iterator{typedef Reverse_iterator<T1, T2> self;typedef ListNode<T1> node;node* _it;Reverse_iterator(node* pos)；self& operator++()；self operator++(int)；self& operator--()；self operator--(int)；T2& operator*()；T2* operator->()；bool operator!=(const self& pos)；bool operator==(const self& pos)；}；

迭代器模板參數說明：

構造函數
迭代器類實際上就是對結點指針進行了封裝

其成員變量就是結點指針,所以其構造函數直接根據所給結點指針構造一個迭代器對象即可,

		Reverse_iterator(node* pos){_it = pos;}

拷貝構造,operator,析構函數我們都不需要寫,因為成員變量是內置類型(指針), 用編譯器默認生成的就可以。

++運算符重載

		self& operator++()//前置{_it =_it->_prev;return *this;}self operator++(int)//后置{self tmp(_it);_it = _it->_prev;return tmp;}

前置++原本的作用是將數據自增,然后返回自增后的數據,

而對于結點迭代器的前置++:應該先讓結點指針指向后一個結點.然后再返回“自增”后的結點迭代器即可

后置++,先拷貝構造當前迭代器結點, 然后讓當前迭代器結點的指針自增指向下一個結點,最后返回“自增”前的結點迭代器即可,

--運算符重載

		self& operator--()//前置{_it = _it->_next;return *this;}self operator--(int)//后置{self tmp(_it);_it = _it->_next;return tmp;}

前置- -：當前迭代器結點中的指針指向前一個結點,然后再返回“自減”后的結點迭代器即可,

后置--：拷貝構造當前迭代器對象 -> 當前迭代器結點中的指針自減指向前一個結點 ->返回自減前的迭代器。

==和!= 運算符重載

		bool operator!=(const self& pos){return _it != pos._it;}bool operator==(const self& pos){return _it == pos._it;}

這里注意形參別寫錯就好了。

* 和 -> 運算符重載

使用解引用操作符時,是想得到該指針指向的數據內容

因此,我們直接返回當前結點指針所指結點的數據即可,這里需要使用引用返回,因為解引用后可能需要對數據進行修改,

		T2& operator*(){return _it->_date;}

->返回當前迭代器結點的指針所指結點的數據的地址

		T2* operator->(){return &_it->_date;}

使用場景：

?list 的insert

insert函數可以在所給迭代器pos之前插入一個新結點,

1.先根據所給迭代器pos得到該位置處的結點指針

2.然后通過該指針找到前一個位置的結點指針last

根據所給數據x構造一個新結點

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

list的erase

erase函數可以刪除所給迭代器位置的結點,

注意**:pos不可以是哨兵位的迭代器,即不能刪除哨兵位 pos迭代器結點中的指針不能為空**

1.根據所給迭代器得到該位置處的結點指針self

2.通過self指針找到前一個位置的結點指針last,以及后一個位置的結點指針next

3.緊接著釋放cur結點,最后prev和next結點進行鏈接

		iterator erase(iterator pos){assert(pos._node);assert(_head != _head->_next);node* self = pos._node;node* next = self->_next;node* last = self->_prev;last->_next = next;next->_prev = last;delete[] self;return iterator(next);}

關于insert 和 erase 迭代器失效的問題：

insert不會導致迭代器失效,因為pos迭代器中的節點指針仍然指向原來的節點。

問:erase之后, pos迭代器是否失效：
一定失效,因為此時pos迭代器中的節點指針指向的節點已經被釋放了,該指針相當于是野指針。

?最后所有代碼如下：
?

namespace bit
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _date;ListNode(const T& pos = T()){_next = nullptr;_prev = nullptr;_date = pos;}};template<class T1,class T2 = T1>struct ListIterator{typedef ListIterator<T1,T2> iterator;typedef ListNode<T1> node;node* _node;ListIterator(node* pos){_node = pos;}T2& operator*(){return _node->_date;}iterator& operator++(){_node = _node->_next;return *this;}		iterator operator++(int){iterator tmp(_node);_node = _node->_next;return tmp;}iterator& operator--(){_node = _node->_prev;return *this;}iterator operator--(int){iterator tmp(_node);_node = _node->_prev;return tmp;}T2* operator->(){return &_node->_date;}bool operator!=(const iterator& pos){return _node != pos._node;}bool operator==(const iterator& pos){return _node == pos._node;}};template<class T1, class T2>struct Reverse_iterator{typedef Reverse_iterator<T1, T2> self;typedef ListNode<T1> node;node* _it;Reverse_iterator(node* pos){_it = pos;}self& operator++(){_it =_it->_prev;return *this;}self operator++(int){self tmp(_it);_it = _it->_prev;return tmp;}self& operator--(){_it = _it->_next;return *this;}self operator--(int){self tmp(_it);_it = _it->_next;return tmp;}T2& operator*(){return _it->_date;}T2* operator->(){return &_it->_date;}bool operator!=(const self& pos){return _it != pos._it;}bool operator==(const self& pos){return _it == pos._it;}};template<class T>class list{public:typedef Reverse_iterator<T, T> reverse_iterator;typedef Reverse_iterator<T, const T> const_reverse_iterator;typedef ListNode<T> node;typedef ListIterator<T> iterator;typedef ListIterator<T,const T> const_iterator;list():_head(new node){_head->_next = _head;_head->_prev = _head;}list(const list& pos){_head = new node;_head->_next = _head;_head->_prev = _head;for (auto e : pos){push_back(e);}}list(initializer_list<T> il){_head = new node;_head->_next = _head;_head->_prev = _head;for (auto e : il){push_back(e);}}void push_back(const T& x){node* head = _head;node* tail = _head->_prev;node* p = new node(x);tail->_next = p;p->_prev = tail;p->_next = head;head->_prev = p;}void pop_back(){assert(_head != _head->_next);node* head = _head;node* tail = head->_prev;node* newtail = tail->_prev;newtail->_next = head;head->_prev = newtail;delete[] tail;}reverse_iterator rbegin(){return reverse_iterator(_head->_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator crbegin()const{return const_reverse_iterator(_head->_prev);}const_reverse_iterator crend()const{return const_reverse_iterator(_head);}iterator begin(){return iterator(_head->_next);}const_iterator begin()const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}void push_front(const T& x){node* newnode = new node(x);node* head = _head;node* tail = _head->_next;head->_next = newnode;newnode->_prev = head;newnode->_next = tail;tail->_prev = newnode;}void pop_front(){assert(_head != _head->_next);node* head = _head;node* tail = _head->_next;head->_next = tail->_next;tail->_next->_prev = head;delete[]tail;}iterator insert(iterator pos,const T& x){node* newnode = new node(x);node* next = pos._node;node* last = next->_prev;last->_next = newnode;newnode->_prev = last;newnode->_next = next;next->_prev = newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos._node);assert(_head != _head->_next);node* self = pos._node;node* next = self->_next;node* last = self->_prev;last->_next = next;next->_prev = last;delete[] self;return iterator(next);}~list(){iterator it1 = begin();while (it1 != end()){it1 = erase(it1);}delete _head;_head = nullptr;}private:node* _head;};

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

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

相關文章

【代碼隨想錄——回溯算法——四周目】

【代碼隨想錄——回溯算法——四周目】

1.重新安排行程 1.1 我的代碼&#xff0c;超時通不過 var (used []boolpath []stringres []stringisFind bool )func findItinerary(tickets [][]string) []string {sortTickets(tickets)res make([]string, len(tickets)1)path make([]string, 0)used make([]bool,…
閱讀更多...
JSON Web Token

JSON Web Token

JWT 什么是JWT JWT&#xff08;JSON Web Token&#xff09;是一種用于在各方之間作為JSON對象安全地傳輸信息的開放標準&#xff08;RFC 7519&#xff09;。該信息經過數字簽名&#xff0c;因此是可驗證和可信的。JWT 可以使用HMAC算法或使用RSA的公鑰/私鑰對進行簽名 JWT的…
閱讀更多...
微信小程序 vant Picker組件default-index不生效的解決辦法

微信小程序 vant Picker組件default-index不生效的解決辦法

1、原始的寫法以及問題 <van-popup show"{{ showPopup && cellClick Freq }}" position"bottom" bind:close"onPopupClose"><van-picker value-key"Spec" show-toolbar title"{{cellClick Freq ? showPcCha…
閱讀更多...
win10鍵盤按亂了，如何恢復？

win10鍵盤按亂了，如何恢復？

今天鍵盤被寶寶給按亂了&#xff0c;好不容易給重新調整回來&#xff0c;記錄備忘&#xff1a; 1、win10的asdf和方向鍵互換了&#xff1a; 使用Fnw鍵來回切換&#xff0c;OK&#xff01; 2、鍵盤的win鍵失效&#xff0c;例如&#xff1a;按winD無法顯示桌面。此時&#xf…
閱讀更多...
Day30

Day30

Day30 CSS CSS常用樣式 font-family:“微軟雅黑” -設置字體 font-size: 50px -設置字體大小 font-style : italic-設置字體風格 font-weight:bolder -設置字體粗細 color: white-設置字體顏色 letter-spacing: 20px-設置文本內容的間隔 text-decoration :underline - 設置劃…
閱讀更多...
電動汽車電子系統架構

電動汽車電子系統架構

電動汽車的普及正在穩步發展&#xff0c;供應鏈的各個環節也在發生變化。它涵蓋了制造電動汽車零件的原材料、化學品、電池和各種組件。與此同時&#xff0c;汽車充電基礎設施也參與其中&#xff0c;它們正經歷一個歷史性的階段&#xff0c;經過徹底的重新設計。它們的電氣化以…
閱讀更多...
Wpf 使用 Prism 實戰開發Day30

Wpf 使用 Prism 實戰開發Day30

登錄界面設計 一.準備登錄界面圖片素材&#xff08;透明背景圖片&#xff09; 1.把準備好的圖片放在Images 文件夾下面&#xff0c;格式分別是.png和.ico 2.選中 login.png圖片鼠標右鍵&#xff0c;選擇屬性。生成的操作選擇>資源 3.MyTodo 應用程序右鍵&#xff0c;屬性&a…
閱讀更多...
如何修改開源項目中發現的bug？

如何修改開源項目中發現的bug？

如何修改開源項目中發現的bug&#xff1f; 目錄 如何修改開源項目中發現的bug&#xff1f;第一步&#xff1a;找到開源項目并建立分支第二步&#xff1a;克隆分支到本地倉庫第三步&#xff1a;在本地對項目進行修改第四步&#xff1a;依次使用命令行進行操作注意&#xff1a;Gi…
閱讀更多...
地質災害位移應急監測站

地質災害位移應急監測站

地質災害位移應急監測站是一種專門用于地質災害預警和應急響應的設施&#xff0c;它能夠實時監測和分析山體、建筑物、管道等的位移變化情況。以下是關于地質災害位移應急監測站的詳細介紹&#xff1a; 主要組成部分 傳感器&#xff1a;安裝于需要監測的位置&#xff0c;用于…
閱讀更多...
RK3588+FPGA+AI高性能邊緣計算盒子，應用于視頻分析、圖像視覺等

RK3588+FPGA+AI高性能邊緣計算盒子，應用于視頻分析、圖像視覺等

搭載RK3588&#xff08;四核 A76四核 A55&#xff09;&#xff0c;CPU主頻高達 2.4GHz &#xff0c;提供1MB L2 Cache 和 3MB L3 &#xff0c;Cache提供更強的 CPU運算能力&#xff0c;具備6T AI算力&#xff0c;可擴展至38T算力。 產品規格 系統主控CPURK3588&#xff0c;四核…
閱讀更多...
Nginx服務器替換SSL證書記得要重啟

Nginx服務器替換SSL證書記得要重啟

輸入訪問域名&#xff0c;發現https證書過期了&#xff0c;果斷申請好ssl證書&#xff0c;并在Nginx服務器上將原證書替換成新申請的證書。 打開瀏覽器輸入網址確認一看&#xff0c;還是原來的證書并沒有替換成功?感覺不合常理 以下開啟了證書為什么替換不成功的排查 1、清除…
閱讀更多...
GUI 02：布局管理器相關知識，AWT 的 3 種布局管理器應用，以及嵌套布局的使用

GUI 02：布局管理器相關知識，AWT 的 3 種布局管理器應用，以及嵌套布局的使用

一、前言 記錄時間 [2024-05-31] 前置文章 GUI 01&#xff1a;GUI 編程概述&#xff0c;AWT 相關知識&#xff0c;Frame 窗口&#xff0c;Panel 面板&#xff0c;及監聽事件的應用 本文講述了 GUI 編程種布局管理器的相關知識&#xff0c;以及 AWT 的 3 種布局管理器——流式布…
閱讀更多...
【FPGA】Verilog語言從零到精通

【FPGA】Verilog語言從零到精通

接觸fpga一段時間&#xff0c;也能寫點跑點吧……試試系統地康康呢~這個需要耐心但是回報巨大的工作。正原子&&小梅哥 15_語法篇&#xff1a;Verilog高級知識點_嗶哩嗶哩_bilibili 1Verilog基礎 Verilog程序框架&#xff1a;模塊的結構 類比&#xff1a;c語言的基礎…
閱讀更多...
P3881

P3881

最小值最大 二分&#xff1a;枚舉兩個牛之間的最小距離&#xff0c;左端點是1&#xff0c;右端點是籬笆總長度。 Check數組&#xff1a; 如果兩頭牛之間距離是Mid不合法&#xff0c;則返回0&#xff08;false&#xff09;&#xff1b; 如果兩頭牛之間距離是Mid合法&#xf…
閱讀更多...
去噪擴散概率模型在現代技術中的應用：圖像生成、音頻處理到藥物發現

去噪擴散概率模型在現代技術中的應用：圖像生成、音頻處理到藥物發現

去噪擴散概率模型&#xff08;DDPMs&#xff09;是一種先進的生成模型&#xff0c;它通過模擬數據的噪聲化和去噪過程&#xff0c;展現出多方面的優勢。DDPMs能夠生成高質量的數據樣本&#xff0c;這在圖像合成、音頻生成等領域尤為重要。它們在數據去噪方面表現出色&#xff0…
閱讀更多...
瑞吉外賣項目學習筆記（二）后臺系統的員工管理業務開發

瑞吉外賣項目學習筆記（二）后臺系統的員工管理業務開發

一、完善登錄功能 1.1 問題分析 1.2 代碼實現 package com.itheima.reggie.filter;//這是一個過濾器類 //登錄檢查過濾器import com.alibaba.fastjson.JSON; import com.itheima.reggie.common.R; import lombok.extern.slf4j.Slf4j; import org.slf4j.Logger; import org.slf…
閱讀更多...
華為OD機試-最大坐標值

華為OD機試-最大坐標值

題目描述與示例 題目描述 小明在玩一個游戲&#xff0c;游戲規則如下&#xff1a;在游戲開始前&#xff0c;小明站在坐標軸原點處&#xff08;坐標值為 0&#xff09;給定一組指令和一個幸運數&#xff0c;每個指令都是一個整數&#xff0c;小明按照指定的要求前進或者后退指…
閱讀更多...
解析Java中1000個常用類：FunctionalInterface類，你學會了嗎？

解析Java中1000個常用類：FunctionalInterface類，你學會了嗎？

Java 8 引入了一系列新的特性和改進，其中之一便是函數式編程。函數式接口（Functional Interface）是函數式編程的核心概念之一。本文將深入探討 FunctionalInterface 注解，介紹其用法、重要性，并通過示例展示如何在實際開發中應用函數式接口。 什么是函數式接口？ 函數式…
閱讀更多...
有向圖的拓撲排序

有向圖的拓撲排序

文章目錄 概念及模板例題 雜務 概念及模板 有向圖的拓撲排序是指將有向無環圖中的所有頂點排成一個線性序列&#xff0c;使得圖中任意一對頂點u和v&#xff0c;若邊(u, v)在圖中&#xff0c;則u在該序列中排在v的前面。 例如&#xff0c;假設有n個任務&#xff0c;這些任務需…
閱讀更多...
HarmonyOS鴻蒙學習筆記（28）@entry和@Component的生命周期

HarmonyOS鴻蒙學習筆記（28）@entry和@Component的生命周期

entry和Component的生命周期 entry和Component的關系Component生命周期Entry生命周期 生命周期流程圖生命周期展示示例代碼參考資料 HarmonyOS的生命周期可以分為Compnent的生命周期和Entry的生命周期&#xff0c;也就是自定義組件的生命周期和頁面的生命周期。 entry和Compone…
閱讀更多...
最新文章

Copyright @ 2022~2023