如何应用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)