• c++ - 第11节 - stack和queue类

    目录

    1.标准库中的stack类

    1.1.stack类

    1.2.stack类的常用接口说明

    1.3.stack类练习题

    1.4.stack类的模拟实现

    2.标准库中的queue类

    2.1.queue类

    2.2.queue类的常用接口说明

    2.3.queue类的模拟实现

    3.标准库中的priority_queue类

    3.1.priority_queue类

    3.2.priority_queue类的常用接口说明

    3.3.priority_queue类的模拟实现

    4.deque的简单介绍

    5.反向迭代器介绍

    5.1.反向迭代器源码分析

    5.2.反向迭代器代码实现

    1.标准库中的stack类

    1.1.stack类

    stack类的文档介绍：https://cplusplus.com/reference/stack/stack/?kw=stack

    注：

    1. stack是一种容器适配器，专门用在具有后进先出操作的上下文环境中，其删除只能从容器的一端进行元素的插入与提取操作。
    2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，将特定类作为其底层的，元素特定容器的尾部(即栈顶)被压入和弹出。
    3. stack的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类，这些容器类应该支持以下操作：
    empty：判空操作
    back：获取尾部元素操作
    push_back：尾部插入元素操作
    pop_back：尾部删除元素操作
    4. 标准容器vector、deque、list均符合这些需求，默认情况下，如果没有为stack指定特定的底层容器，默认情况下使用deque。

    5.下图所示是官方库中链表list、栈stack、队列queue的声明和栈stack、队列queue的介绍。严格地说，list是一种容器，而stack和queue是一种容器适配器，从下图可以看出，链表list声明的第二个参数是一个空间配置器，栈stack和队列queue的第二个参数是一个容器

    栈stack、队列queue（包括后面的priority_queue）是容器适配器，也就是说他们不是自己原生实现的，他们是依靠包装容器适配出来的

    1.2.stack类的常用接口说明

    使用stack前的说明：

    1.使用stack类需要包含stack的头文件，代码为：#include

    注：这里不是包含stack.h是因为会和c语言的库函数冲突，不能直接包含stack.cpp是因为如果项目里面同时两个人都包含stack.cpp，那么就会造成重定义

    2.stack类是在std里面的，因此使用stack类需要using namespace std将std展开（如果不展开每次使用stack类需要std::stack）

    注：std和iostream是无关的，只不过帮助进行输入输出的cout、cin、enl等是在std里面定义的。如果不输入输出，不包含iostream也可以使用stack类，但是需要展开std

    stack的接口：

    函数名称

    功能说明

    stack()
    构造空的栈
    empty()
    检测stack是否为空
    size()
    返回stack中元素的个数
    top()
    返回栈顶元素的引用
    push()
    将元素val压入stack中
    pop()
    将stack中尾部的元素弹出

    注：

    1.stack里面没有迭代器，因为栈这种数据结构让你随便去遍历反而是不好的，如果随便遍历就保证不了后进先出的功能了，栈里面数据的遍历代码如下图所示

    1.3.stack类练习题

    练习题一：

    题目描述：

    题目链接：155. 最小栈 - 力扣（LeetCode）

    思路：

    思路1：建立两个栈st和minst，st是正常的栈存储数据，minst存储最小值数据。插入时插入到st栈中，插入的值如果大于minst栈top的值，则minst栈再插入top的值，插入的值如果小于minst栈top的值，则minst栈插入st栈插入的值。st栈pop删除数据的时候，minst也跟着删除数据。

    例如：st插入5，目前最小值是5，则minst插入5；st插入8，目前最小值是5，则minst再插入5；st插入7，目前最小值是5，则minst再插入5；st插入2，目前最小值是2，则minst插入2，如下图一所示，st进行删除，那么minst也要进行删除，如下图二所示。像前面的操作如果想要得到栈的最小值，直接取minst的的top即可。

      

    上面的思路可以优化一下，见下面思路2。

    思路2：建立两个栈st和minst，st是正常的栈存储数据，minst存储最小值数据。插入时插入到st栈中，插入的值如果大于minst栈top的值，不做处理，插入的值如果小于minst栈top的值，则minst栈插入st栈插入的值。st栈pop删除数据的时候，如果st删除的数据大于minst栈top的值，不做处理，如果st删除的数据等于minst栈top的值（不存在st删除的数据大于minst栈top的值的情况），minst也跟着删除数据，如下图所示。

    代码：

    练习题二：

    题目描述：

    题目链接：栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)

    思路:

    入栈序列先入栈，每次入栈以后，栈顶跟出栈序列比较，有两种情况：

    情况一：能匹配：出栈序列往后，出战。

    情况二：不能匹配：有两种情况：（1）如果入栈序列没有走到尾，说明这个数据可能还没入栈，继续入栈（2）如果入栈序列已经走到尾，说明数据一定在栈中，只是顺序不对，出栈序列非法

    例1：输入[1 2 3 4 5]和[4 5 3 2 1]序列

    出栈序列指向4，入栈序列入栈1，和出栈序列4不匹配，入栈序列入栈2，和出栈序列4不匹配，入栈序列入栈3，和出栈序列4不匹配，入栈序列入栈4，和出栈序列4匹配，出栈序列指向5，入栈序列3，和出栈序列5不匹配，入栈序列入栈5，和出栈序列5匹配，出栈序列指向3，入栈序列3，和出栈序列3匹配，出栈序列指向2，入栈序列2，和出栈序列2匹配，出栈序列指向1，入栈序列1，和出栈序列1匹配，出栈序列没问题

    例2：输入[1 2 3 4 5]和[4 3 5 1 2]序列

    出栈序列指向4，入栈序列入栈1，和出栈序列4不匹配，入栈序列入栈2，和出栈序列4不匹配，入栈序列入栈3，和出栈序列4不匹配，入栈序列入栈4，和出栈序列4匹配，出栈序列指向3，入栈序列3，和出栈序列3匹配，出栈序列指向5，入栈序列2，和出栈序列5不匹配，入栈序列入栈5，和出栈序列5匹配，出栈序列指向1，入栈序列2，和出栈序列1不匹配，入栈序列已经走到尾，出栈序列非法

    代码：

    注：上面 return popi==popV.size 和 return st.empty() 两种结束条件都是可以的

    练习题三：

    题目描述：

    题目链接：150. 逆波兰表达式求值 - 力扣（LeetCode）

    思路：（后缀表达式计算的思路）

    从前往后依次取数据：

    （1）如果是操作数：将操作数入栈

    （2）如果是运算符：取连续两个栈顶数据进行运算，运算结果继续入栈

    数据走完将栈里的操作数出栈，出栈的值就是结果值

    例：计算后缀表达式123*+的结果

    首先遇到数据1，1是操作数将1入栈，此时栈里的数据为1，走到数据2，2是操作数将2入栈，此时栈里的数据为12，走到数据3，3是操作数将3入栈，此时栈里的数据为123，走到数据*，*是运算符，取连续两个栈顶数据3和2进行运算，结果为2*3=6（连续出两个先出来的是运算符的右操作数，后出来的是运算符的左操作数），将结果6入栈，此时栈里的数据为16，走到数据+，+是运算符，取连续两个栈顶数据6和1进行运算，结果为6+1=7，将7入栈，数据取完将栈里面操作数出栈就是结果，结果为7

    代码：

    注：

    1.中缀表达式就是操作符在中间，后缀表达式就是操作符在后面（我们平时写的都是中缀表达式）

    中缀表达式1+2*3转化为后缀表达式就是123*+，后缀表达式123*+的意思就是2和3相乘，然后1加上2和3相乘的结果。本题是给你后缀表达式，让你计算出结果。

    2.本题是后缀表达式计算的问题。还有道题是中缀表达式计算的问题，中缀表达式计算问题的解法是先将中缀表达式转成后缀表达式，将计算后缀表达式的值即可，后缀表达式的计算问题我们已经会了，将中缀表达式转成后缀表达式的思路如下所示

    思路：（中缀表达式转成后缀表达式的思路）

    从前往后依次取数据：

    （1）遇到操作数：将操作数输出或者存储（输出还是存 储是看转成后的表达式输出还是存储）

    （2）遇到运算符：跟栈顶运算符进行比较，如果栈为空或者比栈顶运算符优先级高就将其入栈，然后再往下取数据；如果比栈顶运算符优先级低或者优先级一样就出栈顶的操作符，然后继续和此时栈顶运算符比较......

    数据走完将栈里的运算符依次出栈

    例：将中缀表达式1+2*3/2-5转成后缀表达式

    首先遇到数据1，1是操作数进行存储，存储空间此时为1，走到数据+，+是运算符，此时栈为空运算符+入栈，走到数据2，2是操作数进行存储，存储空间此时为12，走到数据*，*是运算符，*运算符比栈顶+运算符优先级高，运算符*入栈，走到数据3，3是操作数进行存储，存储空间此时为123，走到数据/，/是运算符，/运算符和栈顶*运算符优先级相同，此时栈顶运算符*出栈，存储空间此时为123*，/运算符继续和此时栈顶运算符+比较，/运算符优先级高，运算符/入栈，走到数据2，2是操作数进行存储，存储空间此时为123*2，走到数据-，-是运算符，-运算符比栈顶/运算符优先级低，此时栈顶运算符/出栈，存储空间此时为123*2/，-运算符继续和此时栈顶运算符+比较，-运算符和+运算符优先级相同，此时栈顶运算符+出栈，存储空间此时为123*2/+，走到数据5，5是操作数进行存储，存储空间此时为123*2/+5，数据取完将栈里面运算符出栈，存储空间此时为123*2/+5-

    3.switch语句case的后面不能跟字符串，系统会报错，如果本题判断操作数和运算符时一定要使用switch语句case后面要取字符串的第一个字符，例如取"-"第一个字符，但是这样"-"和"-5"就无法区分了，还得再用字符串长度来区分，较麻烦，所以此处我们使用if语句。if语句中操作数和运算符已经区分开了（"-"和"-5"已经区分开了），我们使用switch语句来区分"+"、"-"、"*"、"/"

    1.4.stack类的模拟实现

    test.cpp文件：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. using namespace std;
    11.  
    12. #include "Stack.h"
    13.  
    14.  
    15. int main()
    16. {
    17. 	bit::test_stack();
    18.  
    19. 	return 0;
    20. }

    stack.h文件：

    1. #pragma once
    2.  
    3. namespace bit
    4. {
    5. 	template<class T, class Container = deque>
    6. 	class stack
    7. 	{
    8. 	public:
    9. 		void push(const T& x)
    10. 		{
    11. 			_con.push_back(x);
    12. 		}
    13.  
    14. 		void pop()
    15. 		{
    16. 			_con.pop_back();
    17. 		}
    18.  
    19. 		const T& top()
    20. 		{
    21. 			return _con.back();
    22. 		}
    23.  
    24. 		size_t size()
    25. 		{
    26. 			return _con.size();
    27. 		}
    28.  
    29. 		bool empty()
    30. 		{
    31. 			return _con.empty();
    32. 		}
    33. 	private:
    34. 		Container _con;
    35. 	};
    36.  
    37.  
    38. 	void test_stack()
    39. 	{
    40. 		stack<int> s;
    41. 		//stack> s;
    42. 		//stack> s;
    43. 		//stack s; 
    44.  
    45. 		s.push(1);
    46. 		s.push(2);
    47. 		s.push(3);
    48. 		s.push(4);
    49. 		s.push(300);
    50.  
    51. 		while (!s.empty())
    52. 		{
    53. 			cout << s.top() << " ";
    54. 			s.pop();
    55. 		}
    56. 		cout << endl;
    57. 	}
    58. }

    注：

    1.前面我们讲过栈stack是一种适配器，适配器的主要作用就是转换，栈stack的功能是实现后进先出功能，实现该功能没必要自己造轮子去实现，可以使用顺序表vector、链表list等很多数据结果去实现，stack类模板的第二个参数是容器Container，给Container参数传什么数据结构就使用该数据结构实现栈stack后进先出的功能。第二个参数有缺省值deque，如果不传该参数默认使用deque这种数据结构来实现栈stack的功能。

    deque的声明如下图所示，deque这种容器适合头尾插入删除（链表的优点），还支持operator[ ]随机访问（vector的优点），既有vector的优点也有list的优点，但是deque也有自己的缺点，具体我们后面会讲

    2.栈stack的成员变量是使用容器Container来定义的自定义对象，该对象用其自己的构造函数、拷贝构造函数、析构函数即可。我们栈stack里面不写这些函数，编译器会自动生成默认的构造函数、拷贝构造函数、析构函数，自动生成默认的函数对于这里自定义类型的对象就会去调用其本身的函数

    3.栈stack里面的入栈push函数、出栈pop函数、查看栈顶元素top函数都可以复用容器Container数据结构的函数来完成，这里复用的函数最好使用各个容器都有的函数以适配各种容器

    4.如下图所示，栈stack可以适配deque来实现、可以适配vector来实现、可以适配list来实现。栈stack可以适配string来实现，但是string类里面无法存储大于127的值，存在截断数据丢失的风险

    2.标准库中的queue类

    2.1.queue类

    queue类的文档介绍：https://cplusplus.com/reference/queue/queue/

    注：

    1. 队列是一种容器适配器，专门用于在FIFO上下文(先进先出)中操作，其中从容器一端插入元素，另一端提取元素。
    2. 队列作为容器适配器实现，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从队尾入队列，从队头出队列。
    3. 底层容器可以是标准容器类模板之一，也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:
       empty：检测队列是否为空
       size：返回队列中有效元素的个数
       front：返回队头元素的引用
       back：返回队尾元素的引用
       push_back：在队列尾部入队列
       pop_front：在队列头部出队列
    4. 标准容器类deque和list满足了这些要求。默认情况下，如果没有为queue实例化指定容器类，则使用标准容器deque。

    2.2.queue类的常用接口说明

    使用queue前的说明：

    1.使用queue类需要包含queue的头文件，代码为：#include

    注：这里不是包含queue.h是因为会和c语言的库函数冲突，不能直接包含queue.cpp是因为如果项目里面同时两个人都包含queue.cpp，那么就会造成重定义

    2.queue类是在std里面的，因此使用queue类需要using namespace std将std展开（如果不展开每次使用queue类需要std::queue）

    注：std和iostream是无关的，只不过帮助进行输入输出的cout、cin、enl等是在std里面定义的。如果不输入输出，不包含iostream也可以使用queue类，但是需要展开std

    queue的接口：

    函数名称

    功能说明

    queue()
    构造空的队列
    empty()
    检测队列是否为空，是返回true，否则返回false
    size()
    返回队列中有效元素的个数
    front()
    返回队头元素的引用
    back()
    返回队尾元素的引用
    push()
    在队尾将元素val入队列
    pop()
    将队头元素出队列

    注：

    1.queue里面没有迭代器，因为队列这种数据结构让你随便去遍历反而是不好的，如果随便遍历就保证不了先进先出的功能了，队列里面数据的遍历代码如下图所示

    2.3.queue类的模拟实现

    test.cpp文件：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. using namespace std;
    11.  
    12. #include "Queue.h"
    13.  
    14.  
    15. int main()
    16. {
    17. 	bit::test_queue();
    18.  
    19. 	return 0;
    20. }

    queue.h文件：

    1. #pragma once
    2.  
    3. namespace bit
    4. {
    5. 	template<class T, class Container = deque>
    6. 	class queue
    7. 	{
    8. 	public:
    9. 		void push(const T& x)
    10. 		{
    11. 			_con.push_back(x);
    12. 		}
    13.  
    14. 		void pop()
    15. 		{
    16. 			_con.pop_front();
    17. 		}
    18.  
    19. 		const T& front()
    20. 		{
    21. 			return _con.front();
    22. 		}
    23.  
    24. 		const T& back()
    25. 		{
    26. 			return _con.back();
    27. 		}
    28.  
    29. 		size_t size()
    30. 		{
    31. 			return _con.size();
    32. 		}
    33.  
    34. 		bool empty()
    35. 		{
    36. 			return _con.empty();
    37. 		}
    38. 	private:
    39. 		Container _con;
    40. 	};
    41.  
    42. 	void test_queue()
    43. 	{
    44. 		queue<int> q;
    45. 		//queue> q;
    46. 		//queue> q; 
    47. 		//queue q;
    48.  
    49. 		q.push(1);
    50. 		q.push(2);
    51. 		q.push(3);
    52. 		q.push(4);
    53.  
    54. 		while (!q.empty())
    55. 		{
    56. 			cout << q.front() << " ";
    57. 			q.pop();
    58. 		}
    59. 		cout << endl;
    60. 	}
    61. }

    注：

    1.队列queue和栈stack相同也是一种适配器，如下图所示，队列queue类模板的第二个参数是容器Container，给Container参数传什么数据结构就使用该数据结构实现队列queue先进先出的功能。第二个参数有缺省值deque，如果不传该参数默认使用deque这种数据结构来实现队列queue的功能。

    2.队列queue和栈stack都是适配器，但是有两点不同：

    （1）队列queue不能适配vector，因为queue要实现先进先出功能，出栈的时候要进行头删，vector头删效率很低并且其没有pop_front头删函数。

    （2）栈stack可以适配string但是存在截断的风险，队列queue不能适配list，除了存在截断数据丢失的风险，最主要的原因也是string头删效率很低并且其没有pop_front头删函数。

    3.如下图所示，队列queue可以适配deque来实现、可以适配list来实现。队列queue不能适配string和vector来实现。

    3.标准库中的priority_queue类

    3.1.priority_queue类

    priority_queue类的文档介绍：https://cplusplus.com/reference/queue/priority_queue/

    注：

    1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
    2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
    3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
    4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
       empty()：检测容器是否为空
       size()：返回容器中有效元素个数
       front()：返回容器中第一个元素的引用
       push_back()：在容器尾部插入元素
       pop_back()：删除容器尾部元素
    5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。
    6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

    3.2.priority_queue类的常用接口说明

    使用priority_queue前的说明：

    1.使用priority_queue类需要包含queue的头文件，代码为：#include，

    注：priority_queue类的定义是在queue头文件里的

    2.priority_queue类是在std里面的，因此使用priority_queue类需要using namespace std将std展开（如果不展开每次使用priority_queue类需要std::priority_queue）

    注：std和iostream是无关的，只不过帮助进行输入输出的cout、cin、enl等是在std里面定义的。如果不输入输出，不包含iostream也可以使用priority_queue类，但是需要展开std

    3.优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
    注意：默认情况下priority_queue是大堆。

    priority_queue的接口：

    函数名称

    功能说明

    priority_queue()  priority_queue(first, last)
    构造一个空的优先级队列
    empty( )
    检测优先级队列是否为空，是返回true，否则返回false
    top( )
    返回优先级队列中最大(最小元素)，即堆顶元素
    push(x)
    在优先级队列中插入元素x
    pop()
    删除优先级队列中最大(最小)元素，即堆顶元素

    注：

    1.priority_queue优先级队列官方库里的声明和介绍如下图所示，priority_queue模板第二个参数的默认值vector，也就是说默认使用vector作为其底层存储数据的容器

    priority_queue优先级队列第三个参数默认传的是仿函数less，传less其实是一个大堆（正常传greater才应该是大堆，这里是c++的一个失误），也就是说priority_queue优先级队列默认取的是大堆。如果想控制成小堆，优先级队列模板中第三个参数传greater仿函数即可。

    2.priority_queue里面没有迭代器，因为堆这种数据结构让你随便去遍历反而是不好的，如果随便遍历就保证不了堆的功能了，优先级队列（堆）里面数据的遍历代码如下图所示

    优先级队列默认情况下是一个大堆，如上图所示，如果要使用小堆，应该手动传priority_queue优先级队列模板的第二第三个参数，如下图所示

    3.3.priority_queue类的模拟实现

    模拟实现一：传仿函数实现的版本

    test.cpp文件：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. using namespace std;
    11.  
    12. #include "Priority_queue.h"
    13.  
    14.  
    15. int main()
    16. {
    17. 	bit::test_priority_queue();
    18.  
    19. 	return 0;
    20. }

    Priority_queue.h文件：

    1. #pragma once
    2.  
    3. namespace bit
    4. {
    5. 	template<class T>
    6. 	struct less
    7. 	{
    8. 		bool operator()(const T& x, const T& y) const
    9. 		{
    10. 			return x < y;
    11. 		}
    12. 	};
    13.  
    14. 	template<class T>
    15. 	struct greater
    16. 	{
    17. 		bool operator()(const T& x, const T& y) const
    18. 		{
    19. 			return x > y;
    20. 		}
    21. 	};
    22.  
    23. 	// 优先级队列 -- 大堆 <  小堆 >
    24. 	template<class T, class Container = vector, class Compare = less>
    25. 	class priority_queue
    26. 	{
    27. 	public:
    28. 		void AdjustUp(int child)
    29. 		{
    30. 			Compare comFunc;
    31. 			int parent = (child - 1) / 2;
    32. 			while (child > 0)
    33. 			{
    34. 				//if (_con[parent] < _con[child])
    35. 				if (comFunc(_con[parent], _con[child]))
    36. 				{
    37. 					swap(_con[parent], _con[child]);
    38. 					child = parent;
    39. 					parent = (child - 1) / 2;
    40. 				}
    41. 				else
    42. 				{
    43. 					break;
    44. 				}
    45. 			}
    46. 		}
    47.  
    48. 		void push(const T& x)
    49. 		{
    50. 			_con.push_back(x);
    51.  
    52. 			AdjustUp(_con.size() - 1);
    53. 		}
    54.  
    55. 		void AdjustDown(int parent)
    56. 		{
    57. 			Compare comFunc;
    58. 			size_t child = parent * 2 + 1;
    59. 			while (child < _con.size())
    60. 			{
    61. 				//if (child+1 < _con.size() && _con[child] < _con[child+1])
    62. 				if (child + 1 < _con.size() && comFunc(_con[child], _con[child + 1]))
    63. 				{
    64. 					++child;
    65. 				}
    66.  
    67. 				//if (_con[parent] < _con[child])
    68. 				if (comFunc(_con[parent], _con[child]))
    69. 				{
    70. 					swap(_con[parent], _con[child]);
    71. 					parent = child;
    72. 					child = parent * 2 + 1;
    73. 				}
    74. 				else
    75. 				{
    76. 					break;
    77. 				}
    78. 			}
    79. 		}
    80.  
    81. 		void pop()
    82. 		{
    83. 			assert(!_con.empty());
    84. 			swap(_con[0], _con[_con.size() - 1]);
    85. 			_con.pop_back();
    86.  
    87. 			AdjustDown(0);
    88. 		}
    89.  
    90. 		const T& top()
    91. 		{
    92. 			return _con[0];
    93. 		}
    94.  
    95. 		size_t size()
    96. 		{
    97. 			return _con.size();
    98. 		}
    99.  
    100. 		bool empty()
    101. 		{
    102. 			return _con.empty();
    103. 		}
    104.  
    105. 	private:
    106. 		Container _con;
    107. 	};
    108.  
    109. 	void test_priority_queue()
    110. 	{
    111. 		/*less LessCom;
    112. 		cout << LessCom(1, 2) << endl;
    114. 		greater GreaterCom;
    115. 		cout << GreaterCom(1, 2) << endl;*/
    116.  
    117. 		//priority_queue pq;
    118. 		priority_queue<int, vector<int>, greater<int>> pq;
    119.  
    120. 		pq.push(2);
    121. 		pq.push(5);
    122. 		pq.push(1);
    123. 		pq.push(6);
    124. 		pq.push(8);
    125.  
    126. 		while (!pq.empty())
    127. 		{
    128. 			cout << pq.top() << " ";
    129. 			pq.pop();
    130. 		}
    131. 		cout << endl;
    132. 	}
    133.  
    134. }

    注：

    1.优先级队列priority_queue和队列queue、栈stack相同也是一种适配器，如下图所示，优先级队列priority_queue类模板的第二个参数是容器Container，给Container参数传什么数据结构就使用该数据结构实现优先级队列priority_queue堆的功能。第二个参数有缺省值vector，如果不传该参数默认使用vector这种数据结构来实现优先级队列priority_queue的功能。

    因为堆这种数据结构要进行数据随机访问并且要在中间插入删除数据，所以这里默认值给的是vector是因为vector适合随机访问数据并且比deque更适合在中间插入删除数据。deque适合在头尾插入删除，但是deque随机访问效率不高，且不适合在中间插入删除数据

    2.优先级队列priority_queue插入数据时，调用容器的尾插函数插入之后，此时优先级队列就不是一个堆了，还需要向上调整算法，将此时的优先级队列变成堆。优先级队列priority_queue插入数据代码和向上调整算法（大堆的向上调整算法）如下图所示。这里可以看出优先级队列priority_queue插入数据的时间复杂度为log_{2}^{n}。

      

    3.优先级队列priority_queue删除数据时，删除的是堆顶数据（二叉树的根节点），也就是优先级队列第一个数据，首先将堆顶数据和最后一个数据进行交换，然后调用容器的尾删函数进行删除，此时优先级队列不是一个堆了，还需要向下调整算法，将此时的优先级队列变成堆。优先级队列priority_queue删除数据代码和向下调整算法（大堆的向下调整算法）如下图所示，这里可以看出优先级队列priority_queue删除数据的时间复杂度为log_{2}^{n}。

    4.这里我们是自己实现了向上向下调整算法，其实算法库algorithm里面，有库里面的入堆函数push_heap（核心是向上调整算法）、出堆函数pop_heap（核心是向下调整算法）、建堆函数make_heap、堆排序函数sort_heap、判断是不是堆函数is_heap，如下图所示

    5.返回堆顶元素top函数官方库里的声明如下图所示，value_type就是类模板中的参数T，也就是说top函数的返回类型是const T&类型，这里采用引用返回是为了避免传值返回拷贝构造，提高效率，但是采用引用返回外面就可以修改堆顶的数据了，如果外面可以修改堆顶的数据是一件很危险的事情，外面将堆顶修改了那么堆很可能就不再是一个堆了，所以引用返回还要使用const进行修饰

    6.仿函数（函数对象）介绍：仿函数（函数对象）其实是一个对象，对象对应的类里面对小括号进行重载。平时小括号的使用方式有两个，一个是(表达式)，其作用是加强优先级和类型强转，另一个是函数名(形参表)，其作用是辅助进行函数的调用。仿函数对应的类里面对小括号进行重载重载的其实是函数名(形参表)里面的小括号，如下图所示就是仿函数对应的类less的实现代码。

    此时less就是一个类型，可以使用less定义出对象，定义出来的对象就叫做仿函数或函数对象，使用less类的方式如下图所示，可以用less来比较大小。LessCom是一个less类型的对象，因为LessCom的使用方式就好像函数一样，所以称LessCom这种对象为函数对象或仿函数

    上面的less类定义出来的仿函数只能比较整型，利用模板的知识我们对上面的less类进行改进，如下图所示，其中形参x和y前面用const修饰是为了接收const类型的变量，支持对const类型的变量进行比较

    除了less类，还有一个类叫做greater，less类定义出的对象可以进行小于的比较，greater类定义出的对象可以进行大于的比较，greater类代码如下图一所示，使用代码如下图二所示

    7.前面的优先级队列priority_queue代码我们是写死实现的大堆，无法实现小堆。解决办法是使用仿函数，在优先级队列priority_queue的模板中再加一个参数，如下图一所示，仿函数的类型也是一种类型，既然是类型我们就可以当作参数进行传参。官方库中的大堆对应的是小于，less就是小于比较的，所以如果要使用大堆模板第三个参数就传less，官方库中的小堆对应的是大于，greater就是大于比较的，所以如果要使用小堆模板第三个参数就传greater，如下图二所示可以看出官方库中优先级队列priority_queue的声明第三个参数默认传的是less，所以如果不传第三个参数，默认是大堆

    注意：官方库中是有less和greater仿函数类的，下图二所示的优先级队列声明用的就是官方库中的仿函数类，要使用官方库中的less和greater这些仿函数需要包含functiona头文件，代码为#include

    在优先级队列priority_queue中，我们使用仿函数来进行比较即可，向上调整算法如下图所示，如果要使用大堆传的是less，这里comFunc仿函数就是比较小于的，实现的就是大堆的向上排序算法；如果要使用小堆传的是greater，这里comFunc仿函数就是比较大于的，实现的就是小堆的向上排序算法。

    向下调整算法如下图所示，如果要使用大堆传的是less，这里comFunc仿函数就是比较小于的，实现的就是大堆的向下排序算法；如果要使用小堆传的是greater，这里comFunc仿函数就是比较大于的，实现的就是小堆的向下排序算法。

    模拟实现二：既可以传仿函数也可以传函数指针实现的版本

    test.cpp文件：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include 
    3. #include 
    4. #include 
    5. #include 
    6. #include 
    7. #include 
    8. #include 
    9. #include 
    10. using namespace std;
    11.  
    12. #include "Priority_queue.h"
    13.  
    14. namespace std
    15. {
    16. 	// 商品
    17. 	struct Goods
    18. 	{
    19. 		string _name;
    20. 		double _price;
    21. 		size_t _saleNum;
    22. 		//...
    23.  
    24. 		/*bool operator<(const Goods& g) const
    25. 		{
    26. 			return _price < g._price;
    27. 		}*/
    28. 	};
    29.  
    30. 	struct LessPrice
    31. 	{
    32. 		bool operator()(const Goods& g1, const Goods& g2) const
    33. 		{
    34. 			return g1._price < g2._price;
    35. 		}
    36. 	};
    37.  
    38. 	struct GreaterPrice
    39. 	{
    40. 		bool operator()(const Goods& g1, const Goods& g2) const
    41. 		{
    42. 			return g1._price > g2._price;
    43. 		}
    44. 	};
    45.  
    46. 	struct LessSaleNum
    47. 	{
    48. 		bool operator()(const Goods& g1, const Goods& g2) const
    49. 		{
    50. 			return g1._saleNum < g2._saleNum;
    51. 		}
    52. 	};
    53.  
    54. 	struct GreaterSaleNum
    55. 	{
    56. 		bool operator()(const Goods& g1, const Goods& g2) const
    57. 		{
    58. 			return g1._saleNum > g2._saleNum;
    59. 		}
    60. 	};
    61.  
    62. 	void test_functional()
    63. 	{
    64. 		vector<int> v;
    65. 		v.push_back(2);
    66. 		v.push_back(1);
    67. 		v.push_back(4);
    68. 		v.push_back(5);
    69. 		v.push_back(3);
    70.  
    71. 		for (auto e : v)
    72. 		{
    73. 			cout << e << " ";
    74. 		}
    75. 		cout << endl;
    76.  
    77. 		// less
    78. 		sort(v.begin(), v.end());
    79. 		for (auto e : v)
    80. 		{
    81. 			cout << e << " ";
    82. 		}
    83. 		cout << endl;
    84.  
    85. 		// greater
    86. 		sort(v.begin(), v.end(), greater<int>());
    87. 		for (auto e : v)
    88. 		{
    89. 			cout << e << " ";
    90. 		}
    91. 		cout << endl;
    92.  
    93. 		// 指向数组的原生指针，本身就是天然迭代器
    94. 		int a[6] = { 1, 2, 5, 2, 5, 7 };
    95. 		sort(a, a + 6);
    96. 		sort(a, a + 6, greater<int>());
    97.  
    98. 		Goods gds[4] = { { "苹果", 2.1, 1000}, { "香蕉", 3.0, 200}, { "橙子", 2.2,300}, { "菠萝", 1.5,50} };
    99.  
    100. 		sort(gds, gds + 4, LessPrice());
    101. 		sort(gds, gds + 4, GreaterPrice());
    102. 		sort(gds, gds + 4, LessSaleNum());
    103. 		sort(gds, gds + 4, GreaterSaleNum());
    104. 	}
    105. }
    106.  
    107. int main()
    108. {
    109. 	//std::test_functional();
    110. 	bit::test_priority_queue2();
    111.  
    112. 	return 0;
    113. }
    114.

    Priority_queue.h文件：

    1. #pragma once
    2.  
    3. namespace bit
    4. {
    5. 	template<class T>
    6. 	struct less
    7. 	{
    8. 		bool operator()(const T& x, const T& y) const
    9. 		{
    10. 			return x < y;
    11. 		}
    12. 	};
    13.  
    14. 	template<class T>
    15. 	struct greater
    16. 	{
    17. 		bool operator()(const T& x, const T& y) const
    18. 		{
    19. 			return x > y;
    20. 		}
    21. 	};
    22.  
    23. 	// 优先级队列 -- 大堆 <  小堆 >
    24. 	template<class T, class Container = vector, class Compare = less>
    25. 	class priority_queue
    26. 	{
    27. 	public:
    28. 		priority_queue(const Compare& comFunc = Compare())
    29. 			:_comFunc(comFunc)
    30. 		{}
    31.  
    32. 		template <class InputIterator>
    33. 		priority_queue(InputIterator first, InputIterator last,
    34. 			const Compare& comFunc = Compare())
    35. 			: _comFunc(comFunc)
    36. 		{
    37. 			while (first != last)
    38. 			{
    39. 				_con.push_back(*first);
    40. 				++first;
    41. 			}
    42.  
    43. 			// 建堆
    44. 			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
    45. 			{
    46. 				AdjustDown(i);
    47. 			}
    48. 		}
    49.  
    50. 		void AdjustUp(int child)
    51. 		{
    52. 			int parent = (child - 1) / 2;
    53. 			while (child > 0)
    54. 			{
    55. 				if (_comFunc(_con[parent], _con[child]))
    56. 				{
    57. 					swap(_con[parent], _con[child]);
    58. 					child = parent;
    59. 					parent = (child - 1) / 2;
    60. 				}
    61. 				else
    62. 				{
    63. 					break;
    64. 				}
    65. 			}
    66. 		}
    67.  
    68. 		void push(const T& x)
    69. 		{
    70. 			_con.push_back(x);
    71.  
    72. 			AdjustUp(_con.size() - 1);
    73. 		}
    74.  
    75. 		void AdjustDown(int parent)
    76. 		{
    77. 			size_t child = parent * 2 + 1;
    78. 			while (child < _con.size())
    79. 			{
    80. 				//if (child+1 < _con.size() && _con[child] < _con[child+1])
    81. 				if (child + 1 < _con.size() && _comFunc(_con[child], _con[child + 1]))
    82. 				{
    83. 					++child;
    84. 				}
    85.  
    86. 				//if (_con[parent] < _con[child])
    87. 				if (_comFunc(_con[parent], _con[child]))
    88. 				{
    89. 					swap(_con[parent], _con[child]);
    90. 					parent = child;
    91. 					child = parent * 2 + 1;
    92. 				}
    93. 				else
    94. 				{
    95. 					break;
    96. 				}
    97. 			}
    98. 		}
    99.  
    100. 		void pop()
    101. 		{
    102. 			assert(!_con.empty());
    103. 			swap(_con[0], _con[_con.size() - 1]);
    104. 			_con.pop_back();
    105.  
    106. 			AdjustDown(0);
    107. 		}
    108.  
    109. 		const T& top()
    110. 		{
    111. 			return _con[0];
    112. 		}
    113.  
    114. 		size_t size()
    115. 		{
    116. 			return _con.size();
    117. 		}
    118.  
    119. 		bool empty()
    120. 		{
    121. 			return _con.empty();
    122. 		}
    123.  
    124. 	private:
    125. 		Compare _comFunc;
    126. 		Container _con;
    127. 	};
    128.  
    129. 	bool ComIntLess(int x1, int x2)
    130. 	{
    131. 		return x1 > x2;
    132. 	}
    133.  
    134. 	void test_priority_queue1()
    135. 	{
    136. 		//priority_queue pq;
    137. 		//priority_queue, greater> pq;
    138. 		priority_queue<int, vector<int>, bool(*)(int, int)> pq(ComIntLess);
    139.  
    140. 		pq.push(2);
    141. 		pq.push(5);
    142. 		pq.push(1);
    143. 		pq.push(6);
    144. 		pq.push(8);
    145.  
    146. 		while (!pq.empty())
    147. 		{
    148. 			cout << pq.top() << " ";
    149. 			pq.pop();
    150. 		}
    151. 		cout << endl;
    152. 	}
    153.  
    154. 	void test_priority_queue2()
    155. 	{
    156. 		int a[] = { 1, 4, 2, 7, 8, 9 };
    157. 		priority_queue<int> pq(a, a + 6);
    158. 	}
    159. }

    注：

    1.仿函数的优势：很多场景下，仿函数用来替代函数指针

    例如：前面学习过，c语言实现的qsort函数就需要传函数指针，来规定数据的比较方式，其声明如下图所示；如果用c++实现qsort函数就可以直接用仿函数来实现的

    这里优先级队列priority_queue如果既想使用仿函数实现又想使用函数指针实现，我们定义一个函数ComIntLess用来进行小于比较，定义一个函数ComIntGreater用来进行大于比较，如下图一所示。优先级队列priority_queue模板第三个参数，如果传的是仿函数的类型，那么在priority_queue类中利用仿函数类型定义一个对象，该对象使用小括号操作符就可以调用自己的成员函数，但是优先级队列priority_queue模板第三个参数如果传的是函数指针类型，在priority_queue类中只有该函数类型是调用不了该函数的。

    如下图二中，官方库的priority_queue第一个构造函数第一个参数可以接收一个Compare类型的对象，Compare类型就是模板第三个参数传的类型，其缺省值给的是Compare类型的匿名对象。那么我们实现可以给模板第三个参数Compare传ComIntLess或ComIntGreater的指针类型，然后定义一个Compare类型的成员变量_comFunc，模仿官方库的priority_queue第一个构造函数将ComIntLess或ComIntGreater传参给构造函数，构造函数用const Compare&类型的comFunc来接收，comFunc就是ComIntLess或ComIntGreater函数的别名，使用comFunc初始化_comFunc成员变量那么_comFunc成员变量就指向了ComIntLess或ComIntGreater函数

    这样上面Priority_queue.h文件里的代码既可以给模板第三个参数传仿函数类型，用仿函数来实现，构造的时候使用缺省的compare()匿名对象进行构造即可，成员变量_comFunc就是仿函数。同时也可以传函数指针类型，定义的时候将对应的函数传过去通过构造函数使成员变量_comFunc指向该函数。如下图所示，这样既可以传仿函数也可以传函数指针来实现优先级队列priority_queue的堆功能

    2.正常情况下优先级队列priority_queue使用库里面的less和greater仿函数就可以了，但是有些情况下必须我们显式的去写仿函数，以c++的sort函数为例。

    我们先介绍一下sort函数，下面是官方库中的sort函数声明，使用c++的sort函数必须包含algorithm头文件，代码为#include

    官方库sort函数第二个声明中模板第二个参数是compare，此处如果传less就是排升序，如果传greater就是排降序。如果不传第二个参数就是调用sort第一个声明的函数，其默认是传less也就是排升序。sort的用法如下图所示，要排降序传greater需要传greater()，和优先级队列Priority_queue.h里面传greater相比多加了一个小括号，原因是优先级队列是给类模板传参，需要传的是类型，greater就是类型，sort函数是给sort函数的形参传参，需要传的是变量，greater()是定义出的匿名对象，然后sort函数模板根据形参类型来推导模板参数（模板隐式实例化）

    如果我们自己去创建一个数组，相对数组里面的数据进行排序，也可以使用sort函数，sort函数的参数要求是迭代器，我们创建的数组将首元素指针和尾元素指针传过去也是可以的，因为如果数据存储是连续的，那么原生指针就是天然的迭代器（vector这种连续存储数据的数据结构其迭代器底层也是指针），如下图所示，注意迭代器传数据要求左闭右开

    less和greater仿函数对于内置类型直接使用<或>进行比较，对于自定义类型会去调用对应的自定义类的比较函数operator<或operator>来进行比较，如下图所示

    然而自定义类只能重载一个小于比较函数和一个大于比较函数，如上图所示，如果排序增序重载了价格的小于比较函数，那么如果排序完价格还想进行名字或售卖数量的增序排序就不行了，解决办法是不再使用less和greater仿函数，自己定义仿函数来进行对应场景的比较即可，如下图所示

    这里通过不同的仿函数来控制sort函数不同的比较逻辑，可以看作是一种更高级的泛型编程

    3.优先级队列还有一个构造函数是用迭代器区间进行构造的，其官方声明如下图所示的第二个声明。

    这个构造函数在许多场景下使用起来很方便，比如top-k问题可以直接利用该构造函数将前k个数据建立一个k个数的小堆或大堆。该构造函数的实现如下图一所示，该构造函数的使用如下图二所示。

    4.deque的简单介绍

    虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为栈stack和队列queue只是对其他容器的接口进行了包装，STL中stack和queue默认使用deque容器， priority_queue默认使用vector容器。栈stack、队列queue和优先级队列 priority_queue官方库中的声明如下图所示

    总结：

    stack可以用deque、vector、list适配，用string适配存在风险

    queue可以用deque、list适配，不能用vector、list适配

    priority_queue可以用vector、deque适配，但是不推荐用deque

    vector特点：

    vector的优点：

    （1）适合尾插尾删

    （2）适合随机访问（vector突出的优点）

    （3）CPU高速缓存命中高

    vector的缺点：

    （1）不适合头部或中部的插入删除（需要挪动数据效率低）

    （2）扩容有一定性能消耗，还可能存在一定程度的空间浪费（原因1是删除数据不缩容，原因2是扩容扩少了可能要频繁扩，扩容扩多了就存在空间浪费）

    list特点：

    list的优点：

    （1）任意位置插入删除效率高（时间复杂度为O(1)）（list突出的优点）

    （2）按需申请释放空间

    list的缺点：

    （1）不支持随机访问

    （2）CPU高速缓存命中低

    deque官方库中的声明如下图所示，deque是一个双端队列，是一种双开口的"连续"空间的数据结构，双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为O(1)

    deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际deque类似于一个动态的二维数组，其底层结构如下图所示：

    开辟多个buffer空间，每个buffer空间固定长度，中控数组（本质是指针数组）指向这些buffer用来将这些buffer空间的链接起来。

    当创建第一个buffer时，开辟buffer空间，中控数组中间的元素指向该buffer，从buffer空间开始位置往后存数据；如果进行尾插，不停的尾插导致该buffer数据存满了，那么再创建一个buffer，开辟buffer空间，中控数组最后一个有效元素的下一个元素指向该buffer，从新开辟buffer空间开始位置往后存数据；如果进行头插，开辟buffer空间，中控数组第一个有效元素的上一个元素指向该buffer，从新开辟buffer空间末尾位置往前存数据。

    如果中控数组满了，还是需要扩容的，但是扩容的代价很低

    这样设计出的deque的特点：

    deque的优点：

    （1）头部和尾部插入删除数据效率较高

    （2）支持随机访问：将要访问的下标值除以一个buffer存储的数据个数得到的结果就是在第几个buffer里面，将要访问的下标值模一个buffer存储的数据个数得到的结果就是要访问的数据是该buffer的第几个元素

    （3）扩容的代价小：只需要堆中控数组扩容，中控数组的扩容代价小

    （4）CPU缓存命中率高

    deque的缺点：

    （1）中部的插入删除效率较低：需要挪动数据

    （2）虽然支持随机访问，但是效率相比vector而言还是有差距（频繁的随机访问要小心）

    结论：deque这种数据结构比较均衡，勉强兼具了vector和list的优点，但是他不像vector和list具有那么极致的优点（vector的极致优点是适合随机访问，vector的极致优点是任意位置插入删除效率高），所以平时用的较少

    因为sort排序需要不停的随机访问，并且对于相同的数据sort排序操作是相同的，可以很好的检测不同数据结构随机访问的效率。这里我们就用sort排序来对比vector和deque两种数据结构对于数据任意访问的效率高低

    从上图可以看出，vector随机访问的效率要明显高于deque。

    如下图所示，如果要对deque的数据进行排序，我们可以先将deque的数据拷贝到vector里面，对vector进行排序然后将排序后的数据拷贝回deque，这样比直接对deque里面数据进行排序效率更高。

    注：string、vector、list、deque等类中有一个赋值函数assign函数，deque中的assign函数声明如下图所示，从第一个声明可以看出deque的assign函数支持用一段迭代器区间进行赋值，来取代原本的值

    问题：什么场景适合用deque？

    答：大量头尾插入删除，不需要或偶尔随机访问的场景，例如栈stack和队列queue就适合使用deque（栈stack和队列queue的尾插使用deque如果要扩容开辟一小段空间即可，不用像vector那样扩容开辟大量空间，也不用像list那样不停的开辟小块空间且deque缓存利用率高，并且很适合头尾插入删除），所以栈和队列将deque作为其默认适配容器。

    5.反向迭代器介绍

    前面的内容我们只讲了各种数据结构迭代器的实现，并没有讲反向迭代器的实现，因为反向迭代器也是一个适配器模式，这里我们学习了栈stack和队列queue这种适配器，在这里讲可以更好的理解反向适配器的原理和实现

    5.1.反向迭代器源码分析

    list的反向迭代器源码分析：

    我们可以看到库里面list的反向迭代器是借助正向迭代器实现的。反向迭代器和正向迭代器相比，除了++和--时方向相反，其他操作基本一致。

    如果每一个数据结构string、vector、list、deque等等要实现一个正向迭代器，就得再实现一个反向迭代器，这样很麻烦。源码的思路是对正向迭代器封装适配一下，生成对应的反向迭代器，上图所示的reverse_iterator类就是用来对正向迭代器进行封装适配的。

    那么我们看一下reverse_iterator类的源码，了解是如何进行封装适配的。reverse_iterator类的源码在stl_iterator.h源码库中，如下图所示。

    从上图我们可以看出反向迭代器指向某一位置本质其实是使用里面的迭代器成员变量current指向该位置（current指向某一位置其实又是里面的指针指向该位置）。我们定义反向迭代器变量时，代码类似vector::reverse_iterator rit=v.rbegin()，编译器会将该代码转换成vector::reverse_iterator rit=v.rbegin，这里是将对应容器的正向迭代器Iterator传给这里reverse_iterator的模板参数，在reverse_iterator的类模板中使用正向迭代器Iterator定义一个成员变量current，然后这里调用拷贝构造函数将v.rbegin返回的反向迭代器（v.rbegin先调用reverse_iterator的构造函数构造一个一个反向迭代器然后将其返回）拷贝给rit，这里拷贝构造的本质是将v.rbegin返回的反向迭代器传给拷贝构造函数的引用形参x，将x里面的迭代器Iterator类型成员变量current构造给rit里面的迭代器Iterator类型成员变量current，这样rit里面的成员变量current指向的位置和v.rbegin返回的反向迭代器里面current指向的位置相同，那么可以说此时反向迭代器rit也指向了v.rbegin返回的位置。

    这里operator*运算符重载函数返回的是当前正向迭代器前一个位置的数据，operator++是让迭代器指向当前位置的前一个位置，operator++是让迭代器指向当前位置的后一个位置。

    上图所示是list官方库中rbegin和rend函数的源代码，其中rbegin返回的是用end函数构造的反向迭代器，rend返回的是用begin函数构造的反向迭代器，这样是一种对称设计。如下图所示

    这样我们用反向迭代器遍历上图list数据，反向迭代器遍历代码如下图所示，rit=v.rbegin()，反向迭代器rit开始指向头节点位置，*rit取的是前一个位置的数据也就是4，++rit，rit指向数据4的位置，依次往后，当++rit后，rit指向数据2的位置，*rit取的是前一个位置的数据也就是1，++rit，rit指向数据1的位置，此时rit=rend()跳出循环遍历结束，这样反向迭代器就从后往前依次便利了list的4321数据

    vector的反向迭代器源码分析：

    从上图我们可以看出vector反向迭代器和list反向迭代器实现原理相同，也是利用reverse_iterator类对正向迭代器进行封装适配实现的，并且vector类的rbegin返回的是用end函数构造的反向迭代器，rend返回的是用begin函数构造的反向迭代器，和list相同，如下图所示

    其实所有的数据结构反向迭代器的实现都和list、vector相同，都是利用reverse_iterator类对正向迭代器进行封装适配实现的，并且所有数据结构都是rbegin返回的是用end函数构造的反向迭代器，rend返回的是用begin函数构造的反向迭代器。

    5.2.反向迭代器代码实现

    Reverselterator.h文件：

    1. #pragma once
    2.  
    3. namespace bit
    4. {
    5. 	template<class Iterator, class Ref, class Ptr>
    6. 	struct Reverse_iterator
    7. 	{
    8. 		Iterator _it;
    9. 		typedef Reverse_iterator Self;
    10.  
    11. 		Reverse_iterator(Iterator it)
    12. 			:_it(it)
    13. 		{}
    14.  
    15. 		Ref operator*()
    16. 		{
    17. 			Iterator tmp = _it;
    18. 			return *(--tmp);
    19. 		}
    20.  
    21. 		Ptr operator->()
    22. 		{
    23. 			return &(operator*());
    24. 		}
    25.  
    26. 		Self& operator++()
    27. 		{
    28. 			--_it;
    29. 			return *this;
    30. 		}
    31.  
    32. 		Self& operator--()
    33. 		{
    34. 			++_it;
    35. 			return *this;
    36. 		}
    37.  
    38. 		bool operator!=(const Self& s)
    39. 		{
    40. 			return _it != s._it;
    41. 		}
    42. 	};
    43. }

    List.h文件：

    1. #pragma once
    2. #include 
    3. #include "Reverselterator.h"
    4.  
    5. namespace bit
    6. {
    7. 	template<class T>
    8. 	struct list_node
    9. 	{
    10. 		list_node* _next;
    11. 		list_node* _prev;
    12. 		T _data;
    13.  
    14. 		list_node(const T& val = T())
    15. 			:_next(nullptr)
    16. 			, _prev(nullptr)
    17. 			, _data(val)
    18. 		{}
    19. 	};
    20.  
    21. 	template<class T, class Ref, class Ptr>
    22. 	struct __list_iterator
    23. 	{
    24. 		typedef list_node Node;
    25. 		typedef __list_iterator self;
    26. 		Node* _node;
    27.  
    28. 		__list_iterator(Node* node)
    29. 			:_node(node)
    30. 		{}
    31.  
    32. 		Ref operator*()
    33. 		{
    34. 			return _node->_data;
    35. 		}
    36.  
    37. 		Ptr operator->()
    38. 		{
    39. 			//return &(operator*());
    40. 			return &_node->_data;
    41. 		}
    42.  
    43. 		self& operator++()
    44. 		{
    45. 			_node = _node->_next;
    46. 			return *this;
    47. 		}
    48.  
    49. 		self operator++(int)
    50. 		{
    51. 			self tmp(*this);
    52. 			_node = _node->_next;
    53. 			return tmp;
    54. 		}
    55.  
    56. 		self& operator--()
    57. 		{
    58. 			_node = _node->_prev;
    59. 			return *this;
    60. 		}
    61.  
    62. 		self operator--(int)
    63. 		{
    64. 			self tmp(*this);
    65. 			_node = _node->_prev;
    66. 			return tmp;
    67. 		}
    68.  
    69. 		bool operator!=(const self& it)
    70. 		{
    71. 			return _node != it._node;
    72. 		}
    73.  
    74. 		bool operator==(const self& it)
    75. 		{
    76. 			return _node == it._node;
    77. 		}
    78.  
    79. 	};
    80.  
    81.  
    82. 	template<class T>
    83. 	class list
    84. 	{
    85. 		typedef list_node Node;
    86. 	public:
    87. 		typedef __list_iterator iterator;
    88. 		typedef __list_iteratorconst T&, const T*> const_iterator;
    89.  
    90. 		// 反向迭代器适配支持
    91. 		typedef Reverse_iterator reverse_iterator;
    92. 		typedef Reverse_iteratorconst T&, const T*> const_reverse_iterator;
    93.  
    94. 		const_iterator begin() const
    95. 		{
    96. 			return const_iterator(_head->_next);
    97. 		}
    98.  
    99. 		const_iterator end() const
    100. 		{
    101. 			return const_iterator(_head);
    102. 		}
    103.  
    104. 		iterator begin()
    105. 		{
    106. 			return iterator(_head->_next);
    107. 			//return _head->_next;
    108. 		}
    109.  
    110. 		iterator end()
    111. 		{
    112. 			return iterator(_head);
    113. 		}
    114.  
    115. 		const_reverse_iterator rbegin() const
    116. 		{
    117. 			return const_reverse_iterator(end());
    118. 		}
    119.  
    120. 		const_reverse_iterator rend() const
    121. 		{
    122. 			return const_reverse_iterator(begin());
    123. 		}
    124.  
    125. 		reverse_iterator rbegin()
    126. 		{
    127. 			return reverse_iterator(end());
    128. 		}
    129.  
    130. 		reverse_iterator rend()
    131. 		{
    132. 			return reverse_iterator(begin());
    133. 		}
    134.  
    135. 		list()
    136. 		{
    137. 			_head = new Node();
    138. 			_head->_next = _head;
    139. 			_head->_prev = _head;
    140. 		}
    141.  
    142. 		// lt2(lt1)
    143. 		/*list(const list& lt)
    144. 		{
    145. 		_head = new Node();
    146. 		_head->_next = _head;
    147. 		_head->_prev = _head;
    149. 		for (auto e : lt)
    150. 		{
    151. 		push_back(e);
    152. 		}
    153. 		}*/
    154.  
    155. 		void empty_init()
    156. 		{
    157. 			_head = new Node();
    158. 			_head->_next = _head;
    159. 			_head->_prev = _head;
    160. 		}
    161.  
    162. 		template <class InputIterator>
    163. 		list(InputIterator first, InputIterator last)
    164. 		{
    165. 			empty_init();
    166.  
    167. 			while (first != last)
    168. 			{
    169. 				push_back(*first);
    170. 				++first;
    171. 			}
    172. 		}
    173.  
    174. 		void swap(list& lt)
    175. 		{
    176. 			std::swap(_head, lt._head);
    177. 		}
    178.  
    179. 		// lt2(lt1) -- 现代写法
    180. 		list(const list& lt)
    181. 		{
    182. 			empty_init();
    183. 			list tmp(lt.begin(), lt.end());
    184. 			swap(tmp);
    185. 		}
    186.  
    187. 		// lt2 = lt1
    188. 		list& operator=(list lt)
    189. 		{
    190. 			swap(lt);
    191. 			return *this;
    192. 		}
    193.  
    194. 		~list()
    195. 		{
    196. 			clear();
    197. 			delete _head;
    198. 			_head = nullptr;
    199. 		}
    200.  
    201. 		void clear()
    202. 		{
    203. 			iterator it = begin();
    204. 			while (it != end())
    205. 			{
    206. 				it = erase(it);
    207. 			}
    208. 		}
    209.  
    210. 		void push_back(const T& x)
    211. 		{
    212. 			//Node* tail = _head->_prev;
    213. 			//Node* newnode = new Node(x);
    214.  
    215. 			 _head       tail  newnode
    216. 			//tail->_next = newnode;
    217. 			//newnode->_prev = tail;
    218. 			//newnode->_next = _head;
    219. 			//_head->_prev = newnode;
    220.  
    221. 			insert(end(), x);
    222. 		}
    223.  
    224. 		void push_front(const T& x)
    225. 		{
    226. 			insert(begin(), x);
    227. 		}
    228.  
    229. 		void pop_back()
    230. 		{
    231. 			erase(--end());
    232. 		}
    233.  
    234. 		void pop_front()
    235. 		{
    236. 			erase(begin());
    237. 		}
    238.  
    239. 		// 插入在pos位置之前
    240. 		iterator insert(iterator pos, const T& x)
    241. 		{
    242. 			Node* newNode = new Node(x);
    243. 			Node* cur = pos._node;
    244. 			Node* prev = cur->_prev;
    245.  
    246. 			// prev  newnode  cur
    247. 			prev->_next = newNode;
    248. 			newNode->_prev = prev;
    249. 			newNode->_next = cur;
    250. 			cur->_prev = newNode;
    251.  
    252. 			return iterator(newNode);
    253. 		}
    254.  
    255. 		iterator erase(iterator pos)
    256. 		{
    257. 			assert(pos != end());
    258.  
    259. 			Node* cur = pos._node;
    260. 			Node* prev = cur->_prev;
    261. 			Node* next = cur->_next;
    262.  
    263. 			// prev  next
    264. 			prev->_next = next;
    265. 			next->_prev = prev;
    266. 			delete cur;
    267.  
    268. 			return iterator(next);
    269. 		}
    270.  
    271. 	private:
    272. 		Node* _head;
    273. 	};
    274.  
    275. 	void test_list()
    276. 	{
    277. 		list<int> lt;
    278. 		lt.push_back(1);
    279. 		lt.push_back(2);
    280. 		lt.push_back(2);
    281. 		lt.push_back(3);
    282. 		lt.push_back(4);
    283.  
    284. 		list<int>::reverse_iterator rit = lt.rbegin();
    285. 		while (rit != lt.rend())
    286. 		{
    287. 			cout << *rit << " ";
    288. 			++rit;
    289. 		}
    290. 		cout << endl;
    291. 	}
    292. }

    vector.h文件：

    1. #pragma once
    2. #include 
    3. #include "Reverselterator.h"
    4.  
    5. namespace bit
    6. {
    7. 	template<class T>
    8. 	class vector
    9. 	{
    10. 	public:
    11. 		typedef T* iterator;
    12. 		typedef const T* const_iterator;
    13.  
    14. 		// 反向迭代器适配支持
    15. 		typedef Reverse_iterator reverse_iterator;
    16. 		typedef Reverse_iteratorconst T&, const T*> const_reverse_iterator;
    17.  
    18. 		const_reverse_iterator rbegin() const
    19. 		{
    20. 			return const_reverse_iterator(end());
    21. 		}
    22.  
    23. 		const_reverse_iterator rend() const
    24. 		{
    25. 			return const_reverse_iterator(begin());
    26. 		}
    27.  
    28. 		reverse_iterator rbegin()
    29. 		{
    30. 			return reverse_iterator(end());
    31. 		}
    32.  
    33. 		reverse_iterator rend()
    34. 		{
    35. 			return reverse_iterator(begin());
    36. 		}
    37.  
    38. 		vector()
    39. 			:_start(nullptr)
    40. 			, _finish(nullptr)
    41. 			, _endofstoage(nullptr)
    42. 		{}
    43.  
    44. 		template <class InputIterator>
    45. 		vector(InputIterator first, InputIterator last)
    46. 			: _start(nullptr)
    47. 			, _finish(nullptr)
    48. 			, _endofstoage(nullptr)
    49. 		{
    50. 			while (first != last)
    51. 			{
    52. 				push_back(*first);
    53. 				++first;
    54. 			}
    55. 		}
    56.  
    57. 		vector(size_t n, const T& val = T())
    58. 			: _start(nullptr)
    59. 			, _finish(nullptr)
    60. 			, _endofstoage(nullptr)
    61. 		{
    62. 			reserve(n);
    63. 			for (size_t i = 0; i < n; ++i)
    64. 			{
    65. 				push_back(val);
    66. 			}
    67. 		}
    68.  
    69. 		vector(int n, const T& val = T())
    70. 			: _start(nullptr)
    71. 			, _finish(nullptr)
    72. 			, _endofstoage(nullptr)
    73. 		{
    74. 			reserve(n);
    75. 			for (int i = 0; i < n; ++i)
    76. 			{
    77. 				push_back(val);
    78. 			}
    79. 		}
    80.  
    81. 		void swap(vector& v)
    82. 		{
    83. 			std::swap(_start, v._start);
    84. 			std::swap(_finish, v._finish);
    85. 			std::swap(_endofstoage, v._endofstoage);
    86. 		}
    87.  
    88. 		//vector(const vector& v);
    89. 		vector(const vector& v)
    90. 			: _start(nullptr)
    91. 			, _finish(nullptr)
    92. 			, _endofstoage(nullptr)
    93. 		{
    94. 			vector tmp(v.begin(), v.end());
    95. 			swap(tmp);
    96. 		}
    97.  
    98. 		//vector& operator=(vector v)
    99. 		vector& operator=(vector v)
    100. 		{
    101. 			swap(v);
    102. 			return *this;
    103. 		}
    104.  
    105. 		~vector()
    106. 		{
    107. 			if (_start)
    108. 			{
    109. 				delete[] _start;
    110. 				_start = _finish = _endofstoage = nullptr;
    111. 			}
    112. 		}
    113.  
    114. 		iterator begin()
    115. 		{
    116. 			return _start;
    117. 		}
    118.  
    119. 		iterator end()
    120. 		{
    121. 			return _finish;
    122. 		}
    123.  
    124. 		const_iterator begin() const
    125. 		{
    126. 			return _start;
    127. 		}
    128.  
    129. 		const_iterator end() const
    130. 		{
    131. 			return _finish;
    132. 		}
    133.  
    134. 		size_t size() const
    135. 		{
    136. 			return _finish - _start;
    137. 		}
    138.  
    139. 		size_t capacity() const
    140. 		{
    141. 			return _endofstoage - _start;
    142. 		}
    143.  
    144. 		void reserve(size_t n)
    145. 		{
    146. 			size_t sz = size();
    147. 			if (n > capacity())
    148. 			{
    149. 				T* tmp = new T[n];
    150. 				if (_start)
    151. 				{
    152. 					//memcpy(tmp, _start, size()*sizeof(T));
    153. 					for (size_t i = 0; i < size(); ++i)
    154. 					{
    155. 						tmp[i] = _start[i];
    156. 					}
    157.  
    158. 					delete[] _start;
    159. 				}
    160.  
    161. 				_start = tmp;
    162. 			}
    163.  
    164. 			_finish = _start + sz;
    165. 			_endofstoage = _start + n;
    166. 		}
    167.  
    168. 		//void resize(size_t n, const T& val = T())
    169. 		void resize(size_t n, T val = T())
    170. 		{
    171. 			if (n > capacity())
    172. 			{
    173. 				reserve(n);
    174. 			}
    175.  
    176. 			if (n > size())
    177. 			{
    178. 				while (_finish < _start + n)
    179. 				{
    180. 					*_finish = val;
    181. 					++_finish;
    182. 				}
    183. 			}
    184. 			else
    185. 			{
    186. 				_finish = _start + n;
    187. 			}
    188. 		}
    189.  
    190. 		void push_back(const T& x)
    191. 		{
    192. 			/*if (_finish == _endofstoage)
    193. 			{
    194. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    195. 				reserve(newCapacity);
    196. 			}
    198. 			*_finish = x;
    199. 			++_finish;*/
    200.  
    201. 			insert(end(), x);
    202. 		}
    203.  
    204. 		void pop_back()
    205. 		{
    206. 			/*if (_finish > _start)
    207. 			{
    208. 				--_finish;
    209. 			}*/
    210. 			erase(end() - 1);
    211. 		}
    212.  
    213. 		T& operator[](size_t pos)
    214. 		{
    215. 			assert(pos < size());
    216.  
    217. 			return _start[pos];
    218. 		}
    219.  
    220. 		const T& operator[](size_t pos) const
    221. 		{
    222. 			assert(pos < size());
    223.  
    224. 			return _start[pos];
    225. 		}
    226.  
    227. 		iterator insert(iterator pos, const T& x)
    228. 		{
    229. 			// 检查参数
    230. 			assert(pos >= _start && pos <= _finish);
    231.  
    232. 			// 扩容
    233. 			// 扩容以后pos就失效了,需要更新一下
    234. 			if (_finish == _endofstoage)
    235. 			{
    236. 				size_t n = pos - _start;
    237.  
    238. 				size_t newCapacity = capacity() == 0 ? 4 : capacity() * 2;
    239. 				reserve(newCapacity);
    240.  
    241. 				pos = _start + n;
    242. 			}
    243.  
    244. 			// 挪动数据
    245. 			iterator end = _finish - 1;
    246. 			while (end >= pos)
    247. 			{
    248. 				*(end + 1) = *end;
    249. 				--end;
    250. 			}
    251.  
    252. 			*pos = x;
    253. 			++_finish;
    254.  
    255. 			return pos;
    256. 		}
    257.  
    258. 		iterator erase(iterator pos)
    259. 		{
    260. 			assert(pos >= _start && pos < _finish);
    261. 			iterator it = pos + 1;
    262. 			while (it != _finish)
    263. 			{
    264. 				*(it - 1) = *it;
    265. 				++it;
    266. 			}
    267. 			--_finish;
    268.  
    269. 			return pos;
    270. 		}
    271.  
    272. 		void clear()
    273. 		{
    274. 			_finish = _start;
    275. 		}
    276.  
    277. 	private:
    278. 		iterator _start;
    279. 		iterator _finish;
    280. 		iterator _endofstoage;
    281. 	};
    282.  
    283. 	void test_vector()
    284. 	{
    285. 		vector<int> v;
    286. 		v.push_back(10);
    287. 		v.push_back(20);
    288. 		v.push_back(30);
    289. 		v.push_back(40);
    290. 		v.push_back(50);
    291.  
    292. 		vector<int>::reverse_iterator rit = v.rbegin();
    293. 		while (rit != v.rend())
    294. 		{
    295. 			cout << *rit << " ";
    296. 			++rit;
    297. 		}
    298. 		cout << endl;
    299. 	}
    300. }

    test.cpp文件：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6. using namespace std;
    7.  
    8. #include"List.h"
    9. #include "vector.h"
    10.  
    11.  
    12. int main()
    13. {
    14. 	bit::test_list();
    15. 	bit::test_vector();
    16.  
    17. 	return 0;
    18. }

    注：

    1.如下图所示，这里和库里面源代码不同的是reverse_iterator类模板参数我们多写了Ref和Ptr两个参数，这样可以同时实现普通反向迭代器和const反向迭代器（和list类中的普通迭代器、const普通迭代器实现方法相同），库里面reverse_iterator类模板只用Iterator一个模板参数就实现了普通反向迭代器和const反向迭代器的原因是使用了迭代器的萃取技术（萃取技术下一节模板进阶我们会进行讲解）

    2.如下图所示是list源代码，源代码中多参数的reverse_bidirectional_iterator类模板和只传迭代器的reverse_iterator类模板都有，旧版本的编译器用的是多参数的reverse_bidirectional_iterator类模板，现在编译器用的是只传迭代器的reverse_iterator类模板。其实不只是list，其他类的源代码也相同

    3.以list类为例，如果我们像源代码一样只传正向迭代器给Reverse_iterator的模板参数（不传Ref和Ptr），如下图所示，此时Reverse_iterator里面只有迭代器类型，那么我们面对的挑战是Reverse_iterator里面的operator*和operator->函数返回值没办法表示。

    其实标准而言，要符合一个迭代器还需要在迭代器里面定义四种类型，如下图list标准库中迭代器的定义。其中iterator_category是迭代器类型用来标识是哪种类型的迭代器，value_type是T用来标识数据的类型，pointer是Ptr用来标识数据的指针，reference是Ref用来标识数据的引用。

    注意：

    （1）标准库中所有容器的迭代器里面都有定义这些类型

    （2）这里的pointer和reference不一定是value_type*和value_type*&，也就是Ptr和Ref不一定是T*和T&，如果是普通迭代器那么Ptr和Ref是T*和T&，如果是const迭代器那么Ptr和Ref是const T*和const T&

    因此在我们的迭代器代码中，也应该定义这四种类型，因为我们这里只需要pointer和reference，所以这里我们只定义这两种，如下图一所示。那么这样reverse_iterator里面的operator*和operator->函数返回值就可以写成Iterator::reference和Iterator::pointer，如下图二所示。但是返回值如果直接写成Iterator::reference和Iterator::pointer是有问题的，编译器会报错不认识Iterator::reference和Iterator::pointer，这是因为Iterator是一个类模板，Iterator类模板还没有实例化，编译器不能去还没有实例化的模板中找东西（如果编译器允许去还没有实例化的模板中找东西，那么这里的Iterator::reference和Iterator::pointer会被翻译成T&和T*，当Iterator类模板实例化了之后只会修改Iterator类模板里面的T类型，不会去修改reverse_iterator类里面的T类型）。

       

    类模板没有实例化之前不能去他里面找内嵌定义的类型（例如上面的pointer和reference），类模板没有实例化，找出来也是虚拟类型，后期无法处理。

    这里我们要在Iterator::reference和Iterator::pointer的前面加上typename关键字，如下图所示，typename关键字我们之前讲模板的时候提过（模板参数定义的时候可以用class也可以用typename），这里我们使用typename关键字，其功能是告诉编译器typename关键字后面的这一串（Iterator::reference和Iterator::pointer）是一个类型，等Iterator实例化以后，再去他里面找这个内嵌类型。

    官方库中反向迭代器的源代码在这个基础上还会再优化一下，如下图一所示，在reverse_iterator类模板中将Iterator::reference和Iterator::pointer类型重定义成reference和pointer，这里也需要加typename关键字，理由和上面相同。那么operator*和operator->前面可以直接用reference和pointer，如下图二所示

      

    这样对于list类，我们就完成了像源代码一样的只有一个模板参数的reverse_iterator类模板。

    4.上面注意点三的实现只有一个模板参数的reverse_iterator类模板思路对于string和vector容器是不行的，只有容器的迭代器是自定义类型的才能在里面类型重定义reference和pointer，然后在reverse_iterator类里面取迭代器类里面的内嵌类型reference和pointer，而string和vector容器的迭代器就是指针类型不是自定义类型的。

    string和vector容器的解决方式有两种：

    （1）不再使用原生指针作为string和vector容器的迭代器，去写一个__string_iterator和__vector_iterator的迭代器类，类里面去封装T*指针，然后在迭代器类里面实现operator++等操作，并且和list一样在类里面类型重定义reference和pointer即可

    （2）萃取（源代码中的reverse_iterator类里面，对于自定义类型的迭代器会像list那样处理，对于像string和vector这样内置类型的迭代器，会进行迭代器萃取，迭代器的萃取下一节模板进阶我们会进行讲解）

    5.如下图一所示的print_list和print_container代码是有问题的，因为在print_list模板函数中，list这个类模板还没有实例化，因此不能去取里面的const_iterator内嵌类型，print_container模板函数中，Container还没有实例化，因此不能去取里面的const_iterator内嵌类型。需要在list::const_iterator和Container::const_iterator的前面加上关键词typename才可以，如下图二所示。

    注意：如果这里的list::const_iterator和Container::const_iterator使用auto代替，那么auto前面是不用加typename的，因为auto会根据lt.begin()的返回值类型直接推出来。

  • 相关阅读:
    Linux常用工具及服务（ssh,rsync）
    【区块链 | 智能合约】Ethereum源代码（2）- go-ethereum 客户端入口代码和Node分析
    jQuery UI简单的讲解
    go-zero微服务实战系列（三、API定义和表结构设计）
    『现学现忘』Git基础 — 22、Git中文件重命名
    代码随想录算法训练营第五十七天 | 动态规划 part 15 | 392.判断子序列、115.不同的子序列
    机器学习入门教学——损失函数（交叉熵法）
    【C++天梯计划】1.10 二叉树(binary tree)
    姿态识别+校准｜视觉技术新突破
    ​Profinet转EtherNET/IP从站连接欧姆龙plc与西门子200smart通讯的配置方法​
  • 原文地址：https://blog.csdn.net/qq_45113223/article/details/127880817