目錄

0. 前言

1、反向迭代器定義

2、反向迭代器需要實現(xiàn)的相關(guān)函數(shù)

3、反向迭代器分析

4、針對vector物理空間結(jié)構(gòu)分析

5、針對list物理空間結(jié)構(gòu)分析

6、反向迭代器適配器的實現(xiàn)及測試

7、有關(guān)迭代器的功能分類

0. 前言

本篇文章主要根據(jù)前面所實現(xiàn)的STL中支持迭代器的容器進行完善，使用了適配器原則，傳遞正向迭代器數(shù)據(jù)類型，從而實現(xiàn)反向迭代器。

STL六大組件中：包括容器（vector、list、queue、stack、string...）、配接器（容器適配器：queue、stack、deque和priority_queue）、迭代器（普通迭代器、const迭代器、反向迭代器、const反向迭代器）、仿函數(shù)（less、greater...）、算法（find、swap、sort、merge、reverse...）、空間配置器（allocator）?。。?/p>

1、反向迭代器定義

1. 反向迭代器從容器的尾元素向首元素反向移動的迭代器
2. 對于反向迭代器，其中遞增遞減的含義完全顛倒
3. 遞增時，會移動到前一個元素
4. 遞減時，會移動到后一個元素
5. 解引用時，需要獲取到所屬位置的前一個元素
6. ->操作時，獲取前一個位置數(shù)據(jù)的地址

2、反向迭代器需要實現(xiàn)的相關(guān)函數(shù)

反向迭代器操作：

• rbegin()——指向容器最后一個元素的下一個位置
• rend()——指向首元素的位置
• crbegin()——const反向迭代器
• crend()——const反向迭代器

反向迭代器內(nèi)部操作：

前置++、后置++、前置--、后置--、關(guān)系運算符!=、解引用*、操作符->等

3、反向迭代器分析

????????在實現(xiàn)list容器時，由于物理空間不連續(xù)，在實現(xiàn)其正向迭代器時，單獨封裝了一個類，而string、vector存儲數(shù)據(jù)的物理空間是連續(xù)的，底層操作的實際時指向數(shù)據(jù)位置的指針。

? ? ? ? 因此，在實現(xiàn)反向迭代器時，難道我們要針對每個容器，在實現(xiàn)一個類嗎？

? ? ? ? 結(jié)合上節(jié)課容器適配器的學(xué)習(xí)，我們可以根據(jù)C++類模板，傳遞正向迭代器，并設(shè)置多個模板參數(shù)，用于根據(jù)所傳模板參數(shù)的不同，實體為不同的類，從而實現(xiàn)const迭代器！??！通過傳遞模板參數(shù)正向迭代器，我們只需要定義一個迭代器對象，復(fù)用正向迭代器的操作即可?。?！對于sting、vector會自動調(diào)用其迭代器普通操作，對于list重載操作符，自動調(diào)用其重載的操作符?。?！

以上操作極大提高了反向迭代器的復(fù)用性、適配性，也可稱為針對迭代器的反向迭代器適配器

4、針對vector物理空間結(jié)構(gòu)分析

		typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
		typedef __reverse_iterator<const_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());
		}

????????通過上述代碼分析，可知rbegin()指向end()位置，rend指向begin()位置，因此遍歷時，rebgin()++便調(diào)用正向迭代器所重載或默認的--，當(dāng)rbegin() == rend()時，遍歷結(jié)束?。。?/p>

????????而由于rbegin()每次指向所需數(shù)據(jù)位置的下一個位置，因此重載反向迭代器*操作時，需要使用中間變量，中間變量拷貝構(gòu)造和--操作,在使用*操作，便獲取到所應(yīng)遍歷數(shù)據(jù)位置的數(shù)據(jù)！同時也不會改變this所指向的位置！??！

? ? ? ??

????????在使用后置++，--操作時，需要記錄前一次數(shù)據(jù)的迭代器，返回所記錄的迭代器，在進行正向迭代器的反向操作

5、針對list物理空間結(jié)構(gòu)分析

?根據(jù)上述分析，結(jié)合list再次進行分析，rbegin()指向頭節(jié)點，rend()指向頭節(jié)點的下一個位置

????????

    template<class T, class Ref, class Ptr>
    struct __list_iterator {
            typedef __list_node<T> list_node;
            typedef __list_iterator<T, Ref, Ptr> iterator;

            list_node* _node;

            __list_iterator(list_node* node)
                :_node(node)
            {}
            bool operator!=(const iterator& it) const {
                return _node != it._node;
            }
            bool operator==(const iterator& it) const {
                return _node == it._node;
            }

            iterator& operator++() {
                _node = _node->_next;
                return *this;
            }
            iterator operator++(int) {
                iterator temp(*this);
                _node = _node->_next;
                return temp;
            }

            iterator& operator--() {
                _node = _node->_prev;
                return *this;
            }
            iterator operator--(int) {
                iterator temp(*this);
                _node = _node->_prev;
                return temp;
            }

            //T* operator->() {
            Ptr operator->() const {
                return &(operator*());
            }
            //T& operator*() const {
            Ref operator*() const {
                return _node->_data;
            }

            //T* operator->() {
            Ptr operator->() {
                return &(operator*());
            }
            //T& operator*() const {
            Ref operator*() {
                return _node->_data;
            }
     };

