[tips][cpp][Problemsolver] 一意制約のあるデータ構造set

今回もtipsです。

積集合とかの集合演算をcppでパッと使いたい時用です。

<set>の一意制約について

setは重複を許さない順序付き集合です。例えば、{3, 1, 4, 1}で初期化すると、内部では、{1,3,4}のように格納されます。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
using namespace std;
int main() {
  // 初期値
  set<int> C{3, 1, 4, 1};
  for (int c : C) {
    cout << c << " ";
  }
}

output

1 3 4 

集合の積

関数set_intersection()を使って積集合を作ります。(#define all(a) a.begin(), a.end()と定義しておくと便利です。)

{1, 2, 3, 4}と{4, 5, 6, 2}の積集合は{2, 4}です。次のように作ります。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#define all(a) a.begin(), a.end()
using namespace std;
int main() {
  set<int> A = {1, 2, 3, 4};
  set<int> B = {4, 5, 6, 2};
  set<int> Result;

  // AとBの積集合を作る
  set_intersection(all(A), all(B), inserter(Result, Result.end()));
  for (int r : Result) {
    cout << r << " ";
  }
}

output

2 4 

集合として等しいかの判定

集合として等しいかどうかは、重複を許さない順序付き集合なので、std::equal()を使用するか==で比較すれば良いです。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
#define all(a) a.begin(), a.end()
using namespace std;

int main() {
  set<int> E = {1, 2, 3, 4};
  set<int> F = {1, 2, 3, 4};
  set<int> G = {1, 2, 3, 4, 5};

  if (equal(all(E), all(F))) cout << "Equal" << endl;
  if (E == F) cout << "Equal" << endl;
  if (equal(all(E), all(G))) cout << "Not Equal" << endl;//表示されません
  if (E == G) cout << "Not Equal" << endl;//表示されません

※もっといい方法知ってる人いたら教えてください。
上記、教えてもらいました。コメントありがとうございます。

備考

積集合はset<int>はmultiset<int>と書いても演算できますが、multiset<>は重複を許す集合なので注意です。