目錄

• 前言
• 一、list和vector的區(qū)別
• 二、節(jié)點的定義
• 三、list類定義
• 四、push_back函數
• 五、push_front函數
• 六、迭代器
• 七、begin和end函數
• 八、迭代器區(qū)間初始化
• 九、迭代器的操作符重載
• • 操作符++重載
  • 操作符- -重載
  • 操作符！=重載
  • 操作符==重載
  • 操作符*重載
• 十、insert函數
• 十一、erase函數
• 十二、pop_back函數
• 十三、pop_front
• 十四、析構函數
• 十五、拷貝構造函數
• 十六、賦值操作符重載
• 十七、迭代器優(yōu)化
• 十七、反向迭代器
• 總結:

在永清等地區(qū)，都構建了全面的區(qū)域性戰(zhàn)略布局，加強發(fā)展的系統(tǒng)性、市場前瞻性、產品創(chuàng)新能力，以專注、極致的服務理念，為客戶提供做網站、成都網站建設 網站設計制作按需策劃,公司網站建設,企業(yè)網站建設,成都品牌網站建設,網絡營銷推廣,外貿網站建設,永清網站建設費用合理。前言

上次模擬實現了一個vector容器，那么我們這次來實現一個list(鏈表)容器，鏈表在實際的開發(fā)中并不常見。但是也是一種很重要的數據結構，下面給大家介紹一下鏈表(list) 和 vector(順序表)的區(qū)別。

---

一、list和vector的區(qū)別

list 和 vector 一樣，是一個存儲容器。不同的是vector在內存中是連續(xù)存儲的，而list每個節(jié)點所在的內存區(qū)域是不連續(xù)的。那我們用vector還是用list呢？vector和list的優(yōu)劣勢有以下幾點。
vector優(yōu)點:
1.支持下標隨機訪問。
2.cpu命中緩存率高
vector缺點:
1.存在一定的程度的空間浪費。
2.擴容代價大。
3.中間和前面元素的刪除與插入，代價大。

list優(yōu)點:
1.按需申請空間，不存在空間浪費。
2.任意位置的插入與刪除，時間復雜度都是O(1)。
list缺點:
1.不支持隨機訪問，以至于查找，排序等操作代價太大。
2.cpu命中緩存率低。

綜上所述，我們可以看到list和vector是完全互補的兩個容器。vector的優(yōu)點就是list的缺點，vector的缺點就是list的優(yōu)點。所以，如果查找多，用vector，如果增刪操作多，用list，了解了list之后，接下來我們就可以模擬實現一下它。

---

二、節(jié)點的定義

我們要實現的是一個帶頭雙向循環(huán)的鏈表。

所以節(jié)點有三個參數，一個的prve指向前一個節(jié)點，一個是date存儲數據，還有一個是next指向下一個節(jié)點。當然，我們還需要有個構造函數，來給date賦值。

代碼:

//節(jié)點結構體
	templatestruct ListNode
	{typedef ListNodeNode;
		Node* _prve;
		Node* _next;
		T _data;

		//構造函數
		ListNode():_prve(nullptr),_next(nullptr),_data(0){}
		
		ListNode(const T& val)
			:_prve(nullptr)
			,_next(nullptr)
		{	_data = val;
		}
	};

---

三、list類定義

list定義很簡單，因為要存任意類型的參數，我們用模板即可。
而私有成員只有一個，那就是頭節(jié)點。

代碼:

templateclass list
	{typedef ListNodeNode;
	public:
		//構造函數
		list()
		{	//開辟空間
			_head = new Node;
			//自己指向自己
			_head->_prve = _head;
			_head->_next = _head;
		}
	private:
		Node* _head;
	};

---

四、push_back函數

push_back函數也就是尾部插入，我們可以通過頭節(jié)點的prev找到最后一個節(jié)點，隨后鏈接即可。

代碼:

void push_back(const T& val)
		{	//創(chuàng)建一個新節(jié)點
			Node* newNode = new Node(val);
			//找到尾節(jié)點
			Node* tail = _head->_prve;
			//尾節(jié)點和創(chuàng)建的節(jié)點鏈接
			tail->_next = newNode;
			newNode->_prve = tail;
			_head->_prve = newNode;
			newNode->_next = _head;
		}

---

五、push_front函數

