由淺到深-模擬實(shí)現(xiàn)list-創(chuàng)新互聯(lián)

前言

為企業(yè)提供成都網(wǎng)站設(shè)計(jì)、成都做網(wǎng)站、網(wǎng)站優(yōu)化、營(yíng)銷(xiāo)型網(wǎng)站、競(jìng)價(jià)托管、品牌運(yùn)營(yíng)等營(yíng)銷(xiāo)獲客服務(wù)。創(chuàng)新互聯(lián)建站擁有網(wǎng)絡(luò)營(yíng)銷(xiāo)運(yùn)營(yíng)團(tuán)隊(duì)，以豐富的互聯(lián)網(wǎng)營(yíng)銷(xiāo)經(jīng)驗(yàn)助力企業(yè)精準(zhǔn)獲客，真正落地解決中小企業(yè)營(yíng)銷(xiāo)獲客難題，做到“讓獲客更簡(jiǎn)單”。自創(chuàng)立至今，成功用技術(shù)實(shí)力解決了企業(yè)“網(wǎng)站建設(shè)、網(wǎng)絡(luò)品牌塑造、網(wǎng)絡(luò)營(yíng)銷(xiāo)”三大難題，同時(shí)降低了營(yíng)銷(xiāo)成本，提高了有效客戶(hù)轉(zhuǎn)化率，獲得了眾多企業(yè)客戶(hù)的高度認(rèn)可！

作者：小蝸牛向前沖

名言：我可以接受失敗，但我不能接受放棄

如果覺(jué)的博主的文章還不錯(cuò)的話，還請(qǐng)點(diǎn)贊，收藏，關(guān)注👀支持博主。如果發(fā)現(xiàn)有問(wèn)題的地方歡迎?大家在評(píng)論區(qū)指正。

目錄

一 、見(jiàn)見(jiàn)STL中的list

1、list的介紹

2、list的常見(jiàn)接口

二、list的模擬實(shí)現(xiàn)

1、list框架搭建

2、模擬實(shí)現(xiàn)list迭代器

3、list整體實(shí)現(xiàn)?

三、list和vector的對(duì)比

1、對(duì)比二者的優(yōu)缺點(diǎn)

2、list和vector的排序效率?

---

本期學(xué)習(xí)目標(biāo)：認(rèn)識(shí)STL中的list，模擬實(shí)現(xiàn)list,對(duì)list的迭代器深入理解，對(duì)比list和vector。

一 、見(jiàn)見(jiàn)STL中的list 1、list的介紹

下面我們了看看cpulcpul官網(wǎng)中的介紹：

文檔介紹：

1. list是可以在常數(shù)范圍內(nèi)在任意位置進(jìn)行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
2. list的底層是雙向鏈表結(jié)構(gòu)，雙向鏈表中每個(gè)元素存儲(chǔ)在互不相關(guān)的獨(dú)立節(jié)點(diǎn)中，在節(jié)點(diǎn)中通過(guò)指針指向 其前一個(gè)元素和后一個(gè)元素。
3. list與forward_list非常相似：最主要的不同在于forward_list是單鏈表，只能朝前迭代，已讓其更簡(jiǎn)單高效。
4. 與其他的序列式容器相比(array，vector，deque)，list通常在任意位置進(jìn)行插入、移除元素的執(zhí)行效率更好。
5. 與其他序列式容器相比，list和forward_list大的缺陷是不支持任意位置的隨機(jī)訪問(wèn)，比如：要訪問(wèn)list 的第6個(gè)元素，必須從已知的位置(比如頭部或者尾部)迭代到該位置，在這段位置上迭代需要線性的時(shí)間 開(kāi)銷(xiāo)；list還需要一些額外的空間，以保存每個(gè)節(jié)點(diǎn)的相關(guān)聯(lián)信息(對(duì)于存儲(chǔ)類(lèi)型較小元素的大list來(lái)說(shuō)這 可能是一個(gè)重要的因素)。

從上面的介紹中我們初步認(rèn)識(shí)到了list的是帶頭雙向鏈表，對(duì)于要掌握的數(shù)據(jù)結(jié)構(gòu)之一，下面我們一起來(lái)回憶一下他的增刪查改操作。?

2、list的常見(jiàn)接口

list的有很多接口，下面我們主要介紹幾個(gè)重點(diǎn)接口：

list的構(gòu)造

因?yàn)閘ist在C++中是用類(lèi)來(lái)封裝的，他也就有自己的構(gòu)造函數(shù)，但由于list初始化的場(chǎng)景非常多，所以他有多個(gè)構(gòu)造函數(shù)，下面的在模擬實(shí)現(xiàn)的時(shí)候可以細(xì)細(xì)體會(huì)，下面我們先見(jiàn)見(jiàn)有哪些構(gòu)造函數(shù)：

