欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++初階之list的模擬實(shí)現(xiàn)過(guò)程詳解

 更新時(shí)間:2021年08月06日 10:01:19   作者:qx LIU 2000  
在C++中我們經(jīng)常使用STL,那個(gè)在那些我們常用的數(shù)據(jù)結(jié)構(gòu)vector,list的背后,又是如何實(shí)現(xiàn)的呢?這篇文章主要給大家介紹了關(guān)于C++初階之list的模擬實(shí)現(xiàn)的相關(guān)資料,需要的朋友可以參考下

list的介紹

list的優(yōu)點(diǎn):

  • list頭部、中間插入不再需要挪動(dòng)數(shù)據(jù),O(1)效率高
  • list插入數(shù)據(jù)是新增節(jié)點(diǎn),不需要增容

list的缺點(diǎn):

  • 不支持隨機(jī)訪(fǎng)問(wèn),訪(fǎng)問(wèn)某個(gè)元素效率O(N)
  • 底層節(jié)點(diǎn)動(dòng)態(tài)開(kāi)辟,小節(jié)點(diǎn)容易造成內(nèi)存碎片,空間利用率低,緩存利用率低。

今天來(lái)模擬實(shí)現(xiàn)list

我們先來(lái)看看官方文檔中對(duì)于list的描述

我們先大致了解一下list的遍歷

迭代器

對(duì)于迭代器我們可以用while循環(huán)+begin()end()。同時(shí)還可以用迭代器區(qū)間。

當(dāng)然迭代器區(qū)間的方式只適用于內(nèi)存連續(xù)的結(jié)構(gòu)比如數(shù)組stringvector等

它們的原生指針就可以當(dāng)作迭代器來(lái)用。

范圍for

其實(shí)范圍for和迭代器的底層是完全一樣的,我們只有寫(xiě)好迭代器,才能用范圍for,而且這里的迭代器必須和庫(kù)里的命名一樣才可以用范圍for

我們?cè)賮?lái)了解一下有關(guān)算法函數(shù)中,我們最常用的函數(shù)

  • swap
  • find
  • sort

我們主要看看sort函數(shù)

sort函數(shù)在官方庫(kù)中是用快排寫(xiě)的,其中快排的精髓就是三數(shù)取中的優(yōu)化操作。

sort默認(rèn)是排升序 如果想排降序需要使用functional文件中的greater()這個(gè)模板函數(shù),我們以vector來(lái)舉例。

對(duì)于list,我們極度不推薦使用algorithm文件中的sort函數(shù),上文提到了sort函數(shù)是使用的快速排序的手段進(jìn)行排序的,而其關(guān)鍵在于三數(shù)取中這樣的操作,那么三數(shù)取中這樣的操作只有在內(nèi)存連續(xù)的數(shù)據(jù)結(jié)構(gòu)中才能操作,如果給你一個(gè)head,給你一個(gè)tail,你如果能找到中間的結(jié)點(diǎn)?很明顯是很復(fù)雜的。

我們這里list迭代器是不支持隨機(jī)訪(fǎng)問(wèn),他不是隨即迭代器。

而vector string這樣的迭代器是支持隨機(jī)訪(fǎng)問(wèn)的,所以他們用快排很有優(yōu)勢(shì)。

我們可以看到這三個(gè)函數(shù)的迭代器是不同的,它們是繼承關(guān)系,隨機(jī)的支持雙向,雙向支持單向,反過(guò)來(lái)就不行。

當(dāng)然除了這幾種迭代器,還有輸入輸出迭代器,也叫可讀可寫(xiě)迭代器,他們是最弱的迭代器,一個(gè)單向迭代器都可以支持可讀可寫(xiě)的功能。也就是說(shuō),可讀可寫(xiě)迭代器在繼承的最上端。所有人都包含了他倆。

但是雖然他們功能很弱,但他們?cè)谝恍┲匾奶匦陨嫌兄陵P(guān)重要的作用,那就是迭代器的萃取。這個(gè)和復(fù)雜,暫時(shí)不去管它們。

總結(jié)上面兩段話(huà):


當(dāng)我們使用迭代器遍歷的時(shí)候,我們需要知道的是,begin()代表了第一個(gè)結(jié)點(diǎn),end()代表了頭結(jié)點(diǎn)。

這里再穿插一個(gè)小知識(shí),我們?cè)俟俜轿臋n中總能看到max_size這樣的變量,
它的意義是整形的最大值除以一個(gè)節(jié)點(diǎn)的大小,也就是得出的節(jié)點(diǎn)個(gè)數(shù)
無(wú)符號(hào)整形最大是2^32-1,也就是42億多,對(duì)于int類(lèi)型的vector,就是42億除以4得到的值,對(duì)于list,就是42億除以三個(gè)指針的大小得到的值。

