1.反向迭代器思路及实现

1.1. 源码及框架分析

SGI-STL30版本源代码，反向迭代器实现的核心源码在stl_iterator.h中。

前文我们了解到了正向迭代器是基于原生指针的封装实现，反向迭代器的逻辑与正向迭代器的逻辑正好相反，代码应该高度相似，因此在学习了stack与queue之后，明白了适配器思想，我们就复用正向迭代器代码实现反向迭代器，减少代码冗余。

下面我们截出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_SPECIALIZATIONtypedef 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 {returnconst_reverse_iterator(end());}reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const {returnconst_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_SPECIALIZATIONtypedef 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 {returnconst_reverse_iterator(end());}reverse_iterator rend() { return reverse_iterator(begin()); }const_reverse_iterator rend() const {returnconst_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_categoryiterator_category;typedef typename iterator_traits<Iterator>::value_typevalue_type;typedef typename iterator_traits<Iterator>::difference_typedifference_type;typedef typename iterator_traits<Iterator>::pointerpointer;typedef typename iterator_traits<Iterator>::referencereference;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_TEMPLATEStemplate <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_OPERATORpointer 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_OPERATORpointer 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_OPERATORpointer 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位置迭代器的反向迭代器，这里是为了与正向迭代器对应，专门实现出一个对称版本，begin与rend，end与rbegin，所以解引用访问的是当前位置的前一个位置，这样返回解引用rbegin时，返回上一个节点，即返回有效节点的最后一个节点，解引用rend就会正好返回哨兵节点。（这里没有其他的特殊作用，如果愿意也可以不对称实现）

1.2. 实现反向迭代器

// ReverseIterator.h
// 所有容器的反向迭代器
// 迭代器适配器
namespace zlr
{template<class Iterator, class Ref, class Ptr>struct ReverseIterator{typedef ReverseIterator<Iterator, Ref, Ptr> Self;// 正向迭代器Iterator _it;ReverseIterator(Iterator it):_it(it){}Ref operator*(){Iterator tmp = _it;return *(--tmp);}Ptr operator->(){return &(operator*());}Self& operator++(){--_it;return *this;}Self& operator--(){++_it;return *this;}Self operator++(int){Self tmp(*this);--_it;return tmp;}Self operator--(int){Self tmp(*this);--_it;return tmp;}bool operator!=(const Self& s) const{return _it != s._it;}bool operator==(const Self& s) const{return _it != s._it;}};
}
// vector.h
#include"ReverseIterator.h"
namespace zlr
{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;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());}iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}// ....private:iterator _start = nullptr;iterator _finish = nullptr;iterator _endofstorage = nullptr;};
}
// list.h
#include"ReverseIterator.h"
namespace zlr
{template<class T>class list{typedef ListNode<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<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;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());}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}// ...private:Node* _head;size_t _size;};
}
// test.cpp
#include"list.h"
#include"vector.h"
int main()
{zlr::list<int> lt = { 1,2,3,4 };zlr::list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){//*rit = 1;cout << *rit << " ";++rit;}cout << endl;return 0;
}
//int main()
//{
// zlr::vector<int> v = { 1,2,3,4 };
// zlr::vector<int>::reverse_iterator rit = v.rbegin();
// while (rit != v.rend())
// {
// //*rit = 1;
// cout << *rit << " ";
// ++rit;
// }
// cout << endl;
//
// return 0;
//}

2.stack和queue练习拓展-计算器实现

2.1. 后缀表达式概念

• 我们日常写的计算表达式都是中缀表达式，也就是运算符在中间，运算数在两边，但是中缀表达式直接读取无法马上进行运算，因为一个计算表达式还涉及运算符优先级问题，中缀表达式无法直接确定一个运算符优先级，必须根据相邻运算符才能确定。如： 1-2*(3-4)+5 中遇到-和*都无法运算，因为后面还有括号优先级更高。

• 所以其中一种实现思路是把中缀表达式转换为后缀表达式，也就是说分析计算表达式的优先级，将运算符放到前面，运算符放到运算数的后面，然后我们依次读取后缀表达式，遇到运算符就可以进行运算了。后缀表达式也就做逆波兰表达式(Reverse Polish Notation, RPN)，这种表示法由波兰逻辑学家J·卢卡西维兹于1929年提出，后来被广泛应用于计算机科学中。

2.2. 后缀表达式运算规则

• 后缀表达式因为已经确定好优先级，运算符方式非常简单，就是遇到运算符时，取前面的两个数进行运算，因为经过中缀转后缀优先级已经确定好了，因此我们根据运算特点，使用栈来实现。

• 建立一个栈存储运算数，读取后缀表达式，遇到运算数入栈；遇到运算符，出栈顶的两个数据进行运算，运算后将结果作为一个运算数入栈继续参与下一次的运算。读取表达式结束后，最后栈里面的值就是运算结果。

• 150. 逆波兰表达式求值 - 力扣（LeetCode）

class Solution {
public:int evalRPN(const vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); ++i){const string& str = tokens[i];// str为运算数，入栈if (!("+" == str || "-" == str || "*" == str || "/" == str)){s.push(stoi(str));}else{// str为运算符，取前两个运算数进行运算int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':s.push(left / right);break;}}}return s.top();}
};

2.3. 中缀表达式转后缀表达式

2.3.1 转换思路

• 依次读取计算表达式中的值，遇到运算数直接输出。

• 建立一个栈存储运算符，利用栈后进新出性质，遇到后面运算符，出栈里面存的前面运算符进行比较，确定优先级。

• 遇到运算符，如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高，则当前运算符入栈。因为如果栈里面存储的是前一个运算符，当前运算符比前一个优先级高，说明前一个不能运算，当前运算符也不能运算，因为后面可能还有更高优先级的运算符。

