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)

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论