c++ - 从2个向量中提取元素？

Question

我有 2 个向量，其中一个具有 vec1{e1,e2,e3,e4}，另一个具有 vec2 {e2,e4,e5,e7}

如何有效地从上述向量中获取三个向量，以使 1.具有仅在 vec1 中可用的元素，类似地 2 仅具有 vec2 元素和 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());

如果它们没有排序，你当然可以先排序，或者你可以遍历 vec1，对于每个元素，使用 std::find 来查看它是否存在于 vec2 中。

Answer 2

您要的是其他两者vec3的交集。Jalf 演示了如何vec3使用header中的std::set_intersection函数进行填充。但请记住，要使 set 函数起作用，向量必须是 sorted。<algorithm>

那么你想要vec1和被自己和vec2被区别vec3。在集合符号中：

vec1 := vec1 \ vec3;
vec2 := 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;

Answer 3

如果元素数量较少，您可以使用易于实现且运行时间为 O(n ^{2 ) 的简单方法。}

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

Answer 4

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

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

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