【C++】list的介紹及模擬實現(xiàn)-創(chuàng)新互聯(lián)

🌈感謝閱讀East-sunrise學習分享——list的介紹及模擬實現(xiàn)
成都創(chuàng)新互聯(lián)公司是少有的成都網(wǎng)站設計、網(wǎng)站建設、營銷型企業(yè)網(wǎng)站、重慶小程序開發(fā)、手機APP,開發(fā)、制作、設計、賣友情鏈接、推廣優(yōu)化一站式服務網(wǎng)絡公司,從2013年成立,堅持透明化,價格低,無套路經營理念。讓網(wǎng)頁驚喜每一位訪客多年來深受用戶好評
博主水平有限，如有差錯，歡迎斧正🙏感謝有你
碼字不易，若有收獲，期待你的點贊關注💙我們一起進步
今天想分享介紹一下STL的容器之一list，以及進行模擬實現(xiàn)📌

一、list的介紹
二、list的模擬實現(xiàn)（簡易版--過渡）
三、迭代器
- 1.迭代器的定義
- 2.迭代器的功能分類
- 3.迭代器失效
- 4.list迭代器的模擬實現(xiàn)
- - 1.普通迭代器
  - 2.const迭代器
- 5.迭代器operator->的重載
- 6.迭代器的價值
四、vector和list的優(yōu)缺點
- 1.vector
- 2.list
五、代碼實現(xiàn)

一、list的介紹

list是可以在常數(shù)范圍內在任意位置進行插入和刪除的序列式容器，并且該容器可以前后雙向迭代。
list的底層是雙向鏈表結構，雙向鏈表中每個元素存儲在互不相關的獨立節(jié)點中，在節(jié)點中通過指針指向其前一個元素和后一個元素。
list的底層結構即是鏈表，這里附上博主之前關于【數(shù)據(jù)結構】鏈表的博客【數(shù)據(jù)結構-鏈表】有助于熟悉list的底層結構
關于list的使用并不復雜，相信學到這的兄弟以及擁有了查文檔的能力，博主就不再贅述list各種接口的具體用法，附上文檔介紹list使用文檔

有了之前對數(shù)據(jù)結構——鏈表的知識基礎，其實list的底層結構也并不神秘了，而list相較于前面的string、vector容器特別的地方就在于其迭代器，今天我們重點放在list的模擬實現(xiàn)及迭代器的介紹

二、list的模擬實現(xiàn)（簡易版–過渡）

list底層結構是帶頭雙向鏈表

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-iCkjCIlz-1672726780572)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221225161843143.png)]$

templatestruct list_node
{list_node* _next;//指向下一個節(jié)點
	list_node* _prev;//指向前一個節(jié)點
	T _data;//節(jié)點數(shù)據(jù)
    //構造函數(shù)
	list_node(const T& x)
		:_next(nullptr)
		, _prev(nullptr)
		, _data(x)
	{}
};

定義完list的節(jié)點，接下來即是list的主要結構

namespace qdy
{templatestruct list_node
	{list_node* _next;
		list_node* _prev;
		T _data;

		list_node(const T& x)
			:_next(nullptr)
			, _prev(nullptr)
			, _data(x)
		{}
	};

