STL之priority_queue源码剖析
heap
在探讨priority_queue之前,我们必须先分析heap。heap并不归属于STL容器,他是个幕后英雄,扮演priorityqueue的助手。顾名思义,priority queue允许用户以任何次序将任何元素推入容器,但取出时一定是从优先权最高的元素开始取。Binary max heap证据有这样的特性,适合作为priority_queue的底层机制。由于关于heap有关的算法可参见相关数据结构书籍,这里只是用图简单的介绍。
push_heap算法:
pop_heap算法:
sort_heap算法
由于的所有元素都是遵循特殊的排列规则,所有heap不过遍历,也不提供迭代器。
priority_queue
priority_queue缺省情况下是以vector为底部容器,再加上heap处理规则实现,它没有迭代器。它只允许在低端加入元,并从顶端取出元素,其内部元素自动按照元素的权值排列。权值最高者排在最前面。
下面是priority_queue的源代码列表:
class priority_queue{
public:
typedef typename Sequence::value_type value_type;
typedef typename Sequence::size_type size_type;
typedef typename Sequence::reference reference;
typedef typename Sequence::const_reference const_reference;
protected:
Sequencec; // 底层容器
Compare comp; // 元素大小比较标准
public:
priority_queue(): c() {}
explicit priority_queue(constCompare& x) : c(), comp(x) {}
// 以下用到的make_heap(), push_heap(),pop_heap()都是泛型算法
// 注意,任何一个构造函数都立刻于底层容器内产生一个implicitrepresentation heap。
#ifdef __STL_MEMBER_TEMPLATES
template <class InputIterator>
priority_queue(InputIteratorfirst, InputIterator last, const Compare& x)
: c(first, last), comp(x) { make_heap(c.begin(),c.end(), comp); }
template <class InputIterator>
priority_queue(InputIteratorfirst, InputIterator last)
: c(first, last) { make_heap(c.begin(),c.end(), comp); }
#else /* __STL_MEMBER_TEMPLATES */
priority_queue(constvalue_type* first, const value_type* last,
const Compare& x) :c(first, last), comp(x) {
make_heap(c.begin(), c.end(), comp);
}
priority_queue(constvalue_type* first, const value_type* last)
: c(first, last) { make_heap(c.begin(),c.end(), comp); }
#endif /* __STL_MEMBER_TEMPLATES */
bool empty()const { return c.empty(); }
size_type size()const { return c.size(); }
const_reference top()const { return c.front(); }
void push(constvalue_type& x) {
__STL_TRY {
// push_heap 是泛型算法,先利用底层容器的push_back()将新元素
// 推入末端,再重排heap
c.push_back(x);
push_heap(c.begin(), c.end(), comp);// push_heap 是泛型演算法
}
__STL_UNWIND(c.clear());
}
void pop(){
__STL_TRY {
// pop_heap 是泛型演算法,從 heap 內取出一個元素。它並不是真正將元素
// 彈出,而是重排heap,然後再以底層容器的pop_back() 取得被彈出
// 的元素。見C++ Primerp.1195。
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
__STL_UNWIND(c.clear());
}
};
分享到:
相关推荐
priority_queue用法,希望对大家会有所帮助
主要介绍了 STL priority_queue(优先队列)详解的相关资料,需要的朋友可以参考下
priority_queue 源码
3.4 traits 编程技法 - stl源码门钥 085 partial specialzation(偏特化)的意义 086 3.4.1 迭代器相应型别之一value_type 090 3.4.2 迭代器相应型别之二difference_type 090 3.4.3 迭代器相应型别之三pointer_...
如果你的Generic Programming/STL实力足以阅读本书所呈现的源码,那么,恭喜,你踏上了基度山岛,这儿有一座大宝库等着你。源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、RB-tree...
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....
压缩包中包括STL数据文件的读取类,包括ASCII格式和Binary格式。
使用priority_queue(即堆)的不同方式 :mount_fuji: 默认声明 priority_queue< int > pq; // creates max-heap priority_queue< int , vector< int >> pq; // creates max-heap 为 priority_queue 编写...
implement huffman algorithm with stl priority-queue, first you must have the file, then the result is saved
本人做的一个二叉堆的课件,附带STL中的priority_queue
gdb 打印功能扩展 ...# std::priority_queue<T> -- via ppqueue command # std::bitset<n> -- via pbitset command # std::string -- via pstring command # std::widestring -- via pwstring command
c++ std stl各容器的应用场合及性能 map hash_map unordered_map multimap list forward_list vector set hash_set multiset unsorted_set queue deque priority_queue
这个文档介绍了PBDS库中的一些数据结构,包括rope、priority_queue以及tree的用法。
STL-ARR,arry, file,list,map,priority_queue,set,share_ptr,stack,string,template,等基本数据类型
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
包含了STL中 dequeue,list,map,multimap,multiset,priority_queue,queue,set,stack,vector等10个代码例子,并列举了各个容器对应的全部函数使用方式,以及函数的调用方式与代码注释,能使您快速掌握STL的...
1、STL标准容器类简介 标准容器类 说明 顺序性容器 vector 相当与数组,从后面快速的插入与删除,直接访问任何元素 deque 双队列,从前面或后面快速的插入与删除,... priority_queue 最高优先级元素总是第一个出列
第20章 priority_queue优先队列容器 275 20.1 priority_queue技术原理 275 20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_...
该篇分为十一部分,分别是:vector类的主要成员...stack类的主要成员、queue类的主要成员、priority_queue类的组要成员、set类的主要成员、multiset类的主要成员、map类的主要成员、multimap类的主要成员、STL算法函数
13_干活要知道在什么框架之下干活 14_结构体类型和变量定义及基本操作 15_结构体元素做函数参数pk结构指针做函数参数 16_结构体做函数基本操作 17_结构体做函数内存分配指针 18_结构中套一级指针 19_结构体中套二级...