就是頭插，很簡單，直接保存節(jié)點的下一個節(jié)點，然后創(chuàng)建一個新節(jié)點。把這倆節(jié)點鏈接起來。

代碼:

void push_front(const T& val)
		{	//創(chuàng)建一個新節(jié)點
			Node* newNode = new Node(val);
			//保存頭節(jié)點的下一個節(jié)點
			Node* next = _head->_next;
			//鏈接
			_head->_next = newNode;
			newNode->_prve = _head;
			next->_prve = newNode;
			newNode->_next = next;
		}

六、迭代器

因為是鏈表容器，鏈表在內存中的存儲不是連續(xù)的，所以迭代器+1是無法找到下一個節(jié)點的。所以我們要單獨弄一個結構體來封裝list的迭代器。

代碼:

templatestruct_list_iterator
	{Node* _it;
		typedef ListNodeNode;
		// 構造函數
		_list_iterator(Node* node)
			:_it(node)
		{		}

	};

---

七、begin和end函數

我們的鏈表是帶頭的，也就是頭節(jié)點是不存放有效值的，所以頭節(jié)點的_next指向的節(jié)點就是鏈表的第一個節(jié)點。而最后一個節(jié)點的下一個節(jié)點又恰好是頭節(jié)點。所以迭代器開始位置是在頭節(jié)點的下一個位置，結束位置是頭節(jié)點。不過再此之前，我們需要把迭代器typedef一下。

代碼:

//迭代器
		typedef _list_iteratoriterator;
		typedef _list_iteratorconst_iterator;
		//迭代器獲取
		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);
		}

八、迭代器區(qū)間初始化

有了迭代器之后，我們可以用迭代器區(qū)間來進行初始化。

代碼:

templatelist(InputIterator first, InputIterator last)
		{	//創(chuàng)建頭節(jié)點
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;

			while (first != last)
			{		pusb_back(*first);
				++first;
			}
		}

九、迭代器的操作符重載

接下來我們來完善迭代器的一些操作。

操作符++重載

迭代器++，就是指向下一個元素。

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

操作符- -重載

和++類似，不過- -是到前一個節(jié)點。

//前置--重載
		self& operator--()
		{	_it = _it->_prve;
			return *this;
		}

		//后置--重載
		self operator--(int)
		{	self tmp(*this);
			_it = _it->_prve;
			return tmp;
		}

操作符！=重載

直接比較地址即可。

// !=重載
		bool operator!=(const self& it)const
		{	return _it != it._it;
		}

操作符==重載

直接比較地址即可。

// ==重載
		bool operator==(const self& it)const
		{	return _it == it._it;
		}

操作符*重載

*就是解引用，所以我們返回節(jié)點的值即可。

T& operator*()
		{	return _it->_data;
		}

但是這個代碼有個缺陷，那就是當容器是const的時候，依舊可以解引用修改它的值，這也就意味著const迭代器根本就不具有常屬性，要想const迭代具備常屬性，我們必須增加模板參數。

當容器是const的時候，返回的const迭代器必須具有常屬性。所以我們要加一個模板參數作為返回值。

然后list里面typedef的類型也修改一下。

然后我們解引用時，返回Ref這個模板參數

這樣，我們就讓const的迭代器具備了常屬性

迭代器結構體的所有代碼:

//迭代器
	templatestruct _list_iterator
	{		typedef ListNodeNode;
		typedef _list_iteratorself;
		Node* _it;
		// 構造函數
		_list_iterator(Node* node)
			:_it(node){}
		//前置++重載
		self& operator++()
		{	_it = _it->_next;
			return *this;
		}

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

		//前置--重載
		self& operator--()
		{	_it = _it->_prve;
			return *this;
		}

		//后置--重載
		self operator--(int)
		{	self tmp(*this);
			_it = _it->_prve;
			return tmp;
		}
		// *重載
		Ref operator*()
		{	return _it->_data;
		}
		// !=重載
		bool operator!=(const self& it)const
		{	return _it != it._it;
		}
		// ==重載
		bool operator==(const self& it)const
		{	return _it == it._it;
		}

	};

十、insert函數

insert函數是在指定位置插入一個節(jié)點，那么我們可以用迭代器來接收這個要插入的位置。

