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

总结：在大量数据访问场景下，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 的分段连续空间设计及其在头尾操作上的优势，掌握了优先级队列基于堆结构的模拟实现方法，并重点探讨了仿函数在自定义排序规则中的灵活应用。希望这些内容能帮助你更好地掌握容器适配器的底层逻辑。