• 遇到运算符，如果栈不为为空且当前运算符比栈顶运算符优先级低或相等，说明栈顶的运算符可以运算了，则输出栈顶运算符，当前运算符继续走前面遇到运算符的逻辑。

• 如果遇到()，则把括号的计算表达式当成一个子表达式，进行递归，跟上思路类似处理子表达式，处理后转换出的后缀表达式加在前面表达式的后面即可。

• 计算表达式或者()中子表达式结束时，输出栈中所有运算符。

2.3.2 代码实现

class Solution {
public://map<char, int> _operatorPrecedence = { { '+', 1 }, { '-', 1 }, { '*', 2//}, { '/', 2 } };//因为运算符优先级与ASCII无关，这里我们使用结构体来处理运算符的优先级比较问题//如果学习过map容器，可以使用map处理int operatorPrecedence(char ch){struct opPD{char _op;int _pd;};static opPD arr[] = { {'+', 1},{'-', 1},{'*', 2},{'/', 2} };for (auto& e : arr){if (e._op == ch){return e._pd;}}assert(false);return -1;}//因为有递归的情况存在，我们这里使用i来记录当前访问位置void toRPN(const string& s, size_t& i, vector<string>& v){stack<char> st;while (i < s.size()){if (isdigit(s[i])){// 操作数输出string num;while (i < s.size() && isdigit(s[i])){num += s[i];++i;}v.push_back(num);}else{if (s[i] == '('){// 递归方式处理括号中的子表达式++i;toRPN(s, i, v);}else if (s[i] == ')'){++i;// 栈中的运算符全部输出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}// 结束递归return;}else{// 运算符// 1、如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高，则当//前运算符入栈// 2、如果栈不为为空且比栈顶运算符优先级低或相等，说明栈顶的运算符//可以运算了，// 输出栈顶运算符，当前运算符继续走前面遇到运算符的逻辑if (st.empty() || operatorPrecedence(s[i]) >operatorPrecedence(st.top())){st.push(s[i]);++i;}else{v.push_back(string(1, st.top()));st.pop();}}}}// 栈中的运算符全部输出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}}
};
int main()
{size_t i = 0;vector<string> v;//string str = "1+2-3";string str = "1+2-(3*4+5)-7";Solution().toRPN(str, i, v);for (auto& e : v){cout << e << " ";}cout << endl;return 0;
}

2.4. 计算器实现

• 224. 基本计算器 - 力扣（LeetCode）

• 有了上面两个部分学习之后，计算器OJ的大部分问题就解决了，但是这里还有一些问题需要处理。因为OJ中给的中缀表达式是字符串，字符串中包含空格，需要去掉空格。

• 其次就是负数和减号，要进行区分，将所有的负数-x转换为0-x，因为我们实现的代码考虑到乘除的情况，针对括号内的符号，我们不能直接变号处理。

class Solution {
public://map<char, int> _operatorPrecedence = { { '+', 1 }, { '-', 1 }, { '*', 2
}, { '/', 2 } };
int operatorPrecedence(char ch)
{struct opPD{char _op;int _pd;};static opPD arr[] = { {'+', 1},{'-', 1},{'*', 2},{'/', 2} };for (auto& e : arr){if (e._op == ch){return e._pd;}}assert(false);return -1;
}
void toRPN(const string& s, size_t& i, vector<string>& v)
{stack<char> st;while (i < s.size()){if (isdigit(s[i])){// 运算数输出string num;while (i < s.size() && isdigit(s[i])){num += s[i];++i;}v.push_back(num);}else{if (s[i] == '('){// 递归方式处理括号中的子表达式++i;toRPN(s, i, v);}else if (s[i] == ')'){++i;// 栈中的运算符全部输出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}// 结束递归return;}else{// 运算符// 1、如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高，则当//前运算符入栈// 2、如果栈不为为空且比栈顶运算符优先级低或相等，说明栈顶的运算符//可以运算了，// 输出栈顶运算符，当前运算符继续走前面遇到运算符的逻辑if (st.empty() || operatorPrecedence(s[i]) >operatorPrecedence(st.top())){st.push(s[i]);++i;}else{v.push_back(string(1, st.top()));st.pop();}}}}// 栈中的运算符全部输出while (!st.empty()){v.push_back(string(1, st.top()));st.pop();}
}
int evalRPN(const vector<string>& tokens) {stack<int> s;for (size_t i = 0; i < tokens.size(); ++i){const string& str = tokens[i];// str为数字if (!("+" == str || "-" == str || "*" == str || "/" == str)){s.push(stoi(str));}else{// str为操作符int right = s.top();s.pop();int left = s.top();s.pop();switch (str[0]){case '+':s.push(left + right);break;case '-':s.push(left - right);break;case '*':s.push(left * right);break;case '/':s.push(left / right);break;}}}return s.top();
}
int calculate(string s)
{// 1、去除所有空格，否则下面的一些逻辑没办法处理std::string news;news.reserve(s.size());for (auto ch : s){if (ch != ' ')news += ch;}s.swap(news);news.clear();// 2、将所有的负数-x转换为0-xfor (size_t i = 0; i < s.size(); ++i){//当-的前一个字符不为运算数时，我们才添加"0-",否则就是减号，不需要处理//同时因为这里是下标比较，需要注意符号在表达式第一位的情况，防止越界if (s[i] == '-' && (i == 0 || (!isdigit(s[i - 1]) && s[i - 1] !=')')))news += "0-";elsenews += s[i];}// 中缀表达式转成后缀表达式size_t i = 0;vector<string> v;toRPN(news, i, v);// 后缀表达式进行运算return evalRPN(v);
}
};