//插入節(jié)點
		iterator insert(iterator pos, const T& val)
		{	assert(pos._it);
			//保存pos的前一個位置
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			//創(chuàng)建節(jié)點
			Node* newNode = new Node(val);
			//鏈接
			prve->_next = newNode;
			newNode->_prve = prve;
			newNode->_next = cru;
			cru->_prve = newNode;

			return pos;
		}

十一、erase函數

指定位置刪除節(jié)點，刪除節(jié)點會影響迭代器失效，所以要返回一個有效的迭代器。刪除操作也十分簡單，保存前一個節(jié)點的地址和后一個地址的節(jié)點，然后鏈接這2個節(jié)點，之后釋放pos節(jié)點。

iterator erase(iterator pos)
		{	assert(pos._it);
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			Node* next = cru->_next;
			//鏈接
			prve->_next = next;
			next->_prve = prve;
			//釋放cru
			delete cru;
			return next;
		}
		

十二、pop_back函數

就是尾刪，我們可以直接復用erase

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

當然，push_back也可以復用inset

十三、pop_front

就是頭刪，還是復用erase。頭插也可以復用insert

void pop_front()
		{	erase(begin());
		}

十四、析構函數

鏈表的基本功能已經實現完了，但是當我們鏈表不用的時候，申請的空間必須銷毀。而自帶的析構函數不會銷毀動態(tài)申請的空間，需要我們自己寫析構函數銷毀。

代碼:

//析構函數
		~list()
		{	//清空鏈表
			clear();
			//釋放頭節(jié)點
			delete _head;
			_head = nullptr;
		}

		void clear()
		{	//除了頭節(jié)點外，其他都釋放。
			iterator it = begin();
			while (it != end())
			{		//保存下一個位置的地址
				iterator next = it++;
				delete next._it;
			}
			//釋放完之后，頭節(jié)點指向的是個野指針，所以我們讓它指向自己
			_head->_next = _head;
			_head->_prve = _head;
		}

十五、拷貝構造函數

那么我們想拷貝鏈表呢？我們可以直接用迭代器區(qū)間去創(chuàng)建一個新的對象，然后把新對象的頭節(jié)點成員和舊對象進行交換。出了函數創(chuàng)建的對象會自動調用析構函數釋放空間。

//拷貝構造
		list(const list& l1)
		{	//創(chuàng)建頭節(jié)點
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;
			//創(chuàng)建新對象，利用迭代器區(qū)間
			listtmp(l1.begin(), l1.end());
			//隨后交換新對象和舊對象的成員
			swap(_head, tmp._head);
		}

十六、賦值操作符重載

我們可以利用拷貝構造創(chuàng)建一個新對象，然后交換頭節(jié)點。函數結束，創(chuàng)建的對象自動析構。

代碼:

list& operator=(const list& l1)
		{	listtmp(l1);
			swap(_head, tmp._head);
			return *this;
		}

十七、迭代器優(yōu)化

我們的迭代器還不夠完美，因為如果list裝的是自定義類型的話，我們還需要讓迭代器支持 ->訪問。期望它返回一個對象的指針回來，然后該對象的指針可以->直接訪問成員。所以我們還需要增加模板參數。

增加一個指針參數

鏈表里的迭代器調整。

然后重載 迭代器的->操作符

Ptr operator->()
		{	//返回對象的指針
			return &(_it->_data);
		}

可以直接支持->訪問

十七、反向迭代器

之前在vector實現的時候，我們實現過反向迭代器。vector實現鏈接。所以我們可以復用這個反向迭代器。

首先，包上反向迭代器的頭文件名。

其次，我們typedef 2個反向迭代器

隨后用rbegin函數和rend函數獲取迭代器的開始和結束位置。
begin返回的是從頭節(jié)點的下一個節(jié)點，所以rend就是返回頭節(jié)點的下一個位置。
end返回的是頭節(jié)點，所以rbegin返回頭節(jié)點。

代碼:

