C++ STL 双端队列原理与优先级队列模拟实现

C++ STL 双端队列原理与优先级队列模拟实现

前言

本文聚焦于 STL 中的双端队列（deque）与优先级队列。我们将深入剖析 deque 如何融合 vector 与 list 的优势，通过中控数组与分段缓存实现高效头尾操作；结合优先级队列的堆结构，详解仿函数在自定义排序规则中的核心作用。通过模拟实现代码与性能对比，帮助大家理解这些容器适配器的底层逻辑。

一、deque（双端队列）

1.1 list 和 vector 的优缺点

在讨论 deque 之前，我们先回顾一下 vector 和 list 的特性，这有助于理解 deque 存在的意义。

vector 的优点：

• 尾插尾删效率高。
• 支持高效的下标随机访问。
• 物理空间连续，高速缓存利用率高。

vector 的缺点：

• 空间需要扩容，扩容代价较高（涉及内存拷贝和释放）。
• 头部和中间的插入删除效率低，需要搬移元素。

list 的优点：

• 按需申请释放空间，不需要整体扩容。
• 支持任意位置的插入删除。

list 的缺点：

• 不支持下标的随机访问。

deque 可以看作是这两者的结合体，它既保留了 vector 的随机访问能力，又具备了 list 在头尾操作上的灵活性。

1.2 deque 的原理介绍

dque（双端队列）是一种双开口的"连续"空间数据结构。所谓的"连续"是指逻辑上的连续，允许在头尾两端进行 O(1) 时间复杂度的插入和删除操作。

底层结构： dque 并非真正连续的内存空间，而是由一段段连续的小空间拼接而成。实际结构类似于一个动态的二维数组：

1. 中控数组（Map）：本质是一个指针数组，用于管理各个缓冲区的地址。
2. 缓冲区（Buffer）：实际存储数据的一段段连续内存。

当缓冲区满了之后，会开辟新的缓冲区，并将新缓冲区的地址存入中控数组。为了维护逻辑上的连续性，deque 的迭代器设计较为复杂，需要处理跨缓冲区的跳转。

迭代器机制： dque 的迭代器包含四个关键成员：cur（当前指向位置）、first（当前缓冲区起始）、last（当前缓冲区结束）、node（指向中控区存放该数组的地址）。

• operator++：判断当前缓冲区是否走完。若未走完，直接 cur++；若走完，则通过 node+1 找到下一个缓冲区，更新 first 和 last，并将 cur 重置为下一个缓冲区的起始位置。

性能分析：

• 头插尾插：效率高于 vector 和 list。list 每次只申请一块，而 deque 一次申请一段空间（如 40 字节），比多次申请小块更高效；vector 扩容代价大，而 deque 只需新增缓冲区并调整指针，仅在中控区满时才需扩容（仅拷贝指针）。
• 随机访问：效率不错，但略低于 vector，因为需要计算索引对应的缓冲区偏移量。
• 中间插入删除：效率为 O(n)，因为涉及缓冲区的移动或扩容。

由于栈和队列通常不涉及中间元素的频繁处理，使用 deque 作为默认适配容器是非常合理的选择。

1.3 deque 和 vector 的性能对比

在 Release 版本下，对 100 万数据进行排序测试，结果如下：

void test_op1() {
    srand(time(0));
    const int N = 1000000;
    deque<int> dq;
    vector<int> v;
    for (int i = 0; i < N; ++i) {
        auto e = rand() + i;
        v.push_back(e);
        dq.push_back(e);
    }
    
    int begin1 = clock();
    sort(v.begin(), v.end());
    int end1 = clock();
    
    int begin2 = clock();
    sort(dq.begin(), dq.end());
    int end2 = clock();
    
    printf("vector: %d\n", end1 - begin1);
    printf("deque: %d\n", end2 - begin2);
}

总结：在大量数据访问场景下，deque 的性能约为 vector 的一半，但在头尾操作上优势明显。

二、优先级队列

2.1 定义及其作用

优先级队列（priority_queue）也是一种容器适配器。与普通队列不同，它的核心特性是：元素的处理顺序不由插入顺序决定，而是由元素的'优先级'决定。每次取出的总是当前优先级最高的元素。

