Chapter 30: Set Algorithms

STL 的 set algorithms 处理两个已排序区间之间的集合关系：并集、交集、差集、对称差、包含判断和有序合并。这里的“集合”指算法语义建立在排序顺序和等价关系上，输入可以来自 std::vector<int>、std::array<int, N>、std::list<int> 或 std::set<int> 的迭代器；容器类型本身没有决定算法是否成立，区间是否按同一个比较规则排序才决定算法前提是否成立。

本章使用一组贯穿材料来追踪所有算法。左侧区间 left = {1, 1, 2, 4, 4, 7}，右侧区间 right = {1, 3, 4, 4, 4, 8}，两者都按默认升序排列。读者读完后应能判断某个 set algorithm 会输出哪些元素、重复元素数量如何计算、目标区间要准备多少空间、比较器和排序前提怎样影响结果合法性。

这些算法位于标准库 <algorithm>。接口形态和版本演进可与 cppreference 的 C++ algorithm 页面 对照；正文只保留本章需要的工程判断：输入区间由 [first, last) 表达，输出从 d_first 开始写入，返回值指向输出结果的尾后位置，比较关系由 operator< 或调用者提供的 comp 决定。

贯穿材料对应的最小代码如下。后续各节会反复回到这两个区间，通过“当前左值、当前右值、比较结果、输出动作、迭代器推进”这条路径解释每个算法。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

void print(const std::vector<int>& values) {
    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
}

int main() {
    std::vector<int> left{1, 1, 2, 4, 4, 7};
    std::vector<int> right{1, 3, 4, 4, 4, 8};

    std::vector<int> out;
    std::set_union(left.begin(), left.end(),
                   right.begin(), right.end(),
                   std::back_inserter(out));
    print(out); // 1 1 2 3 4 4 4 7 8
}

这段代码展示了 set algorithms 的第一个工程事实：输出区间由调用方提供。算法负责按排序规则扫描和写入，内存增长、对象构造和容量管理由目标区间或输出迭代器承担。使用 std::back_inserter(out) 时，写入动作变成 out.push_back(value)；使用普通迭代器写入数组或已有 vector 空间时，调用方要提前保证空间足够。

30.1 set_union

std::set_union 计算两个有序区间的并集。它的输出仍然有序，并且保留每个等价元素组的较大重复次数。对贯穿材料中值 1 来说，左侧出现 2 次，右侧出现 1 次，所以并集输出 2 个 1；对值 4 来说，左侧出现 2 次，右侧出现 3 次，所以并集输出 3 个 4。

并集的“集合”语义在 STL 中按 multiset 计数处理。数学集合常把重复元素折叠成一个值，STL set algorithms 面对的是区间，区间里可以存在重复值。因此并集的结果按每个等价值的 max(left_count, right_count) 计算，和简单去重结果存在明确差异。贯穿材料的输出是 {1, 1, 2, 3, 4, 4, 4, 7, 8}。

set_union 的双指针路径可以用三个分支解释。若当前右值排在当前左值之前，输出右值并推进右侧；若当前左值排在当前右值之前，输出左值并推进左侧；若两者等价，输出左值，左右两侧各推进一次。等价组中的剩余重复元素会在后续循环继续参与比较，最终留下较多一侧的剩余数量。

下面的简化实现保留了这个决策路径。它是教学代码，用来解释标准算法的常见实现形状，不对应某个标准库实现文件。

template <class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt mini_set_union(InputIt1 first1, InputIt1 last1,
                        InputIt2 first2, InputIt2 last2,
                        OutputIt out, Compare comp) {
    while (first1 != last1 && first2 != last2) {
        if (comp(*first2, *first1)) {
            *out++ = *first2++;
        } else {
            *out++ = *first1;
            if (!comp(*first1, *first2)) {
                ++first2;
            }
            ++first1;
        }
    }
    out = std::copy(first1, last1, out);
    out = std::copy(first2, last2, out);
    return out;
}

这段代码里的等价判断来自比较器，和 operator== 没有绑定关系。在有序算法中，两个元素 a 和 b 等价，含义是 comp(a, b) 为 false 且 comp(b, a) 也为 false。当调用者提供自定义比较器时，并集的重复计数和输出顺序都跟这个等价关系绑定。