	templateclass list
	{typedef list_nodenode;
	public:
		list()
		{	_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
            _size = 0;
		}
        
		//尾插
		void push_back(const T& x)
		{	node* newnode = new node(x);
			node* tail = _head->_prev;
			// _head         tail   newnode
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
		}

	private:
		node* _head;//哨兵位的頭節(jié)點
		size_t _size;//記錄節(jié)點個數(shù)
	};

以上便是list的結構框架（簡易版實現(xiàn)），目前僅有尾插的接口，用于對list容器中添加數(shù)據(jù)??

添加數(shù)據(jù)后我們想要遍歷打印怎么辦呢？那就需要用到STL六大組件之一的迭代器🧮

三、迭代器 1.迭代器的定義

iterator的模式定義：“提供一種方法，使之能夠依序巡訪某個聚合物（容器）所含的各個元素，而又無需暴露該聚合物的內部表述方式。”

——《STL源碼剖析》

🎈通俗理解：容器用于存放數(shù)據(jù)，存放數(shù)據(jù)便有訪問數(shù)據(jù)讀寫數(shù)據(jù)的需求，STL六大組件之一的迭代器，便是給每個容器提供一個便于讀取數(shù)據(jù)的方法

2.迭代器的功能分類

單向迭代器：只能++，不能–。例如單鏈表、哈希表
雙向迭代器：既能++也能–。例如雙向鏈表
隨機訪問迭代器：能+±-，也能+和-。例如vector和string

迭代器是內嵌類型，通常定義為內部類或者直接定義在類中

3.迭代器失效

對于list，迭代器在進行insert操作后不失效，在進行erase操作后失效?

前面說過，此處大家可將迭代器暫時理解成類似于指針，迭代器失效即迭代器所指向的節(jié)點無效，即該節(jié)點被刪除了。因為list的底層結構為帶頭結點的雙向循環(huán)鏈表，因此在list中進行插入時是不會導致list的迭代器失效的，只有在刪除時才會失效，并且失效的只是指向被刪除節(jié)點的迭代器，其他迭代器不會受到影響。

void TestListIterator1()
{int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 	listl(array, array+sizeof(array)/sizeof(array[0]));
 	auto it = l.begin();
 	while (it != l.end())
    {// erase()函數(shù)執(zhí)行后，it所指向的節(jié)點已被刪除，因此it無效，在下一次使用it時，必須先給其賦值
        l.erase(it); 
 		++it;
 	}
}
// 改正
void TestListIterator()
{int array[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
 	listl(array, array+sizeof(array)/sizeof(array[0]));
 	auto it = l.begin();
 	while (it != l.end())
 	{it = l.erase(it);
        //為了避免迭代器失效的問題，erase接口提供了返回值可接收，該返回值為刪除后的下一節(jié)點
 	}
}

4.list迭代器的模擬實現(xiàn) 1.普通迭代器

在對迭代器模擬實現(xiàn)之前，我們要搞清楚list迭代器要有什么功能？

支持解引用（讀取數(shù)據(jù)）
支持++和–（訪問上一個or下一個節(jié)點）

回顧之前string和vector迭代器的模擬實現(xiàn)，我們是直接將指針typedef為迭代器使用，因為string和vector的底層結構是順序表，是一段連續(xù)的物理空間，所以通過使用原生指針便能符合其迭代器的需求了??

💥但是list的底層結構是鏈表，鏈表是按需開辟空間，并不是一段連續(xù)的物理空間，每個節(jié)點的物理地址并不連續(xù)，我們無法直接使用原生指針去+±-來遍歷來訪問節(jié)點。我們回顧剛開始接觸C++學習的日期類，日期類中的“日期”是我們自己定義的一種自定義類型，無法使用內置操作符直接對日期進行運算操作（編譯器又不認識那么多）所以我們是通過自己再去重定義日期的操作類，去重載操作符來滿足需求。

🚩類和對象說：該我上場表演了
既然原生指針已經無法滿足list迭代器的需求，那么我們可以自己定義一個迭代器，然后將節(jié)點指針封裝起來，然后再根據(jù)我們具體的需求情況去重載各種運算符實現(xiàn)迭代器功能。

//用類封裝迭代器
templatestruct __list_iterator
{typedef list_nodenode;
	node* _pnode;//封裝一個節(jié)點的指針
    
	//用節(jié)點指針進行構造
	__list_iterator(node* p)
		:_pnode(p)
	{}
	//迭代器運算符的重載
	T& operator*()
	{return _pnode->_data;
	}

	__list_iterator& operator++()
	{_pnode = _pnode->_next;
		return *this;//返回的是迭代器
	}

	bool operator!=(const __list_iterator& it)
	{return _pnode != it._pnode;
	}
};

定義完迭代器后便能對我們添加了數(shù)據(jù)的list進行遍歷打印了
1.迭代器遍歷 2.范圍for遍歷（底層也是調用了迭代器）

void test_list1()
{listlt;
	lt.push_back(1);
	lt.push_back(2);
	lt.push_back(3);
	lt.push_back(4);
    lt.push_back(5);
		
	list::iterator it = lt.begin();
	while (it != lt.end())
	{cout<< *it<< " ";
		++it;
	}
	cout<< endl;

	for (auto e : lt)
	{cout<< e<< " ";
	}
	cout<< endl;
}

定義完迭代器后，通過迭代器對容器數(shù)據(jù)進行訪問，實際上是一種函數(shù)調用

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-pyU84UfV-1672726780573)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221226124335878.png)]$

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-rUjQ5NTn-1672726780573)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221226124607339.png)]$

2.const迭代器

?const迭代器的錯誤寫法

