在 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 )
