聊聊C++标准库中优先队列priority_queue的源码
O(logn)
C++标准库提供了优先队列priority_queue，顾名思义，就是可以按照优先级出队的队列，⽽且时间复杂度为，算法中有很多优化项就是⽤优先队列来优化的。
C++11的标准库是怎么构造出优先队列的呢？优先队列是⽤堆来构造的。所以，优先队列其实并不能叫队列，它的完整定义应该是这样的：优先队列是⽤堆来构造，包装成队列的适配器。
其实想⼀想，堆确实适合构造优先队列，优先队列每次需要弹出优先级最⼤的元素，⽽堆的堆顶恰巧就是优先级最⼤的元素，关于C++11中的堆，可以参考。
那就⼀起来看看MinGW中C++11的标准库stl_queue.h中的priority_queue的源码。
先来看看标准库对优先队列的介绍：
/**
* @brief A standard container automatically sorting its contents.
*
* @ingroup quences
*
* @tparam _Tp Type of element.
* @tparam _Sequence Type of underlying quence, defaults to vector<_Tp>.
* @tparam _Compare Comparison function object type, defaults to
* less<_Sequence::value_type>.
*
* This is not a true container, but an @e adaptor. It holds
* another container, and provides a wrapper interface to that
* container. The wrapper is what enforces priority-bad sorting
* and %queue behavior. Very few of the standard container/quence
* interface requirements are met (e.g., iterators).
*
* The cond template parameter defines the type of the underlying
* quence/container. It defaults to std::vector, but it can be
* any type that supports @c front(), @c push_back, @c pop_back,
her hair* and random-access iterators, such as std::deque or an
* appropriate ur-defined type.
*
* The third template parameter supplies the means of making
* priority comparisons. It defaults to @c less<value_type> but
鼓手英文
* can be anything defining a strict weak ordering.
*
* Members not found in @a normal containers are @c container_type,
* which is a typedef for the cond Sequence parameter, and @c
* push, @c pop, and @c top, which are standard %queue operations.
*
* @note No equality/comparison operators are provided for
* %priority_queue.
*
* @note Sorting of the elements takes place as they are added to,
* and removed from, the %priority_queue using the
教学评价设计
* %priority_queue's member functions. If you access the elements
* by other means, and change their data such that the sorting
* order would be different, the %priority_queue will not re-sort
* the elements for you. (How could it know to do so?)
*/
这⾥⾯⼤致说了优先队列⽀持哪些成员函数，⽤了哪个数据结构来存储元素，排序规则等等。
judgedtemplate <typename _Tp, typename _Sequence = vector<_Tp>,
typename _Compare = less<typename _Sequence::value_type>>
class priority_queue
{
carpenter是什么意思
public:
typedef typename _Sequence::value_type value_type;
typedef typename _Sequence::reference reference;
typedef typename _Sequence::const_reference const_reference;
typedef typename _Sequence::size_type size_type;
typedef _Sequence container_type;
protected:
// See queue::c for notes on the names.
_Sequence c;
_Compare comp;
}
模板参数中，_Sequence默认是vector<_Tp>，也就是说priority_queue默认以vector作为容器，但是⽀持任意
有push_back，pop_back，front成员函数，并且提供随机迭代器的容器；
然后就是容器必须的五个类型重定义；
成员函数只有序列c和⽐较函数comp。
从类的模板参数可以看出来，如果想要⾃定义优先级，那么就必须把第⼆个模板参数显⽰地写出来，即std::priority_queue<int, std::vector<int>, std::greater<int>>
public:
explicit priority_queue(const _Compare &__x,
const _Sequence &__s)
:c(__s),comp(__x)
{
std::make_heap(c.begin(), c.end(), comp);
}
explicit priority_queue(const _Compare &__x =_Compare(),
excited怎么读_Sequence &&__s =_Sequence())
:c(std::move(__s)),comp(__x)
{
std::make_heap(c.begin(), c.end(), comp);
}
template <typename _InputIterator>
priority_queue(_InputIterator __first, _InputIterator __last,
const _Compare &__x,
const _Sequence &__s)
:c(__s),comp(__x)
{
c.d(), __first, __last);
std::make_heap(c.begin(), c.end(), comp);
}
template <typename _InputIterator>
priority_queue(_InputIterator __first, _InputIterator __last,
const _Compare &__x =_Compare(),
_Sequence &&__s =_Sequence())
:c(std::move(__s)),comp(__x)
{
会计从业资格考试科目c.d(), __first, __last);
std::make_heap(c.begin(), c.end(), comp);
}
可以看到，priority_queue的构造函数就是在造⼀个堆。
吸血鬼日记第4季
bool empty()const
{
pty();
}
size_type size()const
{
return c.size();
}
const_reference top()const
{
return c.front();
}
void push(const value_type &__x)
{
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
void push(value_type &&__x)
{
c.push_back(std::move(__x));
std::push_heap(c.begin(), c.end(), comp);
}
template & _Args>
void emplace(_Args &&... __args)peking
{
std::push_heap(c.begin(), c.end(), comp);
}
void pop()
{
std::pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
void swap(priority_queue &__pq)noexcept(noexcept(swap(c, __pq.c))&&noexcept(swap(comp, __pq.comp)))
{
using std::swap;
swap(c, __pq.c);
swap(comp, __pq.comp);新闻翻译
}
这些都是priority_queue的成员函数，其中emplace和swap是C++11新增的成员函数，emplace默认调⽤std::vector::emplace_back来构造元素；
出队就std::pop_heap; std::vector::pop_back;，⼊队就std::vector::push_back; std::push_heap;。
template <typename _Tp, typename _Sequence, typename _Compare>
inline void swap(priority_queue<_Tp, _Sequence, _Compare>&__x,
priority_queue<_Tp, _Sequence, _Compare>&__y)noexcept(noexcept(__x.swap(__y)))
{
__x.swap(__y);
}
template <typename _Tp, typename _Sequence, typename _Compare, typename _Alloc>
struct us_allocator<priority_queue<_Tp, _Sequence, _Compare>, _Alloc>
: public us_allocator<_Sequence, _Alloc>::type
{
};
这两个是C++11为priority_queue做的两个特化。