????????遍歷時，rbegin()++即相當(dāng)于end()--，通過在list正向迭代器重寫的類，此時rbegin()便會反向便利、

????????解引用，獲取到當(dāng)前節(jié)點的前一個結(jié)點的數(shù)據(jù)，直到遍歷到rend()結(jié)束！?。《鴮end()解引用，會獲取到頭結(jié)點的數(shù)據(jù)，因此反向迭代器適配器同時適用所有容器！?。?/p>

6、反向迭代器適配器的實現(xiàn)及測試

反向迭代器的實現(xiàn)：

namespace Thb {
	//復(fù)用、適配，迭代器適配器
	template<class Iterator, class Ref, class Ptr>
	struct __reverse_iterator {
		Iterator _cur;

		typedef __reverse_iterator<Iterator,Ref,Ptr> RIterator;
		__reverse_iterator(Iterator it) :_cur(it) {
		}

		RIterator& operator++() {
			_cur--;
			return *this;
		}
		RIterator& operator--() {
			_cur++;
			return *this;
		}
		RIterator operator++(int) {
			RIterator temp = *this;
			--_cur;
			return temp;
		}
		RIterator operator--(int) {
			RIterator temp = *this;
			++_cur;
			return temp;
		}

		Ref operator*() {
			Iterator temp = _cur;
			--temp;
			return *temp;
		}
		Ref operator*() const {
			Iterator temp = _cur;
			--temp;
			return *temp;
		}

		Ptr operator->() {
			return &(operator*());
			//return _cur.operator->();
		}
		Ptr operator->() const {
			return &(operator*());
			//return _cur.operator->();
		}

		bool operator!=(const RIterator& it) {
			return _cur != it._cur;
		}
	};
}

反向迭代器的測試：

#include"list.h"
#include"vector.h"
#include"stack&&queue.h"
namespace std {
	void testListReverse() {
		int arr[] = { 3,2,7,6,0,4,1,9,8,5 };
		Thb::list<int> ls(arr, arr + sizeof(arr) / sizeof(arr[0]));
		Thb::list<int>::iterator it = ls.begin();
		while (it != ls.end()) {
			cout << *it << " ";
			++it;
		}
		cout << endl;

		auto rit = ls.rbegin();
		while (rit != ls.rend()) {
			*rit += 1;
			cout << *rit << " ";
			++rit;
		}
		cout << endl;

		const Thb::list<int> ls1 = ls;
		auto crit = ls1.rbegin();
		while (crit != ls1.rend()) {
			cout << *crit << " ";
			++crit;
		}
		cout << endl;
	}
	void testVectorReverse() {
		int arr[] = { 3,2,7,6,0,4,1,9,8,5 };
		Thb::vector<int> ls(arr, arr + sizeof(arr) / sizeof(arr[0]));
		Thb::vector<int>::iterator it = ls.begin();
		while (it != ls.end()) {
			cout << *it << " ";
			++it;
		}
		cout << endl;

		auto rit = ls.rbegin();
		while (rit != ls.rend()) {
			cout << *rit << " ";
				rit++;
		}
		cout << endl;

		const Thb::vector<int> ls1 = ls;
		auto crit = ls1.rbegin();
		while (crit != ls1.rend()) {
			cout << *crit << " ";
			crit++;
		}
		cout << endl;
	}
	void testConst() {
		int arr[] = { 3,2,7,6,0,4,1,9,8,5 };
		Thb::vector<int> ls(arr, arr + sizeof(arr) / sizeof(arr[0]));

		const Thb::stack<int, Thb::vector<int>> st(ls);
		cout << st.top() << endl;
	}
}

int main() {
	try {
		std::testListReverse();
		std::cout << std::endl << std::endl << std::endl;
		std::testVectorReverse();
		std::cout << std::endl << std::endl << std::endl;
		std::testConst();
	}
	catch (const std::exception& e) {
		std::cout << e.what() << std::endl;
	}
	return 0;

7、有關(guān)迭代器的功能分類

由上實現(xiàn)的反向迭代器針對list、vector、sting都可實現(xiàn)，底層是對普通迭代器的封裝，而上實現(xiàn)的支持++，--的迭代器又稱為雙向迭代器，其底層的普通迭代器需要支持++、--操作！?。?/p>

而vector、string迭代器底層是原生指針，除了支持正反遍歷之外，還支持算數(shù)+、-操作，因此，這類迭代器又稱為隨機訪問迭代器！??！

對于其他容器如forward_list（單鏈表）、unordered_map、unordered_set，由于其性質(zhì)，只能支持向后遍歷，不能進行反向遍歷，因此，這類迭代器稱為單項迭代器?。。?/p>

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

平時在使用算法庫所提供的sort、reverse等查閱文檔時，可以看到其模板迭代器命名風(fēng)格，名稱暗示你，sort的容器的迭代器是隨機迭代器

?通過查看文檔，可以看到針對不同容器支持的迭代器命名風(fēng)格，其中箭頭表示了繼承關(guān)系！

?

到了這里，關(guān)于C++初階—完善適配器（反向迭代器）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！