?文章來源地址http://www.zghlxwxcb.cn/news/detail-407231.html

?

?

前言

反向迭代器的適配只用于雙向迭代器，對(duì)于單鏈表實(shí)現(xiàn)的單向迭代器是不能通過適配構(gòu)造一個(gè)反向迭代器的，為什么要說反向迭代器適配器呢？因?yàn)槲覀冎恍枰獙?shí)現(xiàn)一個(gè)反向迭代器模板就可以用所有的雙向迭代器的正向?qū)崿F(xiàn)其反向迭代器。

提示：以下是本篇文章正文內(nèi)容，下面案例可供參考

一、list的反向迭代器

對(duì)于list而言，我們想要倒著遍歷該如何實(shí)現(xiàn)呢？其實(shí)實(shí)現(xiàn)過正向迭代器的朋友們都知道，list的迭代器的++是指向鏈表的下一個(gè)節(jié)點(diǎn)，也就是node = node->next,那么要實(shí)現(xiàn)反向我們只需要將++實(shí)現(xiàn)為將node = node->prev即可，如下圖所示：

?

    //反向迭代器
	template<class T, class Ref, class Ptr>
	struct list_reverse_iterator
	{
		typedef list_node<T> node;
		typedef list_reverse_iterator<T, Ref, Ptr> self;
		node* _node;
		list_reverse_iterator(node* n)
			:_node(n)
		{

		}
		Ref operator*()
		{
			return _node->_data;
		}
		self& operator++()
		{
			_node = _node->_prev;
			return *this;
		}
		self operator++(int)
		{
			self tmp(*this);
			_node = _node->_prev;
			return tmp;
		}
		self& operator--()
		{
			_node = _node->_next;
			return *this;
		}
		self operator--(int)
		{
			self tmp(*this);
			_node = _node->_next;
			return tmp;
		}
		Ptr operator->()
		{
			return &_node->_data;
		}
		bool operator!=(const self& it)
		{
			return _node != it._node;
		}
		bool operator==(const self& it)
		{
			return _node == it._node;
		}
	};

?可以看到我們上述代碼對(duì)于反向迭代器確實(shí)只是將++變成了原先的--，--變成了原先的++。現(xiàn)在我們?cè)賹懸幌聄begin(),rbegin().

class list
	{
	public:
		typedef list_node<T> node;
		typedef list_iterator<T, T&, T*> iterator;
		typedef list_iterator<T, const T&, const T*> const_iterator;
		typedef list_reverse_iterator<T, T&, T*> reverse_iterator;
		iterator begin()
		{
			return iterator(_head->_next);
		}
		iterator end()
		{
			return iterator(_head);
		}
		const_iterator begin() const
		{
			return const_iterator(_head->_next);
		}
		const_iterator end() const
		{
			return const_iterator(_head);
		}
		reverse_iterator rbegin() 
		{
			return reverse_iterator(_head->_prev);
		}
		reverse_iterator rend() 
		{
			return reverse_iterator(_head);
		}

?我們先將反向迭代器重命名為reverse_list,然后讓rbegin()變成鏈表的尾節(jié)點(diǎn)，rend()還是鏈表的哨兵位頭結(jié)點(diǎn)不變，下面我們來驗(yàn)證一下看是否正確：

?通過驗(yàn)證我們發(fā)現(xiàn)確實(shí)可以實(shí)現(xiàn)反向迭代，那么現(xiàn)在問題來了，我們剛開始說了反向迭代器是一個(gè)適配器，如果我們用這個(gè)鏈表的反向迭代器去實(shí)現(xiàn)vector的反向迭代器可以實(shí)現(xiàn)嗎？答案肯定是不行，因?yàn)関ector又不是節(jié)點(diǎn)怎么返回節(jié)點(diǎn)的前一個(gè)后一個(gè)呢？所以我們實(shí)現(xiàn)的這個(gè)迭代器只能list使用，下面我們看看大佬是如何實(shí)現(xiàn)反向迭代器的：

我們?nèi)Τ鰜淼腸urrent是什么呢？current是一個(gè)正向迭代器

?那么為什么operator*變成了--迭代器然后解引用呢？再往下看：

?反向迭代器的++是正向迭代器的--，反向迭代器的--是正向迭代器的++。

我們發(fā)現(xiàn)rbegin()是迭代器的end()，rend()是迭代器的begin(),下面我們畫個(gè)圖來驗(yàn)證一下：

?這個(gè)時(shí)候我們終于理解了為什么operator*是--iterator的解引用，因?yàn)閞begin()是指向哨兵位的頭結(jié)點(diǎn)的，這個(gè)時(shí)候是不能對(duì)頭結(jié)點(diǎn)解引用的，所以我們應(yīng)該對(duì)頭結(jié)點(diǎn)的prev也就是最后一個(gè)節(jié)點(diǎn)解引用，這樣一來就能依次從后往前訪問到鏈表的每個(gè)元素，當(dāng)rbegin()==rend()的時(shí)候?qū)⑺性乇闅v完成。

下面我們就來實(shí)現(xiàn)一下：

namespace sxy
{
	template<class iterator,class Ref,class Ptr>
	struct ReverseIterator
	{
		typedef ReverseIterator<iterator, Ref, Ptr> self;
		iterator _cur;
		ReverseIterator(iterator it)
			:_cur(it)
		{

		}
	};
}