構(gòu)造函數(shù)(Construct)	接口說(shuō)明
list (size_type n, const value_type& val = value_type())	構(gòu)造的list中包含n個(gè)值為val的元素
list()	構(gòu)造空的list
list (const list& x)	拷貝構(gòu)造函數(shù)
list (InputIterator first, InputIterator last)	用[first, last)區(qū)間中的元素構(gòu)造list

list modifiers?

為來(lái)對(duì)list進(jìn)行修改，也提供了一些修改的接口：

函數(shù)聲明	接口說(shuō)明
push_front	在list首元素前插入值為val的元素
pop_front	刪除list中第一個(gè)元素
push_back	在list尾部插入值為val的元素
pop_back	刪除list中最后一個(gè)元素
insert	在list position 位置中插入值為val的元素
erase	刪除list position位置的元素
swap	交換兩個(gè)list中的元素
clear	清空l(shuí)ist中的有效元素

二、list的模擬實(shí)現(xiàn)

為了更好的理解list的底層實(shí)現(xiàn)，下面將大家一起去模擬實(shí)現(xiàn)list。

1、list框架搭建

我們要模式實(shí)現(xiàn)list，而list是個(gè)帶頭雙向鏈表，那么我們首先搭建一個(gè)list_node的類(lèi)模板

struct list_node
	{
		list_node*  _next;//指向后一個(gè)節(jié)點(diǎn)
		list_node*  _prev;//指向前一個(gè)節(jié)點(diǎn)
		T _data;//節(jié)點(diǎn)中的數(shù)據(jù)
		list_node(const T& x)
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};

這里我們要注意的是我們不僅僅定義了節(jié)點(diǎn)的指向，我們還應(yīng)該對(duì)節(jié)點(diǎn)進(jìn)行初始化。

有了節(jié)點(diǎn)，那么我們就應(yīng)該定義list類(lèi)的主體，他的私有變量應(yīng)該要有指向list_node的指針head,和記錄鏈表個(gè)數(shù)的size,為了方便定義，這里我們可以直接對(duì)list_node的變量名重定義。

templateclass list
	{
		typedef list_nodenode;
	public:
        //各種成員函數(shù)
	private:
		node* _head;
		size_t _size;
	};

下面我們就要實(shí)現(xiàn)各種成員函數(shù)就可以了，但是在實(shí)現(xiàn)成員函數(shù)之前，我們要先實(shí)現(xiàn)list的迭代器。

2、模擬實(shí)現(xiàn)list迭代器

我們?cè)谀Ｊ綄?shí)現(xiàn)vector的迭代器的時(shí)候，認(rèn)為迭代器就是一個(gè)指針。那么我們這里也可以把list的迭代器當(dāng)作指針實(shí)現(xiàn)嗎？這里顯然是不可以的，為什么這么說(shuō)呢？

當(dāng)一個(gè)指針++他跳過(guò)的是他的一個(gè)類(lèi)型的大小，但是list節(jié)點(diǎn)并不是挨個(gè)存儲(chǔ)的他節(jié)點(diǎn)的空間是隨機(jī)的，節(jié)點(diǎn)間是依靠節(jié)點(diǎn)中存放對(duì)方的地址指向?qū)Ψ降摹?/p>

其實(shí)不僅僅++操作不滿足，還有許多操作都是不滿足的，如--操作。

我們又該如何解決這個(gè)問(wèn)題呢？

其實(shí)我們可以用一個(gè)類(lèi)模板，包含迭代器功能的成員函數(shù)，就可以解決。當(dāng)我們調(diào)用迭代器時(shí)其實(shí)就是調(diào)用類(lèi)模板中的成員函數(shù)。

但是這里要注意一個(gè)細(xì)節(jié)：由于成員函數(shù)他的返回值可能存在類(lèi)型的差異，比如：*解引用的時(shí)候，返回_pnode->_data,但是->的時(shí)候是&_pode->_data;

這樣類(lèi)模板的參數(shù)就不僅僅是一個(gè)模板參數(shù)，而要三個(gè)模板參數(shù)才能解決。

//定義迭代器
	templatestruct __list_iterator
	{
		typedef list_nodenode;
		typedef __list_iteratorSelf;
		node* _pnode;
		//初始化
		__list_iterator(node* p)
			:_pnode(p)
		{}

		Ptr operator->()
		{
			return &_pnode->_data;
		}
		Ref operator*()
		{
			return _pnode->_data;
		}
		Self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		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;
		}
		bool operator!=(const Self it)const
		{
			return _pnode != it._pnode;
		}
		bool operator==(const Self& it)const
		{
			return _pnode == it._pnode;
		}
	};

其實(shí)不少同學(xué)可能會(huì)困惑，為什么要在迭代器中重載出->,這個(gè)不是我們?cè)谟媒Y(jié)構(gòu)體或者類(lèi)中指針成員才用到的嗎？

