【C++】反向迭代器

🕗 发布于 2025-01-15 05:39 c++ java 开发语言

反向迭代器

一.源码及框架分析
二.反向迭代器实现代码

一.源码及框架分析

SGI-STL30版本源代码，反向迭代器实现的核心源码在stl_iterator.h中，反向迭代器是一个适配器，各个容器中再适配出自己的反向迭代器。下面截出vector和list的的反向迭代器结构框架核心部分截取出来如下：

// stl_list.h
template <class T, class Alloc = alloc>
class list {
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_bidirectional_iterator<const_iterator, value_type,
const_reference, difference_type> const_reverse_iterator;
typedef reverse_bidirectional_iterator<iterator, value_type, reference,
difference_type> reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
iterator begin() { return (link_type)((*node).next); }
const_iterator begin() const { return (link_type)((*node).next); }
iterator end() { return node; }
const_iterator end() const { return node; }

reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
return
const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return
const_reverse_iterator(begin());
}
};

// stl_vector.h
template <class T, class Alloc = alloc>
class vector {
public:
typedef T value_type;
typedef value_type* iterator;

#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
typedef reverse_iterator<const_iterator> const_reverse_iterator;
typedef reverse_iterator<iterator> reverse_iterator;
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
typedef reverse_iterator<const_iterator, value_type, const_reference,
difference_type> const_reverse_iterator;
typedef reverse_iterator<iterator, value_type, reference, difference_type>
reverse_iterator;
#endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */
iterator begin() { return start; }
const_iterator begin() const { return start; }
iterator end() { return finish; }
const_iterator end() const { return finish; }

reverse_iterator rbegin() { return reverse_iterator(end()); }
const_reverse_iterator rbegin() const {
return
const_reverse_iterator(end());
}
reverse_iterator rend() { return reverse_iterator(begin()); }
const_reverse_iterator rend() const {
return
const_reverse_iterator(begin());
}
};

// stl_iterator.h
#ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
// This is the new version of reverse_iterator, as defined in the
// draft C++ standard. It relies on the iterator_traits template,
// which in turn relies on partial specialization. The class
// reverse_bidirectional_iterator is no longer part of the draft
// standard, but it is retained for backward compatibility.
template <class Iterator>
class reverse_iterator
{
protected:
Iterator current;
public:
typedef typename iterator_traits<Iterator>::iterator_category
iterator_category;
typedef typename iterator_traits<Iterator>::value_type
value_type;
typedef typename iterator_traits<Iterator>::difference_type
difference_type;
typedef typename iterator_traits<Iterator>::pointer
pointer;
typedef typename iterator_traits<Iterator>::reference
reference;
typedef Iterator iterator_type;
typedef reverse_iterator<Iterator> self;
public:
reverse_iterator() {}
explicit reverse_iterator(iterator_type x) : current(x) {}
reverse_iterator(const self& x) : current(x.current) {}
#ifdef __STL_MEMBER_TEMPLATES
template <class Iter>
reverse_iterator(const reverse_iterator<Iter>& x) : current(x.current) {}
#endif /* __STL_MEMBER_TEMPLATES */

iterator_type base() const { return current; }
reference operator*() const {
Iterator tmp = current;
return *--tmp;
}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
self operator+(difference_type n) const {
return self(current - n);
}
self& operator+=(difference_type n) {
current -= n;
return *this;
}
self operator-(difference_type n) const {
return self(current + n);
}
self& operator-=(difference_type n) {
current += n;
return *this;
}
reference operator[](difference_type n) const { return *(*this + n); }
};

template <class Iterator>
inline bool operator==(const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y) {
return x.base() == y.base();
}
template <class Iterator>
inline bool operator<(const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y) {
return y.base() < x.base();
}
template <class Iterator>
inline typename reverse_iterator<Iterator>::difference_type
operator-(const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y) {
return y.base() - x.base();
}
template <class Iterator>
inline reverse_iterator<Iterator>
operator+(reverse_iterator<Iterator>::difference_type n,
const reverse_iterator<Iterator>& x) {
return reverse_iterator<Iterator>(x.base() - n);
}
#else /* __STL_CLASS_PARTIAL_SPECIALIZATION */

