The adaptation of the reverse iterator is only used for the two-way iterator. For the one-way iterator implemented by the singly linked list, a reverse iterator cannot be constructed through adaptation. Why do we say the reverse iterator adapter? Because we only need to implement a reverse iterator template to implement its reverse iterators in the forward direction of all bidirectional iterators.
1. Reverse iterator of list
For the list, how do we want to traverse backwards? In fact, friends who have implemented the forward iterator know that the ++ of the iterator of the list points to the next node of the linked list, that is, node = node->next, so to achieve the reverse, we only need to implement ++ as Just set node = node->prev, as shown in the figure below:
//reverse iterator
template<class T, class Ref, class Ptr>
struct list_reverse_iterator
{
typedef list_node<T> node;
typedef list_reverse_iterator<T, Ref, Ptr> self;
node* _node;
list_reverse_iterator(node* n)
:_node(n)
{
}
Ref operator*()
{
return _node->_data;
}
self & operator ++ ()
{
_node = _node->_prev;
return *this;
}
self operator + + (int)
{
self tmp(*this);
_node = _node->_prev;
return tmp;
}
self & operator--()
{
_node = _node->_next;
return *this;
}
self operator--(int)
{
self tmp(*this);
_node = _node->_next;
return tmp;
}
Ptr operator->()
{
return &_node->_data;
}
bool operator!=(const self & amp; it)
{
return _node != it._node;
}
bool operator==(const self & it)
{
return _node == it._node;
}
};
It can be seen that our above code really just changes ++ into the original –, — into the original ++ for the reverse iterator. Now let’s write rbegin(), rbegin() again.
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 list_reverse_iterator<T, T &, T*> reverse_iterator;
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(_head->_prev);
}
reverse_iterator rend()
{
return reverse_iterator(_head);
}
}
Here comes the question. We just said that the reverse iterator is an adapter. If we use the reverse iterator of this linked list to realize the reverse iterator of vector, can it be realized? The answer is definitely no, because vector is not a node, how can it return the previous and subsequent nodes? So the iterator we implemented can only be used by list. Let’s see how the big guy implements the reverse iterator: 
What is the current we circled? current is a forward iterator 
So why does operator* become –iterator and then dereference? Look down: 
++ for a reverse iterator is — for a forward iterator, and — for a reverse iterator is ++ for a forward iterator. 
We found that rbegin() is the end() of the iterator, and rend() is the begin() of the iterator. Let’s draw a picture to verify it: 
At this time we finally understand why operator* is the dereference of –iterator, because rbegin () points to the head node of the sentinel position. At this time, the head node cannot be dereferenced. What we want is that the dereferenced element is 3 2 1, which does not contain the head node element, so we should dereference the head node The prev is also the last node dereference, so that each element of the linked list can be accessed from the back to the front in turn, and all elements will be traversed when rbegin()==rend().
Let’s implement it below:
namespace yrj
{
template<class iterator, class Ref, class Ptr>
struct ReverseIterator
{
typedef ReverseIterator<iterator, Ref, Ptr> self;
iterator_cur;
ReverseIterator(iterator it)
:_cur(it)
{}
};
}
First, we create an iterator.h file, and then write a template. The first parameter of this template is an iterator of any type, the second parameter is the return value Ref dereferenced in the iterator, and the third parameter is the overload – > The return value of the symbol Ptr. Then we create a variable _cur with a forward iterator, and initialize _cur with a forward iterator directly when the constructor is initialized.
Then we first implement ++ ,–:
self & operator + + ()
{
--_cur;
return *this;
}
self operator + + (int)
{
iterator tmp = _cur;
--_cur;
return tmp;
}
The difference between pre ++ and post ++ is that post ++ returns the value before –, so we directly use copy to construct a tmp, here we have not implemented the copy construction of the iterator, so use the default Can the copy constructor of The answer is yes, because what we want is a shallow copy, we just want tmp to point to the location of cur, as shown in the figure below: 
Let’s take a look at what the deep copy becomes: 
Through the picture above, we should understand why we can solve the problem by directly using the default constructor.
self & operator--()
{
+ + _cur;
return *this;
}
self operator--(int)
{
iterator tmp = _cur;
+ + _cur;
return tmp;
}
The implementation of — is the same as ++, except that — becomes the ++ of the forward iterator.
Let’s implement the == and != symbols used by the iterator again:
bool operator!=(const self & amp; s)
{
return _cur != s._cur;
}
bool operator==(const self & s)
{
return _cur == s._cur;
}
For the judgment of the reverse iterator, we only need to judge whether the nodes of the two reverse iterators are equal.
Below we implement the dereferencing of reverse iterators:
Ref operator*()
{
iterator tmp = _cur;
--tmp;
return *tmp;
}
For the dereferencing of the reverse iterator, we said that since rbegin() is at the position of end(), we cannot directly dereference it. The correct operation is to dereference the previous node at this position (why is it the previous one? ? because it’s a reverse iterator!). So we use _cur to copy and construct a tmp, then –tmp is the previous node, and then return the dereferenced value. The implementation of the return value is the same as that of the forward iterator. You can read my list simulation implementation article to see why there is an additional template parameter Ref as the return value.
typedef ReverseIterator<iterator,T & amp;,T*> reverse_iterator;
typedef ReverseIterator<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());
}
Back to our original question, can this iterator be used to adapt the reverse iterator of vector? Let’s draw a picture to see:
When the reverse iterator ++ is the forward iterator –, then move from the tail of the vector to the head. At the same time, we found that the implementation of operator* is also satisfactory, because the position of rbegin() is the position next to the position where the last valid data is stored in the vector. There is no data in this position. Only by dereferencing the iterator The correct value, because it is the previous one of each position, when rbegin()==rend(), all data will be traversed in reverse. Let’s demonstrate the reverse iterator of vector:
reverse iterator of vector
typedef ReverseIterator<iterator, T & amp;, T*> reverse_iterator;
typedef ReverseIterator<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());
}
When we want to implement the reverse iterator of the list, we only implement the reverse iterator for the list, but the boss uses a reverse iterator to adapt other reverse iterators.