【优先队列与设计模式】：在设计模式中巧妙应用std::priority_queue

# 1. 优先队列的基础概念和实现

## 1.1 优先队列简介

优先队列是一种抽象数据类型，它允许插入一组具有特定优先级的元素，并且当请求移除元素时，它总是从队列中移除优先级最高的元素。这种数据结构在需要优先处理某些元素的场景中非常有用，例如任务调度、事件处理等。

## 1.2 优先队列的基本原理

在优先队列中，元素按照优先级排序，而不是按照它们进入队列的顺序。优先级最高的元素总是排在队列的前端。这种排序通常通过一个比较器实现，它定义了元素之间的优先级关系。

## 1.3 优先队列的实现方式

优先队列可以用多种方式实现，包括数组、链表、堆结构等。其中，二叉堆是最常用的实现方式，因为它的插入和删除操作的时间复杂度较低，均为O(log n)。在C++中，优先队列通常通过标准库中的`std::priority_queue`实现，它内部使用了最小堆或最大堆。

接下来的章节，我们将深入探讨`std::priority_queue`在C++标准模板库中的具体实现和应用。

# 2. 优先队列的C++ STL实现详解

## 2.1 std::priority_queue的基本使用

### 2.1.1 定义和构造函数
`std::priority_queue`是C++标准库中提供的一个优先队列容器适配器。它允许你插入一组自定义类型的元素，同时能够始终保持队列中的元素按优先级排序。

首先，我们来看看如何定义一个`std::priority_queue`对象。这里我们用一个简单的例子来演示：

#include <queue>
#include <iostream>

int main() {
    // 默认构造函数，使用默认比较函数，元素默认是int类型
    std::priority_queue<int> pq_int;

    // 使用自定义比较函数的priority_queue
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq_custom;

    // 使用自定义容器的priority_queue
    std::vector<int> vec_custom = {1, 5, 3, 4};
    std::priority_queue<int, std::vector<int>> pq_from_vector(vec_custom);
    return 0;
}

在这个例子中，我们创建了三种不同的优先队列：
- `pq_int` 是一个默认的优先队列，它使用 `std::less<T>` 作为比较函数对象，即默认的最大堆行为。
- `pq_custom` 使用了 `std::greater<int>` 作为比较函数对象，实现的是最小堆行为。
- `pq_from_vector` 则是利用已经存在的vector作为底层容器来初始化优先队列。

### 2.1.2 入队和出队操作
接下来我们来看看如何向优先队列中插入元素以及如何移除和获取最高优先级的元素。

#include <queue>
#include <iostream>
#include <vector>

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

    // 入队操作（push）
    pq.push(3);
    pq.push(5);
    pq.push(1);
    // 获取并移除最高优先级元素（top 和 pop）
    while (!pq.empty()) {
        int topElement = ***();
        std::cout << topElement << " ";
        pq.pop();
    }
    return 0;
}

在这个示例中，首先我们使用`push`方法向优先队列中添加元素。然后，我们通过`top`方法获取队列的最高优先级元素，并通过`pop`方法将其从队列中移除。由于`std::priority_queue`默认实现为最大堆，因此最高优先级元素总是最大的元素。

执行上述代码后，我们会得到输出：

5 3 1

这显示了元素以正确的顺序被移除，符合最大堆的行为。

## 2.2 std::priority_queue的比较机制

### 2.2.1 比较函数对象
比较机制是优先队列中控制元素排序的关键。`std::priority_queue`默认使用`std::less<T>`作为比较函数对象，这意味着它会按照元素的自然顺序来决定优先级，通常是数值较大的元素优先。

如果你需要最小堆的行为，你可以使用`std::greater<T>`作为比较函数对象。下面我们通过代码示例来看如何实现这一点：

#include <queue>
#include <iostream>
#include <vector>
#include <functional>

int main() {
    // 使用std::greater<T>创建最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    min_heap.push(3);
    min_heap.push(5);
    min_heap.push(1);

    while (!min_heap.empty()) {
        int topElement = min_***();
        std::cout << topElement << " ";
        min_heap.pop();
    }

    return 0;
}

