1. 單向迭代器：只能++，不能–。例如單鏈表、哈希表
2. 雙向迭代器：既能++也能–。例如雙向鏈表
3. 隨機(jī)訪問(wèn)迭代器：能+±-，也能+和-。例如vector和string

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

對(duì)于list，迭代器在進(jìn)行insert操作后不失效，在進(jìn)行erase操作后失效?

前面說(shuō)過(guò)，此處大家可將迭代器暫時(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ì)受到影響。

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é)點(diǎn)已被刪除，因此it無(wú)效，在下一次使用it時(shí)，必須先給其賦值
        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);
        //為了避免迭代器失效的問(wèn)題，erase接口提供了返回值可接收，該返回值為刪除后的下一節(jié)點(diǎn)
 	}
}

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

1. 支持解引用（讀取數(shù)據(jù)）
2. 支持++和–（訪問(wèn)上一個(gè)or下一個(gè)節(jié)點(diǎn)）

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

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

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

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

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

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

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

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

定義完迭代器后，通過(guò)迭代器對(duì)容器數(shù)據(jù)進(jìn)行訪問(wèn)，實(shí)際上是一種函數(shù)調(diào)用

?const迭代器的錯(cuò)誤寫法

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

const之前我們修飾指針時(shí)有兩種方法

const T* p1;
T* const p2;

正確的const迭代器應(yīng)該是像p1的行為，保護(hù)指向的對(duì)象不被修改，但是迭代器本身是可以修改的

但是上述的const迭代器寫法是保護(hù)了迭代器本身不能被修改，那么我們就不能++迭代器了

??正確寫法：想實(shí)現(xiàn)const迭代器，無(wú)法對(duì)普通迭代器直接加const，需要再寫一個(gè)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;

但是如果像上述一樣，寫一個(gè)普通迭代器再寫一個(gè)const迭代器，代碼看起來(lái)就十分的冗長(zhǎng)。那么我們可以利用好類模板，類模板即是能根據(jù)模板和調(diào)用時(shí)的參數(shù)，根據(jù)實(shí)參類型推演產(chǎn)生函數(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;

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

所以我們有必要對(duì)->也進(jìn)行重載

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

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

//坐標(biāo)類
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類） -- 再取地址訪問(wèn)解引用得到_row
		cout<< it.operator->()->_row;
        //it.operator->()是顯式調(diào)用，然后再->解引用得到_row
        cout<< it->_row;
        //同第二種寫法，編譯器為了可讀性，省略了一個(gè)->
        ++it;
	}
}

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

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

typedef __list_iteratoriterator;
typedef __list_iteratorconst_iterator;

1. 封裝底層實(shí)現(xiàn)，不暴露底層實(shí)現(xiàn)的細(xì)節(jié)
2. 多種容器提供統(tǒng)一的訪問(wèn)方式，降低容器使用成本
3. C語(yǔ)言沒(méi)有運(yùn)算符重載和引用等語(yǔ)法，是實(shí)現(xiàn)不了迭代器的

vector和list就像左右手一樣，是互補(bǔ)配合的關(guān)系

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

vector的優(yōu)點(diǎn)

1. 支持下標(biāo)的隨機(jī)訪問(wèn)
2. 尾插尾刪效率高（但是擴(kuò)容的那一次尾插會(huì)較慢）
3. CPU高速緩存命中高（得益于vector的結(jié)構(gòu)是一段連續(xù)的物理空間，數(shù)據(jù)從緩存加載到CPU時(shí)，是會(huì)加載連續(xù)的一段數(shù)據(jù)，而不是一個(gè)個(gè)加載，這樣一來(lái)在加載vector時(shí)高速緩存命中就很高）

🎈綜上所述vector的優(yōu)點(diǎn)都得益于其結(jié)構(gòu)優(yōu)勢(shì)

vector的缺點(diǎn)

1. 非尾插尾刪效率極低O(N)
2. 擴(kuò)容有消耗，還存在一定的空間浪費(fèi)

🎈迭代器失效

insert和erase均會(huì)導(dǎo)致迭代器失效

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

1. 按需申請(qǐng)釋放，無(wú)需擴(kuò)容
2. 任意位置插入刪除效率高O(1)

list的缺點(diǎn)

1. 不支持下標(biāo)的隨機(jī)訪問(wèn)
2. CPU高速緩存命中率低

🎈迭代器失效

insert不失效，erase失效

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;


		//構(gòu)造函數(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;
	};
}

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

你是否還在尋找穩(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)查看詳情吧

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

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

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(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)