// This is the old version of reverse_iterator, as found in the original
// HP STL. It does not use partial specialization.
template <class BidirectionalIterator, class T, class Reference = T&,
class Distance = ptrdiff_t>
class reverse_bidirectional_iterator {
typedef reverse_bidirectional_iterator<BidirectionalIterator, T, Reference,
Distance> self;
protected:
BidirectionalIterator current;
public:
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef Reference reference;
reverse_bidirectional_iterator() {}
explicit reverse_bidirectional_iterator(BidirectionalIterator x)
: current(x) {}
BidirectionalIterator base() const { return current; }
Reference operator*() const {
BidirectionalIterator tmp = current;
return *--tmp;
}
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
};

template <class RandomAccessIterator, class T, class Reference = T&,
class Distance = ptrdiff_t>
class reverse_iterator {
typedef reverse_iterator<RandomAccessIterator, T, Reference, Distance>
self;
protected:
RandomAccessIterator current;
public:
typedef random_access_iterator_tag iterator_category;
typedef T value_type;
typedef Distance difference_type;
typedef T* pointer;
typedef Reference reference;
reverse_iterator() {}
explicit reverse_iterator(RandomAccessIterator x) : current(x) {}
RandomAccessIterator base() const { return current; }
Reference operator*() const { return *(current - 1); }
#ifndef __SGI_STL_NO_ARROW_OPERATOR
pointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */
self& operator++() {
--current;
return *this;
}
self operator++(int) {
self tmp = *this;
--current;
return tmp;
}
self& operator--() {
++current;
return *this;
}
self operator--(int) {
self tmp = *this;
++current;
return tmp;
}
self operator+(Distance n) const {
return self(current - n);
}
self& operator+=(Distance n) {
current -= n;
return *this;
}
self operator-(Distance n) const {
return self(current + n);
}
self& operator-=(Distance n) {
current += n;
return *this;
}
Reference operator[](Distance n) const { return *(*this + n); }
};
#endif //__STL_CLASS_PARTIAL_SPECIALIZATION

源码中我们可以看到reverse_iterator实现了两个版本，通过 __STL_CLASS_PARTIAL_SPECIALIZATION 条件编译控制使用哪个版本，简单点说就是支持偏特化的迭代器萃取以后，反向迭代器使用的是这个版本，template < class Iterator > class reverse_iterator; 之前使用的是
template <class BidirectionalIterator, class T, class Reference, class Distance> class reverse_bidirectional_iterator;
template <class RandomAccessIterator, class T, class Reference ,class Distance> class reverse_iterator;
可以看到它们的差别主要是在模板参数是否传递迭代器指向的数据类型，支持偏特化的迭代器萃取以后就不需要给了，因为 reverse_iterator 内部可以通过迭代器萃取获取数据类型。迭代器萃取的本质是一个特化，这个还有有些小复杂就不讲解了。这个我们主要使用模版参数传递数据类型的方式实现。
反向迭代器本质是一个适配器，使用模版实现，传递哪个容器的迭代器就可以封装适配出对应的反向迭代器。因为反向迭代器的功能跟正向的迭代器功能高度相似，只是遍历的方向相反，类似operator++ 底层调用迭代器的 operator-- 等，所以封装一下就可以实现。
比较奇怪的是operator*的实现，内部访问的是迭代器当前位置的前一个位置。这个要结合容器中rbegin和rend实现才能看懂，rbegin返回的是封装end位置的反向迭代器，rend返回的是封装begin位置迭代器的反向迭代器，这里是为了实现出一个对称，所以解引用访问的是当前位置的前一个位置。

在这里插入图片描述

二.反向迭代器实现代码

1.ReverseIterator.h

#pragma once