工程上使用 set_union 时，先判断结果容量上界。两个输入长度分别为 N1 和 N2 时，并集最多输出 N1 + N2 个元素，最少输出较长等价覆盖后的数量。目标区间用 std::back_inserter 可以把容量增长交给容器；若写入裸数组或预分配区间，调用方按上界分配最稳妥。

30.2 set_intersection

std::set_intersection 计算两个有序区间的交集。它只输出两边共同出现的等价元素，并且对每个等价元素组取较小重复次数。贯穿材料中值 1 左侧 2 次、右侧 1 次，交集输出 1 个 1；值 4 左侧 2 次、右侧 3 次，交集输出 2 个 4；值 2、3、7、8 只存在于一侧，交集不输出它们。

交集的扫描动作和并集相同地依赖两个当前位置。若左值更小，左侧当前元素已经无法在右侧当前及后续位置找到等价对象，因为右侧区间有序，后续值只会按排序关系前进，所以推进左侧。若右值更小，同理推进右侧。若两者等价，输出左侧当前元素，左右两侧各推进一次。

template <class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt mini_set_intersection(InputIt1 first1, InputIt1 last1,
                               InputIt2 first2, InputIt2 last2,
                               OutputIt out, Compare comp) {
    while (first1 != last1 && first2 != last2) {
        if (comp(*first1, *first2)) {
            ++first1;
        } else if (comp(*first2, *first1)) {
            ++first2;
        } else {
            *out++ = *first1++;
            ++first2;
        }
    }
    return out;
}

交集的输出上界是 min(N1, N2)。这个边界来自“共同出现”要求：输出的每个元素都要消耗左侧一个出现次数和右侧一个出现次数。目标容器若提前 reserve(min(left.size(), right.size()))，通常能减少 push_back 过程中的扩容次数；这只是目标容器的分配优化，不改变算法比较次数的线性上界。

交集常用于过滤已排序 ID 列表、权限列表、倒排索引命中结果和标签集合。使用时的检查顺序应从排序前提出发，再检查比较器一致性，最后检查重复元素语义。若业务含义要求“值出现过即可”，调用方应先把输入整理成唯一有序区间；若业务含义要求保留出现次数，set_intersection 的 multiset 语义正好匹配。

30.3 set_difference

std::set_difference 计算左侧区间相对右侧区间的差集。它保留左侧独有的元素，并且对每个等价元素组输出 max(left_count - right_count, 0) 个元素。贯穿材料中值 1 左侧 2 次、右侧 1 次，差集输出 1 个 1；值 2 只在左侧出现，输出 1 个 2；值 4 左侧 2 次、右侧 3 次，输出 0 个；值 7 只在左侧出现，输出 1 个 7。最终输出是 {1, 2, 7}。

差集具有方向性。交换左右输入后结果会改变，因为算法名称中的 difference 表示“第一个区间减第二个区间”。set_difference(left, right) 追问“左侧有哪些出现次数没有被右侧抵消”；set_difference(right, left) 追问“右侧有哪些出现次数没有被左侧抵消”。在权限撤销、增量同步、索引删减这类场景中，左右含义要在调用点写清楚。

简化路径如下。当前左值更小时，说明它在右侧当前及后续位置没有可抵消对象，输出左值并推进左侧。当前右值更小时，说明右侧当前元素无法抵消左侧当前值，推进右侧。两者等价时，抵消一对出现次数，左右同时推进，当前这一对不输出。

template <class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt mini_set_difference(InputIt1 first1, InputIt1 last1,
                             InputIt2 first2, InputIt2 last2,
                             OutputIt out, Compare comp) {
    while (first1 != last1 && first2 != last2) {
        if (comp(*first1, *first2)) {
            *out++ = *first1++;
        } else if (comp(*first2, *first1)) {
            ++first2;
        } else {
            ++first1;
            ++first2;
        }
    }
    return std::copy(first1, last1, out);
}

差集的输出上界是 N1。右侧区间不会贡献输出元素，它只抵消左侧元素。这个边界使差集适合写入按左侧大小预分配的缓冲区，也适合用 std::back_inserter 写入空 vector。若输入来自 std::set，每个键最多出现一次，差集退化成普通集合减法；若输入来自有重复值的 vector，算法按出现次数逐个抵消。

30.4 set_symmetric_difference

std::set_symmetric_difference 计算对称差。它输出只在一侧出现的元素，并且对每个等价元素组输出两侧出现次数差的绝对值。贯穿材料中值 1 的次数差是 1，输出 1 个 1；值 4 的次数差是 1，输出 1 个 4；值 2、3、7、8 各只在一侧出现，分别输出。最终输出是 {1, 2, 3, 4, 7, 8}。

