devbox
羊村懒王
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

反向迭代器

作者：羊村懒王 | 2024-04-09 06:02:22

赞

踩

反向迭代器
反向迭代器
反向迭代器涉及适配器模式，所以选择接在栈和队列后面。
接list部分
list反向迭代器部分的源码：
按照正常思路，反向迭代器应该是写一个反向迭代器的类，其中对++的重载写成_node = _node->prev;使得反向迭代器的++就是向前走，但是这样只能针对list起效果。虽然其他的迭代器也可以按各自的逻辑写，但是存在更优的方案：使用适配器模式。
正向迭代器和反向迭代器除了++/--方向相反，其他的没有区别。那么可以通过适配器模式，对正向迭代器进行适配生成反向迭代器，这样可以一劳永逸的解决所有容器的反向迭代器。
reverse_iterator编写在stl_iterator.h中，在删除一些看不懂的代码后，得到的reverse_iterator实现基本逻辑，然后在stl_list.h中找到反向迭代器的实现方式：
由图可见，反向迭代器的成员变量是一个正向迭代器，对反向迭代器解引用得到的是正向迭代器的前一个位置，正向迭代器的end()返回的是末尾元素的下一个位置，而反向迭代器的rbegin()返回的是末尾的元素。之前说的适配器模式指的就是这个，使用rbegin()函数实际上使用的是end()，取得的是末尾元素的下一个位置（哨兵位头结点），但是对反向迭代器解引用应该得到末尾元素。所以反向迭代器的解引用重载使用方式不同于正向迭代器(所以需要重新编写)。如图所示：
rbegin()也可以指向6，但是stl源码没有采用这样的设计，而是用end()去构造rbegin()，用begin()去构造rend()。这叫对称设计。当使用反向迭代器时：
while(rit != rend()) //rit为rbegin()返回值
{
    cout << *rit << " ";
    rit++;
}
最开始*rit实际访问到的是6，++后指向6，实际访问到的是5，以此类推，当指向1时，访问完毕，rit和rend()相等。
下面的内容为自己实现的list，其中有迭代器，通过迭代器完成反向迭代器的编写 （蓝字部分为新添加的反向迭代器内容）
list.h中
#pragma once
#include<iostream>
#include<algorithm>
#include<assert.h>
using namespace std;
namespace bit
{
        template<class T>
        struct _list_node
        {
               _list_node(const T& x = T())
               {
                       _date = x;
                       _next = nullptr;
                       _prev = nullptr;
               }
               _list_node<T>* _next;
               _list_node<T>* _prev;
               T _date;
        };
        template<class T, class ref, class ptr>
        struct _list_iterator
        {
               typedef _list_node<T> Node;
               typedef  _list_iterator<T,ref,ptr> Self;
               Node* _node;
               _list_iterator(Node* it)
                       :_node(it)
               {}
               ref operator*()
               {
                       return _node->_date;
               }
               ptr operator->()
               {
                       return &(_node->_date);
               }
               bool operator==(const Self& pos)
               {
                       return _node == pos._node;
               }
               bool operator!=(const Self& pos)
               {
                       return _node != pos._node;
               }
               Self& operator++()
               {
                       _node = _node->_next;
                       return *this;
               }
               Self operator++(int)
               {
                       Self tmp = _node;
                       _node = _node->_next;
                       return tmp;
               }
               Self& operator--()
               {
                       _node = _node->_prev;
                       return *this;
               }
               Self operator--(int)
               {
                       Self tmp = _node;
                       _node = _node->_prev;
                       return tmp;
               }
        };
        template<class T>
        class list
        {
               typedef _list_node<T> Node;
        public:
               typedef _list_iterator<T,T&,T*> iterator;
               typedef _list_iterator<T, const T&, const T*> const_iterator;
              //反向迭代器的适配支持
               typedef Reverse_iterator < iterator , T &, T *> reverse_iterator ;
               list()
               {
                       _head = new Node;
                       _head->_next = _head;
                       _head->_prev = _head;
               }
               void empty_init()
               {
                       _head = new Node;
                       _head->_next = _head;
                       _head->_prev = _head;
               }
               template <class InputIterator>
               list(InputIterator first, InputIterator last)
               {
                       empty_init();
                       while (first != last)
                       {
                              push_back(*first);
                              first++;
                       }
               }
               void swap(list<T>& it)
               {
                       std::swap(_head, it._head);
               }
               list(const list<T>& it)
               {
                       empty_init();
                       list<T> tmp(it.begin(), it.end());
                       swap(tmp);
               }
               list<T>& operator=(list<T> it)
               {
                       swap(it);
                       return *this;
               }
               ~list()
               {
                       clear();
                       delete _head;
                       _head = nullptr;
               }
               void clear()
               {
                       iterator it = begin();
                       while (it != end())
                       {
                              it = erase(it);
                       }
               }
               void push_back(const T& x)
               {
                       insert(end(), x);
               }
               void push_front(const T& x)
               {
                       insert(begin(), x);
               }
               void pop_back()
               {
                       erase(--end());
               }
               void pop_front()
               {
                       erase(begin());
               }
               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 (end());
               }
                reverse_iterator rend()
               {
                   return reverse_iterator (begin());
               }
               iterator insert(iterator pos, const T& val)
               {
                       Node* newnode = new Node(val);
                       Node* cur = pos._node;
                       cur->_prev->_next = newnode;
                       newnode->_prev = cur->_prev;
                       newnode->_next = cur;
                       cur->_prev = newnode;
                       return iterator(newnode);
               }
               iterator erase(iterator pos)
               {
                       assert(pos != end());
                       Node* cur = pos._node;
                       Node* prev = cur->_prev;
                       Node* next = cur->_next;
                       prev->_next = next;
                       next->_prev = prev;
                       delete cur;
                       return iterator(next);
               }
        private:
               Node* _head;
        };
}
创建一个新头文件：reverse_iterator.h
reverse_iterator.h中 //整体还相当粗糙
#pragma once
#include"list.h"
namespace bit
{
         template < class iterator , class ref , class ptr >//库中采用了一种复杂的机制规避掉了ref和ptr
         struct Reverse_iterator
        {
                typedef Reverse_iterator self ;
               Reverse_iterator( iterator x )
                       :_it(x)
               {}
                self & operator++ ()//这里还缺少后缀++，--，const修饰的++，--
               {
                       _it--;
                        return * this ;
               }
                self & operator-- ()
               {
                       _it++;
                        return * this ;
               }
                bool operator!= ( Reverse_iterator x )
               {
                        return _it != x ._it;
               }
                ref operator* ()
               {
                        iterator it = _it;
                        return *(--it);//考虑到保持对称设计，所以访问的位置，是迭代器指向的前一个位置
               }
                ptr operator-> ()
               {
                        return &( operator* ());
               }
                iterator _it;
        };
}
test.cpp中
#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
#include<list>
void test_list1()
{
        bit::list<int> l;
        l.push_back(1);
        l.push_back(2);
        l.push_back(3);
        l.push_back(4);
        l.push_back(5);
        bit::list<int>::iterator it = l.begin();
        while (it != l.end())
        {
               cout << *it << " ";
               ++it;
        }
        bit:: list < int >:: reverse_iterator it = l.rend();
        while (it != l.rbegin())//如果在标准库下，将l.rend()和l.rbegin()互换，且将++it改为--it会报错
        {
            cout << * it << " " ;
            ++ it;
        }
        //提问：既然reverse_iterator采用适配器模式，那么可不可以在这里将list<int>替换成自己写的vector<int>？
        //答案是不能，因为没有对vector进行适配支持，即list.h中所有蓝色字体
}
int main()
{
        test_list1();
        return 0;
}
stl_list.h中存在如下内容
库中list的反向迭代器的实现有两种方式，第一个是新版本的，第二个是旧版本的。新版本和就版本的区别在于新版本只传了迭代器，而旧版本还传了T和T&等，这涉及迭代器萃取，是一种特化。
下面的内容仅做了解。实际当中没什么用途（不是特化没什么用途）
如果这里不写模板参数ref和ptr，会怎么样？
你会发现这两个函数重载的返回值不知道怎么写了。那么标准库中是如何写的呢？
一个标准的迭代器要包含四种类型，即下图中的四种。只有符合这个规范，才能使用迭代器萃取。
具体来说就是需要pointer和reference。
同样可以在stl_list.h中找到
删除Reverse_iterator模板中的ref，ptr，在_list_iterator添加上typedef ptr pointer; typedef ref reference;后就能解决两个重载函数的返回值问题
iterator::reference operator*()
iterator::pointer operator->()
但是这样还是会报错，因为编译器根本不认识iterator::reference和iterator::pointer
原因在于Reverse_iterator的模板参数iterator也是模板，如果编译器允许去iterator中去找，找到的其实就是iterator中的T&和T*，但是iterator实例化后，T得到具体类型(假设是int)，但是Reverse_iterator中的T并没有被实例化(对反向迭代器的适配支持中只传了iterator)，还是虚拟的T类型。所以编译器直接报错。
编译器在类模板没有实例化之前，不允许去类模板中找内嵌类型（就是typedef过的虚拟类型类型）。找到了也是虚拟类型。后期无法处理。要解决这个问题需要加上关键字typename（在模板中提到过，模板可以用class也可以用typename）
typename iterator::reference operator*()
typename iterator::pointer operator->()
typename在这里的价值就是告诉编译器后面这一串是类型，等到iterator实例化后，再去iterator中找它的内嵌类型。
之后list就能完成迭代器，反向迭代器的功能。
stl_iterator.h中的反向迭代器
又重新typedef了一次，这样在写operator*()的返回值时直接用reference就行。(traits直译是特点，品质，在编程中意译为萃取)
如果Reserve_iterator只传iterator，vector是无法正常运行的。
因为vector的迭代器是指针，是原生类型，不是自定义类型，无法从迭代器中取pointer和reference(iterator会正常typedef ptr和ref，但是Reserve_iterator无法从指针中取pointer和reference)
解决方案有两个：
1.封装一个成员变量为指针的自定义类型迭代器
2.使用萃取，如上图不是直接使用Iterator，而是将Iterator给iterator_traits，iterator_traits又针对Iterator为T*时进行特殊处理（即特化）。Iterator为自定义类型时不做处理。
关于typename
先写一段测试程序(vs2013测不出来，要在vs2019或者g++上测)
template<class T>
void print_list(const list<T>& it)
{
    list<T>::const_iterator cit = it.begin(); //会在这里报错
    while(cit != it.end())
    {
        cout << *cit << " ";
        cit++;
    }
    cout << endl;
}
int main()
{
    list<int> it;
    it.push(1);
    it.push(2);
    it.push(3);
    it.push(4);
    print_list(it);
    list<string> itstr;
    itstr.push("aaa");
    itstr.push("bbb");
    itstr.push("ccc");
    itstr.push("ddd");
    print_list(itstr);
    return 0;
}
原因在于list<T>是一个类模板，在对print_list模板进行编译时，list<T>还是类模板，没有实例化。编译器不允许到一个未实例化的类模板中找内嵌类型。
要加上typename，即typename list<T>::const_iterator cit = it.begin();
而类模板类型确定的时候就可以不用加typename，不是类模板不能找内嵌类型，而是类模板包含虚拟类型时不能找内嵌类型。
typename list<T>::const_iterator还可以被替换为auto，编译器知道是类型，会在it.begin()返回时自动推导(这个和auto的机制有关，目前知道可以替代就行了)。
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/390756
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号