//反向迭代器为适配器，适配于所有容器
//其中：Iterator：正向迭代器; Ref：数据类型的引用; Ptr：数据类型的指针
template<class Iterator, class Ref, class Ptr>
class ReverseIterator
{
typedef ReverseIterator<Iterator, Ref, Ptr> Self;

public:
ReverseIterator(Iterator it)
:_it(it)
{}

//迭代器不负责释放资源，没有析构函数

Ref operator*()
{
//return *_it;

Iterator tmp = _it;
--tmp;
return *tmp;
}

Ptr operator->()
{
return &(operator*());
}

Self& operator++()
{
--_it;
return *this;
}

Self operator++(int)
{
Self tmp(*this);
--_it;
return tmp;
}

Self& operator--()
{
++_it;
return *this;
}

Self operator--(int)
{
Self tmp(*this);
--_it;
return tmp;
}

bool operator!=(const Self& s) 
{
return _it != s._it;
}

bool operator==(const Self& s)
{
return _it == s._it;
}

private:
Iterator _it; //利用正向迭代器封装方向迭代器
};

2.Vector.h

#pragma once

#include<assert.h>

#include"ReverseIterator.h"

namespace xzy
{
template<class T>
class vector
{
public:
typedef T* iterator;
typedef const T* const_iterator;
typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

iterator begin()
{
return _start;
}

iterator end()
{
return _finish;
}

const_iterator begin() const
{
return _start;
}

const_iterator end() const
{
return _finish;
}

/*reverse_iterator rbegin()
{
return reverse_iterator(--end());
}

reverse_iterator rend()
{
return reverse_iterator(end());
}

const_reverse_iterator rbegin() const
{
return const_reverse_iterator(--end());
}

const_reverse_iterator rend() const
{
return const_reverse_iterator(end());
}*/

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

vector()
:_start(nullptr)
, _finish(nullptr)
, _end_of_storage(nullptr)
{}

vector(initializer_list<T> il)
{
reserve(il.size());
for (auto& e : il)
{
push_back(e);
}
}

vector(const vector<T>& v)
{
reserve(v.size());
for (auto& e : v)
{
push_back(e);
}
}

//类模版的成员函数可以是函数模版
template<class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
++first;
}
}

vector(size_t n, const T& val = T())
{
reserve(n);
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}

void clear()
{
_finish = _start;
}

void swap(vector<int>& v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}

//类内可以用类名替代类型：vector& operator=(vector tmp)
vector<T>& operator=(vector<T> tmp)
{
swap(tmp);
return *this;
}

~vector()
{
if (_start != nullptr)
{
delete[] _start;
}
_start = _finish = _end_of_storage;
}

void reserve(size_t n)
{
if (n > capacity())
{
//先保存有效数据个数
size_t old_size = size();
//开空间
T* tmp = new T[n];
//拷贝数据
for (size_t i = 0; i < old_size; i++)
{
tmp[i] = _start[i];
}
//释放旧空间
delete[] _start;
//更新数据
_start = tmp;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}

void resize(size_t n, const T& val = T())
{
if (n < size())
{
_finish = _start + n;
}
else
{
reserve(n);
while (_finish < _start + n)
{
*_finish = val;
++_finish;
}
}
}

size_t size() const
{
return _finish - _start;
}

size_t capacity() const
{
return _end_of_storage - _start;
}

void push_back(const T& x)
{
//容量满了——>扩容
if (_finish == _end_of_storage)
{
reserve(capacity() == 0 ? 4 : 2 * capacity());
}
//尾插
*_finish = x;
++_finish;
}

bool empty()
{
return _start == _finish;
}

void pop_back()
{
assert(!empty());
--_finish;
}

iterator insert(iterator pos, const T& x)
{
//容量满了——>扩容
if (_finish == _end_of_storage)
{
//记录pos的相对位置防止迭代器失效
size_t len = pos - _start;
reserve(capacity() == 0 ? 4 : 2 * capacity());
pos = _start + len;
}
//整体后移一位
iterator end = _finish - 1;
while (end >= pos)
{
*(end + 1) = *end;
--end;
}
//插入数据
*pos = x;
++_finish;

return pos;
}

iterator erase(iterator pos)
{
iterator it = pos + 1;
while (it != end())
{
*(it - 1) = *it;
++it;
}
--_finish;

return pos;
}

T& operator[](size_t i)
{
assert(i >= 0 && i < size());
return _start[i];
}

const T& operator[](size_t i) const
{
assert(i >= 0 && i < size());
return _start[i];
}

private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _end_of_storage = nullptr;

};
}