对称差可以看作两个有方向差集的有序合并：left - right 加上 right - left。不过标准算法不要求先生成两个临时区间，它能在一次同步扫描中完成。当前左值更小时，输出左值并推进左侧；当前右值更小时，输出右值并推进右侧；两者等价时抵消一对出现次数，左右同时推进。

template <class InputIt1, class InputIt2, class OutputIt, class Compare>
OutputIt mini_set_symmetric_difference(InputIt1 first1, InputIt1 last1,
                                        InputIt2 first2, InputIt2 last2,
                                        OutputIt out, Compare comp) {
    while (first1 != last1 && first2 != last2) {
        if (comp(*first1, *first2)) {
            *out++ = *first1++;
        } else if (comp(*first2, *first1)) {
            *out++ = *first2++;
        } else {
            ++first1;
            ++first2;
        }
    }
    out = std::copy(first1, last1, out);
    out = std::copy(first2, last2, out);
    return out;
}

对称差的工程含义是“状态不一致的部分”。例如两个版本的有序配置键列表做对称差，输出的是只存在于旧版本或只存在于新版本的键；两个排序后的依赖列表做对称差，输出的是两边不共同拥有的依赖项。若重复次数有业务含义，输出数量表达差异次数；若重复次数没有业务含义，调用方应先把输入整理成唯一化区间。

输出上界是 N1 + N2。当两个区间完全没有等价元素时，对称差会输出全部元素；当两个区间在重复次数上完全一致时，输出为空。这个范围变化较大，使用 std::back_inserter 更稳妥；若预分配，按 N1 + N2 做容量上界。

30.5 includes

std::includes 判断第二个有序区间是否被第一个有序区间包含。它返回布尔值，没有输出区间。这里的包含同样按重复次数计算：第二个区间中某个等价值出现 n 次，第一个区间至少也要出现 n 次，包含关系才成立。

以 left = {1, 1, 2, 4, 4, 7} 为全集候选，probe = {1, 4, 4} 被包含，因为 left 里至少有 1 个 1 和 2 个 4。probe = {1, 4, 4, 4} 不成立，因为 left 只有 2 个 4。这个判断和普通“是否出现过”不同，重复元素会消耗左侧出现次数。

includes 的双指针路径适合写成失败优先判断。若右侧当前值排在左侧当前值之前，说明右侧需要的元素在左侧当前及后续位置已经无法匹配，直接返回 false。若左侧当前值更小，推进左侧去寻找可能匹配项。若两者等价，说明右侧当前需求被满足，左右同时推进。当右侧走到末尾时，所有需求已经匹配，返回 true。

template <class InputIt1, class InputIt2, class Compare>
bool mini_includes(InputIt1 first1, InputIt1 last1,
                   InputIt2 first2, InputIt2 last2,
                   Compare comp) {
    while (first2 != last2) {
        if (first1 == last1 || comp(*first2, *first1)) {
            return false;
        }
        if (!comp(*first1, *first2)) {
            ++first2;
        }
        ++first1;
    }
    return true;
}

这段实现里的 !comp(*first1, *first2) 在前面已经排除了 comp(*first2, *first1) 为真的情况，所以它表达等价匹配。includes 的比较次数上界仍然与两个区间长度线性相关；短路条件使失败场景可能更早返回。工程上它适合权限覆盖检查、特性集合覆盖检查、依赖版本列表包含检查和测试期望集合验证。

30.6 merge

std::merge 把两个有序输入区间稳定合并到一个有序输出区间。它和 set_union 的输入前提相同，都要求两个输入区间有序；差异在重复元素处理：merge 输出两边所有元素，set_union 对等价元素组取较大重复次数。贯穿材料经过 merge 后输出 {1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 7, 8}，长度正好是 left.size() + right.size()。

稳定合并的含义是：当两个当前元素等价时，先输出第一个区间中的元素，再输出第二个区间中的等价元素，同时各自区间内部的原有相对顺序保持。对于整数看不出稳定性的价值；对于带有时间戳、来源编号或对象身份的记录，稳定性会决定等价键下记录的相对排列。

struct Record {
    int key;
    char source;
};

bool by_key(const Record& a, const Record& b) {
    return a.key < b.key;
}