我們要明白list節(jié)點(diǎn)中可能存放的不是數(shù)據(jù),也可能是存放指針一個(gè)結(jié)構(gòu)體的指針。

下面我們來(lái)看代碼理解：

struct Pos
	{
		int _row;
		int _col;

		Pos(int row = 0, int col = 0)
			:_row(row)
			, _col(col)
		{}
	};

	void print_list(const list& lt)
	{
		list::const_iterator it = lt.begin();
		while (it != lt.end())
		{
			//it->_row++;

			cout<< it->_row<< ":"<< it->_col<< endl;

			++it;
		}
		cout<< endl;
	}
	void test3()
	{
		listlt;
		Pos p1(1, 1);
		lt.push_back(p1);
		lt.push_back(p1);
		lt.push_back(p1);
		lt.push_back(Pos(2, 2));
		lt.push_back(Pos(3, 3));

		// int* p  ->*p
		// Pos* p  ->p->list::iterator it = lt.begin();
		//list::iterator it2 = it;
		while (it != lt.end())
		{
			it->_row++;

			//cout<< (&(*it))->_row<< ":"<< (*it)._col<< endl;
			cout<< it->_row<< ":"<< it->_col<< endl;
			//cout<< it.operator->()->_row<< ":"<< it->_col<< endl;

			++it;
		}
		cout<< endl;

		print_list(lt);
	}

這里我們定義了一個(gè)Pos的類(lèi)，他的功能就是記錄row 和col,在定義一個(gè)函數(shù)print_list打印list中的做標(biāo)，下面在我們的測(cè)試函數(shù)在插入一些數(shù)據(jù)。如果是在測(cè)試函數(shù)體內(nèi)打印lt本來(lái)是非常復(fù)雜的如果沒(méi)有重載迭代器的->.

這里理解: (&(*it))->_row？----->簡(jiǎn)單的來(lái)是就是要拿到這個(gè)it節(jié)點(diǎn)中的數(shù)據(jù)

如果我們要拿到Pos中的數(shù)據(jù)就只要用Pos創(chuàng)建一個(gè)變量p,p->row,就能拿到類(lèi)中的數(shù)據(jù)，但是現(xiàn)在我們只有一個(gè)指向鏈表節(jié)點(diǎn)的迭代器，也就是只要我們*解引用it就能拿到節(jié)點(diǎn)中的數(shù)據(jù)，但是節(jié)點(diǎn)中的數(shù)據(jù)是一個(gè)類(lèi)的，要能到類(lèi)Pos的數(shù)據(jù)就要拿到類(lèi)的地址，并用->指向結(jié)構(gòu)體中變量的數(shù)據(jù)。

聽(tīng)起來(lái)是不是好暈，所以為了簡(jiǎn)化操作我們就在迭代器的類(lèi)中封裝了->.

Ptr operator->()
		{
			return &_pnode->_data;//&這里是取地址，也就是說(shuō)返回的指針
		}

迭代器失效問(wèn)題?

我們都知道迭代器是用類(lèi)封裝好的里面有功能各異的成員函數(shù)，迭代器失效即迭代器所指向的節(jié)點(diǎn)的無(wú)效，即該節(jié)點(diǎn)被刪除了。因?yàn)閘ist的底層結(jié)構(gòu)為帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表，因此在list中進(jìn)行插入時(shí)是不會(huì)導(dǎo)致list的迭代 器失效的，只有在刪除時(shí)才會(huì)失效，并且失效的只是指向被刪除節(jié)點(diǎn)的迭代器，其他迭代器不會(huì)受到影響。

3、list整體實(shí)現(xiàn)?

這里我們?cè)谡w實(shí)現(xiàn)的時(shí)候仍然采取分文件的做法，test.cpp用來(lái)包含所要的頭文件，list.h用來(lái)實(shí)現(xiàn)list的主體內(nèi)容。

test.cpp

#define  _CRT_SECURE_NO_WARNINGS

#include#include
using namespace std;
#include"list.h"

int main()
{
	pjb::test1();
	return 0;
}

list.h

#pragma once//防止頭文件被多次包含