3.List.h

#pragma once

#include<assert.h>

#include"ReverseIterator.h"

namespace xzy
{
template<class T>
struct list_node
{
typedef list_node<T> Node;

list_node(const T& data = T())
:_data(data)
, _next(nullptr)
, _prev(nullptr)
{}

T _data;
Node* _next;
Node* _prev;
};

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* node)
:_node(node)
{}

Ref operator*()
{
return _node->_data;
}

Ptr operator->()
{
return &(_node->_data);
}

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

Self& operator--()
{
_node = _node->_prev;
return *this;
}

bool operator==(const Self& s) const
{
return _node == s._node;
}

bool operator!=(const Self& s) const
{
return _node != s._node;
}
};

template<class T>
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 ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;

iterator begin()
{
return _head->_next;
}

iterator end()
{
return _head;
}

const_iterator begin() const
{
return _head->_next;
}

const_iterator end() const
{
return _head;
}

/*reverse_iterator rbegin()
{
return reverse_iterator(--end());
}

reverse_iterator rend()
{
return reverse_iterator(end());
}

const_reverse_iterator rbegin() const
{
return const_reverse_iterator(--end());
}

const_reverse_iterator rend() const 
{
return const_reverse_iterator(end());
}*/

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

void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}

list()
{
empty_init();
}

list(initializer_list<T> il)
{
empty_init();
for (auto& e : il)
{
push_back(e);
}
}

list(const list<T>& lt)
{
empty_init();
for (auto e : lt)
{
push_back(e);
}
}

~list()
{
clear();
delete _head;
_head = nullptr;
}

void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}

list<T>& operator=(list<T> tmp)
{
swap(tmp);
return *this;
}

void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}

void push_back(const T& x)
{
//1.创建要插入的节点
Node* newnode = new Node(x);

//2.寻找尾节点
Node* tail = _head->_prev;

//3.尾插新节点
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;

//4.节点数自增一个
++_size;

//insert(end(), x);
}

void push_front(const T& x)
{
//1.创建要插入的节点
Node* newnode = new Node(x);

//2.定位头节点的下一个节点
Node* next = _head->_next;

//3.头插新节点
_head->_next = newnode;
newnode->_prev = _head;
newnode->_next = next;
next->_prev = newnode;

//4.节点数自增一个
++_size;

//insert(begin(), x);
}

iterator insert(iterator pos, const T& x)
{
//1.保存结构体pos的指针和pos的前一个节点的指针
Node* cur = pos._node;
Node* prev = cur->_prev;

//2.创建要插入的节点
Node* newnode = new Node(x);

//3.插入新节点
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;

//4.节点数自增一个
++_size;

return newnode;
}

void pop_back()
{
//1.保存要删除的节点的指针和前一个节点的指针
Node* del = _head->_prev;
Node* prev = del->_prev;

//2.修改指针的指向+删除节点
prev->_next = _head;
_head->_prev = prev;
delete del;

//3.节点数自减一个
--_size;

//erase(--end());
}

void pop_front()
{
//1.保存要删除的节点的指针和后一个节点的指针
Node* del = _head->_next;
Node* next = del->_next;

//2.修改指针的指向+删除节点
_head->_next = next;
next->_prev = _head;
delete del;

//3.节点数自减一个
--_size;

//erase(begin());
}

iterator erase(iterator pos)
{
//注意：不能删除哨兵位的头节点
assert(pos != end());

//1.保存pos节点的前后节点的指针
Node* prev = pos._node->_prev;
Node* next = pos._node->_next;

//2.修改指针的指向+删除节点
prev->_next = next;
next->_prev = prev;
delete pos._node;

//3.节点数自减一个
--_size;

return next;
}

private:
list_node<T>* _head;
size_t _size;
};
}

4.Test.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
using namespace std;

#include"List.h"
#include"Vector.h"

