总言

  主要介绍栈和队列的基本函数使用：栈和队列、优先级队列、适配器、反向迭代器。

  

  

1、栈和队列接口基本介绍

1.1、基本介绍

  1）、总言

  栈：相关链接

  队列：相关链接

  
  栈和队列我们在基础数据结构|| 栈和队列中，使用C语言实现过，这里相关接口大差不差，比如pop删除、push插入、empty判空，size获取个数等等。
  那么，SQL中栈和队列与之前学习的vector、list间有什么区别呢？
  通过观察可以发现stack和queue中相对而言接口较少，也没有各类迭代器，这是为了让stack/queue符合其后进先出/先进先出的特性。
  此外，二者属于容器适配器： a type of container adaptor。

template <class T, class Container = deque<T> > 
class stack;template <class T, class Container = deque<T> > 
class queue;

template < class T, class Alloc = allocator<T> > 
class vector; template < class T, class Alloc = allocator<T> > 
class list;

  
  2）、使用演示
  以下为使用库中stack和queue的基本演示：

void test_std_01()
{stack<int> st1;//构造st1.push(1);//stack::pushst1.push(2);st1.push(3);st1.push(4);st1.push(5);st1.push(6);cout << "stack_size:" << st1.size() << endl;//stack::while (!st1.empty())//stack::empty{cout << st1.top() << " ";//stack::topst1.pop();//stack::pop}cout << endl;
}

void test_std_02()
{queue<int> qu1;//构造qu1.push(1);//queue::pushqu1.push(2);qu1.push(3);qu1.push(4);qu1.push(5);qu1.push(6);cout << "stack_size:" << qu1.size() << endl;//queue::sizewhile (!qu1.empty())//queue::empty{cout << qu1.front() << " ~ " << qu1.back() << endl;//queue::front、queue::backqu1.pop();//queue::pop}cout << endl;
}

  
  
  

1.2、相关例题

  以下为一些与栈和队列有关的练习，旨在帮助我们熟悉理解相关结构功能。

1.2.1、最小栈

  相关链接

  分析：
  根据题目，本题相当于要实现栈的常见基本接口，相比之下只是多出一个int getMin() 。注意题目要求，常数时间内获取堆栈中的最小元素，即该接口要保持时间复杂度为O(1)。那么，该如何实现呢？
  
  首先，可以考虑到的是，C++中有各种容器，与其像C一样内部需要我们自己实现，这里相对来说便捷的选择是复用SQL，即使用库里的stack进行封装。
  这里有一个方案如下： 在MinStack中建立两个成员变量，一个为std::stack类，用于进行各类pop、push等。另一个为普通变量，用于辅助记录栈中最小元素。

class MinStack {
public://……private:stack<int> _st;int _minval;
};

  思考： 此方案是否可行？
  回答： 这里存在一个问题，假如当前记录的最小元素出栈，那么原先存储在_minval中的最小值将失效。此时，如果要用getMin提取最小元素，那么我们需要遍历栈重新寻找最小值，这样整体下来时间复杂度不符合要求。
  
  改进：既然如此，该如何实现？
  另一方案如下： 新增一个辅助栈_minst。该辅助栈与插入栈_st同步，其作用是记录插入栈_st中插入的最小元素，若该元素出栈，则对应_minst也同步出栈。

  
  代码实现如下：

class MinStack {
public:MinStack() {}void push(int val) {st.push(val);if(minst.empty() || val<=minst.top())//1、注意_minst元素为空时，要插入；2、此处<=是因为存在多组重复最小数，比如3 1 1 2 5 ，这种情况下假如1只入_minst一次，那么_st删除1时，_minst同步删除后，最小值有误。minst.push(val);}void pop() {if(!minst.empty()&& !st.empty() &&st.top()==minst.top())minst.pop();assert(!st.empty());//此处可不写，因为正常使用库中stack，st.pop中会检测st.pop();}int top() {return st.top();}int getMin() {return minst.top();}
private:stack<int> st;stack<int> minst;
};

  注意事项：
  ①、MinStack()构造函数需要我们手动写吗？
  回答：不需要。其一，这里我们可以直接将该接口删除，这时候会生成默认构造函数，其对内置类型不做处理，对自定义类型会调用它自己的构造函数。这里MinStack的类成员恰好是自定义类型。其二，即使将该接口保留但什么也不做，这样也是可行的，因为自定义类型成员变量一定会先进过初始化列表初始化。
  
