关于c++: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)