int TestListReverseIterator()
{
xzy::list<int> lt1 = { 1,2,3,4 };
xzy::list<int>::reverse_iterator rit = lt1.rbegin();
while (rit != lt1.rend())
{
//*rit = 1; 可以修改
cout << *rit << " ";
++rit;
}
cout << endl;

const xzy::list<int> lt2 = { 1,2,3,4 };
xzy::list<int>::const_reverse_iterator crit = lt2.rbegin();
while (crit != lt2.rend())
{
//*crit = 1; 不能修改
cout << *crit << " ";
++crit;
}
cout << endl;

return 0;
}

int TestVectorReverseIterator()
{
xzy::vector<int> lt1 = { 1,2,3,4 };
xzy::vector<int>::reverse_iterator rit = lt1.rbegin();
while (rit != lt1.rend())
{
//*rit = 1; 可以修改
cout << *rit << " ";
++rit;
}
cout << endl;

const xzy::vector<int> lt2 = { 1,2,3,4 };
xzy::vector<int>::const_reverse_iterator crit = lt2.rbegin();
while (crit != lt2.rend())
{
//*crit = 1; 不能修改
cout << *crit << " ";
++crit;
}
cout << endl;

return 0;
}

int main()
{
TestVectorReverseIterator();
TestListReverseIterator();

return 0;
}

原文地址：https://blog.csdn.net/2203_76003626/article/details/145145859

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：68_Redis数据结构-QuickList
下一篇：vue2使用echarts实现折线图图例，悬浮框，折线点改为不同点相同样式

基于Linux系统指令使用详细解析
远程登录linux系统 ssh root@ 192.168 .202 .136 # 断开连接 exit # 重启系统 reboot 或者 shutdown - h now # 关机指令 shutdow
阅读更多2025-01-17
VUE学习笔记6__vue指令v-show和v-if
通过vue调试插件设置flag为false，此时。v-show控制的div结构还在。频繁切换显示隐藏的用v-show。v-if控制的div已经被删除。
阅读更多2025-01-17
SpringSecurity-前后端分离
try {// 设置当前线程的安全上下文。
阅读更多2025-01-17
如何在Mac上使用Brew更新Cursor应用程序
Cursor是一款强大的工具，旨在帮助用户更好地编写、编辑和讨论代码。它结合了AI技术，使得编程过程更加高效和便捷。Cursor不仅支持代码编辑，还可以与团队成员进行实时协作。随着技术的发展，工具的更
阅读更多2025-01-17
Excel中函数SIGN()的用法
number:为任意的实数。
阅读更多2025-01-17
在 macOS 上，用命令行连接 MySQL（/usr/local/mysql/bin/mysql -u root -p）
根据你提供的文件内容，MySQL 的安装路径是。要直接使用mysql命令，你需要找到mysql可执行文件的路径。在 macOS 上，mysql客户端通常位于 MySQL 安装目录的bin子目录中。
阅读更多2025-01-17
MySQL之字段类型和SQL约束
MySQL提供了丰富的数据类型，用于定义表中的列。提供了约束用于指定表中数据的规则，确保数据的完整性和一致性。
阅读更多2025-01-17
Android adb 调试，不在手机上点击信任 “允许usb调试” 即可连接的方式（手机需root）
通过更改手机的 /data/misc/adb/adb_keys 文件来达到直接信任电脑的效果。
阅读更多2025-01-17
47.数据绑定的PropertyChanged C#例子 WPF例子
"invoke" 通常指的是调用一个方法、过程、函数或委托。），编译器会自动将调用该方法的成员（如属性、方法的名称）作为。是一个特性（Attribute），它应用于。这个特性的作用
阅读更多2025-01-17
基于多个边缘盒子部署的综合视频安防系统的智慧地产开源了
智慧地产视觉监控平台是一款功能强大且简单易用的实时算法视频监控系统。它的愿景是最底层打通各大芯片厂商相互间的壁垒，省去繁琐重复的适配流程，实现芯片、算法、应用的全流程组合，从而大大减少企业级应用约95
阅读更多2025-01-17