ranges::set_intersectionset_unionset_differenceset_symme

std::ranges::set_intersection：是 C++20 引入的一个算法，用于计算两个已排序范围的交集。它将两个范围的交集元素复制到输出范围中。

std::ranges::set_intersection 

用于计算两个已排序范围的交集。它将两个范围的交集元素复制到输出范围中。

注意事项 输入范围必须已排序。目标范围必须有足够空间存储交集结果。交集结果默认按升序排列。若元素重复，交集次数取两范围中较小的重复次数（例如 a = [2, 2, 3], b = [2, 2, 2]，则交集为 [2, 2]）。

### 语法

Defined in header <algorithm>

Call signature

template< std::input_iterator I1, std::sentinel_for<I1> S1,

          std::input_iterator I2, std::sentinel_for<I2> S2,           std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr set_intersection_result<I1, I2, O>     set_intersection( I1 first1, S1 last1, I2 first2, S2 last2,                       O result, Comp comp = {},

                      Proj1 proj1 = {}, Proj2 proj2 = {} );(1)(since C++20)template< ranges::input_range R1, ranges::input_range R2,

          std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,                         O, Comp, Proj1, Proj2> constexpr set_intersection_result<ranges::borrowed_iterator_t<R1>,                                   ranges::borrowed_iterator_t<R2>, O>     set_intersection( R1&& r1, R2&& r2, O result, Comp comp = {},

                      Proj1 proj1 = {}, Proj2 proj2 = {} );(2)(since C++20)

Helper types

template< class I1, class I2, class O > using set_intersection_result = ranges::in_in_out_result<I1, I2, O>;

(3)(since C++20)

### 参数 - `r1` 和 `r2`：输入范围，必须是已排序的。 - `result`：输出迭代器，指向存储交集元素的位置。 - `comp`：比较函数对象，用于比较元素。 - `proj1` 和 `proj2`：投影函数对象，用于投影元素。

### 返回值 返回一个 `ranges::set_intersection_result` 结构，包含两个输入范围的结束迭代器和输出范围的结束迭代器。

### 示例 以下是一个使用 `std::ranges::set_intersection` 的示例：

#include <algorithm> #include <iostream> #include <iterator> #include <vector> void print(const auto& v, const auto& rem) { std::cout << "{ "; for (const auto& e : v) std::cout << e << ' '; std::cout << '}' << rem; } int main() { const auto in1 = {1, 2, 2, 3, 4, 5, 6}; const auto in2 = {2, 2, 3, 3, 5, 7}; std::vector<int> out {}; std::ranges::set_intersection(in1, in2, std::back_inserter(out)); print(in1, " ∩ "), print(in2, " = "), print(out, "\n"); }

Output:

{ 1 2 2 3 4 5 6 } ∩ { 2 2 3 3 5 7 } = { 2 2 3 5 }

在这个示例中，`in1` 和 `in2` 是两个已排序的整数向量。`std::ranges::set_intersection` 计算它们的交集，并将结果存储在 `out` 向量中。最后，程序输出交集元素。

示例 2：自定义比较和投影 #include <algorithm> #include <vector> #include <iostream> #include <string> struct Person { std::string name; int age; }; int main() { std::vector<Person> a = {{"Alice", 20}, {"Bob", 25}, {"Charlie", 30}}; std::vector<Person> b = {{"Bob", 25}, {"David", 28}, {"Eve", 30}}; std::vector<Person> out; // 按 age 字段比较，计算交集 std::ranges::set_intersection( a, b, std::back_inserter(out), [](int age1, int age2) { return age1 < age2; }, // 比较函数 &Person::age, // 对 a 的投影：提取 age &Person::age // 对 b 的投影：提取 age ); // 输出结果：Bob(25), Charlie(30) for (const auto& p : out) { std::cout << p.name << "(" << p.age << ") "; } }

更多请了解： en.cppreference /w/cpp/algorithm/ranges/set_intersection

std::ranges::set_union

std::ranges::set_union 是 C++20 引入的算法，用于合并两个已排序范围的并集，并将结果写入目标范围。

Defined in header <algorithm>

Call signature

template< std::input_iterator I1, std::sentinel_for<I1> S1,

          std::input_iterator I2, std::sentinel_for<I2> S2,           std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr set_union_result<I1, I2, O>     set_union( I1 first1, S1 last1, I2 first2, S2 last2,                O result, Comp comp = {},

               Proj1 proj1 = {}, Proj2 proj2 = {} );(1)(since C++20)template< ranges::input_range R1, ranges::input_range R2,

          std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,                         O, Comp, Proj1, Proj2> constexpr set_union_result<ranges::borrowed_iterator_t<R1>,                            ranges::borrowed_iterator_t<R2>, O>     set_union( R1&& r1, R2&& r2, O result, Comp comp = {},

               Proj1 proj1 = {}, Proj2 proj2 = {} );

