c++ - 使用 for 循环并查找而不是 set_intersection？

Question

This question建议使用 std::set_intersection 来查找两个数组的交集。使用 std::find 不是同样有效吗？

int a[5] = {1, 2, 3, 4, 5};
int b[5] = {3, 4, 5, 6, 7};

for (int i=0; i<5; i++)
{
    if (std::find(b, b+5, a[i])!=b+5)
        std::cout << a[i] << std::endl;
}

std::set_intersection 基本上做同样的事情吗？或者它可能使用更有效的算法？如果 std::find 花费 O(n) 时间，我认为上面的复杂度是 O(n^2)。

Answer 1

对于所有(或至少几乎所有)标准库复杂性问题，a good reference可以为您解答。
特别是我们得到了 std::find执行 At most last - first applications of the predicate (在本例中为 operator<)第一个和最后一个定义要搜索的范围。
我们也得到了 std::set_intersection执行 At most 2·(N1+N2-1) comparisons, where N1 = std::distance(first1, last1) and N2 = std::distance(first2, last2) .

这意味着您的循环最多执行 N1 * N2 operator<的应用，在本例中为 25。std::set_intersection最多使用 18 个。

因此，这两种方法在给出相同答案的意义上“同样有效”，但是 std::set_intersection这样做需要更少的比较。