  ②if(minst.empty() || val<=minst.top())
  minst.empty() ：_minst元素为空时，要插入；
  val<=minst.top()：此处<=是因为存在多组重复最小数，比如3 1 1 2 5 ，这种情况下假如1只入_minst一次，那么_st删除1时，_minst同步删除后，最小值有误。
  
  
  扩展延伸：
  问题：假如我们需要插入大量重复数据（特点：数据量很大，数据中重复数多），上述方法是否存在问题，可以如何改进？
  回答：在该情况下，如果我们直接使用上述方法，从空间角度上讲消耗很大。一个解决方案是对_minst做改进，添加一个计数器：

struct conutval
{int val;int count;
}stack<int> st;
stack<countval> minst;

  
  

1.2.2、栈的压入、弹出序列

  相关链接

  
  分析：从逻辑角度判断某个出栈方式是否正确这很容易，但如何用代码控制实现该过程呢？以下给出了一种思路：模拟出栈过程。
  

class Solution {
public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {stack<int> st;//辅助栈：用于模拟出栈过程int popi=0;//用于遍历popV该vector的下标变量for(auto pushVal:pushV)//遍历pushV中数据{st.push(pushVal);//无论结果如何都将pushV中数据插入栈中while(!st.empty() && popV[popi]==st.top())//比较的是辅助栈和popV，使用while是为了持续匹配{popi++;st.pop();}}return st.empty();}
};

  
  
  

1.2.3、逆波兰表达式求值

  相关链接：关于波兰表达式（前缀表达式）和逆波兰表达式（后缀表达式）的两个词条介绍。
  题目链接

  问题： 后缀表达式是什么，如何运算？
  后缀表达式是一种把操作数写在前面，把运算符写在后面的表示方法。例如：我们日常写的中缀表达式1+2*2，在转换为后缀表达式则为1 2 2 * +。
  对于运算：需要借助一个栈。1、若遇到的是操作数，我们将其入栈，若遇到的是操作符，则连续取两次栈顶元素，与当前操作符进行运算，最后再将得到结果入栈。

  
  实现如下：

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto& str:tokens){if(str=="+"||str=="-"||str=="*"||str=="/")//若为操作符，取栈中元素运算{//取值int rightval=st.top();st.pop();int leftval=st.top();st.pop();//运算switch(str[0]){case '+':st.push(leftval+rightval);break;case '-':st.push(leftval-rightval);break;case '*':st.push(leftval*rightval);break;case '/':st.push(leftval/rightval);break;}}else//若为操作数，则一律入栈{st.push(stoi(str));}}return st.top();//最后，将栈顶结果返回}
};

  注意事项：
  ①if(str=="+"||str=="-"||str=="*"||str=="/")：这里实际上是string::operator==的运用。使用字符串而非字符是因为给定的数据是string，可能存在“-23”这类负数情况，需要与减号“-”区分。
  ②switch(str[0])：switch…case语句需要输入整型表达式，故而我们不可以直接使用switch(str)来判断，这里取了其首字符，这是因为这里的操作符+、、*、/本身即单字符。
  
  
  
  
  

2、适配器介绍

2.1、引入：如何实现一个栈/队列（1.0版本）

  1）、模拟实现栈1.0
  在C语言中我们曾从零开始模拟实现过栈，此处C++中如果我们自己手动实现一个效果大差不差，故这里。而C++中有各类容器，我们可以封装一下vector，用其来模拟实现stack。效果如下：
  
  这是需要的基本接口：

//C++98：
void push (const value_type& val);
void pop();value_type& top();
const value_type& top() const;size_type size() const;
bool empty() const;

  
  以下为模拟实现：

namespace My_Stack_Queue
{template<class T>class stack{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top()const{return _con.back();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:vector<T> _con;};
}

  
  验证结果如下：

void test_stack_01()
{My_Stack_Queue::stack<int> st1;//构造st1.push(1);//stack::pushst1.push(2);st1.push(3);st1.push(4);st1.push(5);st1.push(6);cout << "stack_size:" << st1.size() << endl;//stack::sizewhile (!st1.empty())//stack::empty{cout << st1.top() << " ";//stack::topst1.pop();//stack::pop}cout << endl;
}

  
  

2.2、适配器：如何实现一个栈/队列（2.0版本）

  1）、模拟实现栈2.0