typedef __list_iteratoriterator;
const list::iterator cit = lt.begin();

const之前我們修飾指針時有兩種方法
const T* p1;
T* const p2;
正確的const迭代器應該是像p1的行為，保護指向的對象不被修改，但是迭代器本身是可以修改的
但是上述的const迭代器寫法是保護了迭代器本身不能被修改，那么我們就不能++迭代器了

??正確寫法：想實現(xiàn)const迭代器，無法對普通迭代器直接加const，需要再寫一個const版本迭代器的類

templatestruct __list_const_iterator
{typedef list_nodenode;
	node* _pnode;

	__list_const_iterator(node* p)
		:_pnode(p)
	{}

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

	__list_const_iterator& operator++()
	{_pnode = _pnode->_next;
		return *this;
	}

	__list_const_iterator& operator--()
	{_pnode = _pnode->_prev;
		return *this;
	}

	bool operator!=(const __list_const_iterator& it)
	{return _pnode != it._pnode;
	}
};

typedef __list_iteratorconst_iterator;

但是如果像上述一樣，寫一個普通迭代器再寫一個const迭代器，代碼看起來就十分的冗長。那么我們可以利用好類模板，類模板即是能根據(jù)模板和調用時的參數(shù)，根據(jù)實參類型推演產生函數(shù)的特定類型版本。這樣，我們根據(jù)傳入?yún)?shù)的不同，可以使得一份類模板生成兩種類型的迭代器🧮

templatestruct __list_iterator
{typedef list_nodenode;
	typedef __list_iteratorSelf;
	node* _pnode;

	__list_iterator(node* p)
		:_pnode(p)
	{}
    
	Ref operator*()
	{return _pnode->_data;
	}
	
	Self& operator++()
	{_pnode = _pnode->_next;
		return *this;
	}

	Self& operator--()
	{_pnode = _pnode->_prev;
		return *this;
	}

	bool operator!=(const Self& it)
	{return _pnode != it._pnode;
	}
};

typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;

5.迭代器operator->的重載

我們調用對象的成員變量成員函數(shù)是用.實現(xiàn)，對指針解引用取其值是用*實現(xiàn)，而當結構體要解引用是使用->，再用->取其成員變量。而假如現(xiàn)在list中就存放的是結構體類型的數(shù)據(jù)??

所以我們有必要對->也進行重載

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

重載完之后我們要怎么使用呢?一共有3種方法

//坐標類
struct Pos
{int _row;
	int _col;

	Pos(int row = 0, int col = 0)
		:_row(row)
		,_col(col)
	{}
};
void test()
{listlt;
   	lt.push_back(Pos(1,1));
	lt.push_back(Pos(2,2));
	lt.push_back(Pos(3,3));
    
	// int* p  --->*p
	// Pos* p  --->p->list::iterator it = lt.begin();
	while (it != lt.end())
	{cout<< (&(*it))->_row;
        //*it取出容器數(shù)據(jù)（POS類） -- 再取地址訪問解引用得到_row
		cout<< it.operator->()->_row;
        //it.operator->()是顯式調用，然后再->解引用得到_row
        cout<< it->_row;
        //同第二種寫法，編譯器為了可讀性，省略了一個->
        ++it;
	}
}

$[外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-KhMzOZsV-1672726780574)(C:\Users\DongYu\AppData\Roaming\Typora\typora-user-images\image-20221226133619031.png)]$

💥但是當實際使用時，會發(fā)現(xiàn)有問題，那就是->的重載返回值為T*，這樣一來無論是普通迭代器或const迭代器都能對其值進行修改，所以我們需要將operator->的返回值改為泛型，然后針對不同的迭代器給不同的返回參數(shù)以示區(qū)分，如此一來，我們的迭代器模板又得再多一個參數(shù)啦📈

templatePtr operator->()
{return &_pnode->_data;
}

typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;

6.迭代器的價值

封裝底層實現(xiàn)，不暴露底層實現(xiàn)的細節(jié)
多種容器提供統(tǒng)一的訪問方式，降低容器使用成本
C語言沒有運算符重載和引用等語法，是實現(xiàn)不了迭代器的

四、vector和list的優(yōu)缺點

vector和list就像左右手一樣，是互補配合的關系

vector的優(yōu)點即是list的缺點，list的優(yōu)點也是vector的缺點，實際使用時可按照需求擇優(yōu)選用或者結合使用

1.vector

