admin管理员组文章数量:1624351
文章目录
- 【 1. 基本原理 】
- 【 2. priority_queue 的创建 】
- 2.1 创建一个空的 priority_queue
- 2.2 使用普通数组或其它容器中指定范围内的数据,对 priority_queue 初始化
- 2.3 指定 priority_queue 使用的底层容器以及排序规则
- 【 3. priority_queue 的成员函数 】
- 实例
【 1. 基本原理 】
-
priority_queue 优先级队列 容器适配器模拟的也是队列这种存储结构,但是,riority_queue 容器适配器中元素的存和取,遵循的并不是 First in,First out(先入先出)原则,而是 First in, Largest out(优先级最大先出) 原则,即:先进队列的元素并不一定先出队列,而是优先级最大的元素最先出队列。
-
priority_queue 容器适配器为了保证 每次从队头移除的都是当前优先级最高的元素,每当有新元素进入,它都会根据既定的排序规则找到优先级最高的元素,并将其移动到队列的队头;同样,当 priority_queue 从队头移除出一个元素之后,它也会再找到当前优先级最高的元素,并将其移动到队头。
-
那么,priority_queue 容器适配器中存储的元素,优先级是如何评定的呢?很简单,每个 priority_queue 容器适配器在创建时,都制定了一种排序规则。根据此规则,该容器适配器中存储的元素就有了优先级高低之分。
假设当前有一个 priority_queue 容器适配器,其制定的排序规则是按照元素值从大到小进行排序。根据此规则,自然是 priority_queue 中值最大的元素的优先级最高。
【 2. priority_queue 的创建 】
- priority_queue 容器适配器模板位于 <queue> 头文件 中,并定义在 std 命名空间 里,
- STL 中,priority_queue 容器适配器的定义如下:
priority_queue 容器适配器模板类最多可以传入 3 个参数,它们各自的含义如下:- typename T:指定存储元素的具体类型;
- typename Container:指定 priority_queue 底层使用的基础容器,默认使用 vector 容器。
作为 priority_queue 容器适配器的底层容器,其必须包含 empty()、size()、front()、push_back()、pop_back() 这几个成员函数,STL 序列式容器中只有 vector 和 deque 容器符合条件。 - typename Compare:指定容器中评定元素优先级所遵循的排序规则,默认使用 std::less<T> 按照元素值从大到小进行排序,还可以使用 std::greater<T> 按照元素值从小到大排序,但更多情况下是使用自定义的排序规则。
其中,std::less<T> 和 std::greater<T> 都是以函数对象的方式定义在 头文件中。
template <typename T,
typename Container=std::vector<T>,
typename Compare=std::less<T> >
class priority_queue{
//......
}
2.1 创建一个空的 priority_queue
- 创建1个空的 priority_queue 容器适配器,底层采用默认的 vector 容器,排序方式也采用默认的 std::less<T> 方法:
priority_queue<int> values;
2.2 使用普通数组或其它容器中指定范围内的数据,对 priority_queue 初始化
- 必须保证数组或容器中存储的元素类型和 priority_queue 指定的存储类型相同。用来初始化的数组或容器中的数据不需要有序,priority_queue 会自动对它们进行排序。
//使用普通数组
int values[]{4,1,3,2};
priority_queue<int>copy_values(values,values+4);//{4,2,3,1}
//使用序列式容器
array<int,4>values{ 4,1,3,2 };
priority_queue<int>copy_values(values.begin(),values.end());//{4,2,3,1}
2.3 指定 priority_queue 使用的底层容器以及排序规则
int values[]{ 4,1,2,3 };
priority_queue<int,deque<int>, greater<int> >copy_values(values, values+4);//{1,3,2,4}
【 3. priority_queue 的成员函数 】
成员函数 | 功能 |
---|---|
empty() | 如果 priority_queue 为空的话,返回 true;反之,返回 false。 |
size() | 返回 priority_queue 中存储元素的个数。 |
top() | 返回 priority_queue 中第一个元素的引用形式。 |
push(const T& obj) | 根据既定的排序规则,将元素 obj 的副本存储到 priority_queue 中适当的位置。 |
push(T&& obj) | 根据既定的排序规则,将元素 obj 移动存储到 priority_queue 中适当的位置。 |
emplace(Args&&… args) Args&&… args | 表示构造一个存储类型的元素所需要的数据(对于类对象来说,可能需要多个数据构造出一个对象)。此函数的功能是根据既定的排序规则,在容器适配器适当的位置直接生成该新元素。 |
pop() | 移除 priority_queue 容器适配器中第一个元素。 |
swap(priority_queue& other) | 将两个 priority_queue 容器适配器中的元素进行互换,需要注意的是,进行互换的 2 个 |
- 和 queue 一样, priority_queue 也没有迭代器,因此访问元素的唯一方式是遍历容器,通过不断移除访问过的元素,去访问下一个元素。
实例
#include <iostream>
#include <queue>
using namespace std;
int main()
{
//创建一个空的priority_queue容器适配器
priority_queue<int>values;
//使用 push() 成员函数向适配器中添加元素
values.push(3);//{3}
values.push(1);//{3,1}
values.push(4);//{4,1,3}
values.push(2);//{4,2,3,1}
//遍历整个容器适配器
while (!values.empty())
{
//输出第一个元素并移除。
cout << values.top() << " ";
values.pop();//移除队头元素的同时,将剩余元素中优先级最大的移至队头
}
return 0;
}
版权声明:本文标题:【C++ STL容器适配器】priority_queue 优先级队列 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728894851a1178277.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论