C++ 中集合以及集合的相关操作交集（intersection）

72 阅读 0 评论 48 点赞

我是靠谱客的博主优秀冬天，最近开发中收集的这篇文章主要介绍C++ 中集合以及集合的相关操作交集（intersection），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在数学中，集合是最基本的概念之一。编程时，我们不可避免地会涉及到集合及其相关操作。在 C++ 中，标准模板库（STL）提供了 std::set/std::unordered_set 两种传统意义上的集合（除此之外，还有 std::multiset 和 std::unordered_multiset）。

其中，std::set（和 std::multiset）定义在头文件 set 当中，从 C++98 起就有支持；而 std::unordered_set（和 std::unordered_multiset）则定义在头文件 unordered_set 当中，从 C++11 开始支持。

STL库中有丰富的集合运算方法，我们可以使用它们快速完成交集、并集、差集、对称差集的运算。集合运算的前提是两个集合必须按照同样的规则排序就绪，否则不能进行集合运算!
- map,set是有序集合,可以直接参加运算;vector是无序集合,参与运算前必须首先排序.

此处的集合可以为std::set，也可以是std::multiset，但是不可以是hash_set以及hash_multiset。为什么呢？因为set_intersection要求两个区间必须是有序的（从小到大排列），std::set和std::multiset为有序序列，而hash_set以及hash_multiset为无序序列。

交集(set_intersection) A∩BA∩B
OutputIt set_intersection( InputIt1 first1, InputIt1 last1,InputIt2 first2, InputIt2 last2, OutputIt d_first );
并集(set_union) A∪BA∪B
OutputIt set_union( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );
差集(set_difference) A−BA−B
OutputIt set_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );
对称差集(set_symmetric_difference) A∪B−(A∩B)A∪B−(A∩B)
OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first );

交集（intersection）

交集是集合运算中经常会用到的计算，其表达是两个集合共有的部分（图中红色区域）

STL中有set_intersection方法可以实现该功能。它是C++17开始支持的方法，声明于<algorithm>中。其中一种形式是

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_intersection( ExecutionPolicy&& policy, ForwardIt1 first1, ForwardIt1 last1,
                             ForwardIt2 first2, ForwardIt2 last2,
                             ForwardIt3 d_first );

第一二个参数是某个集合的起止迭代器，第二三个参数是另一个集合的起止迭代器。这两个待比较集合要求是有序的。最终得到的交集保存在第五个参数所指向的集合的起始迭代器位置。

#include <vector>
#include <iostream>
#include <iterator>
#include <algorithm>
 
int main() {
    std::vector<int> a{1, 3, 3, 4, 4, 5, 6};
    std::vector<int> b{2, 3, 4, 4, 5, 5, 7};
    std::sort(a.begin(), a.end()); //保证集合是有序的
    std::sort(b.begin(), b.end()); //保证集合是有序的
 
    std::vector<int> result;
 
    std::set_intersection(a.begin(), a.end(),
        b.begin(), b.end(),
        std::back_inserter(result));
 
    std::copy(result.begin(), result.end(), 
        std::ostream_iterator<int>(std::cout, " "));
    return 0;
}

输出结果：