C++ STL 双端队列 deque 与优先级队列模拟实现及仿函数详解

双端队列底层是一段假象的连续空间，实际是分段连续的。为了维护其'整体连续'以及随机访问的假象，落在了 deque 的迭代器身上（也就是 operator++ 和 operator-- 两个运算符重载身上），因此 deque 的迭代器设计就比较复杂。

deqeu 的缓存区、中控器和迭代器的关系如下：

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

deque::begin() 传回迭代器 start，deque::end() 传回迭代器 finish。迭代器由 cur（指向当前位置）、first（指向当前 buffer 的开始位置）、last（当前 buffer 的结束位置）、node（指向中控区存放该数组的地址）组成。

实现 operator++ 时，我们需要判断当前 buffer 有没有走完。如果没有走完，直接 ++cur 即可；走完了，则需找到下一个 buffer，通过 node+1 再解引用就找到了下一个 buffer 的开始位置，因此我们将迭代器的 first 指向找到的新的 buffer 即可。由于 buffer 的大小是固定的，因此 last 也找到了，再让 cur 指向第一个位置便大功告成了！

分析： deque 的头插尾插效率高于 vector 和 list。在 list 中，每次开辟空间只开一个节点；而 deque 每次开一段空间（一次申请 40 字节的空间比 10 次申请 4 个字节的效率高）。vector 的扩容代价太大（后期扩容时，需要将原来的大量数据拷贝下来，并且还需要释放旧空间）。在 deque 中如果 buffer 没满插入数据即可，满了就新开 buffer，再将迭代器的四个指针指向的位置改下即可，只有在中控区满的时候需要扩容（扩容代价很低，只拷贝指针）。

总结：

1. deque 的头插尾插效率很高，更甚于 vector 和 list。
2. 下标随机访问效率还不错，但是比不上 vector（需要调用几个函数并且还有运算）。
3. 在中间插入删除数据的效率为 O(n)。

正是因为栈和队列不需要对中间元素进行处理，所以我们使用 deque 作为其默认适配容器便很合理了。

1.3 deque 和 vector 的性能对比

我们在 release 版本下，对比 100w 数据下，deque 和 vector 的排序表现：

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);
}

总结： 在 release 模式下，大量访问数据时，deque 的性能约为 vector 的 1/2。

二、优先级队列

2.1 定义及其作用

优先级队列是一个容器适配器。根据官方文档定义，它是一种抽象数据类型（ADT），类似普通队列，但核心特性是：元素的处理顺序不由插入顺序决定，而是由元素的'优先级'决定。每次从队列中取出的，总是当前优先级最高的元素（优先级可自定义，例如'数值大的优先'或'数值小的优先'）。

由于其核心的特性类似于堆，而堆的底层通常由 vector 实现（不断地需要根据父亲节点算孩子即下标访问），且 deque 的随机访问效率低于 vector，因此容器默认选择 vector。

在这些接口中我们需要注意 top 和 pop 接口，其要取优先级高的数据（默认是大的数据优先级高，如果想让小的数据优先级高，可以使用仿函数）。

2.2 模拟实现优先级队列

由于其机制类似于堆，我们将用堆来实现优先级队列。以下代码便是其的基本框架：

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

实现插入数据的底层逻辑和堆的插入数据一模一样（物理结构是数组，逻辑结构是堆，因此我们需要把数组的元素一层一层放到堆上，即完全二叉树，其节点下标关系满足 left child = parent * 2 + 1）：

1. 先将元素插入到堆的末尾，即最后一个孩子之后。
2. 插入之后如果堆的性质遭到破坏，将新插入节点顺着其双亲往上调整到合适位置即可（向上调整算法）。

向上调整算法

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

那么向上调整算法搞定了，push 接口便轻松实现了。当然向上调整算法也不需要我们进行底层的搭建，在 C++ 算法库中便已经实现了。

删除接口：

同理删除接口也要调用堆的向下调整算法。

1. 将堆顶元素与堆中最后一个元素进行交换。
2. 删除堆中的最后一个元素。
3. 将堆顶元素向下调整到满足堆的特性为止。

向下调整算法

// 向下调整算法
void AdjustDown(int parent) {
    size_t child = parent * 2 + 1;
    Compare com;
    while (child < _con.size()) { // child >= n 说明孩子不存在，调整到叶子了
        // 找出大的那个孩子
        if (child + 1 < _con.size() && _con[child + 1] > _con[child]) {
            ++child;
        }
        if (_con[child] > _con[parent]) {
            swap(_con[child], _con[parent]);
            parent = child;
            child = parent * 2 + 1;
        } else {
            break;
        }
    }
}

