C++ priority_queue 与 deque 的使用及模拟实现

priority_queue 与 deque 的使用与模拟实现

一、priority_queue

1.1 介绍

【priority_queue 的参考文档】

简单说明：

1. priority_queue（优先级队列）底层的数据结构是堆，底层默认的容器是 vector。对于堆不是很了解的建议看【堆的实现】，可见，堆一般为顺序存储，底层默认的容器是 vector 也就正常了。
2. priority_queue 是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。可参考堆，可以在任何时候插入元素，但只能访问位于顶部的最大元素（即优先队列中最顶端的元素）。
3. 优先队列作为容器适配器实现，它使用特定容器类作为底层容器，并提供一组特定的成员函数来访问元素。元素从底层容器的"尾部"弹出，这个位置被称为优先队列的顶部。
4. 底层容器可以是任何标准容器类模板，也可以是其他专门设计的容器类。该容器必须支持通过随机访问迭代器进行访问，并提供以下操作：
   • empty()：检查容器是否为空
   • size()：返回容器中元素的数量
   • front()：返回容器中第一个元素的引用
   • push_back()：在容器末尾插入元素
   • pop_back()：删除容器末尾的元素
5. 标准容器类 vector 和 deque 满足这些要求。默认情况下，如果没有为特定的 priority_queue 实例指定容器类，则使用 vector。
6. 需要支持随机访问迭代器是为了在内部始终保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来实现这一点。

1.2 使用

我们再对于前面的说明做一个总结： 优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。 我们可以来使用一下：

1. 默认情况下，priority_queue 是大堆。

#include <iostream>
#include <vector>
#include <queue>
#include <functional> // greater 算法的头文件
using namespace std;

void test1(){
    // 默认情况下，创建的是大堆，其底层按照小于比较
    vector<int> v{3, 2, 7, 6, 0, 4, 1, 9, 8, 5};
    priority_queue<int> q1;
    for(auto& e : v) q1.push(e);
    cout << q1.top() << endl;
    
    // 如果要创建小堆，将第三个模板参数换成 greater 比较方式
    priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
    cout << q2.top() << endl;
}

int main(){
    test1();
    return 0;
}

对于它是如何在默认小于比较的情况下实现大堆的，我们后面的模拟实现会进一步说明。

2. 如果在 priority_queue 中放自定义类型的数据，用户需要在自定义类型中提供 > 或者 < 的重载。

class Date{
    friend ostream& operator<<(ostream& _cout, const Date& d);
public:
    Date(int year = 1900, int month = 1, int day = 1):_year(year),_month(month),_day(day){}
    bool operator<(const Date& d) const{
        return (_year < d._year) || (_year == d._year && _month < d._month) || (_year == d._year && _month == d._month && _day < d._day);
    }
    bool operator>(const Date& d) const{
        return (_year > d._year) || (_year == d._year && _month > d._month) || (_year == d._year && _month == d._month && _day > d._day);
    }
private:
    int _year;
    int _month;
    int _day;
};

ostream& operator<<(ostream& _cout, const Date& d){
    _cout << d._year << "-" << d._month << "-" << d._day;
    return _cout;
}

void test2(){
    // 大堆，需要用户在自定义类型中提供<的重载
    priority_queue<Date> q1;
    q1.push(Date(2018, 10, 29));
    q1.push(Date(2018, 10, 28));
    q1.push(Date(2018, 10, 30));
    cout << q1.top() << endl;
    
    // 如果要创建小堆，需要用户提供>的重载
    priority_queue<Date, vector<Date>, greater<Date>> q2;
    q2.push(Date(2018, 10, 29));
    q2.push(Date(2018, 10, 28));
    q2.push(Date(2018, 10, 30));
    cout << q2.top() << endl;
}

int main(){
    test2();
    return 0;
}

有兴趣可以练习一下：数组中的第 K 个最大元素

1.3 模拟实现

接下来我们模拟实现一下，在此之前，我们要对于堆这种数据结构有所了解，不懂的可以去我前面的关于堆的实现的链接。 那咱们就步入正题，对于 priority_queue 的实现其实就是将堆进行一定的封装，那我们就直接写吧。

