我是C++ list的新手。
我有两个列表:list1
和list2
。我需要获取这些列表之间的共同元素。我该如何做到这一点?
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)
std::intersection
的函数。 - Bathsheba
intersection(A,A)=A
。显然,这排除了去重的可能性。 - MSalters