广东省网站建设_网站建设公司_MongoDB_seo优化

本文是集合（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开始的排序范围中。