namespace pjb
{
	templatestruct list_node
	{
		list_node*  _next;
		list_node*  _prev;
		T _data;
		list_node(const T& x)
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};
	//定義迭代器
	templatestruct __list_iterator
	{
		typedef list_nodenode;
		typedef __list_iteratorSelf;
		node* _pnode;
		//初始化
		__list_iterator(node* p)
			:_pnode(p)
		{}

		Ptr operator->()
		{
			return &_pnode->_data;
		}
		Ref operator*()
		{
			return _pnode->_data;
		}
		Self& operator++()
		{
			_pnode = _pnode->_next;
			return *this;
		}
		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;
		}
		bool operator!=(const Self it)const
		{
			return _pnode != it._pnode;
		}
		bool operator==(const Self& it)const
		{
			return _pnode == it._pnode;
		}
	};

	//定義lsit的類(lèi)
	templateclass list
	{
		typedef list_nodenode;
	public:
		typedef __list_iteratoriterator;
		typedef __list_iteratorconst_iterator;
		//初始化哨兵位的頭
		void empty_initialize()
		{
			_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;

			_size = 0;
		}
		//構(gòu)造函數(shù)
		list()
		{
			empty_initialize();
		}
		//析構(gòu)函數(shù)
		~list()
		{
			clear();
			//清除頭節(jié)點(diǎn)
			delete _head;
			_head = nullptr;
		}
		void clear()
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}
		templatelist(InputIterator first, InputIterator last)
		{
			empty_initialize();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}

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

		//交換
		void swap(list& lt)
		{
			std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}
		//lt2(lt1)
		list(const list& lt)
		{
			empty_initialize();
			listtmp(lt.begin(), lt.end());
			swap(tmp);
		}
		//lt3 = lt1
		list& operator=(listlt)
		{
			swap(lt);
			return *this;
		}
		//刪除
		iterator erase(iterator pos)
		{
			assert(pos != end());
			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;

			prev->_next = next;
			next->_prev = prev;
			delete pos._pnode;
			--_size;
			return iterator(next);
		}
		//插入
		iterator insert(iterator pos, const T& x)
		{
			//為插入申請(qǐng)新空間
			node* newnode = new node(x);
			node* cur = pos._pnode;//指向要插入位置的節(jié)點(diǎn)
			node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
			++_size;
			return iterator(newnode);//返回新節(jié)點(diǎn)的地址
		}
		//尾插
		void push_back(const T& x)
		{
			insert(end(),x);
		}
		//頭插
		void push_front(const T& x)
		{
			insert(begin(), x);
		}
		//尾刪除
		void pop_back()
		{
			erase(--end());
		}
		bool empty()const
		{
			return _size == 0;
		}
		size_t size()const
		{
			return _size;
		}

	private:
		node* _head;
		size_t _size;
	};
	//簡(jiǎn)單測(cè)試
	void test1()
	{
		listlt;
		lt.push_back(1);
		lt.push_back(2);
		lt.push_back(3);
		lt.push_back(4);
		list::iterator it = lt.begin();
		while (it != lt.end())
		{
			cout<< *it<< " ";
			++it;
		}
		cout<< endl;
	}
}

這里我們看到模擬實(shí)現(xiàn)的時(shí)候，我們還寫(xiě)了一個(gè)測(cè)試案例，下面去驗(yàn)證一下

三、list和vector的對(duì)比 1、對(duì)比二者的優(yōu)缺點(diǎn)

vector

Vector的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)	缺點(diǎn)
下標(biāo)支持隨機(jī)訪問(wèn)	前面部分效率低O（N）
尾插尾刪效率高	擴(kuò)容有消耗，存在一定的空間浪費(fèi)
Cpu高速緩存命中高

list?

list的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)	缺點(diǎn)
按需申請(qǐng)空間，無(wú)需擴(kuò)容	不支持隨機(jī)訪問(wèn)
任意位置插入刪除O(1)	Cpu高速緩存命中低

2、list和vector的排序效率?

這里我們要注意的是list有自己專(zhuān)門(mén)sort排序，而vector是用算法庫(kù)中的排序，這是因?yàn)閘ist的結(jié)構(gòu)的特殊性，算法庫(kù)中的不能夠滿足list的排序。

那二者那個(gè)效率更好呢?

測(cè)試10萬(wàn)個(gè)數(shù)據(jù)二者的排序時(shí)間的差異：

void test_op()
{
	srand(time(0));
	const int N = 100000;
	vectorv;
	v.reserve(N);

	listlt;
	for (int i = 0; i< N; ++i)
	{
		auto e = rand();
		v.push_back(e);
		lt.push_back(e);
	}

	int begin1 = clock();
	//對(duì)v排序
	sort(v.begin(), v.end());
	int end1 = clock();
	int begin2 = clock();
	//對(duì)lt排序
	lt.sort();
	int end2 = clock();
	printf("vector sort:%d\n", end1 - begin1);
	printf("list sort:%d\n", end2 - begin2);
}

int main()
{
	test_op();
	return 0;
}

從上面來(lái)看vector的排序效率是遠(yuǎn)大于list的，所以我們一個(gè)盡量不要使用list的排序。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)頁(yè)題目：由淺到深-模擬實(shí)現(xiàn)list-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://bm7419.com/article30/iipso.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)網(wǎng)站建設(shè)、小程序開(kāi)發(fā)、關(guān)鍵詞優(yōu)化、網(wǎng)站策劃、微信小程序、網(wǎng)站內(nèi)鏈

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)