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

C++【STL】【反向迭代器】_c++map反向迭代器

作者：小丑西瓜9 | 2024-04-09 05:56:55

赞

踩

c++map反向迭代器

目录

一、反向迭代器的简介

1.什么是反向迭代器

2.方向迭代器的实现

二、反向迭代器的相关问题

1.为什么在operator*中需要--迭代器

2.适配list的反向迭代器

3.适配vector的反向迭代器

4.迭代器的分类

5.迭代器萃取浅述

一、反向迭代器的简介

1.什么是反向迭代器

12345

如果是正向迭代器就是从1->2->3->4->5，也就是正向迭代器的++是向右边走

但是我们的反向迭代器的++是向左边走，也就是5->4->3->2->1

  1. void test_list1()
  2. {
  3.     list<int> lt;
  4.     lt.push_back(1);
  5.     lt.push_back(2);
  6.     lt.push_back(3);
  7.     lt.push_back(4);
  8.     lt.push_back(5);
  9.  
  10.     //正向迭代器
  11.     list<int>::iterator it = lt.begin();
  12.     while (it != lt.end())
  13.     {
  14.         cout << *it << " ";
  15.         ++it;
  16.     }
  17.     cout << endl;
  18.  
  19.     //反向迭代器
  20.     list<int>::reverse_iterator rit = lt.rbegin();
  21.     while (rit != lt.rend())
  22.     {
  23.         cout << *rit << " ";
  24.         ++rit;
  25.     }
  26.     cout << endl;
  27. }

2.方向迭代器的实现

普通思维：拷贝一份正向迭代器，修改一下，搞出我们的方向迭代器

大佬的思维：list是可以通过将遍历p.next变成p.prev，从而在++的时候实现反向迭代，

1.但是vector怎么办呢？因为vector的迭代器底层是原生指针，++就只会往后走。

vector的反向迭代器可以这样生成一个类，直接将++的方式重载成--，从而实现反向迭代

  1. struct_vector_iterator
  2. {
  3.     T *_ptr;
  4.     operator++()
  5.     {
  6.         --_ptr;
  7.     }
  8. }

2.采用复用（正向迭代器）的方式。

从我们下面的STL源码中可以看到我们的STL其实是采用复用正向迭代器的方式的 

一下是我们STL中关于反向迭代器的源码 

  1. template <class Iterator>
  2. class reverse_iterator 
  3. {
  4. protected:
  5.   Iterator current;
  6. public:
  7.   typedef typename iterator_traits<Iterator>::iterator_category
  8.           iterator_category;
  9.   typedef typename iterator_traits<Iterator>::value_type
  10.           value_type;
  11.   typedef typename iterator_traits<Iterator>::difference_type
  12.           difference_type;
  13.   typedef typename iterator_traits<Iterator>::pointer
  14.           pointer;
  15.   typedef typename iterator_traits<Iterator>::reference
  16.           reference;
  17.  
  18.   typedef Iterator iterator_type;
  19.   typedef reverse_iterator<Iterator> self;
  20.  
  21. public:
  22.   reverse_iterator() {}
  23.   explicit reverse_iterator(iterator_type x) : current(x) {}
  24.  
  25.   reverse_iterator(const self& x) : current(x.current) {}
  26. #ifdef __STL_MEMBER_TEMPLATES
  27.   template <class Iter>
  28.   reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}
  29. #endif /* __STL_MEMBER_TEMPLATES */
  30.     
  31.   iterator_type base() const { return current; }
  32.   reference operator*() const {
  33.     Iterator tmp = current;
  34.     return *--tmp;
  35.   }
  36. #ifndef __SGI_STL_NO_ARROW_OPERATOR
  37.   pointer operator->() const { return &(operator*()); }
  38. #endif /* __SGI_STL_NO_ARROW_OPERATOR */
  39.  
  40.   self& operator++() {
  41.     --current;
  42.     return *this;
  43.   }
  44.   self operator++(int) {
  45.     self tmp = *this;
  46.     --current;
  47.     return tmp;
  48.   }
  49.   self& operator--() {
  50.     ++current;
  51.     return *this;
  52.   }
  53.   self operator--(int) {
  54.     self tmp = *this;
  55.     ++current;
  56.     return tmp;
  57.   }
  58.  
  59.   self operator+(difference_type n) const {
  60.     return self(current - n);
  61.   }
  62.   self& operator+=(difference_type n) {
  63.     current -= n;
  64.     return *this;
  65.   }
  66.   self operator-(difference_type n) const {
  67.     return self(current + n);
  68.   }
  69.   self& operator-=(difference_type n) {
  70.     current += n;
  71.     return *this;
  72.   }
  73.   reference operator[](difference_type n) const { return *(*this + n); }  
  74. };

