Physics-Station phst.hateblo.jp

旧 http://physics-station.blogspot.jp/ から当はてなブログに移行しました。間違ってるところがあればコメントください。記述の正確性は保証しません。

2個の自作クラスの配列(std::vector<MyClass>とか)から重複とかを探す

2個の数列(std::vector<int>とか)から重複とかを探す - Physics-Station2 の続き

2個の自作クラスの配列(ベクター)から重複等を探す方法。

#include <algorithm>に便利な関数が用意されている。 ソートして、重複を削除した後、set_intersection, set_union, set_differenceを使えばよいが、自作クラスに比較演算子等がないためそれを別途与える必要がある。この3つの関数に与える演算子は<演算子である。

今回は使い回しが多いため、ラムダ式ではなく関数として与える。 古い例ではインライン関数 inlineが与えられていることがあるが、最近のコンパイラは賢く、勝手に最適化してくれるのでユーザーがわざわざつける必要はない。

f:id:onsanai:20161130074536p:plain:w200

#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());
    ::system("pause");
}