Algorithms on sets in STL

微信扫一扫,分享到朋友圈

Algorithms on sets in STL

数学概念

集合 set ,是一个无序不重复元素集, 可用于消除重复元素。

支持 union (并), intersection (交), difference (差)和 sysmmetric difference (对称差集)等数学运算。

伊始

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

并集 union

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

交集 intersection

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

补集 includes

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

差集 difference

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

对称差集 sysmmetric difference

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

Important

需要注意的是,前面所有的算法都要求输入的数据是排序好的。

  • 实际上,这些算法是基于对输入数据已经排序的事情假设,如果并非如此,则最终的结果都是错的;
  • 正是由于这些假设,算法是复杂度是 O(n) ,而不是 O(nlogn)

微信扫一扫,分享到朋友圈

Algorithms on sets in STL

Bootstrap 开源 SVG 图标库 Bootstrap Icons

上一篇

限时 5.75 元 / 月:芒果 TV 会员年卡 3.5 折 69 元促销活动地址入口

下一篇

你也可能喜欢

Algorithms on sets in STL

长按储存图像,分享给朋友