我們還知道再vector中,我們?cè)趇nsert的擴(kuò)容插入,還有erase的刪除時(shí),會(huì)導(dǎo)致迭代器失效的問(wèn)題。那么對(duì)于list我們還要去關(guān)注迭代器失效的問(wèn)題嗎?

我們?cè)賗nsert的時(shí)候,插入數(shù)據(jù)并不會(huì)影響到其他的數(shù)據(jù)的地址,只是影響鏈接的關(guān)系,所以不會(huì)引起迭代器失效

但是對(duì)于erase,當(dāng)我們刪除對(duì)應(yīng)的結(jié)點(diǎn)之后,他會(huì)變成野指針。所以我們erase的時(shí)候通常去接收它的返回值,也就是下一個(gè)結(jié)點(diǎn)的迭代器。

當(dāng)然庫(kù)中還有一些我們不常用的函數(shù)

splice 接合函數(shù),把一個(gè)list的數(shù)據(jù)轉(zhuǎn)移到另一個(gè)list

這里不是拷貝,是轉(zhuǎn)移。

還有remove,找到就刪,沒(méi)找到就沒(méi)什么反應(yīng)。

unique 去重,這里又一個(gè)小小的bug,只有連續(xù)的重復(fù)數(shù)據(jù)才會(huì)刪除。

聰明的同學(xué)會(huì)反應(yīng)過(guò)來(lái),這里sort+unique可以解決這樣的問(wèn)題。當(dāng)然沒(méi)反應(yīng)過(guò)來(lái)的同學(xué)也很聰明。

這里顯然還是那個(gè)問(wèn)題,我們不建議堆鏈表進(jìn)行排序,效率是很低的。

list的成員函數(shù)是用的歸并排序。為什么不用algorithm中的sort快排呢?原因我們上文已經(jīng)解釋過(guò)了。

說(shuō)了這么多,來(lái)看看代碼吧。

先來(lái)看看頭文件吧!

#pragma once

#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;

namespace LL
{
	我們先寫(xiě)結(jié)點(diǎn)類(lèi),這里用類(lèi)模板,并且是用struct實(shí)現(xiàn),默認(rèn)內(nèi)容是公開(kāi)的,其他的類(lèi)都可以調(diào)用 
	template<class T>
	其中結(jié)點(diǎn)類(lèi)中要有三個(gè)變量,一個(gè)存值,兩個(gè)指針
	struct _list_node
	{
		T _val;
		_list_node<T>*  _next;
		_list_node<T>*  _prev;

		結(jié)點(diǎn)類(lèi)中除了要有三個(gè)變量,還需要有一個(gè)構(gòu)造函數(shù)。當(dāng)我們定義一個(gè)新結(jié)點(diǎn)的時(shí)候,進(jìn)行構(gòu)造函數(shù)初始化
		我們這里的參數(shù)是一個(gè)缺省的val值 ,其中缺省參數(shù)給的是匿名構(gòu)造函數(shù)。最好以const接收。
		_list_node(const T& val = T())
			:_val(val)
			, _next(nullptr)
			, _prev(nullptr)
		{}
	};

	這里實(shí)現(xiàn)迭代器類(lèi)。首先我們依舊是使用類(lèi)模板 ,我們這里給三個(gè)模板參數(shù),同時(shí)類(lèi)還是用struct來(lái)實(shí)現(xiàn)
	在迭代器類(lèi)中,我們主要實(shí)現(xiàn) 1、構(gòu)造 2、解引用操作  3、!= 和== 操作  3、前置++后置++ --操作
	template<class T, class Ref, class Ptr> 這里三個(gè)模板參數(shù)是什么意思呢?當(dāng)我們需要const迭代器和非const迭代器的時(shí)候我們可以根據(jù)第二個(gè)參數(shù)的不同來(lái)實(shí)例化出不同的迭代器,就不需要寫(xiě)兩個(gè)迭代器了
	typedef _list_iterator<T,T&,T*> iterator;
	typedef _list_iterator<T,cosnt T&,const T*> const_iterator; 我們可以根據(jù)模板參數(shù)實(shí)例化出不同的迭代器。
	struct _list_iterator
	{
		typedef _list_node<T>  node;
		typedef _list_iterator<T, Ref, Ptr>  self;

		node* _pnode;

