前言

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

作者：小蝸牛向前沖

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

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

目錄

一 、見見STL中的list

1、list的介紹

2、list的常見接口

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

1、list框架搭建

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

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

三、list和vector的對比

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

2、list和vector的排序效率?

---

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

一 、見見STL中的list 1、list的介紹

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

文檔介紹：

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

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

2、list的常見接口

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

list的構(gòu)造

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

構(gòu)造函數(shù)(Construct)	接口說明
list (size_type n, const value_type& val = value_type())	構(gòu)造的list中包含n個值為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?

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

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

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

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

1、list框架搭建

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

struct list_node
	{
		list_node*  _next;//指向后一個節(jié)點(diǎn)
		list_node*  _prev;//指向前一個節(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)該對節(jié)點(diǎn)進(jìn)行初始化。

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

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

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

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

我們在模式實現(xiàn)vector的迭代器的時候，認(rèn)為迭代器就是一個指針。那么我們這里也可以把list的迭代器當(dāng)作指針實現(xiàn)嗎？這里顯然是不可以的，為什么這么說呢？

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

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

我們又該如何解決這個問題呢？

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

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

這樣類模板的參數(shù)就不僅僅是一個模板參數(shù)，而要三個模板參數(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;
		}
	};

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

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

下面我們來看代碼理解：

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);
	}

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

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

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

聽起來是不是好暈，所以為了簡化操作我們就在迭代器的類中封裝了->.

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

迭代器失效問題?

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

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

這里我們在整體實現(xiàn)的時候仍然采取分文件的做法，test.cpp用來包含所要的頭文件，list.h用來實現(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的類
	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)
		{
			//為插入申請新空間
			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;
	};
	//簡單測試
	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;
	}
}

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

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

vector

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

list?

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

2、list和vector的排序效率?

這里我們要注意的是list有自己專門sort排序，而vector是用算法庫中的排序，這是因為list的結(jié)構(gòu)的特殊性，算法庫中的不能夠滿足list的排序。

那二者那個效率更好呢?

測試10萬個數(shù)據(jù)二者的排序時間的差異：

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();
	//對v排序
	sort(v.begin(), v.end());
	int end1 = clock();
	int begin2 = clock();
	//對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;
}

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

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

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

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

廣告

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