ranges::set_intersection set_union set_difference set_symmetric_difference

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

std::ranges::set_intersection 

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

注意事项

1. 输入范围必须已排序。
2. 目标范围必须有足够空间存储交集结果。
3. 交集结果默认按升序排列。
4. 若元素重复，交集次数取两范围中较小的重复次数（例如 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 << ") ";}
}

更多请了解：https://en.cppreference.com/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 = {} );

参数说明

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

---

要求

1. 输入范围必须按 comp 定义的顺序排序。
2. 目标范围必须有足够空间存储并集结果。
3. 重复元素处理：
   • 若元素在某个范围中重复出现，并集会保留所有重复项（但不会跨范围合并）。
   • 例如：a = [2, 2, 3]，b = [2, 2, 2]，并集为 [2, 2, 2, 3]。
4. 目标空间：需确保目标范围有足够空间，或使用 std::back_inserter 动态扩展。
5. 性能：时间复杂度为线性（最多 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 7for (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 概念明确约束参数类型，增强类型安全。

更多信息：

https://en.cppreference.com/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 的范围适配版本，支持投影和直接使用范围参数。

---

参数说明

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

---

要求

1. 两个输入范围必须按 comp 定义的顺序排序。
2. 目标空间：需确保目标范围有足够空间，或使用 std::back_inserter 动态扩展。
3. 重复元素处理：
   • 若元素在第一个范围中出现 m 次，在第二个范围中出现 n 次，则差集中保留 max(m - n, 0) 次。
   • 例如：a = [2, 2, 3]，b = [2]，差集为 [2, 3]。
4. 性能：时间复杂度为线性（最多 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 2for (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）。

使用条件

1. 输入范围必须已按升序排列。
2. 输出范围不能与输入范围重叠。

示例

#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

步骤解析

1. 输入准备: v1 和 v2 必须有序。
2. 算法执行:
   • 比较 v1 和 v2 的当前元素。
   • 将较小元素写入 out，移动对应迭代器。
   • 若元素相等，则跳过，同时移动两个迭代器。
3. 结果: 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))（不计输出）。需确保输入有序且输出范围足够大。