二、反向迭代器的相关问题

1.为什么在operator*中需要--迭代器

这里我们观察到operator*，也就是解析迭代器所指向的数据，竟然需要先--迭代器，这是为什么呢？

我们的STL源码中的迭代器的是这样定义的

  1. iterator begin() {return (link_type)(*node).next);}
  2. iterator end(){ return node;}

 

这样就设计了一个对称的结构，正向迭代器的开始就是反向迭代器的结束，反向迭代器的开始就是正向迭代器的结束 

  1. reverse_iterator rbegin(){return reverse_iterator(end());}
  2. reverse_iterator rend() {return reverse_iterator(begin());}

所以说我们的迭代器指针指向1前面的那个头结点的时候，将current的值赋给tmp,tmp--就到了5的位置然后将5的值返回，在5的位置的时候解引用得到的是4，在4位置解引用得到的是3，在3的位置解引用得到的是2，在2位置解引用，得到的是1，到了1，也就是我们rend()的位置也就结束了。

当然我们将rebegin()放在5的位置也是可以的，那样的话就不用--再解引用了，这两种方法都是可以的。

2.适配list的反向迭代器

这是定义在reverse_iterator中的代码

由于上面的1中已经介绍过为什么STL中国的源码采用先--在解引用的写法，所以我们下面的写法中，我们也是先--再引用。

  1. #pragma once
  2.  
  3. namespace zhuyuan
  4. {
  5.     // 复用，迭代器适配器
  6.     //Iterator是用来定义反向迭代器的模板的，
  7.     // Ref是用来里定义反向迭代器的数据类型，是const类型的就是const类型的迭代器，不是const类型的，就不是const类型的迭代器
  8.     // Ptr定义的是结构体指针的模板
  9.     template<class Iterator, class Ref, class Ptr>
  10.     struct __reverse_iterator
  11.     {
  12.         Iterator _cur;
  13.         typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;
  14.  
  15.         __reverse_iterator(Iterator it)
  16.                 :_cur(it)
  17.         {}
  18.  
  19.         //反向迭代器的++就是--，这里我们需要重载一下
  20.         RIterator operator++()
  21.         {
  22.             --_cur;
  23.             return *this;
  24.         }
  25.         //反向迭代器--就是++，这里我们需要重载一下
  26.         RIterator operator--()
  27.         {
  28.             ++_cur;
  29.             return *this;
  30.         }
  31.  
  32.         Ref operator*()
  33.         {
  34.             //return *_cur;
  35.             //解引用是不能够改变当前的数据的，所以我们用一个tmp对象来拷贝一下
  36.             auto tmp = _cur;
  37.             --tmp;
  38.             return *tmp;
  39.         }
  40.  
  41.         Ptr operator->()
  42.         {
  43.             //这是一个结构体指针，
  44.             //这两种写法是一样的
  45.             //return _cur.operator->();
  46.             return &(operator*());
  47.         }
  48.  
  49.         bool operator!=(const RIterator& it)
  50.         {
  51.             return _cur != it._cur;
  52.         }
  53.     };
  54. }

然后在我们的list.h中的list类中封装反向迭代器对象，然后再list.h引入我们上面的reverse_iterator.h文件

  1. //封装正向迭代器
  2.         typedef __list_iterator<T, T&, T*> iterator;
  3.         typedef __list_iterator<T, const T&, const T*> const_iterator;
  4.  
  5.         //封装反向迭代器
  6.         typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
  7.         typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
  1.         reverse_iterator rbegin()
  2.         {
  3.             return reverse_iterator(end());
  4.         }
  5.  
  6.         reverse_iterator rend()
  7.         {
  8.             return reverse_iterator(begin());
  9.         }

测试代码

  1.     void test_list1()
  2.     {
  3.         list<int> lt;
  4.         lt.push_back(1);
  5.         lt.push_back(2);
  6.         lt.push_back(3);
  7.         lt.push_back(4);
  8.         lt.push_back(5);
  9.  
  10.         list<int>::iterator it = lt.begin();
  11.         while (it != lt.end())
  12.         {
  13.             cout << *it << " ";
  14.             ++it;
  15.         }
  16.         cout << endl;
  17.  
  18.         list<int>::reverse_iterator rit = lt.rbegin();
  19.         while (rit != lt.rend())
  20.         {
  21.             cout << *rit << " ";
  22.             ++rit;
  23.         }
  24.         cout << endl;
  25.  
  26.         it = lt.begin();
  27.         while (it != lt.end())
  28.         {
  29.             *it *= 2;
  30.             ++it;
  31.         }
  32.         cout << endl;
  33.  
  34.         for (auto e : lt)
  35.         {
  36.             cout << e << " ";
  37.         }
  38.         cout << endl;
  39.     }

