C++初阶—完善适配器（反向迭代器）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C++初阶—完善适配器（反向迭代器）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

C++初阶—完善适配器（反向迭代器）

0. 前言

1、反向迭代器定义

2、反向迭代器需要实现的相关函数

3、反向迭代器分析

4、针对vector物理空间结构分析

5、针对list物理空间结构分析

6、反向迭代器适配器的实现及测试

7、有关迭代器的功能分类

0. 前言

本篇文章主要根据前面所实现的STL中支持迭代器的容器进行完善，使用了适配器原则，传递正向迭代器数据类型，从而实现反向迭代器。

STL六大组件中：包括容器（vector、list、queue、stack、string...）、配接器（容器适配器：queue、stack、deque和priority_queue）、迭代器（普通迭代器、const迭代器、反向迭代器、const反向迭代器）、仿函数（less、greater...）、算法（find、swap、sort、merge、reverse...）、空间配置器（allocator）！！！

1、反向迭代器定义

反向迭代器从容器的尾元素向首元素反向移动的迭代器

对于反向迭代器，其中递增递减的含义完全颠倒

递增时，会移动到前一个元素

递减时，会移动到后一个元素

解引用时，需要获取到所属位置的前一个元素

->操作时，获取前一个位置数据的地址

2、反向迭代器需要实现的相关函数

反向迭代器操作：

rbegin()——指向容器最后一个元素的下一个位置

rend()——指向首元素的位置

crbegin()——const反向迭代器

crend()——const反向迭代器

反向迭代器内部操作：

前置++、后置++、前置--、后置--、关系运算符!=、解引用*、操作符->等

3、反向迭代器分析

在实现list容器时，由于物理空间不连续，在实现其正向迭代器时，单独封装了一个类，而string、vector存储数据的物理空间是连续的，底层操作的实际时指向数据位置的指针。

因此，在实现反向迭代器时，难道我们要针对每个容器，在实现一个类吗？

结合上节课容器适配器的学习，我们可以根据C++类模板，传递正向迭代器，并设置多个模板参数，用于根据所传模板参数的不同，实体为不同的类，从而实现const迭代器！！！通过传递模板参数正向迭代器，我们只需要定义一个迭代器对象，复用正向迭代器的操作即可！！！对于sting、vector会自动调用其迭代器普通操作，对于list重载操作符，自动调用其重载的操作符！！！

以上操作极大提高了反向迭代器的复用性、适配性，也可称为针对迭代器的反向迭代器适配器

4、针对vector物理空间结构分析

		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()++便调用正向迭代器所重载或默认的--，当rbegin() == rend()时，遍历结束！！！

        而由于rbegin()每次指向所需数据位置的下一个位置，因此重载反向迭代器*操作时，需要使用中间变量，中间变量拷贝构造和--操作,在使用*操作，便获取到所应遍历数据位置的数据！同时也不会改变this所指向的位置！！！



        在使用后置++，--操作时，需要记录前一次数据的迭代器，返回所记录的迭代器，在进行正向迭代器的反向操作

5、针对list物理空间结构分析

C++初阶—完善适配器（反向迭代器）

根据上述分析，结合list再次进行分析，rbegin()指向头节点，rend()指向头节点的下一个位置

    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()++即相当于end()--，通过在list正向迭代器重写的类，此时rbegin()便会反向便利、

解引用，获取到当前节点的前一个结点的数据，直到遍历到rend()结束！！！而对rend()解引用，会获取到头结点的数据，因此反向迭代器适配器同时适用所有容器！！！

6、反向迭代器适配器的实现及测试

反向迭代器的实现：

namespace Thb {
	//复用、适配，迭代器适配器
	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、有关迭代器的功能分类

由上实现的反向迭代器针对list、vector、sting都可实现，底层是对普通迭代器的封装，而上实现的支持++，--的迭代器又称为双向迭代器，其底层的普通迭代器需要支持++、--操作！！！

而vector、string迭代器底层是原生指针，除了支持正反遍历之外，还支持算数+、-操作，因此，这类迭代器又称为随机访问迭代器！！！

对于其他容器如forward_list（单链表）、unordered_map、unordered_set，由于其性质，只能支持向后遍历，不能进行反向遍历，因此，这类迭代器称为单项迭代器！！！

文章来源地址https://www.toymoban.com/news/detail-493689.html

平时在使用算法库所提供的sort、reverse等查阅文档时，可以看到其模板迭代器命名风格，名称暗示你，sort的容器的迭代器是随机迭代器

通过查看文档，可以看到针对不同容器支持的迭代器命名风格，其中箭头表示了继承关系！