STLRecipe---priority_queue

• priority_queue容器适配器定义了一个元素有序排列的队列，默认队列头部的元素优先级最高。

priority_queue模板有 3 个参数，其中两个有默认的参数；
第一个参数是存储对象的类型，
第二个参数是存储元素的底层容器，
第三个参数是函数对象，它定义了一个用来决定元素顺序的断言。
因此模板类型是：

template <typename T, typename Container=std::vector<T>, typename Compare=std::less<T>> 
class priority_queue

看出priority_queue 实例默认有一个 vector 容器。函数对象类型 less<T> 是一个默认的排序断言，定义在头文件 function 中，决定了容器中最大的元素会排在队列前面。
function 中定义了 greater<T>，用来作为模板的最后一个参数对元素排序，最小元素会排在队列前面。

• 如果指定模板的最后一个参数，就必须提供另外的两个模板类型参数。

图 1 中显示元素的方式反映了它们被检索的顺序。在 vector 中它们也可以不像这样排序。

• 创建 priority_queue：

std::priority_queue<std::string> words; 
std::string wrds[] { "one", "two", "three", "four"};

初始化列表中的序列可以来自于任何容器，并且不需要有序。优先级队列会对它们进行排序。
// "two" "three" "one" "four" 
std::priority_queue<std::string> words { std::begin(wrds),std:: end(wrds)}; 

可以生成 vector 或 deque 容器，然后用它们来初始化 priority_queue。
下面展示了如何以 vector 的元素作为初始值来生成 priority_queue 对象：
std::vector<int> values{21, 22, 12, 3, 24, 54, 56};
std::priority_queue<int> numbers {std::less<int>(),values};

拷贝构造函数会生成一个和现有对象同类型的 priority_queue 对象，它是现有对象的一个副本。例如：

std::priority_queue<std::string> copy_words {words}; // copy of words 

当对容器内容反向排序时，最小的元素会排在队列前面，这时候需要指定 3 个模板类型参数：

std:: string wrds[] {"one", "two", "three", "four"};
//"four" "one" "three" "two"
std::priority_queue<std::string, std::vector<std::string>,std: :greater<std::string>> 
words1 {std::begin (wrds) , std:: end (wrds) }; 

• 优先级队列中用来保存元素的容器是私有的，因此只能通过调用 priority_queue 对象的成员函数来对容器进行操作。

priority_queue 操作

• 对 priority_queue 进行操作有一些限制：
• push(const T& obj)：将obj的副本放到容器的适当位置，这通常会包含一个排序操作。
• push(T&& obj)：将obj放到容器的适当位置，这通常会包含一个排序操作。
• emplace(T constructor a rgs...)：通过调用传入参数的构造函数，在序列的适当位置构造一个T对象。为了维持优先顺序，通常需要一个排序操作。
• top()：返回优先级队列中第一个元素的引用。
• pop()：移除第一个元素。
• size()：返回队列中元素的个数。
• empty()：如果队列为空的话，返回true。
• swap(priority_queue<T>& other)：和参数的元素进行交换，所包含对象的类型必须相同。

例子：下面展示了如何列出优先级队列 words 的内容：

1. priority_queue 没有迭代器。如果想要访问全部的元素，比如说，列出或复制它们，会将队列清空；priority_queue 和 queue 有相同的限制。如果想在进行这样的操作后，还能保存它的元素，需要先把它复制一份，这里可以使用一个不同类型的容器。

这里首先生成了一个 words 的副本，因为输出 words 会移除它的内容

std::priority_queue<std::string> words_copy {words}; // A copy for output
while (!words_copy.empty())
{
    std:: cout << words_copy.top () <<" ";
    words_copy.pop();
}
std::cout << std::endl;

---