如何在C++中应用两个列表之间的交集？

Question

我是C++ list的新手。

我有两个列表：list1和list2。我需要获取这些列表之间的共同元素。我该如何做到这一点？

- Farjana Parveen Ayubb

---

如果列表本身包含重复项怎么办？ - Bathsheba

请阅读如何提出好问题，并学习如何创建最小、完整和可验证的示例。 - Some programmer dude

有一个方法是参照这里提供的例子：http://en.cppreference.com/w/cpp/algorithm/set_intersection。 - Bathsheba

@Bathsheba：通常的定义意味着intersection(A,A)=A。显然，这排除了去重的可能性。 - MSalters

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) 的摊销复杂度。

template<typename T>
std::list<T> intersection_of(const std::list<T>& a, const std::list<T>& b){
    std::list<T> rtn;
    std::unordered_multiset<T> st;
    std::for_each(a.begin(), a.end(), [&st](const T& k){ st.insert(k); });
    std::for_each(b.begin(), b.end(),
        [&st, &rtn](const T& k){
            auto iter = st.find(k);
            if(iter != st.end()){
                rtn.push_back(k);
                st.erase(iter);
            }
        }
    );
    return rtn;
}

我使用了std::unordered_multiset而不是std::unordered_set，因为它在两个列表中保留了常见重复项的出现次数。

我对随机生成的9000个int运行了一个简陋的基准测试，比较了这两种方法的结果（较低的值表示性能更好）。

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

---

使用 std::set_intersection 方法的分析：

• 对大小为 N 的 列表1 进行排序： O(Nlog(N))
• 对大小为 M 的 列表2 进行排序： O(Mlog(M))
• 查找交集： O(M + N)
• 总计： O(Nlog(N) + Mlog(M) + M + N) ...(一般化为对数)

假设 M 和 N 相等，我们可以将其概括为：O(Nlog(N))

但如果我们使用我上面发布的 intersection_of 方法：

• 遍历大小为 N 的列表1并添加到集合中为： O(N) + O(1) = O(N)
• 遍历大小为 M 的列表2，检查多重集合，将其添加到out中，并从列表2中删除： O(M) + O(1) + O(1) + O(1) = O(M)
• 总计： O(M + N) ...(一般化为线性)

假设 M 和 N 相等，我们可以将其概括为：O(N)

- WhiZTiM

---

看到你撤销了我的编辑：请注意，在标准的C++中并没有名为std::intersection的函数。 - Bathsheba

@Bathsheba，谢谢，我正在编辑答案。反转是一个错误。 - WhiZTiM

使用unordered_multiset的必要性是什么？为什么我们需要保留重复项，因为如果交换a和b的顺序，结果将会不同？ - coin cheung