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

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

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/breaksoftware/article/details/88932820

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

交集(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;
}

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

3 4 4 5 

并集(union)

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

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

         其结果是

1 2 3 3 4 4 5 5 6 7

差集(difference)

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

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

        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中。其结果是

1 3 6

        由于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));

        得出的结果是

2 5 7

等差分集(symmetric difference)

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

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

        得到的结果是

1 2 3 5 6 7 

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    STL库中有丰富的集合运算方法,我们可以使用它们快速完成交集、并集、差集、对称差集的运算。(转载请指明出于breaksoftware的csdn博客)

    方亮
  • C++拾取——使用stl标准库实现排序算法及评测

    今天看了一篇文章,讲各种语言的优势和劣势。其中一个观点:haskell非常适合写算法,因为使用者不用去关心具体的计算机实现,而只要关注于操作语义。这让它在专心研...

    方亮
  • C++拾取——使用stl标准库实现排序算法及评测

            今天看了一篇文章,讲各种语言的优势和劣势。其中一个观点:haskell非常适合写算法,因为使用者不用去关心具体的计算机实现,而只要关注于操作语义...

    方亮
  • C++拾取——stl标准库中集合交集、并集、差集、对称差方法

    STL库中有丰富的集合运算方法,我们可以使用它们快速完成交集、并集、差集、对称差集的运算。(转载请指明出于breaksoftware的csdn博客)

    方亮
  • Mac 使用 OpenMP/Clang

    因为默认的 g++ 编译器不支持 openmp,我们可以设置 LLVM/Clang 编译器来编译 openmp。 执行以下命令:

    饶文津
  • 洪小文:AI、机器学习、大数据已成科学基础工具

    用户1737318
  • 在终端里面测试你的的打字速度

    如果是我这个时代的人,小学的时候肯定接触过一个游戏叫金山打字,也接触过这个警察抓小偷的打字游戏,今天介绍的是wpm,是一个在终端中测试你打字速度的一个工具

    bboysoul
  • 面试整理:关于代价函数,正则化

    机器学习AI算法工程
  • 滴滴柳青:竞争、创新和包容性

    滴滴大家都很熟悉,可能大部分人都用滴滴打过车。滴滴出行总裁柳青用3个关键词回顾了过去的一年。 ? 1.竞争 竞争很容易让人兴奋,处于竞争中的企业很容易就像拳击比...

    企鹅号小编
  • jQuery基础

    一、jQuery是什么? jQuery是一个轻量级的、兼容多浏览器的JavaScript库。 jQuery使用户能够更方便地处理HTML Documen...

    人生不如戏

扫码关注云+社区

领取腾讯云代金券