STL教程(十二): 适配器--priority_queue

admin管理员组

文章数量:1623789

一、priority_queue简介

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

参数说明：

• T：元素的类型 priority_queue::value_type
• Container ：存储元素的内部底层容器对象的类型--queue::container_type，默认为vector
• Compare ：接受两个元素（T 类型）作为参数并返回布尔值的二元谓词。默认为递增

priority_queue被实现为容器适配器，它根据一些严格的排序方法Compare，为其内部元素进行排序，它提供对最大（默认情况下）元素的恒定时间查找，代价是插入和提取。它使用特定容器类的封装对象作为其底层容器的类，提供一组特定的成员函数来访问其元素。

标准容器类deque和vector都满足其作为priority_queue底层容器要求。默认情况下，使用vector作为其底层容器。

二、priority_queue的成员函数

1、构造函数

（1）构造一个priority_queue适配器，并使用comp作为比较函数，ctnr容器中的元素副本作为其数据内容

priority_queue (const Compare& comp, const Container& ctnr);

（2）构造一个priority_queue适配器，并使用comp作为比较函数，将ctnr容器中的元素移动到该适配器中

explicit priority_queue (const Compare& comp = Compare(),
                         Container&& ctnr = Container());

（3）使用ctnr容器中[first,last)区间内的元素的副本赋值到适配器中

template <class InputIterator>
  priority_queue (InputIterator first, InputIterator last,
                  const Compare& comp, const Container& ctnr);

（4）将ctnr容器中[first,last)区间内的元素移动到适配器中

template <class InputIterator>
  priority_queue (InputIterator first, InputIterator last,
                  const Compare& comp, Container&& ctnr = Container());

（5）使用特定的分配器构造一个适配器。

template <class Alloc> explicit priority_queue (const Alloc& alloc);
template <class Alloc> priority_queue (const Compare& comp, const Alloc& alloc);
template <class Alloc> priority_queue (const Compare& comp, const Container& ctnr,
                                       const Alloc& alloc);
template <class Alloc> priority_queue (const Compare& comp, Container&& ctnr,
                                       const Alloc& alloc);
template <class Alloc> priority_queue (const priority_queue& x, const Alloc& alloc);
template <class Alloc> priority_queue (priority_queue&& x, const Alloc& alloc);

示例代码：

#include <iostream>       // std::cout
#include <deque>          // std::priority_queue
#include <vector>         // std::vector
#include <functional>     // std::greater
#include <queue>
#include <list>

using namespace std;

int main ()
{
  // (1) priority_queue默认使用vector作为其底层容器，如果要使用std::deque作为其数据来源，则需要则构造时，显示指明
  std::vector<int> vec {3, 1, 4, 1, 5};
  std::priority_queue<int> pq1 {std::less<int>(),vec};
  cout<<"pq1 = ";
  int len = pq1.size();
  for (int i = 0; i < len; ++i) {
      cout<<pq1.top()<<"    ";
      pq1.pop();
  }

  std::deque<int> de {3, 1, 4, 1, 5};
  std::priority_queue<int,std::deque<int>> pq2 {std::less<int>(),de};
  cout<<"\npq2 = ";
  len = pq2.size();
  for (int i = 0; i < len; ++i) {
      cout<<pq2.top()<<"    ";
      pq2.pop();
  }


 //（2）将pq1内的元素移动到pq3内，此时，pq1内元素个数为0
  std::priority_queue<int> pq3 {std::less<int>(),std::move(vec)};
  std::cout <<"\nvec.size() = "<< vec.size();
  cout<<"\npq3 = ";
  len = pq3.size();
  for (int i = 0; i < len; ++i) {
      cout<<pq3.top()<<"    ";
      pq3.pop();
  }

 //（3）将vec2的元素的副本以及[first,last)内元素赋值到适配器中
  std::vector<int> vec2 {3, 1, 4, 1, 5};
  std::priority_queue<int> pq4 {vec2.begin(),vec2.end(),std::less<int>(),vec2};
  cout<<"\npq4 = ";
  len = pq4.size();
  for (int i = 0; i < len; ++i) {
      cout<<pq4.top()<<"    ";
      pq4.pop();
  }

 //（4）将vec2的元素移动到适配器中，并将[first,last)内元素赋值到适配器中
  std::vector<int> vec3{33, 11, 41, 11, 52};
  std::priority_queue<int> pq5 {vec3.begin(),vec3.end(),std::less<int>(),std::move(vec2)};
  std::cout << "\nvec2.size(): "<<vec2.size();
  std::cout << "\nvec3.size(): "<<vec3.size();
  cout<<"\npq5 = ";
  len = pq5.size();
  for (int i = 0; i < len; ++i) {
      cout<<pq5.top()<<"    ";
      pq5.pop();
  }

  return 0;
}

//输出为：
pq1 = 5    4    3    1    1    
pq2 = 5    4    3    1    1
vec.size() = 0
pq3 = 5    4    3    1    1
pq4 = 5    5    4    4    3    3    1    1    1    1
vec2.size(): 0
vec3.size(): 5
pq5 = 52    41    33    11    11    5    4    3    1    1

2、operator=函数

（1）将该适配器的内容通过赋值方式替换为other元素

priority_queue& operator=( const priority_queue& other );

（2）将该适配器的内容通过移动方式替换为other元素

priority_queue& operator=( priority_queue&& other );

3、元素访问

// 返回适配器中的顶部元素
const_reference top() const

4、容量

bool empty(); // 判断容器是否为空
size_type size();// 返回容器中当前元素个数

5、元素操作

// 将值为value的元素放入到适配器中
void push(const value_type& value );
void push(value_type&& value );

// 根据参数args就地构造新元素，并放入到适配器中
template< class... Args >
void emplace( Args&&... args );

// 移除适配器中的顶部元素
void pop();

// 与适配器other交换内容
void swap (priority_queue& other);

本文标签： 适配器教程stlpriorityqueue十二