C++里算集合差集，别只会用set_difference就完事了

上周帮同事看一段性能瓶颈代码，发现他用std::set_difference处理两个各含10万元素的std::vector——但这两个容器压根没排序。结果程序跑得比泡面还慢，调试器一跟，set_difference在内部疯狂做无效比较，最后还返回了空结果。他挠着头问：“不是叫‘差集’吗？咋不自动排好序再算？”

这问题挺典型。std::set_difference不是万能计算器，它是个严格守规矩的“尺子”：只量已排好序的序列，且默认按 < 比较。你给它乱序数据，它不会帮你整理，只会默默按错序逻辑跑完，结果大概率是错的，或者根本不符合直觉。

先说清楚它到底干啥：
set_difference计算的是有序范围A中存在、但有序范围B中不存在的元素，结果写入指定输出迭代器。注意两个关键词：有序、范围。它不关心你用的是set、vector还是array，只认“是否升序排列”这一条铁律。

举个实在例子：

vector<int> a = {5, 1, 3, 7};   // 乱序
vector<int> b = {2, 4, 6};
vector<int> out;
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(out));
// out 很可能不是 {1,3,5,7}，而是不可预测的一串数字——因为a没排序。

真正安全的写法，得补上排序：

sort(a.begin(), a.end());  // 必须显式排
sort(b.begin(), b.end());
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(out));

但这里埋了个坑：如果你的原始数据本就来自std::set或std::map，它们天生有序，那直接用没问题。可很多人图省事，把vector当set使，又忘了补sort，结果差集算出来像抽奖。

另一个常被忽略的点：set_difference不自动去重。
比如 a = {1,1,2,3}, b = {2}，排序后 a = {1,1,2,3}，b = {2}，差集结果是 {1,1,3}——重复元素全保留。这符合数学定义（多重集差集），但业务上往往要的是“集合”意义上的差（即去重）。这时候得自己加一步：

sort(a.begin(), a.end());
sort(b.begin(), b.end());
vector<int> tmp;
set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(tmp));
// 去重
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());

更进一步，如果数据量大、内存敏感，别一股脑全塞进vector再排。试试分块处理：先用partial_sort保前K个最小值，再对关键子集算差集；或者用std::unordered_set预存B的元素，遍历A时用O(1)哈希查找——虽然不叫set_difference，但实际更快：

unordered_set<int> b_set(b.begin(), b.end());
vector<int> out;
for (int x : a) {
    if (b_set.find(x) == b_set.end()) out.push_back(x);
}
// 注意：结果顺序和a一致，非升序。需不需要排序，取决于你的下游用途。

说到用途，差集真不是只在算法题里打转。比如日志分析：A是今天所有用户ID，B是VIP用户ID，差集就是普通用户；又比如配置同步：A是本地配置项，B是已下发项，差集就是待推送的新配置。关键不在函数名有多酷，而在你清楚自己手里的数据“是不是有序”，以及“要不要去重”、“要不要保序”。

还有个细节：set_difference支持自定义比较器。比如你有一堆Person对象，想按年龄算差集：

struct Person { int id; int age; };
vector<Person> a = {{1,25}, {2,30}};
vector<Person> b = {{2,30}};
auto cmp_by_age = [](const Person& x, const Person& y) { return x.age < y.age; };
sort(a.begin(), a.end(), cmp_by_age);
sort(b.begin(), b.end(), cmp_by_age);
set_difference(a.begin(), a.end(), b.begin(), b.end(), out.begin(), cmp_by_age);

比较器必须和排序用的完全一致，否则行为未定义——这点连不少老手都栽过跟头。

最后提醒一句：别迷信“STL函数一定最优”。当A和B大小悬殊（比如A有100万，B只有10个），用unordered_set查B反而更稳；当数据已在磁盘或数据库里，差集逻辑可能更适合下推到存储层执行。set_difference是利器，但得看清它适用的战场。

下次写差集，先摸摸自己的数据：排好了吗？要重吗？谁更大？再伸手调函数——少一次调试，多十分钟喝咖啡。