тест C++, если 2 набора являются непересекающимися

Поскольку std::set - отсортированный контейнер, можно сравнить границы множества, чтобы посмотреть, могут ли они пересекаться, и если да, то выполнить дорогостоящую операцию STL.

Edit:

Here's where where clam fishing gets serious ...

All the code placed so far trying to re-implement what's already in <алгоритма>. Вот суть 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.

Можно было бы использовать set_intersection и проверить, пустой ли результирующий набор, но не знаю, намного ли быстрее.

Оптимальная реализация остановила бы тестирование и вернула бы false, как только бы был найден первый равный элемент. Готового решения для этого я не знаю, хотя

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    Set1::const_iterator it, itEnd = set1.end();
    for (it = set1.begin(); it != itEnd; ++it)
        if (set2.count(*it))
            return false;

    return true;
}

не слишком сложная и должна хорошо работать.

EDIT: Если вы хотите получить производительность O(n), используйте чуть-чуть менее компактную

template<class Set1, class Set2> 
bool is_disjoint(const Set1 &set1, const Set2 &set2)
{
    Set1::const_iterator it1 = set1.begin(), it1End = set1.end();
    if (it1 == it1End)
        return true; // first set empty => sets are disjoint

    Set2::const_iterator it2 = set2.begin(), it2End = set2.end();
    if (it2 == it2End)
        return true; // second set empty => sets are disjoint

    // first optimization: check if sets overlap (with O(1) complexity)
    Set1::const_iterator it1Last = it1End;
    if (*--it1Last < *it2)
        return true; // all elements in set1 < all elements in set2
    Set2::const_iterator it2Last = it2End;
    if (*--it2Last < *it1)
        return true; // all elements in set2 < all elements in set1

    // second optimization: begin scanning at the intersection point of the sets    
    it1 = set1.lower_bound(*it2);
    if (it1 == it1End)
        return true;
    it2 = set2.lower_bound(*it1);
    if (it2 == it2End)
        return true;

    // scan the (remaining part of the) sets (with O(n) complexity) 
    for(;;)
    {
        if (*it1 < *it2)
        {
            if (++it1 == it1End)
                return true;
        } 
        else if (*it2 < *it1)
        {
            if (++it2 == it2End)
                return true;
        }
        else
            return false;
    }
}

(модифицированная версия Graphics Noob's в дальнейшем, используя только оператор <)

Используйте std::set_intersection и проверьте, не пуст ли выходной файл. Можно сначала проверить, не перекрывается ли диапазон двух множеств (область, охватываемая начальным и конечным итераторами), но подозреваю, что set_intersection уже может это сделать.

Это все операции O(n), так же как и is_disjoint. Если O(n) недопустима, то по мере добавления/удаления элементов придется строить какое-то боковое хранилище, чтобы "отслеживать" разобщенность множеств. Здесь вы оплатите накладные расходы во время вставки (путем обновления вашей "isdisjoint" структуры для каждой модификации множества), но is_disjoint может быть реализован дешево. Это может быть или не быть хорошим компромиссом.