• 【C++】STL-priority_queue

    目录

    1、priority_queue的使用

    2、实现没有仿函数的优先级队列

    3、实现有仿函数的优先级队列

    3.1 仿函数

    3.2 真正的优先级队列

    3.3 优先级队列放自定义类型

    1、priority_queue的使用

    priority_queue是优先级队列，是一个容器适配器，不满足先进先出的特点，而是优先级高的先出，默认的适配器是vector，底层是一个堆，默认是大堆

    priority_queue是可以进行迭代器区间初始化的

    1. void test_priority_queue1()
    2. {
    3. 	vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
    4. 	priority_queue<int> q1;
    5. 	for (auto& e : v)
    6. 		q1.push(e);
    7. 	while (!q1.empty())
    8. 	{
    9. 		cout << q1.top() << " ";
    10. 		q1.pop();
    11. 	}
    12. 	cout << endl;
    13. }
    1. void test_priority_queue2()
    2. {
    3. 	vector<int> v = { 3,2,7,6,0,4,1,9,8,5 };
    4. 	priority_queue<int> q1(v.begin(), v.end());
    5. 	while (!q1.empty())
    6. 	{
    7. 		cout << q1.top() << " ";
    8. 		q1.pop();
    9. 	}
    10. 	cout << endl;
    11. }

    可以用数组直接初始化 

    1. void test_priority_queue3()
    2. {
    3. 	int v[10] = {3,2,7,6,0,4,1,9,8,5};
    4. 	priority_queue<int> q1(v, v + 10);
    5. 	while (!q1.empty())
    6. 	{
    7. 		cout << q1.top() << " ";
    8. 		q1.pop();
    9. 	}
    10. 	cout << endl;
    11. }

    上面3段代码的结果都是相同的，都是9 8 7 6 5 4 3 2 1 0，因为默认是建大堆

    2、实现没有仿函数的优先级队列

    1. namespace cxf
    2. {
    3. 	template<class T,class Container = std::vector<T>>
    4. 	class priority_queue
    5. 	{
    6. 	public:// 建大堆
    7. 		void adjust_up(int child)
    8. 		{
    9. 			int parent = (child - 1) / 2;
    10. 			while (child > 0)
    11. 			{
    12. 				if (_con[parent] < _con[child])
    13. 				{
    14. 					std::swap(_con[parent], _con[child]);
    15. 					child = parent;
    16. 					parent = (child - 1) / 2;
    17. 				}
    18. 				else break;
    19. 			}
    20. 		}
    21. 		void adjust_down(int parent)
    22. 		{
    23. 			int child = parent * 2 + 1;
    24. 			while (child < _con.size())
    25. 			{
    26. 				if (child + 1 < _con.size() && _con[child] < _con[child + 1])
    27. 				{
    28. 					++child;
    29. 				}
    30. 				if (_con[parent] < _con[child])
    31. 				{
    32. 					std::swap(_con[parent], _con[child]);
    33. 					parent = child;
    34. 					child = parent * 2 + 1;
    35. 				}
    36. 				else break;
    37. 			}
    38. 		}
    39. 		// 强制编译器生成默认的构造函数，因为下面有迭代器区间初始化，这样没办法用默认构造函数
    40. 		priority_queue() = default;
    41. 		// 迭代器区间初始化
    42. 		template<class InputIterator>
    43. 		priority_queue(InputIterator first, InputIterator last)
    44. 		{
    45. 			while (first != last)
    46. 			{
    47. 				_con.push_back(*first);
    48. 				++first;
    49. 			}
    50. 			// 建堆
    51. 			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
    52. 			{
    53. 				adjust_down(i);
    54. 			}
    55. 		}
    56. 		void push(const T& x)
    57. 		{
    58. 			_con.push_back(x);
    59. 			adjust_up(_con.size() - 1);
    60. 		}
    61. 		void pop()
    62. 		{
    63. 			std::swap(_con[0], _con[_con.size() - 1]);
    64. 			_con.pop_back();
    65. 			adjust_down(0);
    66. 		}
    67. 		const T& top()
    68. 		{
    69. 			return _con[0];
    70. 		}
    71. 		size_t size()
    72. 		{
    73. 			return _con.size();
    74. 		}
    75. 		bool empty()
    76. 		{
    77. 			return _con.empty();
    78. 		}
    79. 	private:
    80. 		Container _con;
    81. 	};
    82. }

    上面是建大堆的优先级队列，当要建小堆时，需要在adjust_up和adjust_up中将<改成>，这样是十分麻烦的，为例能够在不修改代码的情况下完成建小堆，所以引入了仿函数的概念

    3、实现有仿函数的优先级队列

    3.1 仿函数

    仿函数就是重载了operatror()的类，类的对象可以像调用函数一样使用

    operator()的特点是参数个数和返回值个数可以根据需求来定，很灵活，所以有很多用法

    若用class来定义仿函数的类要加public，所以通常会用struct来定义仿函数

    根据仿函数就可以来实现一个既可建大堆，又可建小堆的优先级队列

    3.2 真正的优先级队列

    1. namespace cxf
    2. {
    3. 	template<class T>
    4. 	class myless // 小于是大堆
    5. 	{
    6. 	public:
    7. 		bool operator()(const T& x, const T& y)
    8. 		{
    9. 			return x < y;
    10. 		}
    11. 	};
    12. 	template<class T>
    13. 	class mygreater // 大于是小堆
    14. 	{
    15. 	public:
    16. 		bool operator()(const T& x, const T& y)
    17. 		{
    18. 			return x > y;
    19. 		}
    20. 	};
    21. 	template<class T, class Container = std::vector<T>, class Comapre = myless<T>>
    22. 	class priority_queue
    23. 	{
    24. 	public:
    25. 		void adjust_up(int child)
    26. 		{
    27. 			Comapre comfunc;
    28. 			int parent = (child - 1) / 2;
    29. 			while (child > 0)
    30. 			{
    31. 				//if (_con[parent] < _con[child])
    32. 				if(comfunc(_con[parent],_con[child]))
    33. 				{
    34. 					std::swap(_con[parent], _con[child]);
    35. 					child = parent;
    36. 					parent = (child - 1) / 2;
    37. 				}
    38. 				else break;
    39. 			}
    40. 		}
    41. 		void adjust_down(int parent)
    42. 		{
    43. 			Comapre comfunc;
    44. 			int child = parent * 2 + 1;
    45. 			while (child < _con.size())
    46. 			{
    47. 				/*if (child + 1 < _con.size() && _con[child] < _con[child + 1])*/
    48. 				if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1]))
    49. 				{
    50. 					++child;
    51. 				}
    52. 				//if (_con[parent] < _con[child])
    53. 				if(comfunc(_con[parent],_con[child]))
    54. 				{
    55. 					std::swap(_con[parent], _con[child]);
    56. 					parent = child;
    57. 					child = parent * 2 + 1;
    58. 				}
    59. 				else break;
    60. 			}
    61. 		}
    62. 		// 强制编译器生成默认的构造函数，因为下面有迭代器区间初始化，这样没办法用默认构造函数
    63. 		priority_queue() = default;
    64. 		// 迭代器区间初始化
    65. 		template<class InputIterator>
    66. 		priority_queue(InputIterator first, InputIterator last)
    67. 		{
    68. 			while (first != last)
    69. 			{
    70. 				_con.push_back(*first);
    71. 				++first;
    72. 			}
    73. 			// 建堆
    74. 			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
    75. 			{
    76. 				adjust_down(i);
    77. 			}
    78. 		}
    79. 		void push(const T& x)
    80. 		{
    81. 			_con.push_back(x);
    82. 			adjust_up(_con.size() - 1);
    83. 		}
    84. 		void pop()
    85. 		{
    86. 			std::swap(_con[0], _con[_con.size() - 1]);
    87. 			_con.pop_back();
    88. 			adjust_down(0);
    89. 		}
    90. 		const T& top()
    91. 		{
    92. 			return _con[0];
    93. 		}
    94. 		size_t size()
    95. 		{
    96. 			return _con.size();
    97. 		}
    98. 		bool empty()
    99. 		{
    100. 			return _con.empty();
    101. 		}
    102. 	private:
    103. 		Container _con;
    104. 	};
    105. }

    priority_queue的第三个模板参数就是仿函数 

    在STL库中的priority_queue来建小堆

    3.3 优先级队列放自定义类型

    1. class Date
    2. {
    3. public:
    4. 	Date(int year = 1900, int month = 1, int day = 1)
    5. 		: _year(year)
    6. 		, _month(month)
    7. 		, _day(day)
    8. 	{}
    9.  
    10. 	bool operator<(const Date& d)const
    11. 	{
    12. 		return (_year < d._year) ||
    13. 			(_year == d._year && _month < d._month) ||
    14. 			(_year == d._year && _month == d._month && _day < d._day);
    15. 	}
    16.  
    17. 	bool operator>(const Date& d)const
    18. 	{
    19. 		return (_year > d._year) ||
    20. 			(_year == d._year && _month > d._month) ||
    21. 			(_year == d._year && _month == d._month && _day > d._day);
    22. 	}
    23.  
    24. 	friend ostream& operator<<(ostream& _cout, const Date& d);
    25. private:
    26. 	int _year;
    27. 	int _month;
    28. 	int _day;
    29. };
    30. ostream& operator<<(ostream& _cout, const Date& d)
    31. {
    32. 	_cout << d._year << "-" << d._month << "-" << d._day;
    33. 	return _cout;
    34. }
    35. int main()
    36. {
    37. 	priority_queue<Date> q1;
    38. 	q1.push(Date(2022, 9, 9));
    39. 	q1.push(Date(2022, 9, 10));
    40. 	q1.push(Date(2022, 9, 11));
    41. 	while (!q1.empty())
    42. 	{
    43. 		cout << q1.top() << endl;
    44. 		q1.pop();
    45. 	}
    46. 	return 0;
    47. }

    结果是正确的，因为只要这个自定义类型是能够比较大小的，都能使用优先级队列

    但是若比较的不是这个自定义类型，而是这个自定义类型的指针，则会出现随机结果

    1. int main()
    2. {
    3. 	priority_queue<Date*> q1;
    4. 	q1.push(new Date(2022, 9, 9));
    5. 	q1.push(new Date(2022, 9, 10));
    6. 	q1.push(new Date(2022, 9, 11));
    7. 	while (!q1.empty())
    8. 	{
    9. 		cout << *q1.top() << endl;
    10. 		q1.pop();
    11. 	}
    12. 	return 0;
    13. }

    此时是错误的，并且每次运行程序结果也不一定都相同。因为less比较的是Date*，是根据地址比较的，而new出来的地址是随机的，所以几次的运行结果也会不同。而且这个比较从逻辑上就是错误的，因为不应该使用对象的地址去比较，应该使用对象的值去比较

    所以可以自己写一个仿函数，达到想要的目的

    1. struct PDateLess
    2. {
    3. 	bool operator()(Date* p1, Date* p2)
    4. 	{
    5. 		return *p1 < *p2;
    6. 	}
    7. };
    8. int main()
    9. {
    10. 	priority_queue<Date*, vector<Date*>, PDateLess> q1;
    11. 	q1.push(new Date(2022, 9, 9));
    12. 	q1.push(new Date(2022, 9, 10));
    13. 	q1.push(new Date(2022, 9, 11));
    14. 	while (!q1.empty())
    15. 	{
    16. 		cout << *q1.top() << endl;
    17. 		q1.pop();
    18. 	}
    19. 	return 0;
    20. }

    此时就正确的

    所以仿函数不仅可以支持比较大小，还可以支持修改比较逻辑，如果默认的比较逻辑不是想要的或者不支持比较大小，都可以通过仿函数来控制。

  • 相关阅读:
    [附源码]计算机毕业设计校园代取快递系统Springboot程序
    SpringBoot整合SpringSecurity实现简单的验证码登陆
    厨房燃气安全新保障：红外点式可燃气体报警器的作用
    图片 视频和Canvas的相互转换
    我有点想用JDK17了
    01-Node-Express系统框架搭建（express-generator）
    CANoe面板中的控件：Switch/Indicator
    Git实用小技巧
    Python编程 赋值，逻辑，位运算符
    [附源码]Python计算机毕业设计Django基于Java的员工管理系统
  • 原文地址：https://blog.csdn.net/2301_80277275/article/details/140009273