  观察库里的stack、queue和list、vector，可看到这里有一个Container，实际上这是一种容器适配器。适配器是一种设计模式，该种模式是将一个类的接口转换成希望达成的另外一个接口。其作用是能让我们按照自己的需求转换接口。
  我们实现的stack1.0版本中，其默认底层封装的是vector，相当于我们将其接口写死固定为vector，这样就不能做到上述描述的任意转换（根据之前所学，栈可以用vector数组结构实现，也可以用list链表结构实现）。
  那么，要做到转换自如，即适配器模式，该如何调整这里的模拟实现呢？
  一个简单的方法是使用模板，别把接口写死。
  class Container = deque<T>，添加一个模板参数。这里为其赋予了一个缺省参数deque，也是SQL中的一种双开口的"连续"空间的数据结构，我们模拟实现时也依照库里的来：

	template<class T, class Container = deque<T>>class stack{public://……//此处实现不变private:Container _con;};

  如下图，我们只需要控制模板实例化时的参数，就能得不同封装下的stack：class Container = deque<T>，我们使用哪一个容器并不重要，只要其能实现stack的相关功能即可（底层角度不同，但上层使用相同）。比如这里，使用vector或者list都能适配出stack。

  
  
  总体效果如下：

	template<class T, class Container = deque<T>>class stack{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_back();}T& top(){return _con.back();}const T& top()const{return _con.back();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:Container _con;};

void test_stack_01()
{My_Stack_Queue::stack<int,vector<int>> st1;//构造st1.push(1);//stack::pushst1.push(2);st1.push(3);st1.push(4);st1.push(5);st1.push(6);cout << "stack_size:" << st1.size() << endl;//stack::sizewhile (!st1.empty())//stack::empty{cout << st1.top() << " ";//stack::topst1.pop();//stack::pop}cout << endl;My_Stack_Queue::stack<int, list<int>> st2;//构造st2.push(1);//stack::pushst2.push(2);st2.push(3);st2.push(4);st2.push(5);st2.push(6);cout << "stack_size:" << st2.size() << endl;//stack::sizewhile (!st2.empty())//stack::empty{cout << st2.top() << " ";//stack::topst2 .pop();//stack::pop}cout << endl;
}

  
  
  2）、模拟实现队列2.0
  同理，我们可以实现队列，以下是基本的接口:

//C++98
void push (const value_type& val);
void pop();value_type& front();
const value_type& front() const;value_type& back();
const value_type& back() const;size_type size() const;
bool empty() const;

  
  实现如下：

	template<class T,class container=deque<T>>class queue{public:void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();}T& front(){return _con.front();}T& back(){return _con.back();}const T& front()const{return _con.front();}const T& back()const{return _con.back();}size_t size()const{return _con.size();}bool empty()const{return _con.empty();}private:container _con;};

  
  测试如下：

void test_queue_01()
{My_Stack_Queue::queue<int> qu1;//构造qu1.push(1);//queue::pushqu1.push(2);qu1.push(3);qu1.push(4);qu1.push(5);qu1.push(6);cout << "stack_size:" << qu1.size() << endl;//queue::sizewhile (!qu1.empty())//queue::empty{cout << qu1.front() << " ~ " << qu1.back() << endl;//queue::front、queue::backqu1.pop();//queue::pop}cout << endl;My_Stack_Queue::queue<int, list<int>> qu2;//构造qu2.push(1);//queue::pushqu2.push(2);qu2.push(3);qu2.push(4);qu2.push(5);qu2.push(6);cout << "stack_size:" << qu2.size() << endl;//queue::sizewhile (!qu2.empty())//queue::empty{cout << qu2.front() << " ~ " << qu2.back() << endl;//queue::front、queue::backqu2.pop();//queue::pop}cout << endl;
}

  问题： queue能否使用vector适配？
  回答：根据我们上述实现的方法，由于存在push.front，该接口vector无法提供，故不能使用其进行queue的适配。这里使用库里的vector和queue也会报错：即不支持。

	std::queue<int, vector<int>> qu2;//构造qu2.push(1);//queue::pushqu2.push(2);qu2.push(3);qu2.push(4);qu2.push(5);qu2.push(6);cout << "stack_size:" << qu2.size() << endl;//queue::sizewhile (!qu2.empty())//queue::empty{cout << qu2.front() << " ~ " << qu2.back() << endl;//queue::front、queue::backqu2.pop();//queue::pop}cout << endl;

  
  
  总结： 适配器的引入一个便捷之处在于，假如我们不想用库提供的这些类，我们也可以根据自己的需求写一个封装进去。
  
  

2.3、deque双端队列简单介绍

  相关链接

  
  
  
  

3、优先级队列priority_queue

3.1、基本介绍

  1）、priority_queue的基础介绍
  相关链接