参数说明 first1, last1：第一个输入范围的起止迭代器。first2, last2：第二个输入范围的起止迭代器。result：目标范围的起始迭代器。comp：比较函数（默认为 std::ranges::less）。proj1, proj2：对输入元素的投影函数（默认为 std::identity）。

---

要求 输入范围必须按 comp 定义的顺序排序。目标范围必须有足够空间存储并集结果。重复元素处理： 若元素在某个范围中重复出现，并集会保留所有重复项（但不会跨范围合并）。例如：a = [2, 2, 3]，b = [2, 2, 2]，并集为 [2, 2, 2, 3]。 目标空间：需确保目标范围有足够空间，或使用 std::back_inserter 动态扩展。性能：时间复杂度为线性（最多 2*(N1 + N2) - 1 次比较，其中 N1 和 N2 为输入范围长度）。 返回值

返回指向目标范围末尾的迭代器

示例 示例 1：基本用法

#include <algorithm> #include <vector> #include <iostream> #include <iterator> int main() { std::vector<int> a = {1, 2, 3, 4, 5}; std::vector<int> b = {3, 4, 5, 6, 7}; std::vector<int> out; // 计算并集 std::ranges::set_union(a, b, std::back_inserter(out)); // 输出结果：1 2 3 4 5 6 7 for (int x : out) { std::cout << x << " "; } }

输出结果：

1 2 3 4 5 6 7

示例 2：自定义比较和投影 #include <algorithm> #include <vector> #include <iostream> #include <string> struct Person { std::string name; int age; }; int main() { std::vector<Person> a = {{"Alice", 20}, {"Bob", 25}, {"Charlie", 30}}; std::vector<Person> b = {{"Bob", 26}, {"David", 28}, {"Eve", 30}}; std::vector<Person> out; // 按 age 字段比较，计算并集 std::ranges::set_union( a, b, std::back_inserter(out), [](int age1, int age2) { return age1 < age2; }, // 比较函数 &Person::age, // 对 a 的投影：提取 age &Person::age // 对 b 的投影：提取 age ); // 输出结果：Alice(20), Bob(25), Charlie(30), David(28), Eve(30) for (const auto& p : out) { std::cout << p.name << "(" << p.age << ") "; } }

输出结果：

Alice(20) Bob(25) Bob(26) David(28) Charlie(30) 

与传统 std::set_union 的区别 范围支持：直接接受范围参数（如 std::ranges::set_union(a, b, ...)），而非迭代器对。投影功能：允许通过 proj1 和 proj2 对输入元素进行变换后再比较。约束检查：通过 C++20 概念明确约束参数类型，增强类型安全。

更多信息：

en.cppreference /w/cpp/algorithm/ranges/set_union

---

std::ranges::set_difference

Defined in header <algorithm>

Call signature

template< std::input_iterator I1, std::sentinel_for<I1> S1,

          std::input_iterator I2, std::sentinel_for<I2> S2,           std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr set_difference_result<I1, O>     set_difference( I1 first1, S1 last1, I2 first2, S2 last2,                     O result, Comp comp = {},

                    Proj1 proj1 = {}, Proj2 proj2 = {} );(1)(since C++20)template< ranges::input_range R1, ranges::input_range R2,

          std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,                         O, Comp, Proj1, Proj2> constexpr set_difference_result<ranges::borrowed_iterator_t<R1>, O>     set_difference( R1&& r1, R2&& r2, O result, Comp comp = {},

                    Proj1 proj1 = {}, Proj2 proj2 = {} );

std::ranges::set_difference 是 C++20 引入的算法，用于计算两个已排序范围的差集（即存在于第一个范围但不在第二个范围中的元素），并将结果写入目标范围。它是传统 std::set_difference 的范围适配版本，支持投影和直接使用范围参数。

---

参数说明 first1, last1：第一个输入范围的起止迭代器（要计算差集的主范围）。first2, last2：第二个输入范围的起止迭代器（被减的范围）。result：目标范围的起始迭代器。comp：比较函数（默认为 std::ranges::less）。proj1, proj2：对输入元素的投影函数（默认为 std::identity）。

---

要求 两个输入范围必须按 comp 定义的顺序排序。目标空间：需确保目标范围有足够空间，或使用 std::back_inserter 动态扩展。重复元素处理： 若元素在第一个范围中出现 m 次，在第二个范围中出现 n 次，则差集中保留 max(m - n, 0) 次。例如：a = [2, 2, 3]，b = [2]，差集为 [2, 3]。 性能：时间复杂度为线性（最多 2*(N1 + N2) - 1 次比较，其中 N1 和 N2 为输入范围长度）。

---