3.适配vector的反向迭代器

在我们的vector类中定义下面的方法

然后再定义引用#include "reverse_iterator.h"，也就是我们之前写的reverse_iterator.h文件

  1.         typedef T* iterator;
  2.         typedef const T* const_iterator;
  3.  
  4.         typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;
  5.         typedef __reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;
  6.  
  7.         reverse_iterator rbegin()
  8.         {
  9.             return reverse_iterator(end());
  10.         }
  11.  
  12.         reverse_iterator rend()
  13.         {
  14.             return reverse_iterator(begin());
  15.         }

测试代码

  1. void test_vector1()
  2.     {
  3.  
  4.         vector<int> v;
  5.         v.push_back(1);
  6.         v.push_back(2);
  7.         v.push_back(3);
  8.         v.push_back(4);
  9.         v.push_back(5);
  10.  
  11.  
  12.         vector<int>::iterator it = v.begin();
  13.         while (it != v.end())
  14.         {
  15.             cout << *it << " ";
  16.             ++it;
  17.         }
  18.         cout << endl;
  19.  
  20.  
  21.         vector<int>::reverse_iterator rit = v.rbegin();
  22.         while (rit != v.rend())
  23.         {
  24.             cout << *rit << " ";
  25.             ++rit;
  26.         }
  27.         cout << endl;
  28.  
  29.     }

 

也就是说我们的rbegin()指向end()的位置也就是最后一个元素的下一个位置，解引用的时候，先--也就是到5的位置然后返回5，然后在5的位置，解引用的时候先--，到4的位置再返回4，以此类推，然后在2的位置解引用先--到1的位置，然后返回1，然后在1的位置到了rend()结束。 

4.迭代器的分类

这里我们的vector和list都是可以用我们上面写的reverse_iterator.h文件的，也就是说我们其实是可以实现大量的复用的！！

我们的反向迭代器中只要是正向迭代器中可以实现的，我们反向迭代器都可以实现。

反向迭代器：迭代器适配器，可以适配生成支持++和--的容器的反向迭代器。

一般的容器都是支持++的，但是--并不是所有的容器都支持的

（forward_list(单链表,forward是单向的意思，bidrectional是双向的意思)，unodered_map(哈希表)和unordered_set）

迭代器从功能的角度分类：

forward_list：只支持++（forward_list，unordered_map，unordered_set）

bidrectional：支持++也支持--（list,map,set）

random_access_iterator：除了支持++也支持--还支持+和-（比方说从第三个位置+5直接到了第八个位置）（vector,deque）

我们注意到 cplusplus的官方网站中写模板函数的时候也是按照迭代器的功能分类的

（这里的名称暗示你sort的容器得是随机迭代器，reverse的名称暗示你，sort的容器得是双向迭代器（当然随机迭代器也支持双向迭代器，其实是继承关系））

 

5.迭代器萃取浅述

这是stl_list中的部分源码

  1. #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  2.   typedef reverse_iterator<const_iterator> const_reverse_iterator;
  3.   typedef reverse_iterator<iterator> reverse_iterator;
  4. #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  5.   typedef reverse_bidirectional_iterator<const_iterator, value_type,
  6.   const_reference, difference_type>
  7.   const_reverse_iterator;
  8.   typedef reverse_bidirectional_iterator<iterator, value_type, reference,
  9.   difference_type>
  10.   reverse_iterator; 
  11. #endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */

这是老版本中的定义，它将value_type和reference全部都传递过去

 也就是我们上面的自己写的

而在新的版本中，我们注意到它只将这里的迭代器传了过去

那按照我们的理解，那要是我们将自己写的代码中的ref和ptr去掉，那我们下面的两个函数就不知道应该返回什么类型了。

 这里就是用到了迭代器萃取。

萃取可以用来提高运算的效率。

适配器真正的特点就是实现了复用。也就是上层的封装，转换出我们想要的东西。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/390736
推荐阅读
相关标签

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

  

闽ICP备14008679号