?首先我們創(chuàng)建一個(gè)iterator.h文件，然后寫一個(gè)模板這個(gè)模板第一個(gè)參數(shù)是任意類型的迭代器，第二個(gè)參數(shù)是迭代器中解引用的返回值Ref，第三個(gè)參數(shù)是在重載->符號(hào)的返回值Ptr。然后我們用正向迭代器創(chuàng)建一個(gè)變量_cur,構(gòu)造函數(shù)初始化的時(shí)候直接用正向迭代器初始化_cur.

然后我們先實(shí)現(xiàn)++,--:

        self& operator++()
		{
			--_cur;
			return *this;
		}
		self operator++(int)
		{
			iterator tmp = _cur;
			--_cur;
			return tmp;
		}

?對(duì)于前置++和后置++的區(qū)別在于后置++要返回--前的那個(gè)值，所以我們直接用拷貝構(gòu)造一個(gè)tmp，這里我們是沒有實(shí)現(xiàn)迭代器的拷貝構(gòu)造的，那么使用默認(rèn)的拷貝構(gòu)造可以嗎？答案是可以，因?yàn)槲覀円木褪菧\拷貝，我們就是要tmp指向cur位置，如下圖：

?我們?cè)倏匆幌律羁截愖兂闪耸裁矗?/p>

通過上圖我們應(yīng)該理解了為什么我們直接使用默認(rèn)的構(gòu)造函數(shù)就能解決問題。

        self& operator--()
		{
			++_cur;
			return *this;
		}
		self operator--(int)
		{
			iterator tmp = _cur;
			++_cur;
			return tmp;
		}

?對(duì)于--的實(shí)現(xiàn)是和++一樣的，只不過--變成了正向迭代器的++。

下面我們?cè)賹?shí)現(xiàn)一下迭代器要使用的==和!=符號(hào)：

        bool operator!=(const self& s)
		{
			return _cur != s._cur;
		}
		bool operator==(const self& s)
		{
			return _cur == s._cur;
		}

?對(duì)于反向迭代器的判斷我們只需要判斷兩個(gè)反向迭代器的節(jié)點(diǎn)是否相等即可。

下面我們實(shí)現(xiàn)反向迭代器的解引用：

        Ref operator*()
		{
			iterator tmp = _cur;
			--tmp;
			return *tmp;
		}

?對(duì)于反向迭代器的解引用我們說過，由于rbegin（）是在end(）的位置所以我們是不能直接解引用的，正確的操作是解引用此位置的前一個(gè)節(jié)點(diǎn)（為什么是前一個(gè)呢？因?yàn)槭欠聪虻鳎。?。所以我們用_cur拷貝構(gòu)造一個(gè)tmp，然后--tmp就是前一個(gè)節(jié)點(diǎn)，然后再返回解引用的值即可。返回值的實(shí)現(xiàn)與正向迭代器一樣具體可以去看我的list模擬實(shí)現(xiàn)那篇文章看看為什么要多一個(gè)模板參數(shù)Ref做返回值。

下面我們?cè)趌ist中定義一下反向迭代器：

?首先包含一下頭文件，然后typedef一下反向迭代器和反向迭代器的const版本：

typedef ReverseIterator<iterator,T&,T*> reverse_iterator;
typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;

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

?接下來我們看看是否能成功反向輸出呢？

看來我們是成功了，那么回到我們一開始的問題，可以用這個(gè)迭代器去適配vector的反向迭代器嗎？我們畫個(gè)圖看看：

?當(dāng)反向迭代器++的時(shí)候是正向迭代器的--，然后從vector的尾部開始向頭部移動(dòng)。同時(shí)我們發(fā)現(xiàn)，operator*的實(shí)現(xiàn)也是滿足的，因?yàn)閞begin()的位置是vector存放最后一個(gè)有效數(shù)據(jù)的位置的下一個(gè)，這個(gè)位置是沒有數(shù)據(jù)的，只有讓迭代器--一下在解引用才是正確的值，由于是每次位置的前一個(gè)所以當(dāng)rbegin()==rend()的時(shí)候?qū)⒎聪虮闅v完所有數(shù)據(jù)，下面我們就演示一下vector的反向迭代器：

vector的反向迭代器

首先在vector.h的頭文件中包含iterator.h的頭文件：

然后在vector中typedef一下反向迭代器：

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<iterator, const T&, const T*> const_reverse_iterator;
        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());
		}

?然后我們運(yùn)行一下程序看是否能成功：

?答案我們也看到了確實(shí)可以，這也就證明了我們一開始所說的大佬思想。當(dāng)我們想實(shí)現(xiàn)list的反向迭代器的時(shí)候只實(shí)現(xiàn)出針對(duì)list的反向迭代器，而大佬卻用一個(gè)反向迭代器適配其他的反向迭代器。

?

總結(jié)

對(duì)于迭代器的適配器最重要的是實(shí)現(xiàn)的思想，比如我們?nèi)绾慰刂茖?duì)迭代器進(jìn)行解引用，++--等等，想要有如同大佬一般的思想我們必須多看優(yōu)秀的代碼，只有去看別人寫的優(yōu)秀的代碼我們才能進(jìn)步。

?

?

到了這里，關(guān)于【c++】:反向迭代器適配器：每天學(xué)一點(diǎn)點(diǎn)優(yōu)秀的思想的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！