C++で2つのリスト間の交差を適用する方法は？

Question

C++を初めて使用しましたリストです。

私は2つのリスト：list1とlist2を持っています。私はこれらのリストの間で共通の要素を取得する必要があります。どのように私はこれを得ることができますか？

を使用でき

Answer 1

：そのためstd::set_intersectionを、あなたは最初の二つのリストを並べ替える提供：

例：

#include <algorithm> 
#include <iostream> 
#include <list> 

int main() { 
    std::list<int> list1{2, 5, 7, 8, -3, 7}; 
    std::list<int> list2{9, 1, 6, 3, 5, 2, 11, 0}; 

    list1.sort(); 
    list2.sort(); 

    std::list<int> out; 
    std::set_intersection(list1.begin(), list1.end(), list2.begin(), list2.end(), 
          std::back_inserter(out)); 

    for(auto k : out) 
     std::cout << k << ' '; 
} 

出力：

2 5 

EDIT：

上記の方法は実行されない可能性があります我々は繰り返すので、スペースのトレードオフのために... std::listをソートすることはCPUに素敵ではない主な理由は、最適であると

をINGの、以下の方法は、確かに、より大きなデータのセットのために高速になりますそれは両方のリストに共通の重複の出現箇所を保持するので、私はstd::unordered_multisetではなくstd::unordered_setを使用

​​

O(1)償却複雑さを超えない各繰り返しで行われ、一度だけ、各リスト、およびすべての操作を通じて

Iは、ランダムに生成9000int S上の2つの方法のためdirty benchmarkを実行し、結果は（低い方がよい）であった。std::set_intersection法を用いる

Average timings for 100 runs: 
intersection_of: 8.16 ms 
sortAndIntersect: 18.38 ms 

---

分析：

• 並べ替えリスト1 Nのは：O(Nlog(N))
• 交差点を見つけることである：O(M + N)
• 合計：
• サイズMの2があるリストソートO(Nlog(N) + Mlog(M) + M + N)を...MとNが等しいと仮定すると、

を（対数として一般化）、我々はとしてそれを一般化することができます：O(Nlog(N))

しかし、我々は、私は上記の投稿intersection_of方法で使用する場合：リストを反復

• を1のサイズがNであり、セットに加えることは：O(N) + O(1) = O(N)
• リスト2 一覧から除去、outに添加サイズM、多重集合をチェックする、2：合計O(M) + O(1) + O(1) + O(1) = O(M)
• ：O(M + N) ...

（リニアとして一般） MとNが等しいと仮定すると、次のように一般化することができます。O(N)