  基本说明： 优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。注意：默认情况下priority_queue是大堆。
  
  关于优先级高低问题： 虽然默认是大堆，但判断优先级高低需要根据实际场景而定，不同类型，比如int、char所获得结果不同。
  
  
  2）、使用演示

  其构造函数如下：

explicit priority_queue (const Compare& comp = Compare(),const Container& ctnr = Container());template <class InputIterator>priority_queue (InputIterator first, InputIterator last,const Compare& comp = Compare(),const Container& ctnr = Container());

  代码演示一：

void test_priority_queue_01()
{priority_queue<int> pq;pq.push(3);pq.push(1);pq.push(6);pq.push(2);pq.push(5);pq.push(7);pq.push(0);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}
}

  验证如下：可以看到默认其建立的是大堆。

  
  根据上述可知，priority_queue同样没有迭代器，不过我们构造时可使用一段范围区间构造：InputIterator first, InputIterator last。例子如下：

	int a[] = { 3,1,6,2,5,7,0,8,4,9 };priority_queue<int> pq2 = { a,a + sizeof(a) / sizeof(int) };while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}

  
  3）、一道例题：

  相关链接

  代码如下：

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {//建堆：O(N)priority_queue<int> maxHeap(nums.begin(),nums.end());//取前K-1个数:O(logN*k)while(--k)//此写法下要用前置自减{maxHeap.pop();}//取第K个数return maxHeap.top();}
};

  
  
  

3.2、模拟实现

template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> > 
class priority_queue;