这些接口实现完后，简单的优先级队列便已经实现好了。

注意：如果对二叉树的性质不熟悉的，建议先阅读相关数据结构文章复习一下树和堆的概念。

2.3 仿函数

可是如果按照上面的写法，那么优先级队列也就写死了，只允许大的优先级高。那么是否要实现两个堆，这样是否过于冗余？因此在前面官方文档的介绍中埋下的伏笔——仿函数便起到了点睛之笔。

仿函数（也称为函数对象）并不是函数，本质是一个重载了 operator() 的类——它的对象可以像普通函数一样被调用，因此得名'仿函数'。

// 仿函数：本质是类
template<class T>
class Less {
public:
    // 仿函数这个类只要有 operator() 就可以
    bool operator()(int x, int y) {
        return x < y;
    }
};

int main() {
    Less<int> lessFunc;
    // 在没有看到上面的类模板实例化前，我们会把 lessFunc 当成函数名或者函数指针，但是这里是对象
    cout << lessFunc(1, 2) << endl;
    cout << lessFunc.operator()(1, 2) << endl;
    return 0;
}

仿函数的核心作用：

1. 替代普通函数作为比较/操作规则：在 STL 算法（如 sort、priority_queue）中，例如在代码中的 Less 和 Greater，用于控制优先级队列的堆结构（最大堆/最小堆）。

   class Greater {
   public:
       bool operator()(int a, int b) const {
           return a > b; // 降序排序
       }
   };
   vector<int> v = {3, 1, 4, 1, 5, 9};
   sort(v.begin(), v.end(), Greater()); // 排序后：9 5 4 3 1 1
   

2. 携带状态：普通函数无法携带成员变量（状态），但仿函数可以通过类的成员变量保存状态，在多次调用中共享信息。

   class Counter {
   private:
       int _count = 0;
   public:
       void operator()() {
           _count++;
           cout << "调用次数：" << _count << endl;
       }
   };
   Counter cnt;
   cnt(); // 输出：调用次数：1
   cnt(); // 输出：调用次数：2
   

3. 通用性：仿函数可以作为模板参数，让算法/数据结构的行为更具通用性（如 priority_queue 模板中通过 Compare 仿函数支持自定义比较）。

在实际实现优先级队列时，我们并不需要自己实现仿函数，直接用即可。

int main() {
    priority_queue<int, vector<int>, greater<int>> pq;
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(7);
    pq.push(9);
    while (!pq.empty()) {
        cout << pq.top() << " ";
    }
    cout << endl;
    return 0;
}

一般场景仿函数不需要我们写，那么既然有一般情况，就会有特殊情况需要我们写仿函数。这里特殊情况分为两种：

1. 类类型不支持比较大小
2. 支持比较大小，但是比较的逻辑不是你想要的

在之前学类和对象的过程我们便模拟实现了日期类这个小项目，这里优先级队列里仿函数是支持日期内里面实现的比大小。

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;
}

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

int main() {
    priority_queue<Date> q1;
    q1.push(Date(2025, 12, 7));
    q1.push(Date(2025, 12, 7));
    q1.push(Date(2025, 12, 7));
    cout << q1.top() << endl;
    while (!q1.empty()) {
        cout << q1.top() << " ";
    }
    cout << endl;
    return 0;
}

因此哪怕是自定义类型，只要我们在该类中实现了内部的比大小即可。但是如果我们在自定义类中没有重载比大小，那么我们就需要自己实现仿函数。

如果比较的逻辑不是我们所想要的，如下：

// Date 类和上一样
int main() {
    priority_queue<Date*> q2;
    q2.push(new Date(2025, 12, 7));
    q2.push(new Date(2025, 12, 7));
    q2.push(new Date(2025, 12, 7));
    cout << *q2.top() << endl;
    q2.pop();
    cout << *q2.top() << endl;
    q2.pop();
    cout << *q2.top() << endl;
    return 0;
}

欧吼，我们发现两次输出的结构并不相同。我们思考下为什么每次比较大小的结果不一样？仔细观察下代码，我们发现，由于每次 new 的地址每个大小是随机的，所以比较结果各不相同。那么这时候我们就需要自己写仿函数实现我们想要的比大小的逻辑。

class DateLess {
    bool operator()(Date* d1, Date* d2) {
        // 我们不需要自己实现比大小逻辑，只需要解引用其对象，其自己重载了比较大小
        return *d1 < *d2;
    }
};

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

如上便是按照我们想法所实现的比大小逻辑。

三、总结

坚持到这里，已经很棒啦。希望读完本文可以帮助读者更好地理解栈和队列的底层逻辑。