C++高效利器：优先级队列与反向迭代器

好的，我们来深入探讨C++标准库中的两个重要特性：优先级队列（priority_queue）和反向迭代器（reverse_iterator）。它们在处理特定问题时非常高效。

🧠 1. 优先级队列 (priority_queue)

优先级队列是一种特殊的队列，其元素按优先级出队，而非先进先出。在C++中，它通常基于堆（Heap）实现，位于<queue>头文件中。

核心特性

• 自动排序：元素插入时根据比较规则自动调整位置。
• 高效操作：插入和删除堆顶元素的时间复杂度为$O(\log n)$，访问堆顶元素为$O(1)$。
• 自定义优先级：可通过比较函数（如greater<>或自定义仿函数）修改排序规则。

基本用法

#include <queue> #include <vector> #include <functional> int main() { // 默认大顶堆（降序） std::priority_queue<int> max_heap; // 小顶堆（升序） std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap; // 插入元素 max_heap.push(3); max_heap.push(1); max_heap.push(4); // 访问堆顶（最大值） int top = max_heap.top(); // 4 // 删除堆顶 max_heap.pop(); // 移除4 }

典型场景

• 任务调度（如按优先级处理任务）
• 求Top K问题（如最大的K个数）
• 哈夫曼编码等贪心算法

🔄 2. 反向迭代器 (reverse_iterator)

反向迭代器允许从容器的末尾向开头遍历，位于<iterator>头文件中。所有标准容器（如vector、list、deque）均支持。

核心特性

• 逆向遍历：通过rbegin()和rend()获取反向迭代器。
• 无缝衔接：与正向迭代器兼容，可直接用于算法（如std::sort）。
• 适配器模式：底层通过适配正向迭代器实现。

基本用法

#include <vector> #include <iostream> int main() { std::vector<int> vec = {1, 2, 3, 4}; // 正向遍历 for (auto it = vec.begin(); it != vec.end(); ++it) { std::cout << *it << " "; // 1 2 3 4 } // 反向遍历 for (auto rit = vec.rbegin(); rit != vec.rend(); ++rit) { std::cout << *rit << " "; // 4 3 2 1 } }

典型场景

• 逆序处理数据（如从后往前修改字符串）
• 与算法结合（如std::copy到另一个容器的末尾）
• 实现双向操作的数据结构

💡 组合使用示例

假设需要按升序输出最后K个最大值：

#include <queue> #include <vector> #include <iostream> int main() { std::vector<int> data = {9, 3, 5, 2, 8}; int k = 3; // 小顶堆保存最大的K个数 std::priority_queue<int, std::vector<int>, std::greater<int>> pq; for (int num : data) { pq.push(num); if (pq.size() > k) pq.pop(); } // 用反向迭代器逆序输出（升序→降序） std::vector<int> result; while (!pq.empty()) { result.push_back(pq.top()); pq.pop(); } for (auto rit = result.rbegin(); rit != result.rend(); ++rit) { std::cout << *rit << " "; // 输出：9 8 5 } }

🧩 总结

掌握这两者，能大幅提升对C++容器复杂场景的处理能力。 🚀