好的！既然你提到了 C++ 标准库中的容器适配器 <priority_queue>，我将为你详细讲解它的用法，包括基本概念、特性、功能以及实用示例。<priority_queue> 是 C++ STL 中的优先级队列容器适配器，默认实现为最大堆（max-heap），元素按优先级顺序出队。它基于底层容器（如 <vector>）实现，提供高效的优先级管理。以下是完整的内容，适合学习和实践。

C++ 标准库：<priority_queue>

<priority_queue> 是一个模板类，封装了优先级队列的行为。它的主要特点是：

  • 优先级顺序：元素按优先级出队，默认最高优先级先出（最大堆）。
  • 适配器设计：基于底层容器（如 <vector>、<deque>）和比较器实现。
  • 动态大小：大小随元素增减动态调整。
  • 堆结构：内部维护堆数据结构，确保顶部元素始终是优先级最高的。

包含头文件

#include <queue> // 注意：priority_queue 和 queue 在同一头文件中
#include <iostream>

定义格式

std::priority_queue<类型, 底层容器, 比较器> 变量名;
  • 类型：队列中元素的数据类型（如 int、double、std::string）。
  • 底层容器：可选，默认是 std::vector<T>，也可以指定为 std::deque<T>。
  • 比较器：可选，默认是 std::less<T>（最大堆），可改为 std::greater<T>（最小堆）。

基本用法

1. 声明和初始化（最大堆）

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq; // 默认最大堆
    pq.push(10);                 // 入队
    pq.push(30);
    pq.push(20);

    std::cout << "Top: " << pq.top() << std::endl; // 输出：30
    return 0;
}
  • 元素按降序排列，最大值在顶部。

2. 入队和出队

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(50);
    pq.push(30);

    std::cout << "Top: " << pq.top() << std::endl; // 输出：50
    pq.pop(); // 出队（移除最大元素）
    std::cout << "After pop: " << pq.top() << std::endl; // 输出：30
    return 0;
}
  • push()：O(log n)，插入并调整堆。
  • pop()：O(log n)，移除顶部元素并调整堆。

3. 访问顶部元素

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<std::string> pq;
    pq.push("Apple");
    pq.push("Banana");
    pq.push("Cherry");

    std::cout << "Top: " << pq.top() << std::endl; // 输出：Cherry（字典序最大）
    return 0;
}
  • top()：O(1)，返回顶部元素的引用。
  • 无 front() 或 back()，只能访问顶部。

4. 大小和状态

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;
    std::cout << "Empty? " << (pq.empty() ? "Yes" : "No") << std::endl; // 输出：Yes
    std::cout << "Size: " << pq.size() << std::endl;                    // 输出：0

    pq.push(1);
    pq.push(2);
    std::cout << "Empty? " << (pq.empty() ? "Yes" : "No") << std::endl; // 输出：No
    std::cout << "Size: " << pq.size() << std::endl;                    // 输出：2
    return 0;
}
  • empty()：O(1)。
  • size()：O(1)。

5. 自定义比较器（最小堆）

#include <queue>
#include <iostream>

int main() {
    // 使用 std::greater 实现最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);

    std::cout << "Top: " << pq.top() << std::endl; // 输出：10
    pq.pop();
    std::cout << "After pop: " << pq.top() << std::endl; // 输出：20
    return 0;
}
  • std::greater<T>：元素按升序排列，最小值在顶部。

6. 自定义类型

#include <queue>
#include <iostream>
#include <string>

struct Task {
    std::string name;
    int priority;
    Task(const std::string& n, int p) : name(n), priority(p) {}
    // 重载 < 运算符（最大堆需要反向比较）
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }
};

int main() {
    std::priority_queue<Task> pq;
    pq.emplace("Write code", 2);
    pq.emplace("Test app", 1);
    pq.emplace("Deploy", 3);

    std::cout << "Tasks by priority:\n";
    while (!pq.empty()) {
        std::cout << pq.top().name << " (Priority: " << pq.top().priority << ")\n";
        pq.pop();
    }
    return 0;
}

输出：

Tasks by priority:
Deploy (Priority: 3)
Write code (Priority: 2)
Test app (Priority: 1)
  • emplace()：直接构造对象入队，避免拷贝。

与其他容器的对比

特性std::priority_queuestd::queuestd::stack
数据结构堆（默认最大堆）队列（FIFO）栈（LIFO）
访问方式仅顶部（优先级最高）队首/队尾仅栈顶
插入/删除O(log n)O(1)O(1)
底层容器默认 vector默认 deque默认 deque
迭代器不支持不支持不支持

注意事项

  1. 接口限制：无迭代器，只能访问顶部元素。
  2. 异常安全：top() 或 pop() 在空队列上调用是未定义行为，需检查 empty()。
  3. 底层容器：
  • 默认 <vector>：适合堆操作，支持随机访问。
  • <deque>：也可使用，但无明显优势。
  • <list> 不适用（堆需要随机访问）。
  1. 性能：插入和删除为 O(log n)，依赖堆调整。

实用示例：调度优先级任务

以下是一个模拟任务调度的示例：

#include <queue>
#include <iostream>
#include <string>

int main() {
    std::priority_queue<std::pair<int, std::string>> pq; // 优先级, 任务名
    pq.emplace(2, "Write code");
    pq.emplace(1, "Test app");
    pq.emplace(3, "Deploy");

    std::cout << "Processing tasks by priority:\n";
    while (!pq.empty()) {
        std::cout << "Priority " << pq.top().first << ": " << pq.top().second << "\n";
        pq.pop();
    }
    return 0;
}

输出：

Processing tasks by priority:
Priority 3: Deploy
Priority 2: Write code
Priority 1: Test app

小练习

以下是一个基于 <priority_queue> 的练习题，你可以尝试：

问题：

写一个 C++ 程序：

  1. 定义一个 std::priority_queue<int>（最大堆）。
  2. 依次入队 10、50、30、20、40。
  3. 输出顶部元素。
  4. 出队两个元素。
  5. 输出剩余元素个数和顶部元素。

参考答案（你可以先尝试）

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int> pq;

    // 入队
    pq.push(10);
    pq.push(50);
    pq.push(30);
    pq.push(20);
    pq.push(40);

    // 输出顶部
    std::cout << "Top: " << pq.top() << std::endl; // 输出：50

    // 出队两个元素
    pq.pop();
    pq.pop();

    // 输出剩余元素个数和顶部
    std::cout << "Size: " << pq.size() << std::endl;    // 输出：3
    std::cout << "New top: " << pq.top() << std::endl;  // 输出：30

    return 0;
}

下一步

  • 如果你想试试这个练习，请写下你的代码，我会帮你检查。
  • 如果你想要更复杂的内容（如最小堆应用、自定义比较器扩展），或者设计 <priority_queue> 的测验题，请告诉我！
  • 你也可以提出具体问题，如“如何用 <priority_queue> 实现调度算法？”或“<priority_queue> 和 <queue> 的区别？”。

现在，你想做什么？试试练习，还是有其他需求？