Skip to main content

Chapter 30: Set Algorithms

核心问题与阅读主线

本章导读8 个核心小节 · 附自检与总结

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},统一按“比较当前值 → 输出或抵消 → 推进迭代器”追踪各算法行为:

#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
}

算法只负责扫描与写入,输出容器的扩容和构造由调用方承担:std::back_inserter(out) 将写入转为 out.push_back(value),而写入普通迭代器则需提前保证容量足够。

关键事实

下列算法均位于 <algorithm>(完整重载与演进见 cppreference 的 C++ algorithm 页面):

  • 输入区间由 [first, last) 指定,默认使用 operator< 或调用方传入的二元比较器 comp。
  • 输出从 d_first 开始写入,返回值指向输出结果的尾后位置(past-the-end)。

30.1 set_union​

std::set_union 合并两个有序区间,对每个等价组按 multiset 计数保留较大出现次数 max(left_count, right_count)(而非数学去重)。

对贯穿材料,1 左侧 2 次、右侧 1 次,保留 2 个;4 左侧 2 次、右侧 3 次,保留 3 个,输出 {1, 1, 2, 3, 4, 4, 4, 7, 8}。

双指针扫描按三种分支推进(等价组多余的重复元素会在后续循环自然保留):

  • 右值更小(comp(*first2, *first1)):输出右值,推进右侧。
  • 左值更小(comp(*first1, *first2)):输出左值,推进左侧。
  • 两者等价:输出左值,左右各推进一次。
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;
}

关键事实

  • 等价由比较器定义:a 与 b 等价意味着 comp(a, b) 与 comp(b, a) 均为 false,与 operator== 无关;自定义比较器同时决定重复计数与输出顺序。
  • 输出容量上界为 N1 + N2:最少输出较长等价覆盖后的数量,最多为 N1 + N2。写入裸数组或预分配缓冲区应按 N1 + N2 分配;需要自动扩容时用 std::back_inserter。

30.2 set_intersection​

std::set_intersection 输出两侧共同出现的等价元素,每个等价组保留较小出现次数 min(left_count, right_count)。对贯穿材料,1 输出 1 次、4 输出 2 次,单侧值 2、3、7、8 全部跳过,结果为 {1, 4, 4}。

由于输入有序,较小一侧的当前元素绝不可能与另一侧当前及后续位置等价,因此扫描路径如下:

  • 左值更小:只推进左侧。
  • 右值更小:只推进右侧。
  • 两者等价:输出左值,左右各推进一次。
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(std::min(left.size(), right.size())) 可减少扩容次数(仅优化分配,不改变线性比较上界)。

交集常用于过滤已排序 ID、权限列表、倒排索引命中与标签集合:若只需“是否出现过”,应先整理为唯一有序区间;若需保留频次,multiset 语义可直接匹配。

30.3 set_difference​

std::set_difference 计算第一个区间减去第二个区间的差集,按等价组输出 max(left_count - right_count, 0) 个元素。对贯穿材料,1 剩 1 个、2 与 7 保留、4(2 - 3)完全抵消,输出 {1, 2, 7}。

差集具有方向性:交换 left 与 right 会得到完全不同的结果(即“左侧未被右侧抵消的部分”对比“右侧未被左侧抵消的部分”),因此在权限撤销、增量同步和索引删减等场景必须在调用点明确左右角色。扫描规则如下:

  • 左值更小:右侧后续不会再有等价项可抵消它,输出左值并推进左侧。
  • 右值更小:推进右侧寻找可能匹配的左侧元素。
  • 两者等价:互相抵消一对出现次数,左右同时推进且不输出。
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,适合按 N1 预分配或配合 std::back_inserter 追加:

  • 输入来自 std::set(键唯一):退化为普通集合减法。
  • 输入来自含重复值的 std::vector:按出现次数逐个抵消。

30.4 set_symmetric_difference​

std::set_symmetric_difference 计算对称差,输出只在一侧出现的元素以及两侧等价组次数差的绝对值 abs(left_count - right_count)。对贯穿材料,1 与 4 各多出 1 次,单侧值 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;
}

工程上对称差表示“双边状态不一致的部分”,常用于比对有序配置键或排序后的依赖列表(若频次无业务意义,应先去重)。输出长度从全同的 0 到无交集的 N1 + N2 跨度较大,优先使用 std::back_inserter,预分配则按 N1 + N2 准备。

30.5 includes​

std::includes 判断第二个有序区间是否被第一个有序区间包含,直接返回 bool 且不写入输出区间。包含判定同样遵守 multiset 规则:右侧某等价值出现 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,重复匹配会消耗左侧计数)。

扫描采用失败优先短路:右值更小(或左侧先耗尽)时右侧当前元素已无匹配可能,立即返回 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) 为真后即代表等价匹配。算法比较次数上界仍呈线性,但短路条件可让失败场景提前返回,常用于权限覆盖、特性集覆盖、依赖版本包含及测试期望校验。