int main() {
    std::vector<Record> left{{1, 'A'}, {2, 'A'}};
    std::vector<Record> right{{1, 'B'}, {3, 'B'}};
    std::vector<Record> out;

    std::merge(left.begin(), left.end(),
               right.begin(), right.end(),
               std::back_inserter(out), by_key);

    // key 相同的 1 中，来自 left 的 {1, 'A'} 排在来自 right 的 {1, 'B'} 前面。
}

merge 的输出容量要求最明确：结果长度等于 N1 + N2。这使它适合用于外部排序、多路归并的二路步骤、已排序批次数据合并和日志流合并。与集合算法相比，merge 不抵消、不折叠、不做包含判断；它只把两个排序流编织成一个排序流。

merge 的目标区间同样由调用方负责。若把输出写回与输入重叠的区间，会越过标准算法的前提。若需要在同一容器中合并两个相邻有序子区间，应使用 std::inplace_merge，因为它的接口和内部移动路径就是为原地相邻区间设计的。

30.7 前提条件：有序区间

set algorithms 的共同前提是两个输入区间都按同一个比较规则排序。这个前提支撑了双指针算法的全部剪枝逻辑：当前左值小于当前右值时，左侧当前值已经不可能和右侧当前及后续元素等价；当前右值小于当前左值时，右侧当前值已经不可能和左侧当前及后续元素等价。没有这个单调性，推进某一侧就可能跳过后面真正应匹配的元素。

比较器一致性和排序前提要一起检查。若输入用 std::sort(values.begin(), values.end(), by_id) 排序，后续集合算法也要使用同一个 by_id 或语义等价的比较器。若排序按 id，集合算法按 name，算法看到的区间不再是按当前比较器有序，结果合法性失去标准保证。

等价关系也由比较器决定。若比较器只比较 id，两个对象只要 id 相同就被集合算法视为等价，即便它们的其他字段不同。这个规则对输出对象来源有直接影响：set_intersection 在等价时输出左侧对象，set_union 在等价时也优先输出左侧对象并消耗右侧一个等价对象，merge 在等价时保持左侧等价元素排在右侧等价元素之前。

目标区间容量是另一个前提。集合算法和 merge 都通过输出迭代器写入，普通输出迭代器不会自动分配空间。写入 std::vector<int> result; 的 result.begin() 是错误调用路径，因为空 vector 没有可写元素；写入 std::back_inserter(result) 会把写入动作转换成 push_back，容器负责增长。

std::vector<int> result;

std::set_intersection(left.begin(), left.end(),
                      right.begin(), right.end(),
                      std::back_inserter(result)); // 正确：按需追加

std::vector<int> fixed(std::min(left.size(), right.size()));
auto out_end = std::set_intersection(left.begin(), left.end(),
                                     right.begin(), right.end(),
                                     fixed.begin());
fixed.erase(out_end, fixed.end()); // 正确：预留上界后收缩有效结果

输入区间和输出区间的重叠也要纳入检查。set_union、set_intersection、set_difference、set_symmetric_difference 和 merge 都会边读边写；若输出位置覆盖了尚未读取的输入元素，算法后续读取到的值会被自己写入动作改坏。标准库对这类重叠输入输出不给稳定结果承诺，调用方应使用独立输出区间，或选择专门支持原地路径的算法。

30.8 集合算法底层双指针思想

本章所有 set algorithms 都可以归纳为同一个双指针骨架。两个迭代器分别指向左侧和右侧当前元素，比较器给出三种关系：左小、右小、等价。算法的差异不在扫描方式，而在每种关系下是否输出、输出哪一侧、推进哪一侧、剩余区间如何收尾。

这个骨架可以画成下面的流程。图中 L 表示左侧当前元素，R 表示右侧当前元素；“输出策略”由具体算法替换。

把这个骨架落实到具体算法，可以得到一张判断表。表中“左小”表示 comp(*left_it, *right_it) 为真，“右小”表示 comp(*right_it, *left_it) 为真，“等价”表示两个方向比较都为假。

算法	左小	右小	等价	剩余区间处理
set_union	输出左，推进左	输出右，推进右	输出左，左右都推进	输出另一侧全部剩余
set_intersection	推进左	推进右	输出左，左右都推进	丢弃剩余
set_difference	输出左，推进左	推进右	左右都推进	输出左侧剩余
set_symmetric_difference	输出左，推进左	输出右，推进右	左右都推进	输出另一侧全部剩余
includes	推进左	返回 false	左右都推进	右侧结束为 true，左侧先结束为 false
merge	输出左，推进左	输出右，推进右	输出左，推进左	输出另一侧全部剩余

