C++里求交集，别急着手写循环——set_intersection的实用边界与真实坑点

刚接手一个日志去重模块时，我下意识想用两个for嵌套遍历找共同元素。写到一半突然停住：等等，STL不是有set_intersection吗？翻文档、写demo、测数据……结果发现，它远不是“调个函数就完事”的省心工具。用对了是利器，用错了反而比手写还慢，还崩得莫名其妙。

set_intersection本质是个归并式交集算法，要求两个输入区间都已升序排列，且输出目标容器必须预留足够空间，或配合插入迭代器使用。它不关心你用的是vector还是set，只认“有序”这个硬门槛——这点常被忽略，却直接决定程序跑不跑得通。

最典型的翻车场景：拿两个unordered_set直接喂进去。编译能过，运行直接未定义行为。因为unordered_set底层是哈希表，遍历顺序无序，set_intersection内部按“两路归并”逻辑推进指针，遇到乱序数据就像开车时导航突然把地图倒过来，下一步该往哪走完全不可知。务必先排序再调用，哪怕你用的是set——别以为红黑树自动排序就万事大吉，set_intersection接受的是迭代器范围，不是容器类型。

实际项目中，我们常需要从两个vector<int>里取交集。正确姿势是：

vector<int> a = {1, 3, 5, 7, 9};
vector<int> b = {2, 3, 6, 7, 10};
vector<int> result;
result.reserve(min(a.size(), b.size())); // 预分配，避免多次realloc

sort(a.begin(), a.end());
sort(b.begin(), b.end());
set_intersection(a.begin(), a.end(),
                 b.begin(), b.end(),
                 back_inserter(result));

注意三个细节：reserve提前预分配空间，sort确保有序，back_inserter接管插入逻辑。漏掉任意一个，轻则性能打折，重则内存越界。

有人问：能不能直接输出到set里去重？可以，但没必要。set_intersection本身不负责去重——它只忠实输出所有匹配项。如果输入序列本身含重复元素（比如a = {1,1,2}，b = {1,1,3}），结果会是{1,1}。若你真要唯一交集，要么提前用unique去重，要么最后塞进set再转回来。但多数业务场景中，交集结果天然无重（比如ID集合），这时强行套set反而多一次O(n log n)插入开销。

另一个隐蔽陷阱是自定义类型。比如用struct User { int id; string name; };，想按id求交集。这时候不能只重载operator<，还必须保证比较逻辑与排序依据严格一致。曾有个同事在operator<里混用了name和id，导致sort和set_intersection用的排序规则不一致，交集结果时多时少，查了两天才定位到。

更现实的问题是：当数据量上百万，set_intersection还是最优解吗？答案取决于数据分布。如果两个集合交集极小（比如百万级用户中只有几十个重叠），用unordered_set建哈希表查更快；如果交集占比高（>30%），归并确实更稳。我们做过实测：100万有序int求交，set_intersection比哈希方案快1.8倍；但若把其中一个改成随机打乱再排序，总耗时反超哈希方案——排序成本吃掉了算法优势。所以别迷信接口名，先看数据是否“天然有序”。

最后说个容易被文档带偏的点：set_intersection返回的是输出区间的尾后迭代器，不是交集大小。想获取数量？得自己算distance(result.begin(), it)，或者更直白地用result.size()（前提是用back_inserter）。别指望它像Python的len(set(a) & set(b))那样一步到位。

回到开头那个日志模块——最终我们没用set_intersection。因为原始日志ID流本身就是时间序，但存在重复和乱序，排序代价太高。改用unordered_set加载小集合，大集合流式扫描查表，整体耗时降了40%。技术选型没有银弹，set_intersection是好刀，但得看清切的是什么菜。

下次看到“求交集”，别条件反射去翻算法手册。先摸清数据底细：它有序吗？重复吗？规模多大？内存敏感吗？——把问题理清楚，函数自然就选对了。