C / C++ / 系统课时
用优先队列生成库存预警排行
用优先队列生成库存预警排行
库存预警通常只关心“最紧张的商品是谁”,而不是每次都完整排序全部商品。本节使用 std::priority_queue 建立按库存紧张程度排序的队列,并通过自定义比较器让库存最低、同库存时编号更小的商品优先弹出。
学习目标
- 理解
std::priority_queue的top()与比较器关系 - 自定义库存预警的优先级规则
- 判断优先队列与完整排序各自适合的场景
定义预警优先级
本例的规则是:库存越少,预警优先级越高;库存相同,编号越小越优先。因为 std::priority_queue 默认把“最大元素”放在 top(),自定义比较器时要特别注意方向。
比较器返回 true 表示左侧元素的优先级低于右侧元素,也就是它应该被放到更靠后的位置。要让较小库存出现在顶部,就需要在库存比较时写 a.stock > b.stock。
建立库存预警队列
下面把库存不高于 20 的商品加入预警队列,再依次输出排行榜。
#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;
}
}预期输出
1 103 Webcam 8
2 105 Stand 8
3 104 Hub 12
4 101 Keyboard 18103 和 105 的库存同为 8,因此编号较小的 103 先出现。库存为 35 的商品没有进入队列,因为它高于预警阈值。
看懂比较器方向
priority_queue 的比较器常被误写成与 std::sort 完全相同的方向。两者语义不同:sort 的比较器表示“左侧是否应排在右侧前面”,而 priority_queue 的比较器用于判断元素优先级,top() 保留的是没有被其他元素判定为更低优先级的那个元素。
可以用一个简单检查验证方向:向空队列依次放入库存 18、8、12,如果目标是“库存越少越紧急”,那么 top().stock 应该得到 8。只要这个最小例子正确,再扩展第二排序字段通常更不容易出错。
与 sort 的选择边界
如果最终必须输出全部商品的完整有序列表,std::sort 通常更直接,时间复杂度是 。优先队列更适合持续插入商品并频繁查询当前最高优先级项;单次插入和弹出通常为 ,读取 top() 为 。
当预警系统只需要前几名时,没有必要先把所有候选项完整排序。相反,如果页面要展示所有商品并支持翻页、二次筛选,完整排序或更适合的数据索引会更自然。