示例 示例 1：基本用法 #include <algorithm> #include <vector> #include <iostream> #include <iterator> int main() { std::vector<int> a = {1, 2, 3, 4, 5}; std::vector<int> b = {3, 4, 5, 6, 7}; std::vector<int> out; // 计算差集：a 中存在但 b 中不存在的元素 std::ranges::set_difference(a, b, std::back_inserter(out)); // 输出结果：1 2 for (int x : out) { std::cout << x << " "; } }

输出结果：

1 2

示例 2：自定义比较和投影 #include <algorithm> #include <vector> #include <iostream> #include <string> struct Person { std::string name; int age; }; int main() { std::vector<Person> a = {{"Alice", 20}, {"Bob", 25}, {"Charlie", 30}}; std::vector<Person> b = {{"Bob", 26}, {"David", 28}, {"Eve", 30}}; std::vector<Person> out; // 按 age 字段比较，计算差集（a 中存在但 b 中不存在的元素） std::ranges::set_difference( a, b, std::back_inserter(out), [](int age1, int age2) { return age1 < age2; }, // 比较函数 &Person::age, // 对 a 的投影：提取 age &Person::age // 对 b 的投影：提取 age ); // 输出结果：Alice(20) Bob(25) for (const auto& p : out) { std::cout << p.name << "(" << p.age << ") "; } }

输出结果：

Alice(20) Bob(25)

与传统 std::set_difference 的区别 范围支持：直接接受范围参数（如 std::ranges::set_difference(a, b, ...)）。投影功能：允许通过 proj1 和 proj2 对输入元素进行变换后再比较。约束检查：通过 C++20 概念明确约束参数类型，增强类型安全。

---

std::ranges::set_symmetric_difference

std::ranges::set_symmetric_difference 是 C++20 中引入的算法，用于计算两个有序范围的对称差集，即存在于任一输入范围但不同时存在于两个范围中的元素。结果会写入输出范围，且保持有序。

函数原型

Defined in header <algorithm>

Call signature

template< std::input_iterator I1, std::sentinel_for<I1> S1,

          std::input_iterator I2, std::sentinel_for<I2> S2,           std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<I1, I2, O, Comp, Proj1, Proj2> constexpr set_symmetric_difference_result<I1, I2, O>     set_symmetric_difference( I1 first1, S1 last1, I2 first2, S2 last2,                               O result, Comp comp = {},

                              Proj1 proj1 = {}, Proj2 proj2 = {} );(1)(since C++20)template< ranges::input_range R1, ranges::input_range R2,

          std::weakly_incrementable O, class Comp = ranges::less,           class Proj1 = std::identity, class Proj2 = std::identity > requires std::mergeable<ranges::iterator_t<R1>, ranges::iterator_t<R2>,                         O, Comp, Proj1, Proj2> constexpr set_symmetric_difference_result<ranges::borrowed_iterator_t<R1>,                                           ranges::borrowed_iterator_t<R2>, O>     set_symmetric_difference( R1&& r1, R2&& r2, O result, Comp comp = {},

                              Proj1 proj1 = {}, Proj2 proj2 = {} );

参数说明 first1, last1: 第一个输入范围的迭代器对。first2, last2: 第二个输入范围的迭代器对。result: 输出范围的起始迭代器。comp: 比较函数（默认为 std::ranges::less）。proj1, proj2: 应用于输入元素的投影（默认为 std::identity）。 使用条件 输入范围必须已按升序排列。输出范围不能与输入范围重叠。 示例 #include <algorithm> #include <vector> #include <iostream> #include <iterator> int main() { std::vector<int> v1 = {1, 2, 4, 5, 6}; std::vector<int> v2 = {2, 3, 5, 7}; std::vector<int> out; std::ranges::set_symmetric_difference(v1, v2, std::back_inserter(out)); // 输出结果 for (int n : out) { std::cout << n << ' '; } }

输出:

1 3 4 6 7

步骤解析 输入准备: v1 和 v2 必须有序。算法执行: 比较 v1 和 v2 的当前元素。将较小元素写入 out，移动对应迭代器。若元素相等，则跳过，同时移动两个迭代器。 结果: out 包含对称差集元素，保持有序。 自定义比较和投影 // 使用自定义比较函数（按降序） std::ranges::set_symmetric_difference( v1 | std::views::reverse, v2 | std::views::reverse, std::back_inserter(out), std::greater{} ); // 使用投影（如比较字符串长度） std::vector<std::string> s1 = {"apple", "banana", "cherry"}; std::vector<std::string> s2 = {"grape", "kiwi", "orange"}; std::ranges::set_symmetric_difference( s1, s2, std::back_inserter(out_str), [](int a, int b) { return a < b; }, [](const std::string& s) { return s.length(); }, [](const std::string& s) { return s.length(); } );

 总结

std::ranges::set_symmetric_difference 高效计算两个有序范围的对称差集，时间复杂度为 (O(N+M))，空间复杂度为 (O(1))（不计输出）。需确保输入有序且输出范围足够大。