类模板：
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> >
class priority_queue;构造函数：
explicit priority_queue (const Compare& comp = Compare(),
const Container& ctnr = Container());
template <class InputIterator>
priority_queue (InputIterator first, InputIterator last,
const Compare& comp = Compare(),
const Container& ctnr = Container());1. 关于构造函数的第一个参数 const Compare& comp
(1) 如果不指定，则采用类模板参数 Compare 创建的对象，而Compare 的默认值为 less()
因此，对于自定义结构，有两种方式实现比较操作：
a. 重载 "<"(即采用 less, 因为 less 重载调动操作符，比较通过 "<" 实现的)
b. 自定义 functor——重载调用操作符的类
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.
实质上，comp 被传给了底层的堆方法，见下文 priority_queue 的实现
2. priority_queue 实质上不是容器，默认底层容器为 vector
This is not a true container, but an @e adaptor. It holds another container, and provides a wrapper interface to that container.
默认底层容器为 vector
The second template parameter defines the type of the underlying sequence/container. It defaults tostd::vector, but it can be any type that supports @cfront(), @cpush_back, @cpop_back, and random-access iterators, such asstd::deque or an appropriate user-defined type.
这一点同 stack, queue
3. priority_queue 的实现与make_heap()、push_heap()、pop_heap()
g++ 中 priority_queue 的实现代码(g++ bits/stl_queue.h)：
#include <vector>
#include <algorithm>
#include <iostream>
/**
* 这段 priority_queue 实现的代码摘自 g++ bits/stl_queue.h
*/
template<typename _Tp, typename _Sequence = std::vector<_Tp>,
typename _Compare = std::less<typename _Sequence::value_type> >
class priority_queue
{
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 these names.
_Sequence c;
_Compare comp;
public:
/**
* @brief Default constructor creates no elements.
*/
explicit priority_queue(const _Compare& __x = _Compare(),
const _Sequence& __s = _Sequence()) : c(__s), comp(__x)
{
std::make_heap(c.begin(), c.end(), comp);
}
/**
* @brief Builds a %queue from a range.
* @param __first An input iterator.
* @param __last An input iterator.
* @param __x A comparison functor describing a strict weak ordering.
* @param __s An initial sequence with which to start.
*
* Begins by copying @a __s, inserting a copy of the elements
* from @a [first,last) into the copy of @a __s, then ordering
* the copy according to @a __x.
*
* For more information on function objects, see the
* documentation on @link functors functor base
* classes@endlink.
*/
template<typename _InputIterator>
priority_queue(_InputIterator __first, _InputIterator __last,
const _Compare& __x = _Compare(),
const _Sequence& __s = _Sequence())
: c(__s), comp(__x)
{
c.insert(c.end(), __first, __last);
std::make_heap(c.begin(), c.end(), comp);
}
/**
* Returns true if the %queue is empty.
*/
bool empty() const
{
return c.empty();
}
/** Returns the number of elements in the %queue. */
size_type size() const
{
return c.size();
}
/**
* Returns a read-only (constant) reference to the data at the first
* element of the %queue.
*/
const_reference top() const
{
return c.front();
}
/**
* @brief Add data to the %queue.
* @param __x Data to be added.
*
* This is a typical %queue operation.
* The time complexity of the operation depends on the underlying
* sequence.
*/
void push(const value_type& __x)
{
c.push_back(__x);
std::push_heap(c.begin(), c.end(), comp);
}
/**
* @brief Removes first element.
*
* This is a typical %queue operation. It shrinks the %queue
* by one. The time complexity of the operation depends on the
* underlying sequence.
*
* Note that no data is returned, and if the first element's
* data is needed, it should be retrieved before pop() is
* called.
*/
void pop()
{
std::pop_heap(c.begin(), c.end(), comp);
c.pop_back();
}
};
int main ()
{
int myints[]= {10,60,50,20};
priority_queue<int, std::vector<int>, std::greater<int> >
first (myints, myints+4);
std::cout << first.top() << std::endl;
first.pop();
std::cout << first.top() << std::endl;
first.push(5);
std::cout << first.top() << std::endl;
return 0;
}(1) priority_queue 中 comp 参数实质上是传递给了 make_heap(), push_heap(), pop_heap(), 而它们都有两种形式：
template <class RandomAccessIterator>
void make_heap (RandomAccessIterator first, RandomAccessIterator last);
template <class RandomAccessIterator, class Compare>
void make_heap (RandomAccessIterator first, RandomAccessIterator last, Compare comp );第一种默认使用 "<", 即
大根堆（父节点的关键码都大于或者等于其子节点的关键码的完全二叉树）；
第二种是指定比较规则，priority_queue 中全部使用的是第二种方式，而 priority_queue 默认使用 less，所以默认也是使用大根堆。
因此，对于自定义结构，使用 priority_queue 时，既可以自己编写比较规则，也可以重载 "<"（即使用默认的 less）
例如上面的代码中用的是 greater，那么就是小根堆。
(2) pop_heap() 注意事项
pop_heap() 并不减少容器中的元素，而是将根节点放在容器尾，使用者自己再将容器尾的元素 pop_back()
// range heap example
#include <iostream> // std::cout
#include <algorithm> // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector> // std::vector
void print_all(std::vector<int> &v)
{
for (unsigned i=0; i<v.size(); ++i)
std::cout << ' ' << v[i];
std::cout << '\n';
}
int main ()
{
int myints[] = {10,20,30,5,15};
std::vector<int> v(myints,myints+5);
std::make_heap (v.begin(),v.end());
std::cout << "initial max heap : " << v.front() << '\n';
std::cout << "all:";
print_all(v);
/**
* pop_heap() 并不减少容器中的元素，而是将根节点放在容器尾，
* 使用者自己再将容器尾的元素 pop_back()
*/
std::pop_heap (v.begin(),v.end());
//v.pop_back();
std::cout << "max heap after pop : " << v.front() << '\n';
std::cout << "all:";
print_all(v);
v.push_back(99);
std::push_heap (v.begin(),v.end());
std::cout << "max heap after push: " << v.front() << '\n';
std::cout << "all:";
print_all(v);
std::sort_heap (v.begin(),v.end());
std::cout << "final sorted range :";
print_all(v);
return 0;
}4. 关于构造函数的第二个参数 const Container& ctnr
stack, queue）
这里的类模板参数（ Container ）和构造函数参数（ ctnr ）都有默认值，搞清楚它们之间的区别和联系。
// constructing priority queues
#include <iostream> // std::cout
#include <queue> // std::priority_queue
#include <vector> // std::vector
#include <functional> // std::greater
typedef std::priority_queue<int, std::vector<int>, std::greater<int> > PQ;
void print_vec(const std::vector<int> &vec)
{
for (std::vector<int>::const_iterator it = vec.begin();
it != vec.end(); ++it)
{
std::cout << *it << " ";
}
std::cout << std::endl;
}
int main ()
{
int myints[]= {10,60,50,20};
PQ first (myints, myints+4);
std::cout << first.top() << std::endl;
first.pop();
std::cout << first.top() << std::endl;
first.push(5);
std::cout << first.top() << std::endl;
std::cout << "-------------------" << std::endl;
//
// 指定第 3,4 个参数
std::greater<int> mygrtr;
std::vector<int> myvec(3, 1);
PQ second (myints, myints+4, mygrtr, myvec);
std::cout << second.top() << std::endl;
print_vec(myvec);
second.pop();
std::cout << second.top() << std::endl;
print_vec(myvec);
second.push(5);
std::cout << second.top() << std::endl;
print_vec(myvec);
return 0;
}
/*
10
20
5
-------------------
1
1 1 1
1
1 1 1
1
1 1 1
*/
结合输出结果，看 priority_queue 实现代码中的这段就更清晰了：
c.insert(c.end(), __first, __last);
5. 容器适配小结——stack, queue, priority_queue
(1) 可以通过类模板参数指定底层容器类型；
(2) 可以通过构造函数指定的底层容器对象初始化；