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

2個の数列から重複等を探す方法を紹介する。Linuxのjoinコマンドを高速化する場合などに使える。

続きは 2個の自作クラスの配列(std::vector<MyClass>)から重複とかを探す - 物理の駅 Physics station by 現役研究者

#include <algorithm>に便利な関数が用意されている。 ソートして、重複を削除した後、set_intersection, set_union, set_differenceを使ってみよう。

参照

Tech Tips: 知ってると便利なSTL(10) set_intersection, set_union, set_difference

乱数発生器についてのコードを修正しました(2016/11/30)

list1 = {5,7,4,2,9}
list2 = {4,3,8,3,2}
↓ソート
list1 = {2,4,5,7,9}
list2 = {2,3,3,4,8}
↓重複を削除
list1 = {2,4,5,7,9}
list2 = {2,3,4,8}
↓比較
積集合 = {2,4}
和集合 = {2,3,4,5,7,8,9}
差集合1 = {5,7,9}
差集合2 = {3,8}

#include <random>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iterator>

void main()
{
    const int Ntrk = 10000000;

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<> dis(0, Ntrk - 1);
    std::vector<unsigned int> list1, list2;

    for (int i = 0; i < Ntrk; ++i) {
        list1.emplace_back(dis(gen)); //乱数を作成
        list2.emplace_back(dis(gen)); //乱数を作成
    }

    std::sort(list1.begin(), list1.end()); //ソート
    std::sort(list2.begin(), list2.end()); //ソート

    std::cout << list1.size() << " -> ";
    //重複を削除
    list1.erase(std::unique(list1.begin(), list1.end()), list1.end());
    std::cout << list1.size() << std::endl;

    std::cout << list2.size() << " -> ";
    //重複を削除
    list2.erase(std::unique(list2.begin(), list2.end()), list2.end()); 
    std::cout << list2.size() << std::endl;

    std::vector<unsigned int> list_inter; 
    //list1とlist2の両方にある値 (積集合)
    std::set_intersection(list1.begin(), list1.end(), list2.begin(), list2.end(), std::back_inserter(list_inter));

    std::vector<unsigned int> list_union; 
    //list1かlist2のどちらかに存在する値(和集合)
    std::set_union(list1.begin(), list1.end(), list2.begin(), list2.end(), std::back_inserter(list_union));

    std::vector<unsigned int> list_dif1; 
    //list1にあってlist2にない値(差集合)
    std::set_difference(list1.begin(), list1.end(), list2.begin(), list2.end(), std::back_inserter(list_dif1));

    std::vector<unsigned int> list_dif2; 
    //list2にあってlist1にない値(差集合)
    std::set_difference(list2.begin(), list2.end(), list1.begin(), list1.end(), std::back_inserter(list_dif2));

    //結果の確認
    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());
}