C++反向迭代器
文章目录
- 一、反向迭代器(reverse_iterator)
- 1.1 反向迭代器的功能
- 1.2 迭代器适配器
- 二、模拟实现list容器的反向迭代器
- 三、模拟实现vector容器的反向迭代器
- 四、C++std库中实现的反向迭代器
一、反向迭代器(reverse_iterator)
我们模拟实现过string、vector或list容器的迭代器，但是我们实现的iterator和const_iterator都是正向的，而反向的迭代器我们并没有实现。那下面就来讲一下反向迭代器的实现。
1.1 反向迭代器的功能
● 功能: 逆向遍历容器(如list、vector等)，通过重载++和- -运算符实现逻辑反转。
● 底层依赖: 需基于双向或随机访问迭代器实现。
● 实现方式: 对正向迭代器进行封装，通过rbegin()和rend()获取逆向迭代范围。
1.2 迭代器适配器
🔥在模拟实现list容器时，我们曾模拟实现过迭代器，由于list容器的底层是一个双向链表，则遍历链表就不能是普通的节点指针++或- -，因为节点与节点之间并不是连续的物理空间，所以要实现一个list容器的迭代器就稍难一些。我们要将遍历节点的各种操作封装起来，使之成为一个不关心底层实现细节的迭代器。所以list容器的迭代器是一个类。
🔥我们在实现list容器的迭代器时，是将迭代器定义成了一个类模版，这样做的好处是：针对普通的iterator和const_iterator，实例化时通过对迭代器的模版参数传T&、T*或const T&、const T*参数，就可以实现普通版本的迭代器或const版本的迭代器。因为普通版本的迭代器和const版本的迭代器无非就是节点的内容是否能修改，所以两种迭代器种除了operator*和operator->函数以外，其他的操作都是相同的，那就可以通过定义类模板来实现两种版本的迭代器。
那我们要实现一个反向的迭代器，能否通过正向迭代器去适配出一个反向的迭代器，实现代码的复用呢？答案是可以的！
//my_reverseiterator.h
//迭代器适配器(用正向迭代器适配出反向迭代器)
template<class Iterator,class Ref,class Ptr>
class ReverseIterator
{
public:
typedef ReverseIterator<Iterator, Ref, Ptr> self;
ReverseIterator(Iterator it)
:_it(it)
{ }
self& operator++()
{
--_it;
return *this;
}
self& operator--()
{
++_it;
return *this;
}
Ref operator*()
{
return *_it;
}
Ptr operator->()
{
return _it.operator->(); //显式调用
}
bool operator!=(const self& s)
{
return _it != s._it;
}
private:
Iterator _it;
};
正向迭代器能用来适配反向迭代器的原因是：反向迭代器中很多功能和正向迭代器是重叠的。可以看到反向迭代器中的成员变量就只有一个正向迭代器对象_it，当将一个正向迭代器作为参数传给ReverseIterator时，就可以适配出一个反向迭代器。只不过反向迭代器的++是正向迭代器的- -，反向迭代器的- -是正向迭代器的++。
二、模拟实现list容器的反向迭代器
上面我们实现了一个反向迭代器适配器，那现在可以将各种容器的正向迭代器传给他，即可实现该容器的反向迭代器。比如list类的：
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 ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
iterator begin()
{
//return iterator(_head->_next); //返回一个匿名对象
return _head->_next;
}
iterator end()
{
return _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() - 1);
}
reverse_iterator rend()
{
return reverse_iterator(end());
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end() - 1);
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(end());
}
//…
private:
Node* _head;
size_t _size;
};
注意：上面反向迭代器中所给的end()是正向迭代器的一个函数调用，即end()的返回值是iterator类型的对象，所以要实现end()-1的话就要在iterator类中重载-运算符才行。
三、模拟实现vector容器的反向迭代器
vector容器的底层是一个顺序表(数组)，所以vector的反向迭代器适配出来比较简单：
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()-1);
}
reverse_iterator rend()
{
return reverse_iterator(begin()-1);
}
const_reverse_iterator rbegin() const
{
return const_reverse_iterator(end()-1);
}
const_reverse_iterator rend() const
{
return const_reverse_iterator(begin()-1);
}
//…
private:
iterator _start = nullptr;
iterator _finish = nullptr;
iterator _endofstorage = nullptr;
};
注意：这里的begin()和end()迭代器就是一个原生指针，只不过是重命名的，所以这里的iterator并不是一个对象，而是一个指针；则begin()-1或end()-1其实就是指针的-1，而指针是一个内置类型，所以减整数1就是往后退vector存储的一个元素(T类型)大小。
四、C++std库中实现的反向迭代器
上面的list容器和vector容器的底层展示图中，还有一个std库中实现的反向迭代器。跟我们自己实现的反向迭代器有所差异，它反向的rbegin()就是正向的end()，反向的rend()就是正向的begin()。那标准库中的反向迭代器是怎么实现的呢？其实就是做了一点点的改动，就变成了我们自己实现的反向迭代器：
//std_reverseiterator.h
//实现库中的迭代器适配器
template<class Iterator, class Ref, class Ptr>
class SReverseIterator
{
public:
typedef SReverseIterator<Iterator, Ref, Ptr> self;
SReverseIterator(Iterator it)
:_it(it)
{ }
self& operator++()
{
--_it;
return *this;
}
self& operator--()
{
++_it;
return *this;
}
Ref operator*()
{
Iterator cur = _it;
return *(--cur);
}
Ptr operator->()
{
return &(operator->());
}
bool operator!=(const self& s)
{
return _it != s._it;
}
private:
Iterator _it;
};
有所改动的部分就是*和->的重载：
库中实现的反向迭代器rbegin()和rend()虽然在对应正向的end()和begin()的位置，但是对迭代器进行解引用时，却不是对应位置的迭代器进行解引用，而是前一个元素位置的迭代器解引用。所以其实就是一种错位访问的方式。这样做的好处是：反向迭代器能和正向迭代器对称起来。
还需要注意的是：正向迭代器的begin()和end()作为reverse_itertor或者const_reverse_iterator的参数时，如果使用重载的- -的话可能会出现问题：比如- -end()或者end()- -做反向迭代器的参数的话，由于end()是一个Iterator类型的迭代器，并且end()是一个临时对象；因为end()是一个函数调用，它的返回值是值返回，就是一个临时对象，而临时对象是具有常性的，所以不能对其进行++或- -，所以要使用end()-1，这样不会改变这个迭代器本身。
但是这个其实是C++中遗留的坑，在很多地方，一个匿名对象(临时对象)又可以调用其类中的函数。所以上面的end()- -或- -end()在一些编译器下可能不会报错。
