如何應用C++中兩個列表之間的交集？

Question

我是C++新手list。

我有兩個列表：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 

編輯：

以上方法很可能不會荷蘭國際集團是最佳的，主要是因爲分選std::list是不是很好的CPU ...

對於空間的權衡，下面的方法一定會成爲更大的數據集的速度更快，因爲我們遍歷通過每個列表只有一次，而且所有的操作在每次迭代完成不超越一個O(1)攤銷複雜

​​

我用std::unordered_multiset而不是std::unordered_set因爲它保留了普通副本的出現次數在這兩個列表

我跑dirty benchmark對隨機生成的9000int S中的兩種方法，其結果是（越低越好）：

• ：

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

  ---

  使用std::set_intersection方法的分析分類列表1的大小N是：O(Nlog(N))

• 排序表2大小M的是：O(Mlog(M))
• 尋找交集：O(M + N)
• 總：O(Nlog(N) + Mlog(M) + M + N) ...（概括爲對數的）

假設M和N是相等的，我們可以概括它爲：O(Nlog(N))

但是，如果我們使用intersection_of方法我張貼以上：

• 迭代通過列表1的大小爲N並且添加到該集合中的是：O(N) + O(1) = O(N)
• 遍歷列表2大小M，檢查多重集的，加入到out，從列表中除去2：O(M) + O(1) + O(1) + O(1) = O(M)
• 總計：O(M + N) ...（概括爲線性）

假設M和N是相等的，我們可以將其概括爲：O(N)