从2个向量中提取元素？

Question

我有与一种具有VEC1 {E1，E2，E3，E4}，而另一个与VEC2 {E2，E4，E5，E7}

2矢量如何有效地获得从上述载体使得三个矢量1.has元素，只有在VEC 1可用类似的2只VEC 2单元和3，具有共同的元素

Answer 1

std::set_intersection应该做的伎俩，如果两个向量进行排序： http://msdn.microsoft.com/en-us/library/zfd331yx.aspx

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3)); 

自定义谓词也可用于比较：

std::set_intersection(vec1.begin(), vec1.end(), vec2.begin(), vec2.end(), std::back_inserter(vec3), my_equal_functor()); 

如果它们没有排序，你当然可以先对它们进行排序，或者您可以通过迭代VEC 1，对于每个元素，使用std ::发现，看它是否在VEC 2存在。

Answer 2

如果元素数量很少，则可以使用易于实现且具有O（n ）运行时间的朴素方法。

如果您有大量元素，您可以从其中一个构建哈希表并查找其中的其他向量元素。或者，您可以对其中的一个进行排序并通过二进制搜索。

Answer 3

您描述的问题是矢量交集。这取决于输入向量的大小。

如果两个向量的大小彼此接近，则合并（如合并排序）是最好的。如果一个矢量比另一个小得多，则执行以下操作：对于较小矢量的每个元素，使用二分搜索在较大矢量中搜索该元素。

这是信息检索中的一个常见问题，您必须与倒排索引相交。有一些关于此的研究论文。

Answer 4

你要求的是vec3是十字路口其他两个。 Jalf演示了如何使用the <algorithm> header的std::set_intersection函数填充vec3。但请记住，要使所设置的功能正常工作，必须对向量进行排序。

那么你一定要vec1和vec2是自己和vec3之间的差异。在一套符号：

您可以使用该功能std::set_difference，但你不能用它来修改向量的地方。你必须计算另一个向量以保持差异：

std::vector<foo> temp; 
std::set_difference(vec1.begin(), vec1.end(), 
        vec3.begin(), vec3.end(), 
        std::back_inserter(temp)); 
vec1 = temp; 
temp.clear(); 
std::set_difference(vec2.begin(), vec2.end(), 
        vec3.begin(), vec3.end(), 
        std::back_inserter(temp)); 
vec2 = temp;