在 C++ 中查找集合交集
本文将为大家讲解几种在 C++ 中如何寻找集合交集的方法。
使用 std::set_intersection 方法在 C++ 中寻找集合交集
std::set_intersection 方法是 C++ 算法库的一部分，它包含在 <algorithm> 头中。set_intersection 算法操作并不局限于 std::set 对象，而是可以处理任何基于范围的对象，例如 std::vector。需要注意的是，两个输入范围在传递给 set_intersection 算法之前必须进行排序。
在下面的例子中，我们声明两个 std::set 变量，并用任意 string 类型的元素初始化它们。set_intersection 函数的前四个参数是对应对象的范围迭代器，第五个参数是存储计算出的交集的范围的开始。在这种情况下，我们声明一个 std::vector 来存放这些元素。
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;
template<typename T>
void printVectorElements(vector<T> &vec)
{
cout << "{ ";
for (const auto &item : vec) {
cout << item << ", ";
}
cout << "\b\b }" << endl;
}
int main() {
set<string> s1 {"array", "vector",
"deque", "list",
"set", "map",
"multimap", "span"};
set<string> s2(s1);
s2.insert("stack");
s2.insert("queue");
vector<string> s1s2_intsec;
std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(),
std::back_inserter(s1s2_intsec));
cout << "s1 ∩ s2: ";
printVectorElements(s1s2_intsec);
exit(EXIT_SUCCESS);
}
输出：
s1 ∩ s2: ( array, deque, list, map, multimap, set, span, vector )
尽管 std::set_intersection 存储了用户指定的交集元素，但它不能是与输入范围重叠的范围。另一个需要注意的重要点是指定目标范围，它有足够的空间来存储交叉元素。灵活的方法是使用动态数组 std::vector，并使用 std::back_inserter 方法将元素推送到对象中。如果你指定 vector.begin() 迭代器时没有预留内存作为目的参数，算法可能会抛出一个分段故障。下一个例子演示了 vector 对象上的 set_intersection 方法。
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;
template<typename T>
void printVectorElements(vector<T> &vec)
{
cout << "{ ";
for (const auto &item : vec) {
cout << item << ", ";
}
cout << "\b\b }" << endl;
}
int main() {
vector<int> v1v2_intsec;
vector<int> v1 {9,7,5,1,2};
vector<int> v2 {4,3,2,1,7,8};
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
std::set_intersection(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(v1v2_intsec));
cout << "v1 ∩ v2: ";
printVectorElements(v1v2_intsec);
exit(EXIT_SUCCESS);
}
输出：
v1 ∩ v2: ( 1, 2, 7 )
使用 std::set_symmetric_difference 方法在 C++ 中查找集合对称差异
另一个来自 C++ 标准库的算法是 std::set_symmetric_difference，它搜索只在其中一个输入范围内找到的元素。函数参数与 std::set_intersection 方法类似。两种算法都采取排序的范围，并将找到的元素也以排序的方式存储。注意，std::set 容器默认包含排序元素。因此，它可以直接作为输入范围传递。而 std::vector 内容在被 std::set_symmetric_difference 处理之前必须明确地进行排序。
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
using std::cout; using std::endl;
using std::cin; using std::string;
using std::set; using std::vector;
template<typename T>
void printVectorElements(vector<T> &vec)
{
cout << "{ ";
for (const auto &item : vec) {
cout << item << ", ";
}
cout << "\b\b }" << endl;
}
int main() {
vector<int> v1 {9,7,5,1,2};
vector<int> v2 {4,3,2,1,7,8};
std::sort(v1.begin(), v1.end());
std::sort(v2.begin(), v2.end());
vector<int> v1v2_symdif;
std::set_symmetric_difference(v1.begin(), v1.end(),
v2.begin(), v2.end(),
std::back_inserter(v1v2_symdif));
cout << "v1 △ v2: ";
printVectorElements(v1v2_symdif);
exit(EXIT_SUCCESS);
}
输出：
v1 △ v2: ( 3, 4, 5, 8, 9 )