//反向迭代器獲取
		reverse_iterator rbegin()
		{	return reverse_iterator(end());
		}

		reverse_iterator rend()
		{	return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{	return reverse_const_iterator(end());
		}

		const_reverse_iterator rend()const
		{	return reverse_const_iterator(begin());
		}

全部代碼:
list.h代碼

#pragma once
#include "reverse_iterator.h"

namespace wyl
{//節(jié)點結構體
	templatestruct ListNode
	{typedef ListNodeNode;
		Node* _prve;
		Node* _next;
		T _data;

		//構造函數
		ListNode():_prve(nullptr),_next(nullptr),_data(0){}

		ListNode(const T& val)
			:_prve(nullptr)
			,_next(nullptr)
		{	_data = val;
		}
	};

	//迭代器
	templatestruct _list_iterator
	{		typedef ListNodeNode;
		typedef _list_iteratorself;
		Node* _it;
		// 構造函數
		_list_iterator(Node* node)
			:_it(node){}
		//前置++重載
		self& operator++()
		{	_it = _it->_next;
			return *this;
		}

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

		//前置--重載
		self& operator--()
		{	_it = _it->_prve;
			return *this;
		}

		//后置--重載
		self operator--(int)
		{	self tmp(*this);
			_it = _it->_prve;
			return tmp;
		}
		// *重載
		Ref operator*()
		{	return _it->_data;
		}
		// !=重載
		bool operator!=(const self& it)const
		{	return _it != it._it;
		}
		// ==重載
		bool operator==(const self& it)const
		{	return _it == it._it;
		}

		Ptr operator->()
		{	//返回對象的指針
			return &(_it->_data);
		}

	};

	templateclass list
	{typedef ListNodeNode;
		
	public:
		//迭代器
		typedef _list_iteratoriterator;
		typedef _list_iteratorconst_iterator;
		//反向迭代器
		typedef _reverse_iteratorreverse_iterator;
		typedef _reverse_iteratorconst_reverse_iterator;

		//構造函數
		list()
		{	//開辟空間
			_head = new Node();
			//自己指向自己
			_head->_prve = _head;
			_head->_next = _head;
		}
		//迭代器區(qū)間初始化
		templatelist(InputIterator first, InputIterator last)
		{	//創(chuàng)建頭節(jié)點
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;

			while (first != last)
			{		push_back(*first);
				++first;
			}
		}
		//拷貝構造
		list(const list& l1)
		{	//創(chuàng)建頭節(jié)點
			_head = new Node();
			_head->_prve = _head;
			_head->_next = _head;
			//創(chuàng)建新對象，利用迭代器區(qū)間
			listtmp(l1.begin(), l1.end());
			//隨后交換新對象和舊對象的成員
			swap(_head, tmp._head);
		}
		list& operator=(const list& l1)
		{	listtmp(l1);
			swap(_head, tmp._head);
			return *this;
		}

		//析構函數
		~list()
		{	//清空鏈表
			clear();
			//釋放頭節(jié)點
			delete _head;
			_head = nullptr;
		}

		void clear()
		{	//除了頭節(jié)點外，其他都釋放。
			iterator it = begin();
			while (it != end())
			{		//保存下一個位置的地址
				iterator next = it++;
				delete next._it;
			}
			//釋放完之后，頭節(jié)點指向的是個野指針，所以我們讓它指向自己
			_head->_next = _head;
			_head->_prve = _head;
		}

		void push_back(const T& val)
		{	//創(chuàng)建一個新節(jié)點
			Node* newNode = new Node(val);
			//找到尾節(jié)點
			Node* tail = _head->_prve;
			//尾節(jié)點和創(chuàng)建的節(jié)點鏈接
			tail->_next = newNode;
			newNode->_prve = tail;
			_head->_prve = newNode;
			newNode->_next = _head;
		}

		void push_front(const T& val)
		{	//創(chuàng)建一個新節(jié)點
			Node* newNode = new Node(val);
			//保存頭節(jié)點的下一個節(jié)點
			Node* next = _head->_next;
			//鏈接
			_head->_next = newNode;
			newNode->_prve = _head;
			next->_prve = newNode;
			newNode->_next = next;
		}



		//迭代器獲取
		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);
		}

		//反向迭代器獲取
		reverse_iterator rbegin()
		{	return reverse_iterator(end());
		}

		reverse_iterator rend()
		{	return reverse_iterator(begin());
		}

		const_reverse_iterator rbegin()const
		{	return const_reverse_iterator(end());
		}

		const_reverse_iterator rend()const
		{	return const_reverse_iterator(begin());
		}


		//插入節(jié)點
		iterator insert(iterator pos, const T& val)
		{	assert(pos._it);
			//保存pos的前一個位置
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			//創(chuàng)建節(jié)點
			Node* newNode = new Node(val);
			//鏈接
			prve->_next = newNode;
			newNode->_prve = prve;
			newNode->_next = cru;
			cru->_prve = newNode;

			return pos;
		}

		iterator erase(iterator pos)
		{	assert(pos._it);
			Node* cru = pos._it;
			Node* prve = cru->_prve;
			Node* next = cru->_next;
			//鏈接
			prve->_next = next;
			next->_prve = prve;
			//釋放cru
			delete cru;
			return next;
		}
		
		void pop_back()
		{	erase(end());
		}

		void pop_front()
		{	erase(begin());
		}

	private:
		Node* _head;
	};


	//--------------------------------------------------------------------------------------------
	//以下是測試內容

	void listTest1()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		l.push_front(30);
		l.push_front(20);
		l.push_front(10);
	}

	void a(const list& l)
	{list::const_iterator it = l.begin();
		while (it != l.end())
		{	//*it = 5;
			cout<< *it<< " ";
			it++;
		}
	}

	void listTest2()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(3);
		list::iterator it = l.begin();
		while (it != l.end())
		{	*it = 55;
			cout<< *it<< " ";
			++it;
		}
		//a(l);
	}

	void listTest3()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(4);
		l.push_back(5);
		l.insert(l.begin(),100);
		l.insert(l.end(), 10);

		list::iterator it = l.begin();
		while (it != l.end())
		{	if (*it % 2 == 0)
			{		it = l.erase(it);
			}
			else
				++it;
		}
		it = l.begin();
		while (it != l.end())
		{	cout<< *it<< " ";
			++it;
		}
	}

	void listTest4()
	{listl;
		l.push_back(1);
		l.push_back(2);
		l.push_back(4);
		l.push_back(5);
		l.clear();
		l.push_back(1);
		l.push_back(2);
		l.push_back(4); 
		l.push_back(5);
		listl2 = l;
		list::iterator it = l2.begin();
		while (it != l2.end())
		{	cout<< *it<< " ";
			++it;
		}
	}


	void listTest5()
	{listl;
		l.push_back(Date(2022, 1, 3));
		l.push_back(Date(2022, 1, 4));
		l.push_back(Date(2022, 1, 5));

		list::iterator it = l.begin();
		while (it != l.end())
		{	cout<< it->_year<< "/"<_month<<"/"<_day<listl;
		l.push_back(Date(2022, 1, 3));
		l.push_back(Date(2022, 1, 4));
		l.push_back(Date(2022, 1, 5));

		list::reverse_iterator it = l.rbegin();
		while (it != l.rend())
		{	cout<< it->_year<< "/"<< it->_month<< "/"<< it->_day<< endl;
			++it;
		}

	}

}