vector的優(yōu)點

支持下標的隨機訪問
尾插尾刪效率高（但是擴容的那一次尾插會較慢）
CPU高速緩存命中高（得益于vector的結構是一段連續(xù)的物理空間，數(shù)據(jù)從緩存加載到CPU時，是會加載連續(xù)的一段數(shù)據(jù)，而不是一個個加載，這樣一來在加載vector時高速緩存命中就很高）

🎈綜上所述vector的優(yōu)點都得益于其結構優(yōu)勢

vector的缺點

非尾插尾刪效率極低O(N)
擴容有消耗，還存在一定的空間浪費

🎈迭代器失效

insert和erase均會導致迭代器失效

2.list

list的優(yōu)點

按需申請釋放，無需擴容
任意位置插入刪除效率高O(1)

list的缺點

不支持下標的隨機訪問
CPU高速緩存命中率低

🎈迭代器失效

insert不失效，erase失效

五、代碼實現(xiàn)

namespace qdy
{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--()
		{	_pnode = _pnode->_prev;
			return *this;
		}

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

		bool operator!=(const Self& it)
		{	return _pnode != it._pnode;
		}

		bool operator==(const Self& it) const
		{	return _pnode == it._pnode;
		}
	};

	templateclass list
	{typedef list_nodenode;
	public:
		typedef __list_iteratoriterator;
		//typedef __list_const_iteratorconst_iterator;
		typedef __list_iteratorconst_iterator;


		//構造函數(shù)
		list()
		{	empty_initialize();
		}

		~list()
		{	clear();

			delete _head;
			_head = nullptr;
		}

		void clear()
		{	iterator it = begin();
			while (it != end())
			{		it = erase(it);
			}
		}

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

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

		iterator begin()
		{	return iterator(_head->_next);
			//iterator it(_head->_next);
			//return it;
		}

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

		void empty_initialize()
		{	_head = new node(T());
			_head->_next = _head;
			_head->_prev = _head;
			_size = 0;
		}

		templatelist(InputIterator first, InputIterator last)
		{	empty_initialize();
			while (first != last)
			{		push_back(*first);
				++first;
			}
		}

		void swap(list& lt)
		{	std::swap(_head, lt._head);
			std::swap(_size, lt._size);
		}

		// 現(xiàn)代寫法
		// lt2(lt1)
		list(const list& lt)
			//list(const list& lt) // 不建議
		{	empty_initialize();

			listtmp(lt.begin(), lt.end());
			swap(tmp);
		}

		// lt3 = lt1
		list& operator=(listlt)
			//list& operator=(list lt) // 不建議
		{	swap(lt);
			return *this;
		}

		//尾插
		void push_back(const T& x)
		{	//node* newnode = new node(x);
			//node* tail = _head->_prev;
			_head     tail   newnode
			//newnode->_prev = tail;
			//tail->_next = newnode;
			//newnode->_next = _head;
			//_head->_prev = newnode;

			insert(end(), x);
		}

		void push_front(const T& x)
		{	insert(begin(), x);
		}

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

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

		iterator insert(iterator pos, const T& x)
		{	node* newnode = new node(x);
			node* cur = pos._pnode;
			node* prev = cur->_prev;

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

			++_size;
			return iterator(newnode);
		}

		iterator erase(iterator pos)
		{	assert(pos != _head);

			node* prev = pos._pnode->_prev;
			node* next = pos._pnode->_next;

			prev->_next = next;
			next->_prev = prev;

			delete pos._pnode;
			--_size;

			return iterator(next);
		}

		size_t size()const
		{	return _size;
		}

		bool empty()const
		{	return _size == 0;
		}

	private:
		node* _head;
		size_t _size;
	};
}

🌈🌈寫在最后
我們今天對list的分享就到此結束了
對于這篇博客最精華的部分便是迭代器的實現(xiàn)，迭代器在各種容器中是不可或缺的一部分🚩
🎈感謝能耐心地閱讀到此
🎈碼字不易，感謝三連
🎈關注博主，我們一起學習、一起進步

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

當前名稱：【C++】list的介紹及模擬實現(xiàn)-創(chuàng)新互聯(lián)
瀏覽地址：http://muchs.cn/article16/idjgg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供用戶體驗、品牌網(wǎng)站建設、定制開發(fā)、全網(wǎng)營銷推廣、靜態(tài)網(wǎng)站、響應式網(wǎng)站

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

猜你還喜歡下面的內容