		構(gòu)造函數(shù),把node傳進(jìn)來(lái),然后把值賦給我們內(nèi)部創(chuàng)建的_pnode,總不能亂修改外部指針吧。
		_list_iterator(node * node)
			:_pnode(node)
		{}

		這里我們不需要實(shí)現(xiàn)拷貝構(gòu)造、operator=、析構(gòu),直接用編譯器生成的,對(duì)于內(nèi)置類(lèi)型直接進(jìn)行淺拷貝
		我們發(fā)現(xiàn)淺拷貝指針對(duì)于list來(lái)說(shuō)完全沒(méi)問(wèn)題。

		解引用,解引用我們返回值寫(xiě)為Ref ,這樣可以根據(jù)const和非const,并且就是引用返回可讀可修改,如果ref為const,那就不可修改只可讀。
		這里不需要傳入?yún)?shù),我們直接進(jìn)行調(diào)用,返回值當(dāng)然為對(duì)應(yīng)的val引用.
		Ref operator * ()
		{
			return _pnode->_val;
		}
		同理的我們寫(xiě)一下這個(gè)指針解引用,這里返回值依舊用模板參數(shù),很方便啊。我們應(yīng)該返回一個(gè)地址。
		Ptr operator ->()
		{
			return &(_pnode->_val);
		}

		!= 和 == ,當(dāng)我們使用迭代器的時(shí)候,需要比較兩個(gè)迭代器是否相等來(lái)進(jìn)行循環(huán)條件判定,所以這是必要的。
		我們這里返回值當(dāng)然是bool,參數(shù)傳入我們的迭代器,比較迭代器內(nèi)的節(jié)點(diǎn)是否相等。再加上const最好。
		bool operator != (const self& s) const
		{
			return _pnode != s._pnode;
		}
		bool operator == (const self& s) const
		{
			return _pnode == s._pnode;
		}
		接著我們實(shí)現(xiàn)前置后置++--
		前置 ++ it  我們返回值是 原迭代器
		self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		后置 ++ it ,我們需要進(jìn)行傳參,第一個(gè)參數(shù)就是默認(rèn)的this,第二個(gè)參數(shù)為0
		it ++ --> it.operator ++(&it,0);我們可以缺省掉第二個(gè)參數(shù),因?yàn)槟J(rèn)是從參數(shù)列表末尾開(kāi)始匹配的。
		當(dāng)然返回值就不能返回引用了,因?yàn)檫@里我們要用臨時(shí)變量進(jìn)行返回,我們先用傳入的it拷貝構(gòu)造一個(gè)臨時(shí)迭代器。然后在進(jìn)行++操作。
		因?yàn)楹笾眉蛹邮窍荣x值再++所以我們先用臨時(shí)變量保存一下之前的迭代器,再給之前的迭代器++,最后再返回未修改的臨時(shí)迭代器。
		self operator++(int)
		{
			self tmp(*this);
			_pnode = _pnode->_next;
			return tmp;
		}

		self& operator--()
		{
			_pnode = _pnode->_prev;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_pnode = _pnode->_prev;
			return tmp;
		}


	};




	接下來(lái)我們開(kāi)始寫(xiě)list類(lèi),當(dāng)然也要用類(lèi)模板來(lái)寫(xiě),里面要實(shí)現(xiàn)1、迭代器 2、構(gòu)造 3、push_back 。我們這里的list是帶頭雙向循環(huán)列表
	template <class T>
	class list
	{
		我們先來(lái)實(shí)現(xiàn)一下迭代器,我們首先需要typedef 我們的迭代器 ,所以先實(shí)現(xiàn)迭代器。然后需要定義const和非const的beginend ,
		這里需要記住end和begin要有非const和cosnt,因?yàn)闊o(wú)法同時(shí)滿(mǎn)足可修改和可讀。比如const迭代器調(diào)用只能掉const的end,非const的迭代器雖然可以調(diào)用const的end,但是導(dǎo)致權(quán)限縮小,無(wú)法修改內(nèi)容。
		typedef _list_node<T> node;
	public:
		typedef _list_iterator<T, T&, T*> iterator;
		typedef _list_iterator<T, const T&, const T*> const_iterator;

		iterator begin()                   //begin指頭結(jié)點(diǎn)后第一個(gè)結(jié)點(diǎn),end指頭結(jié)點(diǎn)。
		{
			return iterator(_head->_next); //這里調(diào)用的是匿名構(gòu)造然后直接返回。
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

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


		構(gòu)造函數(shù),這里直接進(jìn)行頭結(jié)點(diǎn)的創(chuàng)建(自己鏈自己)
		list()
		{
			_head = new node(T());    當(dāng)然可以有這種寫(xiě)法,我們用匿名構(gòu)造一個(gè)頭結(jié)點(diǎn),可以是各種類(lèi)型。這里和上文中,結(jié)點(diǎn)的構(gòu)造函數(shù)是一樣的,我們寫(xiě)一個(gè)就好了。
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		push_back 我們傳入一個(gè)要插入的值,創(chuàng)建新節(jié)點(diǎn)進(jìn)行鏈接的更新。
		void push_back(const T& val)
		{
			node* newnode = new node(val);   //這里因?yàn)槲覀冊(cè)诮Y(jié)點(diǎn)的構(gòu)造函數(shù)中寫(xiě)了模板參數(shù)類(lèi)型匿名構(gòu)造,可以傳任意類(lèi)型。
			node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;

		}

		拷貝構(gòu)造  1、創(chuàng)造新的頭結(jié)點(diǎn),把傳入的list循環(huán)賦值給新的頭結(jié)點(diǎn)。
		list(const list<T>& l)
		{
			_head = new node;
			_head->_next = _head;
			_head->_prev = _head;
			const_iterator it = l.begin();
			while (it != l.end())
			{
				push_back(*it);
				++it;
			}
		}

		insert,在指定位置插入元素,我們不用返回值,參數(shù)是pos迭代器和val
		先給一個(gè)cur 存pos位置的結(jié)點(diǎn),然后定義一個(gè)我們的prev,為了之后和新節(jié)點(diǎn)鏈接。2、創(chuàng)建新節(jié)點(diǎn),更新鏈接就好了。
		void insert(iterator pos, const T& val)   //這里不需要用const 因?yàn)?,const迭代器對(duì)應(yīng)了constlist ,const list怎么會(huì)來(lái)插入數(shù)據(jù)呢?
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* newnode = new node(val);

			newnode->_next = cur;
			newnode->_prev = prev;
			prev->_next = newnode;
			cur->_prev = newnode;
		}

		erase ,返回下一個(gè)位置的迭代器,傳入一個(gè)pos
		1、保存指向結(jié)點(diǎn),并找到前后的兩節(jié)點(diǎn) 2、更新鏈接 刪除掉當(dāng)前節(jié)點(diǎn)。3、返回迭代器。這里需要強(qiáng)轉(zhuǎn),從指針轉(zhuǎn)成迭代器類(lèi)型。
		iterator erase(iterator pos)
		{
			node* cur = pos._pnode;
			node* prev = cur->_prev;
			node* next = cur->_next;
			
			prev->_next = next;
			next->_prev = prev;
			delete cur;
			return (iterator)next;
		}


		那我們?cè)谫x值運(yùn)算符重載的時(shí)候需要先清理掉自身的結(jié)點(diǎn),所以我們實(shí)現(xiàn)一下clear
		clear 清空l(shuí)ist中除了頭結(jié)點(diǎn)以外的所有結(jié)點(diǎn)。很好實(shí)現(xiàn),我們循環(huán)erase就好了,erase返回下一個(gè)的迭代器,所以接收其返回值就好了。
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		賦值運(yùn)算符重載,返回值是類(lèi)型的引用 ,參數(shù)傳入list
		1、首先判斷是否給自己賦值,否則我們刪除后會(huì)發(fā)生野指針的問(wèn)題 2、條件成立我們先清除現(xiàn)在的一切,然后循環(huán)賦值。最后返回*this;
		list<T>& operator = (list<T>& l)
		{
			if (this != &l)
			{
				clear ();
				iterator it = l.begin();
				while (it != l.end())
				{
					push_back(*it);
					it++;
				}
				
			}
			return *this;
		}

		析構(gòu):析構(gòu)要做的就是析構(gòu)一切,先clear,在delete 頭,并給頭賦空
		~list()
		{
			clear();
			delete _head;
			_head = nullptr;
			cout << "析構(gòu)執(zhí)行成功" << endl;
		}

		獲得第一個(gè)元素,返回一定是類(lèi)型的引用,這里應(yīng)該有兩個(gè)版本,否則當(dāng)const對(duì)象調(diào)用的時(shí)候,會(huì)無(wú)法調(diào)用。這里返回也要返回const,否則你給人家偷偷擴(kuò)大了權(quán)限。
		T& front()
		{
			return _head->_next->_val;
		}

		const T& front() const
		{
			return _head->_next->_val;
		}
		獲得最后一個(gè)元素
		
		T& back()
		{
			return _head->_prev->_val;

		}
		const T& back() const
		{
			return _head->_prev->_val;

		}

		交換兩個(gè)list,傳入list。我們只需要交換一下頭結(jié)點(diǎn)就可以了
		void swap(list<T>& l)
		{
			::swap(_head, l._head);
		}

		void push_back_insert(const T& val)
		{
			insert(end(), val);
		}

		void push_front_insert(const T& val)
		{
			insert(begin(), val);
		}

		void pop_front_erase()
		{
			erase(begin());
		}
		void pop_back_erase()
		{
			erase(--end());
		}

		求結(jié)點(diǎn)個(gè)數(shù)循環(huán)計(jì)數(shù)
		size_t size()
		{
			size_t count = 0;
			auto it = begin();
			while (it != end())
			{
				++it;
				++count;

			}
			return count;
		}

		bool empty()
		{
			return begin() == end();		
		}

		resize ,開(kāi)辟n個(gè)空間并賦初始值,用匿名構(gòu)造賦值。
		1、計(jì)算舊結(jié)點(diǎn)個(gè)數(shù),如果就空間比新的空間大,我們就刪除多余的空間2、否則就從新空間開(kāi)始給其賦初值。
		void resize(size_t newsize, T& val = T())
		{
			size_t oldsize = size();
			if (oldsize > newsize)
			{
				for (int i = newsize; i < oldsize; i++)
				{
					pop_back_erase();
				}
			}
			else
			{
				for (int i = oldsize; i < newsize; i++)
				{
					push_back_insert(val);
				}
			}
		}




	private:
		node* _head;
	};

}

