顺序容器 — priority_queue
最后更新于：2022-04-01 19:54:35
拥有权值的queue，权值最高者永远排在最前面。priority_queue以vector为底层容器，配合heap的一套泛型算法，就能实现相应功能。
代码如下：
~~~
template ,
class Compare = less >
class priority_queue {
....
protected:
Sequence c; // 底层容器
Compare comp; // 比较标准
....
template
priority_queue(InputIterator first, InputIterator last, const Compare& x)
: c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); } // 将vector变为heap
template
priority_queue(InputIterator first, InputIterator last)
: c(first, last) { make_heap(c.begin(), c.end(), comp); } // 将vector变为heap
bool empty() const { return c.empty(); }
size_type size() const { return c.size(); }
const_reference top() const { return c.front(); }
void push(const value_type& x) {
__STL_TRY {
c.push_back(x); // 先压入vector
push_heap(c.begin(), c.end(), comp); // 再调整
}
__STL_UNWIND(c.clear());
}
void pop() {
__STL_TRY {
pop_heap(c.begin(), c.end(), comp); // 最大元素放vector尾部
c.pop_back(); // 弹出
}
__STL_UNWIND(c.clear());
}
};
~~~
priority_queue内部代码很简单，都是直接调用vector或heap的提供的一些接口。由于priority_queue和queue一样也具有“先进先出”的性质，所以没有定义迭代器。
参考：
《STL源码剖析》 P183.
';