Я знаю, что STL имеет set_difference, но мне нужно просто знать, являются ли 2 set непересекающимися. Я профилировал свой код, и это немного замедляет мое приложение. Есть ли простой способ увидеть, не установлены ли два набора, или мне нужно просто свернуть собственный код?
EDIT: я также пробовал set_intersection, но это заняло то же время...
Измененный код hjhill для уменьшения сложности с коэффициентом O (log n), избавляясь от вызова count().
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;
}
Я выполнил и протестировал этот код сейчас, чтобы он был хорошим.
Вы можете использовать set_intersection и протестировать, если результирующий набор пуст, но я не знаю, если это намного быстрее.
Оптимальная реализация остановит тестирование и return 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 далее, используя только оператор <)
Так как 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.
Можно получить O (log (n)), используя тот факт, что оба набора сортируются. Просто используйте std::lower_bound вместо перемещения итератора на один.
enum Ordering { EQ = 0, LT = -1, GT = 1 };
template <typename A, typename B>
Ordering compare(const A &a, const B &b)
{
return
a == b ? EQ :
a < b ? LT : GT;
}
template <typename SetA, typename SetB>
bool is_disjoint(const SetA &a, const SetB &b)
{
auto it_a = a.begin();
auto it_b = b.begin();
while (it_a != a.end() && it_b != b.end())
{
switch (compare(*it_a, *it_b))
{
case EQ:
return false;
case LT:
it_a = std::lower_bound(++it_a, a.end(), *it_b);
break;
case GT:
it_b = std::lower_bound(++it_b, b.end(), *it_a);
break;
}
}
return true;
}
Используйте std:: set_intersection и посмотрите, пустой ли вывод. Вы можете проверить, перекрывает ли диапазон двух наборов (область, охватываемая начальными и конечными итераторами), но я подозреваю, что set_intersection уже может это сделать.
Это все операции O (n), как is_disjoint. Если O (n) неприемлемо, вам нужно будет создать некоторое боковое хранилище, чтобы "отслеживать" непересекаемость наборов при добавлении/удалении элементов. Здесь вы будете оплачивать накладные расходы во время ввода (путем обновления вашей структуры "isdisjoint" для каждой модификации набора), но is_disjoint может быть реализовано дешево. Это может быть или не быть хорошим компромиссом.