#pragma once
#include <vector>

// 优先队列模板类
// T: 元素类型，Container: 底层容器类型 (默认 vector), Compare: 比较器类型 (默认 less<T>)
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue {
public:
    // 默认构造函数
    priority_queue() {}

    // 向下调整算法 (堆化)
    // 用于维护堆性质，当某个节点不满足堆性质时，将其向下调整
    // a: 容器引用，n: 堆的大小，root: 要调整的根节点下标
    void AdjustDown(Container& a, int n, int root) {
        int parent = root;
        int child = parent * 2 + 1; // 左孩子
        while(child < n) {
            // 如果右孩子存在且比左孩子大 (对于大堆)，选择较大的孩子
            if(child + 1 < n && _comp(a[child], a[child + 1])) {
                ++child; // 选择右孩子
            }
            // 如果父节点小于孩子节点 (对于大堆)，需要交换
            if(_comp(a[parent], a[child])) {
                swap(a[child], a[parent]);
                parent = child; // 继续向下调整
                child = parent * 2 + 1; // 新的左孩子
            } else {
                break; // 已经满足堆性质，退出循环
            }
        }
    }

    // 向上调整算法
    // 用于在插入新元素后维护堆性质，从叶子节点向上调整
    // child: 新插入元素的下标
    void AdjustUp(int child) {
        Compare com;
        int parent = (child - 1) / 2; // 计算父节点下标
        while(child > 0) {
            // 如果父节点小于孩子节点 (对于大堆)，需要交换
            //if (_c[parent] < _c[child])
            if(com(_c[parent], _c[child])) {
                swap(_c[child], _c[parent]);
                child = parent; // 继续向上调整
                parent = (child - 1) / 2; // 新的父节点
            } else {
                break; // 已经满足堆性质，退出循环
            }
        }
    }

    // 使用迭代器范围构造优先队列
    // first: 起始迭代器，last: 结束迭代器
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last):_c(first, last) // 用迭代器范围初始化底层容器
    {
        int size = _c.size();
        // 从最后一个非叶子节点开始，向前逐个向下调整建堆
        int i = (size - 2) / 2; // 最后一个非叶子节点的下标
        while(i >= 0) {
            AdjustDown(_c, last - first, i);
            i--;
        }
    }

    // 判断优先队列是否为空
    bool empty() const {
        return _c.empty();
    }

    // 返回优先队列中元素个数
    size_t size() const {
        return _c.size();
    }

    // 返回堆顶元素 (非 const 版本)
    T& top() {
        return _c[0]; // 堆顶元素总是在容器首部
    }

    // 返回堆顶元素 (const 版本)
    const T& top() const {
        return _c[0];
    }

    // 插入新元素
    void push(const T& x) {
        _c.push_back(x); // 在尾部插入新元素
        AdjustUp(_c.size() - 1); // 从新插入的位置向上调整
    }

    // 删除堆顶元素
    void pop() {
        swap(_c[0], _c[_c.size() - 1]); // 将堆顶元素与最后一个元素交换
        _c.pop_back(); // 删除原来的堆顶元素 (现在在尾部)
        AdjustDown(_c, _c.size(), 0); // 从新的堆顶位置向下调整
    }

private:
    Container _c; // 底层容器，用于存储堆元素
    Compare _comp; // 比较器对象，用于元素比较
};

对于堆比较了解的我们来说，实现很简单，这里我们就主要再来说明一下它为什么小于是大堆：

二、deque

2.1 介绍

在上篇文章中，我们对于两者的模拟实现的时候底层容器其采用的是 vector，我也提到，底层并未用 vector 作为默认容器，而是 deque（双端队列），现在我们就对于 deque 来进行简单的介绍吧。

deque(双端队列)：是一种双开口的"连续"空间的数据结构。 双开口的含义是：可以在头尾两端进行插入和删除操作，且时间复杂度为 O(1)，与 vector 比较，头插效率高，不需要搬移元素；与 list 比较，空间利用率比较高。