3.2.1、1.0：基础框架实现

  我们先实现一个基础版本，根据先前所属，优先级队列从物理角度空间连续，从逻辑角度其底层实际是堆。因此，我们需要将给定的数据构成堆的结构即可。
  priority_queue中基本成员变量：

	template<class T, class container = vector<T>>class priority_queue{public://……private:container _con;};

  
  1）、priority_queue::push、adjust_up

//C++98
void push (const value_type& val);

		void push(const T& val){_con.push_back(val);//先尾插adjust_up(_con.size() - 1);//为了保持堆特性：使用向上调整函数}

		void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child>0)//默认大堆{if(_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}

  
  
  2）、priority_queue::pop、adjust_down

		void pop(){std::swap(_con.front(), _con.back());//首位数据交换_con.pop_back();//尾删adjust_down(0);//向下调整头部元素到适合位置}

		void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child<_con.size()){//大堆if (child+1<_con.size() && _con[child + 1] > _con[child])//修正左右孩子{child++;}if (_con[child] > _con[parent]){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}

  
  
  3）、priority_queue::top

//C++98
const value_type& top() const;

		const T& top()const{return _con[0];}

  
  
  4）、迭代器区间构造

		template <class InputIterator>priority_queue(InputIterator first, InputIterator last){//插数while (first != last){_con.push_back(*first);++first;}//自下而上建堆：向下调整函数for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){adjust_down(i);}}

  
  
  5）、priority_queue::empty、priority_queue::size

//C++98
bool empty() const;
size_type size() const;

		bool empty()const{return _con.empty();}size_t size()const{return _con.size();

  
  
  6）、结果验证

void test_my_priority_queue_01()
{my_priority_queue::priority_queue<int, vector<int>> pq;pq.push(3);pq.push(1);pq.push(6);pq.push(2);pq.push(5);pq.push(7);pq.push(0);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;int a[] = { 3,1,6,2,5,7,0,8,4,9 };my_priority_queue::priority_queue<int,vector<int>> pq2 = { a,a + sizeof(a) / sizeof(int) };while (!pq2.empty()){cout << pq2.top() << " ";pq2.pop();}}

  
  
  

3.2.2、2.0：加入仿函数

  在上述1.0版本的实现中，我们建立起的是大堆，如果需要小堆则要求我们手动调整adjust_down和adjust_up中的关系运算符。而实际中手动去修改priority_queue内部结构不现实。那么，有什么解决方案呢？
  回想C中我们学习qsort时，也涉及这样的比较，在那里我们使用的是函数指针compar，C++中，相比于函数指针，我们使用的是仿函数。
  
  1）、仿函数基本演示

  仿函数是什么： 通俗来讲，仿函数也称为函数对象，本质是一个类，可重载运算符operator()，那么 类对象可以像函数一样去使用。
  演示如下：

namespace fun
{template<class T> //使用了类模板定义类型：泛型struct less//也可以使用class,但需要注意public该运算符重载{bool operator()(const T& A, const T& B)const //()是可以进行运算符重载的{return A < B; //这里less小于，根据需求我们返回小于号}};template<class T>struct greater{bool operator()(const T& A, const T& B)const{return A > B;}};
}

  验证如下：

void test_fun_01()
{fun::greater<int> lsFunc1;cout << "lsFunc1(2, 1): " << lsFunc1(2, 1) << endl;cout << "lsFunc1(4, 5): " << lsFunc1(4, 5) << endl;fun::less<int> lsFunc2;cout << "llsFunc2(2, 8): " << lsFunc2(2, 8) << endl;cout << "llsFunc2(9, 1): " << lsFunc2(9, 1) << endl;
}

  
  
  
  2）、在优先级队列中加入仿函数
  观察库中priority_queue，其默认给的仿函数是大堆--less，小堆--greater，我们在此基础上修改1.0中模拟实现。

template <class T, class Container = vector<T>,  class Compare = less<typename Container::value_type> > 
class priority_queue;

  
  相关代码如下：整体逻辑不变，我们只是加入了两个结构体定义的仿函数，并修改调整adjust_down和adjust_up中的写法：

namespace my_priority_queue
{template<class T>struct less{bool operator()(const T& left, const T& right)const{return left < right;}};template<class T>struct greater{bool operator()(const T& Aleft, const T& right)const{return left > right;}};template<class T, class container = vector<T>, class Compare = less<T>>class priority_queue{public:priority_queue()//无参构造{}template <class InputIterator>priority_queue(InputIterator first, InputIterator last)//迭代器构造{//插数while (first != last){_con.push_back(*first);++first;}//自下而上建堆：向下调整函数for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i){adjust_down(i);}}void push(const T& val){_con.push_back(val);//先尾插adjust_up(_con.size() - 1);//为了保持堆特性：使用向上调整函数}void pop(){std::swap(_con.front(), _con.back());//首位数据交换_con.pop_back();//尾删adjust_down(0);//向下调整头部元素到适合位置}const T& top()const{return _con[0];}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}private:void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0)//默认大堆{//if (_con[child] > _con[parent])if(com(_con[parent],_con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//大堆--less//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//修正左右孩子if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}//if (_con[child] > _con[parent])if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}container _con;};
}

  
  写法一：Compare com

		void adjust_up(size_t child){Compare com;size_t parent = (child - 1) / 2;while (child > 0)//默认大堆--less{//if (_con[child] > _con[parent])if(com(_con[parent],_con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){Compare com;size_t child = parent * 2 + 1;while (child < _con.size()){//大堆--less//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//修正左右孩子if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){child++;}if (com(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}

  
  写法二：匿名对象

		void adjust_up(size_t child){size_t parent = (child - 1) / 2;while (child > 0)//默认大堆{//if (_con[child] > _con[parent])if (Compare()(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(size_t parent){size_t child = parent * 2 + 1;while (child < _con.size()){//大堆--less//if (child + 1 < _con.size() && _con[child + 1] > _con[child])//修正左右孩子if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1])){child++;}//if (_con[child] > _con[parent])if (Compare()(_con[parent], _con[child])){std::swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}

  
  
  

4、反向迭代器相关

4.1、基本介绍

  1）、正向迭代器、反向迭代器对比
  在list模拟实现中，我们遗留下一个问题，关于反向迭代器的模拟实现。

  先来看看二者区别：

  以上是我们认知的begin(有效首元素)、end(有效尾元素的下一个位置)、rbegin(反向有效首元素)、rend(反向有效尾元素的下一个位置)的相关指向。
  以list举例，我们已经实现过正向的迭代器，那么其反向迭代器该如何实现？
  观察正向、反向迭代器区别，其需要实现的运算符重载大差不差，只是对于正向迭代器，operator++是向后挪动，而反向迭代器恰好与之相反，operator--同理。其余operator*、operator->所得结果一致。

		//++ititerator& operator++(){_node = _node->_next;return *this;}//--ititerator& operator--(){_node = _node->_prev;return *this;}

  因此一个实现方案是，根据正向迭代器的实现方法，同理创建一个struct __reverse_list_iterator的类，用于实现反向迭代器，其内部与struct __list_iterator相差无几，只需要对++、--做适当的方向处理即可。比如：

对正向：operator++()中，_node = _node->_next;
对反向，operator++()中，_node = _node->_prev;

  
  以上方法虽然可行，但其只针对list类，类似于vector、stirng这样的类，其迭代器为原生指针，++指针所得结果是向后移一位，这样，上述方法就不具有普适性。此外，迭代器本身功能相似，上述方法为了实现反向迭代器，还得重新创建一个类，是否有简化操作？
  
  即，有没有什么方法，能够实现上述多种容器下的反向迭代器，又能够尽可能的复用我们已经实现的功能？
  

4.2、框架实现

4.2.1、框架搭建1.0：非对称性

  基于上述问题，我们可以考虑如何复用正向迭代器来实现反向迭代器。以下为一个框架搭建：

	template<class Iterator, class Ref, class Ptr>struct __reverse_iterator{typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;//重命名Iterator _cur;//成员变量：当前指向__reverse_iterator(Iterator it)//反向迭代器构造：使用正向迭代器构造:_cur(it){}RIterator operator++(){--_cur;return *this;}RIterator operator--(){++_cur;return *this;}Ref operator*(){return *_cur;}Ptr operator->(){return &(*_cur);}bool operator!=(const RIterator& it){return _cur != it._cur;}};

  
  
  

4.2.2、框架搭建2.0：对称性

  1）、情况说明

  观察库中实现，我们发现其对反向迭代器进行了对称性设计：

//stl_list.h:正向迭代器
iterator begin() { return (link_type)((*node).next); }
iterator end() { return node; }
//stl_list.h:反向迭代器
reverse_iterator rbegin() { return reverse_iterator(end()); }
reverse_iterator rend() { return reverse_iterator(begin()); }

  这种设计情况下会存在一个问题：如果直接使用我们上述1.0中的模拟实现，对rbegin解引用，实际指向的哨兵位的头结点：

		Ref operator*(){return *_cur;}

  这也是为什么反向迭代器在设置时，做了如下处理：*--tmp先自减，再解引用。

//stl_iterator.hreference operator*() const {Iterator tmp = current;return *--tmp;}

  问题： 为什么这里要创建一个新的临时变量tmp？
  回答： 我们只是需要获取到正确的指向位置，而不改变current当前迭代器指针，如果直接使用*--current，相当于进行了operator--()的运算符重载。
  
  
  2）、模拟实现
  基于上述，我们再来完善修改以下1.0中的反向迭代器框架：

	template<class Iterator, class Ref, class Ptr>struct __reverse_iterator{typedef __reverse_iterator<Iterator, Ref, Ptr> RIterator;//重命名Iterator _cur;__reverse_iterator(Iterator it):_cur(it){}RIterator operator++(){--_cur;return *this;}RIterator operator++(int)//修改处一{auto tmp;--_cur;return tmp;}RIterator operator--(){++_cur;return *this;}RIterator operator--(int){auto tmp;++_cur;return tmp;}Ref operator*(){auto tmp = _cur;--tmp;return *tmp;}Ptr operator->(){return &(operator*());//修改处二}bool operator!=(const RIterator& it){return _cur != it._cur;}};

  
  相应的在list.h中需要加入参数如下：

		//反向迭代器typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __reverse_iterator<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());}

  
  结果演示如下：

	mylist::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);mylist::list<int>::reverse_iterator it = lt.rbegin();while (it != lt.rend()){cout << *it << " ";++it;}cout << endl;

  
  

4.3、与适配器融合理解

4.3.1、通用性说明

  一个问题：上述实现的反向迭代器，能否适配vector？
  回答：一样可以。

  以下为相关演示：
  vector.h文件中将相同代码包含进去；

		//反向迭代器typedef __reverse_iterator<iterator, T&, T*> reverse_iterator;typedef __reverse_iterator<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());}

  

void vector_test_04()//验证正、反迭代器
{myvector::vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);myvector::vector<int>::iterator lt = v.begin();while (lt != v.end()){cout << *lt << " ";++lt;}cout << endl;myvector::vector<int>::reverse_iterator rlt = v.rbegin();while (rlt != v.rend()){cout << *rlt << " ";++rlt;}cout << endl;}

  
  
  

4.3.2、迭代器类型简单介绍

  一个问题：上述的反向迭代器能适用于SQL的所有容器吗？
  要回答此问题首先要知晓迭代器的分类，从功能性角度上来说，可以将迭代器分为一下三种：

类型	功能	举例
forward_iterator单向迭代器	++	< forward_list >、< unordered_map >、< unordered_set >
bidirectional_iterator双向迭代器	++、- -	< list >、< map >、< set >
random_access_iterator 随机迭代器	++、- -、+n、-n	< vector >、< deque >

  
  这也说明了库里不同函数，其需求的迭代器类型的区别：