C / C++ / 系统课时

用优先队列生成库存预警排行

用优先队列生成库存预警排行

库存预警通常只关心“最紧张的商品是谁”,而不是每次都完整排序全部商品。本节使用 std::priority_queue 建立按库存紧张程度排序的队列,并通过自定义比较器让库存最低、同库存时编号更小的商品优先弹出。

学习目标

  • 理解 std::priority_queue 的 top() 与比较器关系
  • 自定义库存预警的优先级规则
  • 判断优先队列与完整排序各自适合的场景

定义预警优先级

本例的规则是:库存越少,预警优先级越高;库存相同,编号越小越优先。因为 std::priority_queue 默认把“最大元素”放在 top(),自定义比较器时要特别注意方向。

比较器返回 true 表示左侧元素的优先级低于右侧元素,也就是它应该被放到更靠后的位置。要让较小库存出现在顶部,就需要在库存比较时写 a.stock > b.stock。

建立库存预警队列

下面把库存不高于 20 的商品加入预警队列,再依次输出排行榜。

cpp
#include <iostream>
#include <queue>
#include <string>
#include <vector>

struct Product {
    int id;
    std::string name;
    int stock;
};

struct StockPriority {
    bool operator()(const Product& a, const Product& b) const {
        if (a.stock != b.stock) {
            return a.stock > b.stock;
        }
        return a.id > b.id;
    }
};

int main() {
    std::vector<Product> products{
        {101, "Keyboard", 18},
        {102, "Mouse", 35},
        {103, "Webcam", 8},
        {104, "Hub", 12},
        {105, "Stand", 8}
    };

    std::priority_queue<
        Product,
        std::vector<Product>,
        StockPriority
    > warnings;

    constexpr int threshold = 20;

    for (const auto& product : products) {
        if (product.stock <= threshold) {
            warnings.push(product);
        }
    }

    int rank = 1;
    while (!warnings.empty()) {
        const auto& product = warnings.top();
        std::cout << rank << ' '
                  << product.id << ' '
                  << product.name << ' '
                  << product.stock << '\n';
        warnings.pop();
        ++rank;
    }
}

预期输出

text
1 103 Webcam 8
2 105 Stand 8
3 104 Hub 12
4 101 Keyboard 18

103 和 105 的库存同为 8,因此编号较小的 103 先出现。库存为 35 的商品没有进入队列,因为它高于预警阈值。

看懂比较器方向

priority_queue 的比较器常被误写成与 std::sort 完全相同的方向。两者语义不同:sort 的比较器表示“左侧是否应排在右侧前面”,而 priority_queue 的比较器用于判断元素优先级,top() 保留的是没有被其他元素判定为更低优先级的那个元素。

可以用一个简单检查验证方向:向空队列依次放入库存 18、8、12,如果目标是“库存越少越紧急”,那么 top().stock 应该得到 8。只要这个最小例子正确,再扩展第二排序字段通常更不容易出错。

与 sort 的选择边界

如果最终必须输出全部商品的完整有序列表,std::sort 通常更直接,时间复杂度是 O(nlog⁡n)O(n\log n)。优先队列更适合持续插入商品并频繁查询当前最高优先级项;单次插入和弹出通常为 O(log⁡n)O(\log n),读取 top() 为 O(1)O(1)。

当预警系统只需要前几名时,没有必要先把所有候选项完整排序。相反,如果页面要展示所有商品并支持翻页、二次筛选,完整排序或更适合的数据索引会更自然。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用优先队列生成库存预警排行

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通