我有一个集合std::set 。 我想找到的所有集合的交集在此集合，以最快的方式。 集合集合中的数量通常非常小（〜5-10），和元素在每一组的数量通常小于1000，但可以偶尔去四处高达10000。但是，我需要做的这些相交数数以千计的时间，尽可能快。 我试图基准数的方法如下：
- 就地相交在一个
std::set对象最初复制所述第一组。 那么对于后续组，它遍历自身所有的元素和第i组的集合，并根据需要从自身删除的项目。 - 使用
std::set_intersection到一个临时std::set ，内容交换到当前组，然后再找到当前组与下一组的交集，并插入到临时设置，等等。 - 手动迭代所有集合的像在1）在所有的元件，但使用一个
vector作为目标容器代替std::set 。 - 同在4，但使用
std::list ，而不是一个的vector ，怀疑一个list将提供从中间快的缺失。 - 使用哈希集（
std::unordered_set ），并检查所有组的所有项目。
事实证明，使用vector是稍快时在各集合中元素的数目少，和list是稍微较大的集更快。 就地使用set是一个显着大于两个慢，接着set_intersection和散列集。 是否有更快的算法/数据结构/技巧来实现这一目标？ 如果需要的话我可以张贴代码片段。 谢谢！
你可能会想尝试的一个推广std::set_intersection()该算法是使用迭代器对所有套组：
- 如果有任何迭代器已到达
end()及其相应的一套，你做。 因此，可以认为，所有的迭代器都是有效的。 - 以作为下一个候选值第一个迭代器的值
x 。 - 通过迭代器和列表中移动
std::find_if()的第一个元素至少大如x 。 - 如果该值大于
x使其成为新的候选值和迭代器的序列中再次搜索。 - 如果所有的迭代器是价值
x你找到交集的元素：记录它，增加所有迭代器，重新开始。
夜是一个很好的顾问，我想我可能有一个想法;）
- 内存比CPU这些天慢得多，如果在L1高速缓存中没有什么大不了的所有数据适合，但它很容易波及到L2或L3：5台1000元的已经是5000元，这意味着5000个节点，和一组节点包含至少3个指针+的对象（即，一个32位机器上的至少16个字节和32个字节的64位机器上）=>这是至少80K存储器，以及最近的CPU只有32K为L1D所以我们已经溢出到L2
- 以前的事实是，设置节点可能分散在各地的内存，而不是紧紧地挤在一起，这意味着高速缓存行的一部分充满了完全无关的东西的问题加剧。 通过提供密切保持对每个人节点分配器这可以缓解。
- 这是进一步的事实，CPU是在连续的要好得多混合读取（在你需要它才可以预取存储器，所以你不要等待它），而不是随机读取（和树结构不幸导致相当随机读取）
这就是为什么无论哪里的速度，一个vector （或者一个deque ）是如此之大的结构：他们发挥得很好，记忆。 因此，我肯定会推荐使用vector作为我们的中间结构; 从肢体虽然护理需要采取永远只能插入/删除，以避免搬迁。
于是，我想到了一个比较简单的方法：
#include <cassert>
#include <algorithm>
#include <set>
#include <vector>
// Do not call this method if you have a single set...
// And the pointers better not be null either!
std::vector<int> intersect(std::vector< std::set<int> const* > const& sets) {
for (auto s: sets) { assert(s && "I said no null pointer"); }
std::vector<int> result; // only return this one, for NRVO to kick in
// 0. Check obvious cases
if (sets.empty()) { return result; }
if (sets.size() == 1) {
result.assign(sets.front()->begin(), sets.front()->end());
return result;
}
// 1. Merge first two sets in the result
std::set_intersection(sets[0]->begin(), sets[0]->end(),
sets[1]->begin(), sets[1]->end(),
std::back_inserter(result));
if (sets.size() == 2) { return result; }
// 2. Merge consecutive sets with result into buffer, then swap them around
// so that the "result" is always in result at the end of the loop.
std::vector<int> buffer; // outside the loop so that we reuse its memory
for (size_t i = 2; i < sets.size(); ++i) {
buffer.clear();
std::set_intersection(result.begin(), result.end(),
sets[i]->begin(), sets[i]->end(),
std::back_inserter(buffer));
swap(result, buffer);
}
return result;
}
它似乎正确 ，我也不能保证它的速度虽然明显。
