在C++中,优先级队列(std::priority_queue)是一个功能强大的容器适配器,它基于堆实现,提供了基于元素优先级的快速访问和排序功能。下面,我们将结合代码示例来深入理解std::priority_queue的使用方法和实战技巧。
基本用法
std::priority_queue的基本使用示例如下:
#include <iostream>
#include <queue>
int main() {
// 创建一个整型的最大堆
std::priority_queue<int> pq;
// 添加元素
pq.push(3);
pq.push(1);
pq.push(4);
// 访问顶部元素
std::cout << "Top element: " << pq.top() << std::endl; // 输出 4
// 移除顶部元素
pq.pop();
std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 3
// 检查队列是否为空
if (pq.empty()) {
std::cout << "Queue is empty." << std::endl;
}
else {
std::cout << "Queue is not empty." << std::endl;
}
// 获取队列大小
std::cout << "Size of queue: " << pq.size() << std::endl; // 输出 2
return 0;
}
如上示例代码中使用了priority_queue的push、pop、top、empty、size函数,其中:
自定义比较函数
默认情况下,std::priority_queue使用std::less<T>作为比较函数实现最大堆,其也支持用户指定比较函数,如指定STL内置的比较算法,甚至自定义比较函数
使用内置比较算法
在如上的代码中,指定优先级队列的比较函数为std::greater,构建一个小顶堆,只需修改一行代码,如下:
// 创建一个整型的小顶堆
std::priority_queue<int,std::vector<int>,std::greater<int>> pq;
//其余代码同上例
自定义比较函数
std::priority_queue支持自定义比较函数,示例代码如下:
#include <iostream>
#include <queue>
#include <functional>
struct Person {
std::string name;
int age;
public:
Person(const std::string& n, int a) : name(n), age(a) {}
};
// 自定义比较函数,实现最小堆
struct ComparePerson {
bool operator()(const Person& p1, const Person& p2)
{
return p1.age > p2.age;
}
};
int main() {
std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;
pq.push(Person("Alice", 25));
pq.push(Person("Bob", 20));
pq.push(Person("Charlie", 30));
std::cout << "Top element (youngest person): " \
<< pq.top().name << ", " \
<< pq.top().age << std::endl; // 输出 Charlie, 30
return 0;
}
改变底层容器
默认情况下,priority_queue使用std::vector作为底层容器。但其支持在构造对象时显示指定其底层容器,如上例中在构造对象pq时指定容器为std::vector<>;也可以使用std::deque或`std::std::list作为底层容器。
//以std::queue作为底层容器
int main() {
std::priority_queue<int, std::deque<int>, std::less<int>> pq;
pq.push(3);
pq.push(1);
pq.push(4);
// 访问顶部元素
std::cout << "Top element: " << pq.top() << std::endl; // 输出 4
// 移除顶部元素
pq.pop();
std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 3
return 0;
}
注意:由于priority_queue需要支持随机访问和高效的插入和删除操作,因此并不是所有的容器都适合作为底层容器。
优先级队列的遍历
在C++标准库中std::priority_queue并未直接提供遍历元素的接口,因为它是基于堆实现的,主要优化了插入和顶部元素的取出操作。所以针对优先级队列的遍历需要将值一个个取出来,示例代码如下:
int main() {
std::priority_queue<int> pq;
pq.push(20);
pq.push(15);
pq.push(30);
while (!pq.empty()) {
// 理论述逻辑上访问顶部元素,实际STL priority_queue不支持直接遍历
std::cout << pq.top() << " ";
// 正常情况下这里无法直接pop后继续遍历,因为会改变pq
// 这里仅为示意,实际代码中不能如此操作
pq.pop();
}
std::cout<<"\n";
return 0;
}
/*output:
30 20 15
*/
当然将队列中所有的数据取出来放到支持迭代器的数据结构中,但是那已是对应数据结构的特性。
总结
C++的priority_queue是一个功能强大的容器适配器,它基于堆实现,提供了基于元素优先级的快速访问和排序功能。通过自定义比较函数,你可以轻松地改变priority_queue的排序方式。priority_queue虽好,但在选用数据结构要结合应用场景,慎重抉择。