由于其核心特性类似于堆，且堆的底层通常由 vector 实现（便于根据下标计算父子节点关系），因此 priority_queue 默认使用 vector 作为底层容器。

需要注意的是 top() 和 pop() 接口。默认情况下，数值大的优先级高。如果需要让小的数据优先级高，可以通过仿函数来定制比较规则。

2.2 模拟实现优先级队列

基于堆的结构，我们可以模拟实现一个简单的优先级队列。

基本框架：

namespace hxx {
template<class T, class Container = std::vector<T>>
class PriorityQueue {
public:
    void push(const T& x) {}
    void pop() {}
    void top() {}
private:
    Container _con;
};
}

插入逻辑（向上调整）： 插入时，先将元素放到堆末尾，然后顺着双亲往上调整，直到满足堆的性质。

void AdjustUp(int child) {
    int parent = (child - 1) / 2;
    while (child > 0) {
        if (_con[child] > _con[parent]) {
            std::swap(_con[child], _con[parent]);
            child = parent;
            parent = (child - 1) / 2;
        } else {
            break;
        }
    }
}

删除逻辑（向下调整）： 删除堆顶元素时，将堆顶与最后一个元素交换，删除末尾元素，然后将新的堆顶向下调整。

// 向下调整算法
void AdjustDown(int parent) {
    size_t child = parent * 2 + 1;
    while (child < _con.size()) {
        // 找出较小的孩子（针对最大堆，这里假设我们要找的是较大的孩子来维持最大堆性质，或者根据 Compare 类型调整）
        // 此处以构建最大堆为例，寻找较大的孩子
        if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {
            ++child;
        }
        
        if (_con[child] > _con[parent]) {
            std::swap(_con[child], _con[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

完成上述接口后，一个简单的优先级队列便已实现。

2.3 仿函数

如果按照上面的写法，优先级队列只能固定为最大堆。为了实现最小堆或自定义类型的排序，我们需要引入仿函数（Functor）。

什么是仿函数？ 仿函数本质上是一个重载了 operator() 的类。它的对象可以像普通函数一样被调用，因此得名。

template<class T>
class Less {
public:
    bool operator()(const T& x, const T& y) {
        return x < y;
    }
};

int main() {
    Less<int> lessFunc;
    cout << lessFunc(1, 2) << endl;
    cout << lessFunc.operator()(1, 2) << endl;
    return 0;
}

仿函数的核心作用：

1. 替代普通函数：在 STL 算法中作为比较规则，例如控制优先级队列的堆结构（最大堆/最小堆）。
2. 携带状态：普通函数无法携带成员变量，但仿函数可以通过类的成员变量保存状态。
3. 模板参数：让算法更具通用性，支持自定义比较逻辑。

实际应用： 在实际开发中，我们通常直接使用标准库提供的仿函数，如 std::greater 或 std::less。

int main() {
    // 使用 greater 实现最小堆
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(4); pq.push(1); pq.push(5);
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

自定义类型比较： 对于自定义类型（如日期类），如果已经重载了比较运算符，可以直接使用；如果没有，则需要编写仿函数。

class Date {
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);
    }
    
    friend ostream& operator<<(ostream& os, const Date& d) {
        os << d._year << "-" << d._month << "-" << d._day;
        return os;
    }
private:
    int _year, _month, _day;
};

int main() {
    priority_queue<Date> q;
    q.push(Date(2025, 12, 7));
    q.push(Date(2025, 8, 25));
    cout << q.top() << endl;
    return 0;
}

如果是指针类型，直接比较地址没有意义，必须解引用后比较内容，此时就需要自定义仿函数：

class DateLess {
public:
    bool operator()(Date* d1, Date* d2) {
        return *d1 < *d2;
    }
};

int main() {
    priority_queue<Date*, vector<Date*>, DateLess> q;
    q.push(new Date(2025, 12, 7));
    q.push(new Date(2025, 8, 25));
    cout << *q.top() << endl;
    return 0;
}

三、总结

通过本文的学习，我们深入理解了 C++ STL 中 deque 的分段连续空间设计及其在头尾操作上的优势，掌握了优先级队列基于堆结构的模拟实现方法，并重点探讨了仿函数在自定义排序规则中的灵活应用。希望这些内容能帮助你更好地掌握容器适配器的底层逻辑。