输出结果将是：

1 3 5

这表明元素现在是以最小值为优先级进行排列的。

### 2.2.2 自定义优先级规则
如果默认的比较函数不能满足需求，你也可以定义自己的比较函数对象。假设我们有一个结构体`Person`，我们想要根据年龄来创建一个优先队列。

#include <queue>
#include <iostream>
#include <vector>
#include <functional>

struct Person {
    std::string name;
    int age;

    // 构造函数
    Person(std::string n, int a) : name(n), age(a) {}

    // 重载<运算符
    bool operator<(const Person& other) const {
        return age < other.age; // 按年龄升序排列
    }
};

int main() {
    std::priority_queue<Person> people;

    people.push(Person("Alice", 30));
    people.push(Person("Bob", 25));
    people.push(Person("Charlie", 35));

    while (!people.empty()) {
        Person topPerson = ***();
        std::cout << topPerson.name << " (" << topPerson.age << ") ";
        people.pop();
    }

    return 0;
}

这段代码定义了一个`Person`类，并重载了小于运算符，使得优先队列按照`Person`对象的年龄进行排序。输出结果将是：

Bob (25) Alice (30) Charlie (35)

这展示了我们如何利用优先队列根据自定义规则对元素进行排序。

## 2.3 std::priority_queue的内存管理

### 2.3.1 内存分配策略
在使用`std::priority_queue`时，内部容器（通常是`std::vector`）负责内存分配。`std::priority_queue`使用容器的`push_back`方法来添加新元素，并通过调用`pop_back`来移除最后一个元素。

在内部，`std::vector`的容量会根据元素的数量动态调整。当容量不足以存储新元素时，`std::vector`通常会分配一个更大的内存块，并将旧数据复制到新内存中，然后释放旧内存。

### 2.3.2 调整容量的时机和方法
优先队列的容量调整时机取决于底层容器的实现。对于`std::vector`，容量会在每次元素数量超过当前容量时增加。默认情况下，`std::vector`容量的增加策略是增长到当前大小的两倍。

下面是一个示例，说明如何观察容量调整：

#include <queue>
#include <iostream>
#include <vector>

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

    std::cout << "Initial size: " << pq.size() << " capacity: " << pq.max_size() << std::endl;

    for (int i = 0; i < 10; ++i) {
        pq.push(i);
    }

    std::cout << "Size: " << pq.size() << " capacity: " << pq.max_size() << std::endl;

    return 0;
}

这段代码创建了一个`std::priority_queue`并尝试添加10个元素。在添加这些元素之前，我们先打印出了优先队列的当前大小和容量。在添加元素之后，我们再次打印，以观察容量是否发生变化。

请注意，实际容量的变化可能会依赖于编译器和库的实现细节，因此可能在不同的编译器或库版本中有所不同。

以上就是我们深入探讨`std::priority_queue`的基础使用和其比较机制。在下一节中，我们将进一步探讨优先队列在设计模式中的应用，看看它是如何与各种设计模式相结合，并在实际开发中发挥它的功能。

# 3. 设计模式与优先队列的结合应用

设计模式是软件开发中解决特定问题的一套经验和解决方案，它们在各种编程语言和应用领域中都有广泛的应用。在本章节中，我们将探讨设计模式与优先队列结合的多种方式，以及它们在实际开发中的应用。

## 3.1 工厂模式与优先队列的融合

### 3.1.1 工厂模式简介

工厂模式是创建型设计模式之一，用于创建对象而不暴露创建逻辑给客户端，并通过使用一个共同的接口来指向新创建的对象。工厂模式主要分为简单工厂、工厂方法和抽象工厂三种类型。

### 3.1.2 创建优先级对象池

结合优先队列，我们可以设计一种优先级对象池。在这个池中，对象被创建时根据优先级分配，并由工厂模式管理它们的生命周期。对象池中的对象可以是任何类型，而优先级可以用来决定对象创建和销毁的顺序。

// 例子：使用工厂模式创建优先级对象池
class ObjectFactory {
public:
    // 创建对象的接口
    virtual BaseObject* CreateObje