在STL中检查空交集

Question

我该如何检查两个std::set的空交集？我可以使用set_intersection，但那样会很慢，我只需要一个bool答案。

备注：std::set表示有序集合，它们是相同类型等。

- yo'

---

除非问题是“我们在STL中是否有适当的算法？”，否则请参考https://dev59.com/tHI-5IYBdhLWcg3wN1hD的副本。 - ony

Answer 1

自己编写代码有什么问题吗？

bool empty_intersection(const set<int>& x, const set<int>& y)
{
    set<int>::const_iterator i = x.begin();
    set<int>::const_iterator j = y.begin();
    while (i != x.end() && j != y.end())
    {
      if (*i == *j)
        return false;
      else if (*i < *j)
        ++i;
      else
        ++j;
    }
    return true;
}

总之应该是这样的。完全没有经过测试的代码。

- john

---

我只使用迭代器工作了两天，很高兴能够做到我所能做的。 - yo'

好的，上面的算法类似于set_intersection使用的算法，只是如果它发现有一个共同元素，它会立即返回false。显然，这依赖于集合已经排序的事实，因此如果你每次循环只增加较低值迭代器，你将找到所有的共同元素。 - john

非常感谢。我认为我能够阅读这个，但我自己无法编写这样的代码。 - yo'

您可以进行微小的更改以去除对 operator== 的要求：if(*i<*j) ++i; else if(*j<*i) ++j; else return false; - Mark Ransom