c ++测试如果2组是不相交的

Question

我知道STL有set_difference,但我需要知道2 sets是否是不相交的.我已经分析了我的代码,这使我的应用程序放慢了很多.有没有一种简单的方法可以看出2套是不相交的,还是我只需要自己编写代码？

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

Answer 1

修改了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;
}

我现在已经编译并测试了这段代码,所以它应该是好的.

Answer 2

由于std::set是一个已排序的容器，您可以比较设置的边界以查看它们是否可能相交，如果相交，则执行昂贵的 STL 操作。

编辑：

在这里，蛤蜊捕鱼变得严肃起来......

到目前为止发布的所有代码都试图重新实现 <algorithm> 中已经存在的内容。以下是要点set_intersection：

  template<typename _InputIterator1, typename _InputIterator2,
           typename _OutputIterator>
    _OutputIterator
    set_intersection(_InputIterator1 __first1, _InputIterator1 __last1,
                     _InputIterator2 __first2, _InputIterator2 __last2,
                     _OutputIterator __result)
    {
      while (__first1 != __last1 && __first2 != __last2)
        if (*__first1 < *__first2)
          ++__first1;
        else if (*__first2 < *__first1)
          ++__first2;
        else
          {
            *__result = *__first1;
            ++__first1;
            ++__first2;
            ++__result;
          }
      return __result;
    }

除了分配给输出迭代器之外，已经非常优化了，这对于查找两个集合是否联合的事实是不必要的。这可用于翻转标志，如下所示：

  /// fake insert container
  template <typename T> struct intersect_flag
  {       
    typedef int iterator;
    typedef typename T::const_reference const_reference;

    bool flag_; // tells whether given sets intersect

    intersect_flag() : flag_( false ) {}

    iterator insert( iterator, const_reference )
    {       
      flag_ = true; return 0;
    }
  };

  // ...
  typedef std::set<std::string> my_set;

  my_set s0, s1;
  intersect_flag<my_set> intf;

  // ...        
  std::set_intersection( s0.begin(), s0.end(),
    s1.begin(), s1.end(), std::inserter( intf, 0 ));

  if ( intf.flag_ ) // sets intersect
  {
    // ...

这避免了从原始集合中复制对象，并允许您重用 STL 算法。