1.反向迭代器思路及实现1.1. 源码及框架分析SGI-STL30版本源代码反向迭代器实现的核心源码在stl_iterator.h中。前文我们了解到了正向迭代器是基于原生指针的封装实现反向迭代器的逻辑与正向迭代器的逻辑正好相反代码应该高度相似因此在学习了stack与queue之后明白了适配器思想我们就复用正向迭代器代码实现反向迭代器减少代码冗余。下面我们截出vector和list的的反向迭代器结构框架核心部分截取出来如下代码语言javascriptAI代码解释// stl_list.h template class T, class Alloc alloc class list { public: typedef __list_iteratorT, T, T* iterator; typedef __list_iteratorT, const T, const T* const_iterator; #ifdef __STL_CLASS_PARTIAL_SPECIALIZATION typedef reverse_iteratorconst_iterator const_reverse_iterator; typedef reverse_iteratoriterator reverse_iterator; #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ typedef reverse_bidirectional_iteratorconst_iterator, value_type, const_reference, difference_type const_reverse_iterator; typedef reverse_bidirectional_iteratoriterator, 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_iteratorconst_iterator const_reverse_iterator; typedef reverse_iteratoriterator reverse_iterator; #else /* __STL_CLASS_PARTIAL_SPECIALIZATION */ typedef reverse_iteratorconst_iterator, value_type, const_reference, difference_type const_reverse_iterator; typedef reverse_iteratoriterator, 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_traitsIterator::iterator_category iterator_category; typedef typename iterator_traitsIterator::value_type value_type; typedef typename iterator_traitsIterator::difference_type difference_type; typedef typename iterator_traitsIterator::pointer pointer; typedef typename iterator_traitsIterator::reference reference; typedef Iterator iterator_type; typedef reverse_iteratorIterator 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_iteratorIter 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_iteratorIterator x, const reverse_iteratorIterator y) { return x.base() y.base(); } template class Iterator inline bool operator(const reverse_iteratorIterator x, const reverse_iteratorIterator y) { return y.base() x.base(); } template class Iterator inline typename reverse_iteratorIterator::difference_type operator-(const reverse_iteratorIterator x, const reverse_iteratorIterator y) { return y.base() - x.base(); } template class Iterator inline reverse_iteratorIterator operator(reverse_iteratorIterator::difference_type n, const reverse_iteratorIterator x) { return reverse_iteratorIterator(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_iteratorBidirectionalIterator, 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_iteratorRandomAccessIterator, 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 Iteratorclass reverse_iterator一个参数; 之前使用的是template class BidirectionalIterator, class T, class Reference,class Distanceclass reverse_bidirectional_iterator;template class RandomAccessIterator, class T, class Reference,class Distanceclass reverse_iterator;多个参数 • 我们可以看到他们的差别主要是在模板参数是否传递迭代器指向的数据类型支持偏特化的迭代器萃取以后就不需要给了因为reverse_iterator 内部可以通过迭代器萃取获取数据类型。迭代器萃取的本质是一个特化这里我们就不讲解了想了解可以去看源码。本文这里我们为了便于理解我们主要使用模版参数传递数据类型的方式实现。 • 反向迭代器本质是一个适配器使用模版实现传递哪个容器的迭代器就可以封装适配出对应的反向迭代器。因为反向迭代器的功能跟正向的迭代器功能高度相似只是遍历的方向相反类似operator 底层调用迭代器的operator-- 等所以封装一下就可以实现。 • 比较奇怪的是operator*的实现源码内部访问的是迭代器当前位置的前一个位置。 这个要结合容器中rbegin和rend实现才能看懂rbegin返回的是封装end位置的反向迭代器rend返回的是封装begin位置迭代器的反向迭代器这里是为了与正向迭代器对应专门实现出一个对称版本begin与rendend与rbegin所以解引用访问的是当前位置的前一个位置这样返回解引用rbegin时返回上一个节点即返回有效节点的最后一个节点解引用rend就会正好返回哨兵节点。这里没有其他的特殊作用如果愿意也可以不对称实现1.2. 实现反向迭代器代码语言javascriptAI代码解释// ReverseIterator.h // 所有容器的反向迭代器 // 迭代器适配器 namespace zlr { templateclass Iterator, class Ref, class Ptr struct ReverseIterator { typedef ReverseIteratorIterator, 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 #includeReverseIterator.h namespace zlr { templateclass T class vector { public: typedef T* iterator; typedef const T* const_iterator; typedef ReverseIteratoriterator, T, T* reverse_iterator; typedef ReverseIteratorconst_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 #includeReverseIterator.h namespace zlr { templateclass T class list { typedef ListNodeT Node; public: typedef ListIteratorT, T, T* iterator; typedef ListIteratorT, const T, const T* const_iterator; typedef ReverseIteratoriterator, T, T* reverse_iterator; typedef ReverseIteratorconst_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 #includelist.h #includevector.h int main() { zlr::listint lt { 1,2,3,4 }; zlr::listint::reverse_iterator rit lt.rbegin(); while (rit ! lt.rend()) { //*rit 1; cout *rit ; rit; } cout endl; return 0; } //int main() //{ // zlr::vectorint v { 1,2,3,4 }; // zlr::vectorint::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​​​​​​代码语言javascriptAI代码解释class Solution { public: int evalRPN(const vectorstring tokens) { stackint 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 转换思路• 依次读取计算表达式中的值遇到运算数直接输出。 • 建立一个栈存储运算符利用栈后进新出性质遇到后面运算符出栈里面存的前面运算符进行比较确定优先级。 •遇到运算符如果栈为空或者栈不为空且当前运算符比栈顶运算符优先级高则当前运算符入栈。因为如果栈里面存储的是前一个运算符当前运算符比前一个优先级高说明前一个不能运算当前运算符也不能运算因为后面可能还有更高优先级的运算符。 •遇到运算符如果栈不为为空且当前运算符比栈顶运算符优先级低或相等说明栈顶的运算符可以运算了则输出栈顶运算符当前运算符继续走前面遇到运算符的逻辑。 •如果遇到()则把括号的计算表达式当成一个子表达式进行递归跟上思路类似处理子表达式处理后转换出的后缀表达式加在前面表达式的后面即可。 • 计算表达式或者()中子表达式结束时输出栈中所有运算符。