c++测试2组是否不相交

我知道 STL 有 set_difference ，但我只需要知道 2 set 是否不相交。我已经分析了我的代码，这大大降低了我的应用程序的速度。有没有一种简单的方法可以查看 2 个集合是否不相交，或者我是否需要滚动自己的代码？

编辑:我也试过 set_intersection 但花了同样的时间......

最佳答案

修改了 hjhill 的代码，通过去掉 count() 调用将复杂性降低了 O(log n) 倍。

template<class Set1, class Set2>
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    if(set1.empty() || set2.empty()) return true;

    typename Set1::const_iterator
        it1 = set1.begin(),
        it1End = set1.end();
    typename Set2::const_iterator
        it2 = set2.begin(),
        it2End = set2.end();

    if(*it1 > *set2.rbegin() || *it2 > *set1.rbegin()) return true;

    while(it1 != it1End && it2 != it2End)
    {
        if(*it1 == *it2) return false;
        if(*it1 < *it2) { it1++; }
        else { it2++; }
    }

    return true;
}

我现在已经编译并测试了这段代码，所以它应该很好。

关于c++测试2组是否不相交，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/1964150/