C++STL之priority_queue的简单使用

不念不忘少年蓝@ 2022-12-02 04:21 136阅读 0赞

**目录**

简介

常用函数

代码

运行截图

参考

--------------------

# 简介 #

priority\_queue（优先级队列）模拟的也是队列这种存储结构，它底层采用堆结构存储数据，即使用此容器存储元素只能“从一端进（称为队尾），从另一端出（称为队头）”，且每次只能访问 priority\_queue 中位于队头的元素。  
但是，priority\_queue 中元素的存和取，遵循的并不是 “First in,First out”（先入先出）原则，而是“First in，Optimal out”原则。指的就是先进队列的元素并不一定先出队列，而是优先级最大的元素最先出队列。

注意，“First in，Optimal out”原则是博主为了总结 priority\_queue 存取元素的特性自创的一种称谓，为了方便读者理解。

优先级评定规则？？？

默认使用`std::less<T>`按照元素值从大到小进行排序，还可以使用`std::greater<T>`按照元素值从小到大排序，但更多情况下是使用自定义的排序规则。定义在 <function> 头文件中  
priority\_queue 为了保证每次从队头移除的都是当前优先级最高的元素，每当有新元素进入，它都会根据排序规则找到优先级最高的元素，并将其移动到队列的队头。

# 常用函数 #

<table> 
 <tbody> 
  <tr> 
   <th style="width:265px;">常用成员函数</th> 
   <th style="width:640px;">功能</th> 
  </tr> 
  <tr> 
   <td style="width:265px;">bool empty() const</td> 
   <td style="width:640px;">如果 priority_queue 为空的话，返回 true；反之，返回 false。</td> 
  </tr> 
  <tr> 
   <td style="width:265px;">size_type size() const</td> 
   <td style="width:640px;">返回 priority_queue&nbsp;中存储元素的个数。</td> 
  </tr> 
  <tr> 
   <td style="width:265px;">const_reference top() const</td> 
   <td style="width:640px;">返回 priority_queue&nbsp;中第一个元素的引用形式。</td> 
  </tr> 
  <tr> 
   <td style="width:265px;">void push (value_type&amp;&amp; val)</td> 
   <td style="width:640px;">根据既定的排序规则，将元素 obj 的副本存储到 priority_queue&nbsp;中适当的位置。</td> 
  </tr> 
  <tr> 
   <td style="width:265px;">void emplace (Args&amp;&amp;... args)</td> 
   <td style="width:640px;">Args&amp;&amp;... args 表示构造一个存储类型的元素所需要的数据（对于类对象来说，可能需要多个数据构造出一个对象）。此函数的功能是根据既定的排序规则，在适当的位置直接生成该新元素。</td> 
  </tr> 
  <tr> 
   <td style="width:265px;">void pop()</td> 
   <td style="width:640px;">移除 priority_queue&nbsp;容器适配器中第一个元素。</td> 
  </tr> 
  <tr> 
   <td style="width:265px;">void swap (priority_queue&amp; x) noexcept</td> 
   <td style="width:640px;">将两个 priority_queue 容器适配器中的元素进行互换，需要注意的是，进行互换的两个 priority_queue 容器适配器中存储的元素类型以及底层采用的基础容器类型，都必须相同。</td> 
  </tr> 
 </tbody> 
</table>

# 代码 #