那么 deque 到底是怎么实现的呢。难道 deque 是一块连续的空间，然后怎么样怎么样……

其实，**deque 并不是真正连续的空间，而是由一段段连续的小空间拼接而成的，实际 deque 类似于一个动态的二维数组。**其底层结构如下图所示：

可见，双端队列底层采用分段存储的方式，实际内存是不连续的。所以为了给用户提供连续空间和随机访问的错觉，deque 的迭代器承担了屏蔽底层复杂性的重任。

我们也可以来看一下 deque 的迭代器实现，如下图:

解释：

我们可以看出，中控器其实是一个指针数组，每个指针指向一个缓冲区，当缓冲区不够时可以动态增长。迭代器的指针： cur: 指向当前元素 first: 指向当前缓冲区的起始位置 last: 指向当前缓冲区的结束位置 node: 指向中控器中当前缓冲区对应的指针

那 deque 是如何借助其迭代器维护其假想连续的结构呢？

其实，在 deque 的底层，除了中控数组以外，还有两个迭代器，start 与 finish 迭代器。如下图：

这样，在对于头插和头删以及尾插、尾删的时候，就会很快 O(1)。

这样一看，deque 与 vector 比较，deque 的优势是：头部插入和删除时，不需要搬移元素，效率特别高，而且在扩容时，也不需要搬移大量的元素，因此其效率是比 vector 高的。 与 list 比较，其底层是连续空间，空间利用率比较高，不需要存储额外字段。 dque 的核心特点就是：

• 头尾插入删除时间复杂度 O(1)
• 支持随机访问，但效率低于 vector
• 底层采用"中控器 + 缓冲区"的分段存储方式

但是，它也是有缺陷的。

2.2 缺陷

尽管 deque 功能强大，但也有明显缺陷：

1. 随机访问效率较低（需要计算缓冲区位置）
2. 迭代器失效规则复杂
3. 内存使用效率不如 vector
4. 缓存局部性较差

因此在实际中，需要线性结构时，大多数情况下优先考虑 vector 和 list，deque 的应用并不多，而目前能看到的一个应用就是，STL 用其作为 stack 和 queue 的底层数据结构。

三、STL 标准库中对于 stack 和 queue 的模拟实现

3.1 为什么选择 deque 作为 stack 和 queue 的底层默认容器

stack 是一种后进先出的特殊线性数据结构，因此只要具有 push_back() 和 pop_back() 操作的线性结构，都可以作为 stack 的底层容器，比如 vector 和 list 都可以； queue 是先进先出的特殊线性数据结构，只要具有 push_back 和 pop_front 操作的线性结构，都可以作为 queue 的底层容器，比如 list。 但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器，主要是因为：

stack 和 queue 不需要遍历 (因此 stack 和 queue 没有迭代器)，只需要在固定的一端或者两端进行操作。在 stack 中元素增长时，deque 比 vector 的效率高 (扩容时不需要搬移大量数据)；queue 中的元素增长时，deque 不仅效率高，而且内存使用率高。

结合了 deque 的优点，而完美的避开了其缺陷。 下面我们就仿照标准库来进行 stack 和 queue 的模拟实现。

3.2 stack 的模拟实现

#include <deque>

template<class T, class Con = deque<T>>
class stack {
public:
    stack() {}
    void push(const T& x) { _c.push_back(x); }
    void pop() { _c.pop_back(); }
    T& top() { return _c.back(); }
    const T& top() const { return _c.back(); }
    size_t size() const { return _c.size(); }
    bool empty() const { return _c.empty(); }
private:
    Con _c;
};

3.3 queue 的模拟实现

#include <deque>

template<class T, class Con = deque<T>>
class queue {
public:
    queue() {}
    void push(const T& x) { _c.push_back(x); }
    void pop() { _c.pop_front(); }
    T& back() { return _c.back(); }
    const T& back() const { return _c.back(); }
    T& front() { return _c.front(); }
    const T& front() const { return _c.front(); }
    size_t size() const { return _c.size(); }
    bool empty() const { return _c.empty(); }
private:
    Con _c;
};