C++ で集合交差を検索
-
C++ で集合の交差を求めるには
std::set_intersectionメソッドを使用する -
C++ でセット対称差を求めるには
std::set_symmetric_differenceメソッドを用いる
この記事では、C++ で集合の共通部分を求める方法のいくつかの方法について説明します。
C++ で集合の交差を求めるには std::set_intersection メソッドを使用する
std::set_intersection メソッドは C++ アルゴリズムライブラリの一部であり、 <algorithm> ヘッダに含まれています。set_intersection アルゴリズムの操作は std::set オブジェクトに限定されるものではなく、std::vector のような任意の範囲ベースのオブジェクトを処理することができます。set_intersection アルゴリズムに渡す前に、両方の入力範囲をソートしなければならないことに注意してください。
以下の例では、2つの std::set 変数を宣言し、任意の string 型の要素で初期化します。関数 set_intersection の最初の 4つのパラメータは対応するオブジェクトからの範囲イテレータであり、第 5 引数は計算された交点が格納される範囲の先頭です。この場合、これらの要素を保持するために 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 )
C++ でセット対称差を求めるには std::set_symmetric_difference メソッドを用いる
C++ 標準ライブラリのもう 1つのアルゴリズムは 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 )
