STL `pair` 的详细介绍

1. 什么是 `pair`

pair 是一个简单的模板类，用于将两个类型不同的值绑定在一起，形成一个二元组。
它常用于函数返回多个值、构建键值对以及配合 STL 容器（如 map 和 multimap）使用。
pair 定义在 <utility> 头文件中。

2. `pair` 的底层实现

pair 是一个模板类，其定义如下：

template <class T1, class T2>
struct pair {
    T1 first; // 第一个值
    T2 second; // 第二个值

    // 默认构造函数
    pair() {}

    // 带参数的构造函数
    pair(const T1& x, const T2& y) : first(x), second(y) {}

    // 拷贝构造函数（支持类型转换）
    template <class U, class V>
    pair(const pair<U, V>& p) : first(p.first), second(p.second) {}
};

优先级队列（`priority_queue`）详解

1. 什么是优先级队列？

优先级队列是一种特殊的容器，其特点是：

优先级最高 的元素始终位于队列顶部。
优先级由比较函数（如 std::less 或 std::greater）决定，通常以堆为实现基础。
适用于需要动态管理优先级的场景，如：
- 任务调度
- 数据压缩（如霍夫曼编码）
- 图算法（如 Dijkstra 和 Prim 算法）

2. `priority_queue` 的基本结构

优先级队列是一个 容器适配器，基于以下模板实现：

template <
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
>
class priority_queue;

3. `priority_queue` 的常用操作

优先级队列包含以下成员函数：

成员函数	作用
`priority_queue()`	构造函数，初始化一个空的优先级队列。
`push(const T& x)`	插入元素 `x`，重新调整堆结构以保持优先级队列的性质。
`pop()`	移除优先级最高的元素（堆顶元素），重新调整堆结构。
`top()`	返回优先级最高的元素（堆顶元素）。
`empty()`	检查队列是否为空。
`size()`	返回队列中元素的数量。

4. 优先级队列的实现原理

优先级队列的实现基于堆数据结构，通常使用二叉堆作为底层实现。堆是一种特殊的完全二叉树，满足以下性质：

大顶堆：父节点的值总是大于或等于其子节点的值。
小顶堆：父节点的值总是小于或等于其子节点的值。

4.1 堆的存储方式

优先级队列使用 数组（如 std::vector） 存储堆结构，以便高效地进行插入和删除操作。

索引关系：
- 根节点索引：0
- 父节点索引：(i - 1) / 2
- 左子节点索引：2 * i + 1
- 右子节点索引：2 * i + 2

示例

假设堆的树结构如下：

对应的数组表示为：[20, 10, 15, 8, 7, 9]

4.2 堆的核心操作

1. 插入操作（`push_heap`）

新元素插入到堆的末尾。
通过上浮操作维护堆性质：与父节点比较并交换，直到父节点的优先级高于该元素。

时间复杂度：O(log n)（树的高度）。

2. 删除操作（`pop_heap`）

堆顶元素与堆的最后一个元素交换。
移除最后一个元素。
通过下沉操作维护堆性质：与子节点比较并交换，直到子节点的优先级低于该元素。

时间复杂度：O(log n)（树的高度）。

4.3 优先级的定义

优先级由比较器（Compare）决定，可以通过模板参数指定：

默认使用 std::less，实现 大顶堆（优先级最高的元素是值最大的元素）。 降序排列
使用 std::greater，实现 小顶堆（优先级最高的元素是值最小的元素）。 升序排列

示例：大顶堆和小顶堆

#include <queue>
#include <vector>
#include <functional>
#include <iostream>
using namespace std;

int main() {
    // 大顶堆（默认）
    priority_queue<int> maxHeap;
    maxHeap.push(10);
    maxHeap.push(5);
    maxHeap.push(20);

    // 小顶堆
    priority_queue<int, vector<int>, greater<int>> minHeap;
    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(20);

    // 输出
    cout << "大顶堆顶部: " << maxHeap.top() << endl; // 输出 20
    cout << "小顶堆顶部: " << minHeap.top() << endl; // 输出 5

    return 0;
}

4.4 priority_queue 的具体实现

插入元素（push）

void push(const T& x) {
    c.push_back(x); // 将元素插入到数组末尾
    std::push_heap(c.begin(), c.end(), comp); // 调整堆结构
}

删除元素（pop）

void pop() {
    std::pop_heap(c.begin(), c.end(), comp); // 将堆顶元素移到数组末尾
    c.pop_back(); // 移除数组末尾的元素
}

访问堆顶元素（top）

1
2
3

const T& top() const {
    return c.front(); // 堆顶元素始终存储在数组的第一个位置
}

4.5 push_heap 和 pop_heap 的示例

插入元素过程
假设插入元素 25 到以下堆：

[20, 10, 15, 8, 7, 9, 25]
[20, 10, 25, 8, 7, 9, 15]
[25, 10, 20, 8, 7, 9, 15]

    25
   /  \
  10   20
 / \   / \ 
8   7 9   15

4.6 优先级队列的复杂度

操作	时间复杂度	备注
插入元素	O(log n)	维护堆性质需要上浮操作。
删除堆顶元素	O(log n)	维护堆性质需要下沉操作。
获取堆顶元素	O(1)	直接访问数组的第一个元素。

总结

优点

高效性：插入和删除操作的时间复杂度为 O(log n)，对于动态调整数据非常高效。
灵活性：支持通过自定义比较器实现多种优先级规则，如大顶堆、小顶堆，甚至是自定义排序。
应用广泛：适用于动态排序需求，如任务调度、路径搜索、数据压缩等场景。

缺点

有限操作：不支持随机访问（不像 vector 或 deque 那样灵活）。
迭代访问困难：优先级队列不支持直接遍历，访问所有元素需要逐个 pop。
复杂场景额外开销：在处理复杂多任务场景时，自定义比较器可能增加实现成本。

优先级队列是一种高效且灵活的工具，在解决动态排序和优先级管理问题时具有独特优势。

STL pair 的详细介绍

1. 什么是 pair

2. pair 的底层实现

优先级队列（priority_queue）详解