我們來(lái)測(cè)試一下我們的函數(shù)

#include "List.h"

//printlist 打印不需要返回什么,參數(shù)是一個(gè)模板參數(shù)類(lèi)型的列表
template<class Con>
void PrintContainer(const Con& c)
{
	Con::const_iterator it = c.begin();
	while (it != c.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;

}

void test_list1()
{
	cout << "list1使用pushback插入數(shù)據(jù)的打印" << endl;
	LL::list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);
	lt1.push_back(4);
	lt1.push_back(5);
	lt1.push_back(6);
	PrintContainer(lt1);
	//for (auto e : lt)
	//{
	//	cout << e << " ";

	//}
	//cout << endl;

	//LL::list<int>::iterator it = lt.begin();
	//while (it != lt.end())
	//{
	//	(*it)++;
	//	cout << *it << " ";
	//	++it;
	//}
	//cout << endl;


	cout << "拷貝構(gòu)造list2的打印" << endl;
	LL::list<int> lt2(lt1);
	PrintContainer(lt2);
	
	//cout << "在list2的2位置前insert一個(gè)0并打印" << endl;
	//LL::list<int>::iterator pos = find(lt2.begin(), lt2.end(),2);		
	//lt2.insert(pos,0);
	//PrintContainer(lt2);

	//cout << "在list2的2位置前insert一個(gè)0并打印" << endl;
	//lt2.erase(pos);
	//PrintContainer(lt2);

	cout << "用list2給list3賦值,并打印" << endl;
	LL::list<int> lt3;
	lt3 = lt2;
	PrintContainer(lt3);

	cout << "獲得list3的第一個(gè)元素和最后一個(gè)元素" << endl;
	cout << lt3.front() <<"  ";
	cout << lt3.back() << endl;

	cout << "整一個(gè)全是0的list4,并打印" << endl;
	LL::list<int> lt4;
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	lt4.push_back(0);
	PrintContainer(lt4);

	cout << "交換鏈表list1和list4、并打印" << endl;
	lt1.swap(lt4);
	PrintContainer(lt4);


	cout << "頭刪list4" << endl;
	lt4.pop_front_erase();
	PrintContainer(lt4);
	cout << "頭插list4" << endl;
	lt4.push_front_insert(0);
	PrintContainer(lt4);
	cout << "尾刪list4" << endl;
	lt4.pop_back_erase();
	PrintContainer(lt4);
	cout << "尾插list4" << endl;
	lt4.push_back_insert(0);
	PrintContainer(lt4);


	cout << "list4的節(jié)點(diǎn)個(gè)數(shù)" << endl;
	cout << lt4.size() << endl;

	cout << "判斷是list1是否為空鏈表" << endl;
	cout << lt1.empty() << endl;




	cout << "    " << endl;
	cout << "    " << endl;
	cout << "    " << endl;
	cout << "    " << endl;

	cout << "    " << endl;
	cout << "    " << endl;
}


int main()
{

	test_list1();
	return 0;
}

總結(jié)

到此這篇關(guān)于C++初階之list的模擬實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++ list模擬實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

最新評(píng)論