Algorithms on sets in STL

2021年01月14日 阅读数:5
这篇文章主要向大家介绍Algorithms on sets in STL,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

数学概念

集合set,是一个无序不重复元素集, 可用于消除重复元素。
支持union(并), intersection(交), difference(差)和sysmmetric difference(对称差集)等数学运算。程序员

伊始

STL提供了上面这些经常使用的数学运算算法,C++程序员应该熟练掌握它们,但它们也只是咱们处理集合算法的冰山一角,下面咱们对它们展开介绍。算法

并集 union

union.png

std::set_union(A.begin(), A.end(),
               B.begin(), B.end(),
               std::back_inserter(results));

交集 intersection

intersection.png

std::set_intersection(A.begin(), A.end(),
                      B.begin(), B.end(),
                      std::back_inserter(results));

补集 includes

includes.png

bool UincludesA = std::includes(begin(U), end(U), begin(A), end(A));

差集 difference

difference.png

std::set_difference(A.begin(), A.end(),
                    B.begin(), B.end(),
                    std::back_inserter(results));

对称差集 sysmmetric difference

sysmmetric difference.png

std::set_symmetric_difference(A.begin(), A.end(),
                              B.begin(), B.end(),
                              std::back_inserter(results));

Important

须要注意的是,前面全部的算法都要求输入的数据是排序好的。spa

  • 实际上,这些算法是基于对输入数据已经排序的事情假设,若是并不是如此,则最终的结果都是错的;
  • 正是因为这些假设,算法是复杂度是O(n),而不是O(nlogn)
下一篇: C++ 方法引用