set_union、set_intersection、set_difference —— 对两个已排序序列做并集、交集、差集运算。
这三个函数都对两个已排序的序列做集合运算，写法几乎一样：传入两个序列各自的 [begin, end)，再传入存放结果的起始位置。返回值是结果的尾后迭代器，配合 erase 才能让 result 容器的大小刚好等于真实结果长度。
合并两个序列中出现过的所有元素（重复元素只保留一份），结果同样保持有序。
| 1 | vector<int> a = {1, 2, 3, 4, 5}; |
| 2 | vector<int> b = {3, 4, 5, 6, 7}; |
| 3 | vector<int> result; |
| 4 | |
| 5 | // 并集：a ∪ b |
| 6 | result.resize(a.size() + b.size()); |
| 7 | auto it = set_union(a.begin(), a.end(), b.begin(), b.end(), result.begin()); |
| 8 | result.erase(it, result.end()); |
| 9 | // result = {1, 2, 3, 4, 5, 6, 7} |
resize？这三个集合运算函数都是把结果写入到 result.begin() 开始的位置，而不是自动 push_back——如果 result 本身空间不够，会越界。并集结果最多有 a.size() + b.size() 个元素，所以按这个上限先分配空间最安全，多余的部分用 erase 删掉。只保留两个序列都出现过的元素。
| 1 | // 交集：a ∩ b |
| 2 | result.resize(min(a.size(), b.size())); |
| 3 | it = set_intersection(a.begin(), a.end(), b.begin(), b.end(), result.begin()); |
| 4 | result.erase(it, result.end()); |
| 5 | // result = {3, 4, 5} |
min(a.size(), b.size()) 来预分配空间最合适。保留在 a 中但不在 b 中的元素——注意差集是有方向的，set_difference(a, b) 和 set_difference(b, a) 结果不一样。
| 1 | // 差集：a - b（在 a 中但不在 b 中） |
| 2 | result.resize(a.size()); |
| 3 | it = set_difference(a.begin(), a.end(), b.begin(), b.end(), result.begin()); |
| 4 | result.erase(it, result.end()); |
| 5 | // result = {1, 2} |
sort 一遍。如果你存的本身就是 set 或者 map（天然有序），可以直接拿 begin() / end() 用，不需要再排序。find 暴力查找另一个序列"的 O(n × m) 快得多，原理类似归并排序里的双指针合并。