2個の数列(std::vector<int>とか)から重複とかを探す - 物理の駅 Physics station by 現役研究者 の続き
2個の自作クラスの配列(ベクター)から重複等を探す方法を紹介する。Linuxのjoinコマンドを高速化する場合などに使える。
#include <algorithm>に便利な関数が用意されている。
std::sortでソートして、std::uniqueとeraseで重複を削除した後、set_intersection, set_union, set_differenceで、積集合、和集合、差集合を得ることができる。自作クラスに比較演算子等がないため、自分で関数を作って与える必要がある。この3つの関数に与える演算子は比較 (<) 演算子である。
今回は比較演算用の関数の使い回しが多いため、ラムダ式ではなく関数として定義する。
古い例ではインライン関数 inlineが与えられていることがあるが、最近のコンパイラは賢く、勝手に最適化してくれるのでユーザーがわざわざつける必要はない(らしい)。
#include <random> #include <vector> #include <algorithm> #include <iostream> #include <iterator> class MyClass { public: unsigned int id; double x, y, ax, ay; }; bool mycomp_size(const MyClass &a, const MyClass &b) { return (a.id < b.id); } //大小比較 bool mycomp_equal(const MyClass &a, const MyClass &b) { return (a.id == b.id); } //イコール比較 void main() { const int Ntrk = 10000000; std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distribution<> dis(0, Ntrk - 1); std::vector<MyClass> list1, list2; for (int i = 0; i < Ntrk; ++i) { MyClass t; t.id = dis(gen); //乱数を作成 list1.emplace_back(t); t.id = dis(gen); //乱数を作成 list2.emplace_back(t); } std::sort(list1.begin(), list1.end(), mycomp_size); //ソート std::sort(list2.begin(), list2.end(), mycomp_size); //ソート std::cout << list1.size() << " (unique)-> "; //重複を削除 list1.erase(std::unique(list1.begin(), list1.end(), mycomp_equal), list1.end()); std::cout << list1.size() << std::endl; std::cout << list2.size() << " (unique)-> "; //重複を削除 list2.erase(std::unique(list2.begin(), list2.end(), mycomp_equal), list2.end()); std::cout << list2.size() << std::endl; std::vector<MyClass> list_inter; //list1とlist2の両方にある値 (積集合 intersection) std::set_intersection(list1.begin(), list1.end(), list2.begin(), list2.end(), std::back_inserter(list_inter), mycomp_size); std::vector<MyClass> list_union; //list1かlist2のどちらかに存在する値 (和集合 union) std::set_union(list1.begin(), list1.end(), list2.begin(), list2.end(), std::back_inserter(list_union), mycomp_size); std::vector<MyClass> list_dif1; //list1にあってlist2にない値 (差集合 dif1) std::set_difference(list1.begin(), list1.end(), list2.begin(), list2.end(), std::back_inserter(list_dif1), mycomp_size); std::vector<MyClass> list_dif2; //list2にあってlist1にない値 (差集合 dif2) std::set_difference(list2.begin(), list2.end(), list1.begin(), list1.end(), std::back_inserter(list_dif2), mycomp_size); //結果の確認 std::cout << "dif1 + dif2 + inter = union" << std::endl; printf_s("%u + %u + %u = %u\n", list_dif1.size(), list_dif2.size(), list_inter.size(), list_union.size()); }
