如果C ++测试2台是不相交 [英] c++ test if 2 sets are disjoint

问题描述

我知道STL具有 set_difference ，但我只是需要知道，如果2 设置是不相交的。我已经异形我的code，这是减缓我的程序下来不少。有一种简单的方法，如果2台是不相交的，还是我只是需要推出自己的code？

I know the STL has set_difference, but I need to just know if 2 sets are disjoint. I've profiled my code and this is slowing my app down quite a bit. Is there an easy way to see if 2 sets are disjoint, or do I need to just roll my own code?

编辑：我也尝试 set_intersection ，但它采取了同样的时间...

I also tried set_intersection but it took the same time...

推荐答案

修改hjhill的code。通过O（log n）的一个因素，以降低复杂性摆脱计数（）的调用。

Modified hjhill's code to reduce complexity by a factor of O(log n) by getting rid of the count() call.

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;
}

我已经遵守，现在测试这code所以它应该是不错的。

I've complied and tested this code now so it should be good.

这篇关于如果C ++测试2台是不相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！