30.6 merge​

std::merge 将两个有序区间稳定合并到独立输出区间,保留两边全部元素且长度固定为 N1 + N2。对贯穿材料,输出 {1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 7, 8}。

稳定性的工程价值在于等价键的相对顺序:当左右元素等价时,先输出左侧元素,再输出右侧元素,且各区间内部原有的相对顺序保持不变。对仅含整数的区间看不出差异,但对带时间戳、来源编号或对象身份的记录至关重要:

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'} 前面。
}
算法重复元素处理输出长度 / 位置适用场景
std::set_union等价组取较大重复次数不超过 N1 + N2,写入独立输出集合并集、去重或最大频次合并
std::merge保留两边全部元素,等价时左侧优先固定 N1 + N2,写入独立输出外部排序、二路归并、有序日志流合并
std::inplace_merge保留全部元素,等价时前段优先原地合并同一容器内两个相邻有序子区间同容器分段排序后的就地归并

std::merge 不做抵消、折叠或包含判断,仅将两个排序流编织为一条有序流;同容器内合并两段相邻有序子区间须改用 std::inplace_merge,切勿将 std::merge 的输出指回重叠的输入区间。

30.7 前提条件:有序区间​

set algorithms 要求双输入按同一比较规则有序。这一单调性支撑了全部剪枝逻辑(左小于右时,左侧当前值绝不可能与右侧当前及后续元素等价,反之亦然);若用 by_id 排序却按 by_name 调用集合算法,标准结果保证立即失效。

核心判断

比较器同时决定等价判定与输出对象来源:若比较器只比较 id,即使其他字段不同,同 id 对象也被视为等价:

  • set_intersection:等价时输出左侧对象。
  • set_union:等价时优先输出左侧对象,并消耗右侧一个等价对象。
  • merge:等价时保持左侧对象排在右侧对象之前。

目标区间容量同样由调用方保证。普通输出迭代器不会自动扩容,常用两种安全写法如下:

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()); // 正确:预留上界后收缩有效结果

边界与误区

注意
  • 禁止写入未分配空间:对空的 std::vector<int> result; 直接传 result.begin() 属于错误调用路径,写入会立即越界;必须改用 std::back_inserter(result) 或先按上界分配空间。
  • 禁止输入与输出区间重叠:set_union、set_intersection、set_difference、set_symmetric_difference 与 merge 均边读边写,若输出覆盖了尚未读取的输入元素会改坏后续输入,标准库对此不提供结果保证,必须使用独立输出区间或专用原地算法。

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

本章所有算法共用同一套双指针扫描骨架(下图中 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输出左,推进左输出右,推进右输出左,推进左输出另一侧全部剩余

对应到重复元素计数与目标区间容量上界:

算法等价组输出数量 / 返回值输出容量上界
set_unionmax(left_count, right_count)N1 + N2
set_intersectionmin(left_count, right_count)min(N1, N2)
set_differencemax(left_count - right_count, 0)N1
set_symmetric_differenceabs(left_count - right_count)N1 + N2
includes返回 bool(右侧每项频次不超左侧)无输出区间
mergeleft_count + right_countN1 + N2

排查顺序

  1. 确认两个输入区间按同一比较器有序,且与传入算法一致。
  2. 确认等价关系由比较器的双向否定定义(而非 operator==)及等价时哪一侧对象胜出。
  3. 按左小、右小、等价三分支核对输出动作与重复计数。
  4. 核对目标容量上界、非重叠写入约束与返回的尾后迭代器。

由于每次循环至少推进一个输入迭代器,两个区间总共最多推进 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) 的结果或返回值,并说明将结果写入普通 std::vector 时的空间准备方式。

本章知识点总结​

  • 排序与等价前提

    合法调用要求双输入按同一比较规则有序(容器类型不限),等价由 !comp(a, b) && !comp(b, a) 定义,无关 operator==。

  • 并集与交集计数

    均按 multiset 语义计数,set_union 取等价组较大频次(上界 N1 + N2),set_intersection 取较小频次(上界 min(N1, N2))。

  • 差集与对称差

    set_difference 具有方向性,输出 max(left - right, 0)(上界 N1);set_symmetric_difference 输出 abs(left - right)(上界 N1 + N2)。

  • 包含与稳定合并

    includes 要求左侧各值频次不低于右侧;merge 输出全部 N1 + N2 个元素,等价时左侧先于右侧且各自保持原序。

  • 等价对象来源

    当比较器只比部分字段时,等价元素在交集与并集中输出左侧对象,在 merge 中左侧排在右侧之前。

  • 双指针骨架与复杂度

    各算法依左小、右小、等价三分支同步推进,非并行重载仅需输入/输出迭代器,总推进与比较受线性上界 N1 + N2 约束。

  • 容量责任与重叠边界

    调用方需通过 std::back_inserter 或上界预分配保证空间,且输出不得覆盖未读输入(同容器相邻分段合并用 std::inplace_merge)。