C / C++ / 系统课时
用 set 维护商品分类集合
用 set 维护商品分类集合
商品列表中可能有许多商品属于同一分类,如果手工判断重复再排序,会增加不必要的代码。std::set 可以在插入分类时自动去重,并始终保持有序。本节从商品列表提取分类集合,并说明什么时候应直接维护集合、什么时候重新生成更安全。
学习目标
- 从商品列表中提取分类并写入
std::set - 利用
set的唯一性和有序性生成分类列表 - 理解分类集合与商品数据同步时的处理方式
set 为什么适合分类集合
分类列表通常有两个直接要求:同一个分类只显示一次,并且输出顺序稳定。例如商品数据中可能依次出现“外设、显示器、外设、存储”,最终分类列表只需要三个值。
std::set<std::string> 会按照比较规则保存唯一元素。重复插入已有分类不会产生第二份记录,默认又会按字符串升序排列,因此不需要先使用容器去重,再额外调用排序算法。
从商品列表提取分类
下面的程序保留商品原始顺序,只把每个商品的 category 插入分类集合。重复的 Peripherals 会被 set 自动忽略。
#include <iostream>
#include <set>
#include <string>
#include <vector>
struct Product {
int id;
std::string name;
std::string category;
};
int main() {
const std::vector<Product> products{
{1001, "Keyboard", "Peripherals"},
{1002, "Mouse", "Peripherals"},
{1003, "Monitor", "Displays"},
{1004, "SSD", "Storage"}
};
std::set<std::string> categories;
// 每次插入都同时完成去重,集合内部自动维持顺序。
for (const Product& product : products) {
categories.insert(product.category);
}
for (const std::string& category : categories) {
std::cout << category << std::endl;
}
}预期输出
Displays
Peripherals
Storage这里不需要判断分类是否已经存在。insert 本身就具有集合语义;对于已经存在的值,集合保持不变。单次查找或插入的时间复杂度通常为 ,其中 是当前分类数量。
判断分类是否存在
如果业务需要判断某个分类是否出现在商品数据中,可以直接使用 find 或 C++20 的 contains。为了兼容 C++17,使用 find 更通用:当返回值等于 categories.end() 时,说明分类不存在。
不要用遍历集合并逐项比较的方式代替 find。set 本身采用有序树结构,成员查询通常为 ;手工从头扫描会退化为线性查找,也没有利用容器已经提供的能力。
商品删除后的同步问题
如果分类集合只是展示商品列表当前包含哪些分类,那么商品被新增、删除或修改分类后,集合也必须反映变化。新增商品时直接插入新分类很容易,但删除商品时不能看到一个分类就立即从 set 删除,因为其他商品可能仍属于该分类。
对于内存版练习系统,一个稳妥策略是在需要展示分类时,从当前商品列表重新生成 set。这样商品列表仍是唯一事实来源,不需要额外维护分类引用计数,也不容易留下已经没有商品使用的过期分类。
set 最适合“唯一且有序”的分类结果。如果只要求去重而完全不关心顺序,可以考虑 unordered_set;当前练习需要稳定生成分类清单,因此 set 能用更少的代码直接表达需求。