C++反向迭代器实现与逆波兰表达式计算器

C++反向迭代器实现与逆波兰表达式计算器

1. 反向迭代器思路 (源码及框架分析)

反向迭代器是一种特殊的迭代器，它的核心作用是：从容器的末尾开始，逆向遍历容器中的元素（正常迭代器是从头部到尾部）。可以把它理解成： 正常迭代器：像你从队伍第一个人走到最后一个人； 反向迭代器：像你从队伍最后一个人倒着走回第一个人。

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


 < ,   = alloc>
 vector {
:
     T value_type;
     value_type* iterator;

     reverse_iterator<const_iterator> const_reverse_iterator;
     reverse_iterator<iterator> reverse_iterator;

     reverse_iterator<const_iterator, value_type, const_reference, difference_type> const_reverse_iterator;
     reverse_iterator<iterator, value_type, reference, difference_type> reverse_iterator;

    {  start; }
    {  start; }
    {  finish; }
    {  finish; }
    {  (()); }
    {  (()); }
    {  (()); }
    {  (()); }
};






 < >
  {
:
    Iterator current;
:
      iterator_traits<Iterator>::iterator_category iterator_category;
      iterator_traits<Iterator>::value_type value_type;
      iterator_traits<Iterator>::difference_type difference_type;
      iterator_traits<Iterator>::pointer pointer;
      iterator_traits<Iterator>::reference reference;
     Iterator iterator_type;
     reverse_iterator<Iterator> self;
:
    () {}
    }
    ( self& x) : (x.current) {}

     < >
    ( reverse_iterator<Iter>& x) : (x.current) {}

    {  current; }
    reference *()  { Iterator tmp = current;  *--tmp; }

    pointer ->()  {  &(*()); }

    self& ++() { --current;  *; }
    self ++() { self tmp = *; --current;  tmp; }
    self& --() { ++current;  *; }
    self --() { self tmp = *; ++current;  tmp; }
    self +(difference_type n)  {  (current - n); }
    self& +=(difference_type n) { current -= n;  *; }
    self -(difference_type n)  {  (current + n); }
    self& -=(difference_type n) { current -= n;  *; }
    reference [](difference_type n)  {  *(* + n); }
};
 < >
  ==( reverse_iterator<Iterator>& x,  reverse_iterator<Iterator>& y) {
     x.() == y.();
}
 < >
  <( reverse_iterator<Iterator>& x,  reverse_iterator<Iterator>& y) {
     y.() < x.();
}
 < >
  reverse_iterator<Iterator>::difference_type -( reverse_iterator<Iterator>& x,  reverse_iterator<Iterator>& y) {
     y.() - x.();
}
 < >
 reverse_iterator<Iterator> +(reverse_iterator<Iterator>::difference_type n,  reverse_iterator<Iterator>& x) {
     <Iterator>(x.() - n);
}



 < ,  ,   = T&,  Distance = >
 reverse_bidirectional_iterator {
     reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, Distance> self;
:
    BidirectionalIterator current;
:
     bidirectional_iterator_tag iterator_category;
     T value_type;
     Distance difference_type;
     T* pointer;
     Reference reference;
    () {}
    }
    {  current; }
    Reference *()  { BidirectionalIterator tmp = current;  *--tmp; }

    pointer ->()  {  &(*()); }

    self& ++() { --current;  *; }
    self ++() { self tmp = *; --current;  tmp; }
    self& --() { ++current;  *; }
    self --() { self tmp = *; ++current;  tmp; }
};
 < ,  ,   = T&,  Distance = >
 reverse_iterator {
     reverse_iterator<RandomAccessIterator, T, Reference, Distance> self;
:
    RandomAccessIterator current;
:
     random_access_iterator_tag iterator_category;
     T value_type;
     Distance difference_type;
     T* pointer;
     Reference reference;
    () {}
    }
    {  current; }
    Reference *()  {  *(current - ); }

    pointer ->()  {  &(*()); }

    self& ++() { --current;  *; }
    self ++() { self tmp = *; --current;  tmp; }
    self& --() { ++current;  *; }
    self --() { self tmp = *; ++current;  tmp; }
    self +(Distance n)  {  (current - n); }
    self& +=(Distance n) { current -= n;  *; }
    self -(Distance n)  {  (current + n); }
    self& -=(Distance n) { current -= n;  *; }
    Reference [](Distance n)  {  *(* + n); }
};