C++中priority_queue的头文件是#include <queue>, priority_queue是调用STL里面的 make_heap(), pop_heap(), push_heap() 算法实现,也算是堆的另外一种形式。
priority_queue 对于基本类型的使用方法相对简单。他的模板声明带有三个参数:
priority_queue<Type, Container, Functional>,其中Type 为数据类型, Container 为保存数据的容器,Functional 为元素比较方式。Container 必须是用数组实现的容器,比如vector, deque 但不能用 list. STL里面默认用的是 vector. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。
如果要用到小顶堆,则一般要把模板的三个参数都带进去。STL里面定义了一个仿函数greater<>,对于基本类型可以用这个仿函数声明小顶堆,如下代码,使用greater<>后,输出的就是队列中最小的,否则缺省为输出最大的。
#include <iostream> #include <queue> using namespace std; int main(){ priority_queue<int, vector<int>, greater<int> > q; for( int i= 0; i< 10; ++i ) q.push( rand() ); while( !q.empty() ){ cout << q.top() << endl; q.pop(); } getchar(); return 0; }
对于自定义类型,则必须自己重载 operator< 或者自己写仿函数。
#include <iostream> #include <queue> using namespace std; struct Node{ int x, y; Node( int a= 0, int b= 0 ): x(a), y(b) {} }; bool operator<( Node a, Node b ){ if( a.x== b.x ) return a.y> b.y; return a.x> b.x; } int main(){ priority_queue<Node> q; for( int i= 0; i< 10; ++i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout << q.top().x << ' ' << q.top().y << endl; q.pop(); } getchar(); return 0; }
自定义类型重载 operator< 后,声明对象时就可以只带一个模板参数。但此时不能像基本类型这样声明priority_queue<Node, vector<Node>, greater<Node> >;原因是 greater<Node> 没有定义,如果想用这种方法定义则可以按如下方式,这样就可以产生一个小顶堆:
#include <iostream> #include <queue> using namespace std; struct Node{ int x, y; Node( int a= 0, int b= 0 ): x(a), y(b) {} }; struct cmp{ bool operator() ( Node a, Node b ){ if( a.x== b.x ) return a.y> b.y; return a.x> b.x; } }; int main(){ priority_queue<Node, vector<Node>, cmp> q; for( int i= 0; i< 10; ++i ) q.push( Node( rand(), rand() ) ); while( !q.empty() ){ cout << q.top().x << ' ' << q.top().y << endl; q.pop(); } getchar(); return 0; }
来源:http://blog.chinaunix.net/uid-533684-id-2100009.html
相关推荐
priority_queue用法,希望对大家会有所帮助
这个文档介绍了PBDS库中的一些数据结构,包括rope、priority_queue以及tree的用法。
priority_queue 源码
使用priority_queue(即堆)的不同方式 :mount_fuji: 默认声明 priority_queue< int > pq; // creates max-heap priority_queue< int , vector< int >> pq; // creates max-heap 为 priority_queue 编写...
4.3 C++ STL的Visual C++编译 50 4.4 C++ STL的体系结构 52 4.4.1 容器(Container) 52 4.4.2 迭代器(Iterator) 53 4.4.3 算法(Algorithm) 53 4.4.4 函数对象(Function Object) 54 4.4.5 适配器(Adapter...
4.3 C++ STL的Visual C++编译 50 4.4 C++ STL的体系结构 52 4.4.1 容器(Container) 52 4.4.2 迭代器(Iterator) 53 4.4.3 算法(Algorithm) 53 4.4.4 函数对象(Function Object) 54 4.4.5 适配器(Adapter...
priority_queue_learn.cpp queue_learn.cpp set_learn.cpp stack_learn.cpp static_var_in_class.cpp std_except.cpp std_io.cpp stl_alg_learn.cpp string_learn.cpp test_init.cpp type_change.cpp vector_learn....
4.3 C++ STL的Visual C++编译 50 4.4 C++ STL的体系结构 52 4.4.1 容器(Container) 52 4.4.2 迭代器(Iterator) 53 4.4.3 算法(Algorithm) 53 4.4.4 函数对象(Function Object) 54 4.4.5 适配器(Adapter...
c++ std stl各容器的应用场合及性能 map hash_map unordered_map multimap list forward_list vector set hash_set multiset unsorted_set queue deque priority_queue
10.2.7优先级队列priority_queue 110 10.2.8Set和multiset容器 111 10.2.9Map和multimap容器 118 10.2.10容器共性机制研究 123 10.2.11其他 124 10.3算法 125 10.3.1算法基础 125 10.3.2STL算法中函数对象和谓词 138...
丰富的范例程序 Sample of STL STL 范例(一) 容器部分 Vector-------------------------------------------1 Deque---------------------------------...Priority_queue------------------------------------------139
第二篇C++ STL 技术原理和组成 第3 章STL 技术原理· · · · · · · · · · · · · · · · · ·................................. 103 3-1 模板概述· · · · · · • · · · · · · · · · ·...
1、STL标准容器类简介 标准容器类 说明 顺序性容器 vector 相当与数组,从后面快速的插入与删除,直接访问任何元素 deque 双队列,从前面或后面快速的插入与删除,... priority_queue 最高优先级元素总是第一个出列
MyStl 实现自己的STL 环境 Microsoft Windows 10 Visual Studio 2015 c++11 要点 模板实现 traits编程技巧 c++11 自定义内存管理 ...顺序容器适配器:stack,queue ...容器适配器:priority_queue 迭代器:反向迭代器
1.1.2 stl与c++ 标准程序库 003 . 1.2 stl 六大组件 - 功能与运用 004 1.3 gnu源码开放精神 007 1.4 hp stl实现版本 009 1.5 p.j. plauger stl实现版本 010 1.6 rouge wave stl实现版本 011 1.7 stlport 实现...
LightSTLLightSTL是STL的一个子集和一个超集,是我在分析STL源码后结合自己的理解进行编写的主要目的在于提高数据结构与算法和C++编程LightSTL开发进度底层配置和主要容器iterator_traits(100%)type_traits(100%)...
C++模板库的许多容器需要相关类型有序,例如set<T> 和priority_queue。 这篇文章旨在告诉大家如何为一个类定义一个排序方法,以便在STL容器或者方法中使用。 作为一个C++程序员,你应该知道这些方法。 如何定义排序...
priority_queue set unordered_set multiset unordered_multiset map multimap unordered_map unordered_multimap algorithm 其它 实现自定义排序规则 Python 攻略 基本数据类型 生成器 文件操作 并发 三方库 jieba ...
本教程共分为5个部分,第一部分是C语言提高部分,第二部分为C++基础部分,第三部分为C++进阶部分,第四部分为C、C++及数据结构基础部分,第五部分为C_C++与设计模式基础,内容非常详细. 第一部分 C语言提高部分目录...
内容简介回到顶部↑这本书不适合C++ 初学者,不适合 Genericity(泛型技术)初学者,或 STL 初学者。这本书也不适合带领你学习面向对象(Object Oriented)技术 — 是的,STL 与面向对象没有太多关连。本书前言清楚...