C++实现线程安全的优先级队列 _ std::mutex与堆排算法封装【源码】

直接说结论：用 `std::mutex` 把堆操作包起来，确实可以实现线程安全，但千万不能只锁 `push` 和 `pop` 这两个函数——`top()`、`empty()`、`size()` 这些看似只读的操作，同样需要上锁。否则，你很容易读到中间态的数据，甚至直接引发竞态崩溃。 ### 为什么 `std::priority_queue` 本身不线程安全 `std::priority_queue` 是一个容器适配器，底层默认使用 `std::vector`，再加上 `std::make_heap`、`std::push_heap`、`std::pop_heap` 这些算法来维护堆结构。问题就出在这里：这些函数操作的是裸内存，没有任何同步机制。假如一个线程刚调完 `push_heap`，还没来得及更新底层容器的 `size`，另一个线程恰好来读 `top()`，那它拿到的可能是一个未初始化的尾元素。 实践中常见的错误现象有： * 抛出 `std::out_of_range` 异常或直接访问违规（因为 `top()` 返回的是底层 `vector` 的引用，而 `size` 已经混乱了）。 * 两次连续调用 `top()`，结果返回的值不一样（因为另一个线程正在执行 `pop` 操作，正处于半路）。 * 调用 `empty()` 返回 `false`，但紧接着 `pop()` 就报错了——元素已经被其他线程抢先取走了。 ### 封装时必须加锁的操作 不是“增删查”里只锁增删就够了——所有需要访问内部容器状态的函数，都得进入同一把 `std::mutex` 的保护范围。具体来说： * **`push()`**：从调用 `c.push_back()` 到执行 `std::push_heap`，整个流程不可分割。 * **`pop()`**：必须先 `std::pop_heap`，再 `c.pop_back()`，两步缺一不可，且必须一气呵成。 * **`top()`**：返回 `c.front()`，此时必须保证没有其他线程在修改 `c`。 * **`empty()` 和 `size()`**：读 `c.size()` 看起来是只读的，但假如另一个线程正在执行 `pop_back()`，就可能读到撕裂值。在 debug 模式下，`vector` 的迭代器检查会更敏感，问题更容易暴露。 别想着用 `std::shared_mutex` 来做读写分离优化——`std::make_heap` 这类算法会重排整个容器，读操作和写操作根本没法真正并发，硬要分离反而只会徒增锁的开销。 ### 关键代码片段与易错点 下面是一个典型的封装结构（省略模板参数，聚焦同步逻辑）： ```cpp template, typename Compare = std::less> class thread_safe_priority_queue { mutable std::mutex mtx; Container c; Compare comp; public: void push(const T& value) { std::lock_guard lock(mtx); c.push_back(value); std::push_heap(c.begin(), c.end(), comp); // 注意：comp 必须可拷贝或无状态 } void pop() { std::lock_guard lock(mtx); std::pop_heap(c.begin(), c.end(), comp); // 堆顶移到末尾 c.pop_back(); // 再删末尾 } const T& top() const { std::lock_guard lock(mtx); return c.front(); // 用 c.front() 而不是 c.at(0)，避免 bounds check 开销 } bool empty() const { std::lock_guard lock(mtx); return c.empty(); } }; ``` 这里面有几个容易踩的坑： 1. **`std::pop_heap` 不删除元素**，必须紧跟一个 `c.pop_back()`。如果漏掉后者，容器的 `size` 会不断膨胀，后续再调 `push_heap` 就可能导致未定义行为。 2. **比较对象 `comp` 的生命周期问题**。如果它捕获了外部局部变量（比如用 lambda 表达式），多线程下极易产生悬挂引用。 3. 不要在锁内做耗时操作，比如日志输出或网络调用，否则整个队列会被阻塞住。另外，`top()` 返回的是引用，锁释放后这个引用就失效了——这一点必须清楚地写进文档里。 最后提醒一点：上面这个封装只解决了基本的线程安全问题。如果队列用在生产者-消费者模型中，`pop()` 在队列为空时应该阻塞等待，而不是直接崩溃。这需要额外引入 `std::condition_variable`，并且 `wait` 的 predicate 必须和 `mutex` 配合检查队列状态，否则惊群效应和虚假唤醒的问题一个都躲不掉。