/*
    Project:priority_queue
    Date:   2020/08/30
    Author: Frank Yu
    */
    #include<iostream>
    #include<string>
    #include<queue>
    #include<functional>
    using namespace std;
    priority_queue<int> pq;
    //菜单
    void menu()
    {
    	cout << "**************1.入队			2.出队**************" << endl;
    	cout << "**************3.生成			4.队头**************" << endl;
    	cout << "**************5.交换			6.排序规则展示******" << endl;
    	cout << "**************7.自定义			8.退出**************" << endl;
    }
    //入队 无参数
    void Push_pq()
    {
    	int n;
    	cout << "请输入一个整数:" << endl;
    	cin >> n;
    	pq.push(n);
    	cout << "已入队，队列大小："<<pq.size()<< endl;
    }
    //出队 无参数
    void Pop_pq()
    {
    	int n;
    	if (!pq.empty())
    	{
    		n = pq.top();
    		pq.pop();
    		cout << "队头:" << n << "已出队" << endl;
    		if(pq.empty())cout << "队列已空！！！" << endl;
    	}
    	else
    	{
    		cout << "队列已空！！！" << endl;
    	}
    }
    //插入 直接在某个位置生成，效率更高
    void Insert()
    {
    	int n;
    	cout << "请输入一个整数:" << endl;
    	cin >> n;
    	pq.emplace(n);
    	cout << "已生成，队列大小：" << pq.size() << endl;
    }
    //队头 获取队头，可修改
    void Top()
    {
    	int n;
    	if (!pq.empty())
    	{
    		cout << "队头为：" << pq.top() << endl;
    	}
    	cout << "是否修改？ 0.不修改 1.修改" << endl;
    	cin >> n;
    	if (n) {
    		cout << "请输入一个整数:" << endl;
    		cin >> n;
    		int value = pq.top();
    		value = n;
    	}
    }
    //交换两个优先队列 用的比较少
    void Swap()
    {
    	int values[4] = {1,2,3,4};
    	priority_queue<int> pq_cp(values,values+4);
    	pq.swap(pq_cp);
    	cout << "交换后为{1,2,3,4}" << endl;
    }
    //排序规则展示
    void Priority()
    {
    	int int_values[5] = { 1,3,2,0,4 };
    	priority_queue<int> int_pq(int_values, int_values + 5);
    	cout << "{ 1,3,2,0,4 }整型默认为从大到小(std::less):" << endl;
    	while (!int_pq.empty())
    	{
    		cout << int_pq.top() << " ";
    		int_pq.pop();
    	} 
    	cout<< endl;
    	priority_queue<int,vector<int>,greater<int>> int_pq_new(int_values, int_values + 5);
    	cout << "{ 1,3,2,0,4 }排序规则改为从小到大(std::greater):" << endl;
    	while (!int_pq_new.empty())
    	{
    		cout << int_pq_new.top()<<" ";
    		int_pq_new.pop();
    	}
    	cout << endl;
    
    	char char_values[5] = { 'b','a','1','c','?'};
    	priority_queue<char> char_pq(char_values, char_values + 5);
    	cout << "{ 'b','a','1','c','?'}字符型默认按ASCII为从大到小(std::less):" << endl;
    	while (!char_pq.empty())
    	{
    		cout << char_pq.top() << " ";
    		char_pq.pop();
    	}
    	cout << endl;
    	priority_queue<char, vector<char>, greater<char>> char_pq_new(char_values, char_values + 5);
    	cout << "{ 'b','a','1','c','?'}排序规则改为从小到大(std::greater):" << endl;
    	while (!char_pq_new.empty())
    	{
    		cout << char_pq_new.top() << " ";
    		char_pq_new.pop();
    	}
    	cout << endl;
    
    	string str_values[5] = { "bde","abc","bbe","cdf","cde" };
    	priority_queue<string> str_pq(str_values, str_values + 5);
    	cout << "{ 'b','a','1','c','?'}字符串型默认从左到右一个个字符按ASCII比较，大的优先级高(std::less):" << endl;
    	while (!str_pq.empty())
    	{
    		cout << str_pq.top() << " ";
    		str_pq.pop();
    	}
    	cout << endl;
    	priority_queue<string, vector<string>, greater<string>> str_pq_new(str_values, str_values + 5);
    	cout << "{ 'b','a','1','c','?'}排序规则改为从小到大(std::greater):" << endl;
    	while (!str_pq_new.empty())
    	{
    		cout << str_pq_new.top() << " ";
    		str_pq_new.pop();
    	}
    	cout << endl;
    }
    //自定义排序规则 偶数优先，同为偶数或奇数，大数优先
    struct oddFirst
    {
    	bool operator()(const int &a, const int &b)
    	{
    		if (a % 2 == 0 && b % 2 == 0)
    		{
    			return a < b ? true : false;
    		}
    		else if (a % 2 != 0 && b % 2 != 0)
    		{
    			return a < b ? true : false;
    		}
    		else
    		{
    			return a % 2 == 0 ?  false : true;
    		}
    	}
    };
    //自定义排序规则
    void Priority_self()
    {
    	int int_values[5] = { 1,3,2,0,4 };
    	priority_queue<int, std::vector<int>, oddFirst> mypq(int_values,int_values+5);
    	cout << "{ 1,3,2,0,4 }整型自定义偶数优先排序:" << endl;
    	while (!mypq.empty())
    	{
    		cout << mypq.top() << " ";
    		mypq.pop();
    	}
    	cout << endl;
    }
    int main()
    {
    	int i;
    	while (true)
    	{
    		menu();
    		cout << "请输入菜单号:" << endl;
    		cin >> i;
    		if (i == 8)break;
    		switch (i)
    		{
    			case 1:Push_pq(); break;
    			case 2:Pop_pq(); break;
    			case 3:Insert(); break;
    			case 4:Top(); break;
    			case 5:Swap(); break;
    			case 6:Priority(); break;
    			case 7:Priority_self(); break;
    			default:cout << "输入错误！" << endl;
    		}
    	}
    	return 0;
    }

# 运行截图 #

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2][]

注意：队头修改后也会调整至应该在的位置，所谓修改队头相当于删除原有队头再插入新的。

# 参考 #

[cplusplus-priority\_queue][cplusplus-priority_queue]

更多STL例子:[C++ STL的使用][C_ STL]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221123/18fc1387d4824659b7d9fde166ea74da.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1]: /images/20221123/f54140a55ec644688cd68de9f99c3942.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2]: /images/20221123/7cb86b0830db445494d3242aacce22a4.png
[cplusplus-priority_queue]: http://www.cplusplus.com/reference/queue/priority_queue/priority_queue/
[C_ STL]: https://blog.csdn.net/lady_killer9/article/details/81175682