C++拾取——stl标准库中集合交集、并集、差集、对等差分方法

栏目: 编程工具 · 发布时间: 5年前

内容简介:在《C++拾取——使用stl标准库简化代码》一文中,我们看到如何使用STL标准库精简代码。之后的若干博文中,我们将继续相关的内容,只是标题没有延续《——1》、《——2》这样的风格,而是以更加突出文章主题的方式表达。交集是集合运算中经常会用到的计算,其表达是两个集合共有的部分(图中红色区域)

在《C++拾取——使用stl标准库简化代码》一文中,我们看到如何使用STL标准库精简代码。之后的若干博文中,我们将继续相关的内容,只是标题没有延续《——1》、《——2》这样的风格,而是以更加突出文章主题的方式表达。 (转载请指明出于breaksoftware的csdn博客)

交集(intersection)

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

C++拾取——stl标准库中集合交集、并集、差集、对等差分方法

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;
}

第7~10行保证了待比较的两个集合是有序的。第14行是将a、b两个集合的交集保存到result集合中。最终输出的是

并集(union)

并集是指两个集合组合在一起集合(图中红色区域)。

C++拾取——stl标准库中集合交集、并集、差集、对等差分方法

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

template< class ExecutionPolicy, class ForwardIt1, class ForwardIt2, class ForwardIt3 >
ForwardIt3 set_union( 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_union(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;
}

其结果是

差集(difference)

差集是指在一个集合中,不再另外一个集合中的部分(图中红色区域)

C++拾取——stl标准库中集合交集、并集、差集、对等差分方法

可以见得,两个集合的差集存在两个可能性:一种是在左侧集合不在右侧集合中的部分;一种是在右侧集合不在左侧集合中的部分。

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

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_difference( InputIt1 first1, InputIt1 last1,
                         InputIt2 first2, InputIt2 last2,
                         OutputIt 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_difference(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;
}

这个例子中,我们将算出在a集合中,不在b集合中的元素,并保存到result中。其结果是

由于a集合中有两个3,所以结果中有一个3。

如果求在集合b中,不在集合a中的集合,只需要把std::set_difference中a、b替换位置

std::set_difference(b.begin(), b.end(),
        a.begin(), a.end(),
        std::back_inserter(result));

得出的结果是

等差分集(symmetric difference)

等差分集是指并集中,去除交集之外的部分(图中红色区域)

C++拾取——stl标准库中集合交集、并集、差集、对等差分方法

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

template< class InputIt1, class InputIt2, class OutputIt >
OutputIt set_symmetric_difference( InputIt1 first1, InputIt1 last1,
                                   InputIt2 first2, InputIt2 last2,
                                   OutputIt 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_symmetric_difference(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;
}

得到的结果是

在项目中,我们使用上述集合操作方法,将使代码变的简洁。


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

数据结构基础

数据结构基础

[美]Ellis Horowitz 霍罗维兹 / 朱仲涛 / 清华大学出版社 / 2009-3 / 49.00元

《数据结构基础(C语言版)(第2版)》是最经典数据结构教材的最新版本,国内外大多数的同类教材都是以《数据结构基础(C语言版)(第2版)》为蓝本编写而来的。《数据结构基础(C语言版)(第2版)》用C作为描述语言,全面而生动地介绍了数据结构的有关知识,如数组、栈、队列、链表、树和图,以及构成所有软件基础的排序散列技术。此外,《数据结构基础(C语言版)(第2版)》还介绍了各种高级或特殊数据结构,如优先级......一起来看看 《数据结构基础》 这本书的介绍吧!

URL 编码/解码
URL 编码/解码

URL 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具