C++ STL中的优先队列：实现和用法详解 |21xrx.com

C++ STL中的优先队列：实现和用法详解

2023-06-29 08:27:07 深夜i -- --

C++ STL 优先队列实现用法详解

C++标准库中的STL(Standard Template Library)提供了许多数据结构和算法，其中包括用于实现优先队列的容器——优先队列(priority_queue)。优先队列与普通队列的区别在于元素被弹出的顺序是由元素的权值决定的，而不是FIFO(first in first out)。

实现优先队列

C++中的优先队列是一个封装了底层容器的适配器类，可以封装任何满足序列容器要求的容器，如vector、deque、list等。默认情况下，使用底层容器vector实现优先队列。优先队列在插入元素和弹出元素时都需要进行堆操作来保证元素的权值有序，因此底层容器需要提供支持堆操作的方法，如push_heap()和pop_heap()。

用法详解

创建优先队列

std::priority_queue pq; // 默认使用vector容器，元素类型为int

std::priority_queue , std::greater > pq; // 使用vector容器，元素类型为int，按照元素从小到大排列

std::priority_queue > pq; // 使用deque容器，元素类型为double，按照元素从大到小排列

元素操作

插入元素

void push(const T& value); // 向优先队列中插入一个元素，value为插入元素的值

删除元素

void pop(); // 从优先队列中弹出顶部元素

查看顶部元素

const T& top() const; // 返回优先队列的顶部元素

判断是否为空

bool empty() const; // 判断优先队列是否为空

获取元素个数

size_t size() const; // 获取优先队列中的元素个数

常用操作

优先队列常用的操作包括插入元素、弹出顶部元素、获取顶部元素，如下示例：

std::priority_queue pq;

pq.push(1);

pq.push(3);

pq.push(2);

while (!pq.empty()) {

std::cout << pq.top() << ' '; //输出：3 2 1

pq.pop();

}

std::cout << std::endl;

输出结果按照元素的权值从小到大排列，原因是默认情况下，使用less 进行元素比较，即元素从大到小排列。如果需要顺序相反，可以自定义比较函数：

std::priority_queue , std::greater > pq;

pq.push(1);

pq.push(3);

pq.push(2);

while (!pq.empty()) {

std::cout << pq.top() << ' '; //输出：1 2 3

pq.pop();

}

std::cout << std::endl;

总结

C++ STL中的优先队列是一个非常实用的数据结构，它不仅实现了元素的权值有序，而且通过适配器机制支持底层容器的替换，具有高度的灵活性。在实际应用中，优先队列可用于求解最短路径、排序等问题。

上一篇: idea打包java可执行jar包

下一篇: 《C++嵌入式开发实例精解PDF》

评论区

()

相似文章