反向迭代器代碼:
reverse_iterator.h

#pragma once

templateclass _reverse_iterator
{typedef _reverse_iteratorself;
public:	
	_reverse_iterator(iterator it)
		:_it(it)
	{}
	//前置++
	self& operator++()
	{--_it;
		return *this;
	}
	//后置++
	self operator++(int)
	{self tmp(*this);
		--_it;
		return tmp;
	}

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

	Ref operator*()
	{iterator tmp = (*this)._it;
		return *(--tmp);
	}

	Ptr operator->()
	{return &operator*();
	}

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

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

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

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


private:
	iterator _it;
};

主程序代碼:

#include"list.h"
void listTest()
{//wyl::listTest2();
	//wyl::listTest3();
	//wyl::listTest4();
	//wyl::listTest5();
	wyl::listTest6();

}

int main()
{listTest();

}

總結:

list的實現，其實最主要的部分還是迭代器。list的迭代器是比較特殊的，因為list在內存中不是連續(xù)存儲的。以上代碼都是我邊打，邊測試，沒問題了才會發(fā)出來。如果有什么沒測試到的錯誤，歡迎大家指出。以后會持續(xù)為大家更新STL的內容，以及數據結構，C語言，linux等方面的內容。感謝大家的支持，如果感覺寫的還不錯，麻煩給個三連嘛。我會多多努力的！

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

標題名稱：【C++】STL---list的模擬實現-創(chuàng)新互聯(lián)
文章來源：http://weahome.cn/article/jccpd.html