C++ 优先队列priority_queue
priority_queue
priority_queue 是 C++ 标准库中的一个容器适配器，定义在头文件 <queue> 中。它提供了一种优先队列的数据结构，类似于堆，能够根据元素的优先级来组织数据。默认情况下，它是一个最大堆，即最大的元素总是位于队首。你可以通过自定义比较函数实现最小堆。
一.特性
最大堆：默认情况下，priority_queue 是最大堆，队首元素是最大值。
动态大小：可以动态调整队列大小。
不支持随机访问：不像 vector 或 deque，你无法通过索引访问 priority_queue 中的元素。
二.模板定义
template <class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type>> |
T：存储的元素类型。Container：用于存储元素的底层容器，默认是 std::vector。Compare：比较函数对象，默认是 std::less<T>，实现最大堆。
三.用法示例
1.基本用法
int main() {
std::priority_queue<int> pq;
pq.push(10);
pq.push(5);
pq.push(20);
// 输出队首元素（最大值）：20
std::cout << "Top element: " << pq.top() << std::endl;
pq.pop(); // 移除队首元素
// 输出新的队首元素（剩余最大值）：10
std::cout << "New top element: " << pq.top() << std::endl;
return 0;
}
2.最小堆的实现
可以通过自定义比较器来构造最小堆，将 std::greater<T> 作为第三个模板参数，或者使用负值来实现最小堆。
int main() {
// 使用 std::greater<int> 创建最小堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
min_pq.push(10);
min_pq.push(5);
min_pq.push(20);
// 输出最小值：5
std::cout << "Top element (min): " << min_pq.top() << std::endl;
return 0;
}
3.自定义类型的优先队列
你可以自定义比较器来处理复杂类型，如 struct 或 class。
struct Task {
int priority;
std::string name;
// 自定义比较器，按优先级比较
bool operator<(const Task& other) const {
return priority < other.priority;
}
};
int main() {
std::priority_queue<Task> task_pq;
task_pq.push({3, "Task C"});
task_pq.push({1, "Task A"});
task_pq.push({2, "Task B"});
// 输出优先级最高的任务
std::cout << "Top task: " << task_pq.top().name << std::endl; // 输出: Task C
return 0;
}
四.常用成员函数
1.push()
向优先队列中添加一个元素。 pq.push(30);
2.pop()
移除队首元素（优先级最高的元素）。注意，这不会返回该元素的值，所以需要在调用 pop() 之前先使用 top() 来获取队首元素。 pq.pop();
3.top()
返回优先队列中的队首元素，即优先级最高的元素，但不移除它。 int highest = pq.top();
4.empty()
检查优先队列是否为空，返回 true 表示为空，false 表示不为空。 if (pq.empty()) {
// 队列为空
}
5.size()
返回优先队列中的元素个数。 std::cout << "Size: " << pq.size() << std::endl;
Pair
pair 是 C++ 标准库中的一个模板类，定义在头文件<utility> 中。它用于存储一对值，可以是不同类型的值，提供了方便的方式来关联两个数据元素。
一.特性
- pair 是一个模板类，可以容纳两个类型不同的值。
- 两个值可以直接通过 first 和 second 成员变量来访问。
- 常用于将两个相关联的值打包在一起传递或存储，像是键值对。
二.模板定义
template <class T1, class T2> |
- T1：第一个元素的类型。
- T2：第二个元素的类型。
二.创建 pair
1.直接初始化std::pair<int, std::string> p(1, "apple");
该语句创建了一个 pair，其中 first 为整数 1，second 为字符串 “apple”。
2.使用 make_pair 函数auto p = std::make_pair(1, "apple");
make_pair 函数可以自动推断类型，不需要显式指定模板参数。
三.用法示例
1.基本示例
int main() {
// 创建 pair 并直接初始化
std::pair<int, std::string> p(1, "apple");
// 使用 make_pair 创建 pair
auto p2 = std::make_pair(2, "banana");
// 访问 first 和 second
std::cout << "Pair 1: " << p.first << ", " << p.second << std::endl;
std::cout << "Pair 2: " << p2.first << ", " << p2.second << std::endl;
return 0;
}
2.结合 map 使用
pair 常用于关联数据结构，例如 std::map，其元素通常是键值对的形式（即 pair）。
int main() {
// 创建 map，map 的元素类型是 pair
std::map<int, std::string> m;
// 插入元素，pair 类型的键值对
m.insert(std::make_pair(1, "apple"));
m.insert(std::pair<int, std::string>(2, "banana"));
// 访问 map 中的元素 for (const auto& entry : m) {
std::cout << "Key: " << entry.first << ", Value: " << entry.second << std::endl;
}
return 0;
}
三.常用成员
1.first 和 second
直接访问 pair 的第一个和第二个元素。std::pair<int, double> p(10, 20.5);
int key = p.first; // 获取第一个元素
double value = p.second; // 获取第二个元素
2.make_pair()
创建一个 pair 对象，函数会自动推断类型。auto p = std::make_pair(5, "text");
3.operator==、operator!=
比较两个 pair 是否相等。std::pair<int, int> p1(1, 2);
std::pair<int, int> p2(1, 2);
if (p1 == p2) {
std::cout << "Pairs are equal" << std::endl;
}
4.operator<、operator>
pair 可以按字典顺序比较：首先比较 first，如果 first 相等，则比较 second。std::pair<int, int> p1(1, 2);
std::pair<int, int> p2(1, 3);
if (p1 < p2) {
std::cout << "p1 is smaller than p2" << std::endl;
}
Operator
比较函数应遵循严格弱排序规则，返回 true 表示第一个参数应该排在第二个参数之前。
bool operator()(int a, int b) const { |
为什么这是降序？
这个比较函数会返回 true 当且仅当 a > b。也就是说，只有当 a 大于 b 时，a 会被排在 b 的前面。换句话说：
- 如果 a = 5，b = 3，比较函数返回 true，表示 5 应该排在 3 之前。
- 如果 a = 3，b = 5，比较函数返回 false，表示 3 应该排在 5 之后。
这与降序排列的逻辑一致：大的元素排在前面，小的元素排在后面。