这张表给出可复用判断顺序。分析任何一个调用时，先确认两个输入是否按同一个比较器排序；再确认等价关系由哪个比较器定义；随后按左小、右小、等价三种比较结果推演输出；最后检查输出容量、重叠边界和重复元素计数。这个顺序比记忆函数名更稳定，因为所有函数共享同一个扫描模型。

复杂度也来自这个骨架。每次循环至少推进一个输入迭代器，两个区间总共最多推进 N1 + N2 次；每个位置只参与常数次比较，所以比较次数是线性上界。迭代器能力方面，普通非并行重载主要依赖输入迭代器和输出迭代器能力；算法不需要随机访问，因为它从头到尾同步推进。

最小自检任务

给定两个已经按升序排序的区间：

std::vector<int> a{1, 1, 2, 5, 5, 9};
std::vector<int> b{1, 3, 5, 5, 5, 9, 10};

请分别判断 std::set_union(a, b)、std::set_intersection(a, b)、std::set_difference(a, b)、std::set_symmetric_difference(a, b)、std::includes(a, b) 和 std::merge(a, b) 的结果或返回值。然后说明若把结果写入普通 vector，应如何准备目标区间。

答案要点

set_union 对每个等价值取较大重复次数，结果是 {1, 1, 2, 3, 5, 5, 5, 9, 10}。其中 1 取 2 次，5 取 3 次，9 取 1 次，其余独有值保留。

set_intersection 对每个等价值取较小重复次数，结果是 {1, 5, 5, 9}。其中 1 取 1 次，5 取 2 次，9 取 1 次。

set_difference(a, b) 表示左侧减右侧，结果是 {1, 2}。1 的次数差为 1，2 只在左侧出现，5 和 9 都被右侧抵消。

set_symmetric_difference 对每个等价值输出次数差的绝对值，结果是 {1, 2, 3, 5, 10}。1 多出 1 个左侧出现次数，5 多出 1 个右侧出现次数，2、3、10 分别只在一侧出现。

includes(a, b) 返回 false。右侧区间需要值 3，左侧区间没有；右侧还需要 3 个 5，左侧只有 2 个 5。任一条件已经足以使包含关系失败。

merge 输出两边所有元素并保持有序，结果是 {1, 1, 1, 2, 3, 5, 5, 5, 5, 5, 9, 9, 10}。它保留所有重复元素，输出长度等于 a.size() + b.size()。

目标区间可以使用 std::back_inserter(result) 让 vector 追加元素；若使用 result.begin() 这类普通输出位置，应先按输出上界分配空间。并集、对称差和 merge 的安全上界是 a.size() + b.size()，交集上界是 min(a.size(), b.size())，差集上界是 a.size()。

本章知识点总结

• 排序前提：set algorithms 的合法调用建立在两个输入区间按同一个比较规则排序之上。
• 区间语义：这些算法处理的是有序区间，输入容器可以是 vector、array、list 或关联容器。
• 等价关系：等价由比较器定义，条件是两个方向的比较结果都为假。
• 并集计数：set_union 对每个等价值输出两侧出现次数的较大值。
• 交集计数：set_intersection 对每个等价值输出两侧出现次数的较小值。
• 差集方向：set_difference 保留左侧未被右侧抵消的出现次数，交换输入会改变结果。
• 对称差计数：set_symmetric_difference 输出两侧出现次数差的绝对值。
• 包含判断：includes 判断第二个区间的每个出现次数是否都能被第一个区间匹配。
• 稳定合并：merge 输出两个输入的全部元素，并在等价元素上保持左侧优先和各自内部顺序。
• 双指针骨架：左小、右小、等价三种比较结果决定输出动作和迭代器推进方式。
• 容量责任：输出区间由调用方提供，std::back_inserter 适合让目标容器自行增长。
• 重叠边界：边读边写的集合算法要求输出不要覆盖尚未读取的输入区间。
• 复杂度来源：每次循环至少推进一个输入迭代器，总推进次数受 N1 + N2 约束。
• 判断顺序：先查排序与比较器，再推演重复计数，最后检查容量、重叠和返回位置。