关于STL的知识：集合算法，你学会了吗
本文是集合（set）上的算法，这里的“集合”一词是元素集合的一般含义，而不仅仅是std::set，这篇文章是STL学习资源的一部分，一次一点关于STL的知识。
前提：范围已排序。即这篇文章提到的所有算法都要求输入范围是排序的。同样，它们的输出范围（当存在时）也是排序的。
二、取两个集合的部分数据
STL具有4种互补算法，可以取2个给定集合的不同部分。它们有一种常见的原型形式，输入两个范围，输出一个范围：
代码语言：C++
自动换行
AI代码解释
template<typename InputIterator1, typename InputIterator2, typename OutputIterator> OutputIterator algo(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
因此，对于两个排序集合A和B，可以这样调用：
代码语言：C++
自动换行
AI代码解释
algo(A.begin(), A.end(), B.begin(), B.end(), result);
result可以是vector上的std::back_inserter，也可以是任何其他输出迭代器。
假设有两个集合A和B。
2.1、std::set_difference
std::set_difference将在A中而不是B中的所有元素复制到result中。也可以称为取非（即NOT）。
示例：
展开
代码语言：C++
自动换行
AI代码解释
#include <algorithm> #include <iterator> #include <set> #include <vector> std::vector<int> A = {...} // sorted vector std::set<int> B = {...} // std::set is always sorted std::vector<int> results; std::set_difference(A.begin(), A.end(), B.begin(), B.end(), std::back_inserter(results));
2.2、std::set_intersection
std::set_intersection将既在A中也在B中的所有元素复制到result中。即交集。
2.3、std::set_union
std::set_union将A、B或两者中的所有元素复制到result中。对于同时存在于两者中的元素，将取A的版本(除非在B中出现的公共元素比在A中出现的多，在这种情况下，也取其在B中的附加版本)。
2.4、std::set_symmetric_difference
std::set_symmetric_difference只是简单地将在 A 中却不在 B 中的元素以及在 B 中却不在 A 中的元素复制到result中。
std::set_symmetric_difference是一个特别好的算法示例，虽然听起来很复杂，但它实际上非常容易理解，并且在日常编码中非常有用。这种情况在STL算法中经常发生。
三、比较两个集合
比较两个集合的算法不得不提到std::includes，因为它操作的是集合（即前面解释过的按顺序排列的元素集合）。
给定两个排序集合A和B，std::include检查B的所有元素是否也在A中。
函数原型：
代码语言：C++
自动换行
AI代码解释
template<typename InputIterator1, typename InputIterator2> bool std::includes(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2 );
使用方式：
代码语言：C++
自动换行
AI代码解释
bool AincludesB = std::includes(A.begin(), A.end(), B.begin(), B.end());
四、合并两个集合
4.1、std::merge
std::merge用于将两个排序集合 合并为一个排序集合。函数原型：
代码语言：JavaScript
自动换行
AI代码解释
template<typename InputIterator1, typename InputIterator2, typename OutputIterator> OutputIterator merge(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
给定两个排序集合A和B，将A和B合并到从result开始的排序范围中。