Алгоритм C ++ STL как утилита ‘comm’
Может кто-нибудь указать мне, пожалуйста, где в STL какие-то алгоритмы для вычисления разности и пересечения за один вызов в виде утилиты связи unix?
int main()
{
//For example we have two sets on input
std::set<int>a = { 1 2 3 4 5 };
std::set<int>b = { 3 4 5 6 7 };
std::call_some_func(a, b, ... );
//So as result we need obtain 3 sets
//x1 = {1, 2} // present in a, but absent in b (difference)
//x2 = {3, 4, 5} // present on both sets (intersection)
//x3 = {6, 7} // present in b, but absent in a
}
Моя текущая реализация использует 2 вызова ‘std :: set_difference’ и один вызов ‘std :: set_intersection’.
Решение
Я думаю, что это, вероятно, достаточно эффективная реализация:
Особенности:
а) работает за линейное время.
б) работает со всеми упорядоченными типами контейнеров для ввода и со всеми типами итераторов для вывода.
в) требуется только operator< быть определенным для содержимого типа в соответствии с алгоритмами STL для отсортированных диапазонов.
template<class I1, class I2, class I3, class I4, class ITarget1, class ITarget2, class ITarget3>
auto comm(I1 lfirst, I2 llast, I3 rfirst, I4 rlast, ITarget1 lonly, ITarget2 both, ITarget3 ronly)
{
while (lfirst != llast and rfirst != rlast)
{
auto&& l = *lfirst;
auto&& r = *rfirst;
if (l < r) *lonly++ = *lfirst++;
else if (r < l) *ronly++ = *rfirst++;
else *both++ = (++lfirst, *rfirst++);
}
while (lfirst != llast)
*lonly++ = *lfirst++;
while (rfirst != rlast)
*ronly++ = *rfirst++;
}
пример:
#include <tuple>
#include <set>
#include <vector>
#include <unordered_set>
#include <iterator>
#include <iostream>
/// @pre l and r are ordered
template<class I1, class I2, class I3, class I4, class ITarget1, class ITarget2, class ITarget3>
auto comm(I1 lfirst, I2 llast, I3 rfirst, I4 rlast, ITarget1 lonly, ITarget2 both, ITarget3 ronly)
{
while (lfirst != llast and rfirst != rlast)
{
auto&& l = *lfirst;
auto&& r = *rfirst;
if (l < r) *lonly++ = *lfirst++;
else if (r < l) *ronly++ = *rfirst++;
else *both++ = (++lfirst, *rfirst++);
}
while (lfirst != llast)
*lonly++ = *lfirst++;
while (rfirst != rlast)
*ronly++ = *rfirst++;
}
int main()
{
//For example we have two sets on input
std::set<int>a = { 1, 2, 3, 4, 5 };
std::set<int>b = { 3, 4, 5, 6, 7 };
std::vector<int> left;
std::set<int> right;
std::unordered_set<int> both;
comm(begin(a), end(a),
begin(b), end(b),
back_inserter(left),
inserter(both, both.end()),
inserter(right, right.end()));
//So as result we need obtain 3 sets
//x1 = {1, 2} // present in a, but absent in b (difference)
//x2 = {3, 4, 5} // present on both sets (intersection)
//x3 = {6, 7} // present in b, but absent in a
std::copy(begin(left), end(left), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
std::copy(begin(both), end(both), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
std::copy(begin(right), end(right), std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl;
}
Пример вывода (обратите внимание, что цель ‘both’ — неупорядоченный набор):
1, 2,
5, 3, 4,
6, 7,
Другие решения
Для этого не существует единой функции, вам придется вызывать три упомянутые вами функции или писать что-то самостоятельно. Тем не менее, вот моя попытка, хотя я не уверен, что это будет быстрее, чем трехшаговый метод, который вы уже описали
#include <algorithm>
#include <iostream>
#include <iterator>
#include <set>
template <typename T>
void partition_sets(std::set<T> const& a,
std::set<T> const& b,
std::set<T>& difference_a,
std::set<T>& difference_b,
std::set<T>& intersection)
{
std::set_intersection(begin(a), end(a),
begin(b), end(b),
std::inserter(intersection, intersection.begin()));
std::copy_if(begin(a), end(a), std::inserter(difference_a, difference_a.begin()), [&intersection](int i)
{
return intersection.find(i) == intersection.end();
});
std::copy_if(begin(b), end(b), std::inserter(difference_b, difference_b.begin()), [&intersection](int i)
{
return intersection.find(i) == intersection.end();
});
}
Выполнение вашего примера
int main()
{
//For example we have two sets on input
std::set<int> a = { 1, 2, 3, 4, 5 };
std::set<int> b = { 3, 4, 5, 6, 7 };
std::set<int> x1;
std::set<int> x2;
std::set<int> x3;
partition_sets(a, b, x1, x2, x3);
std::cout << "a - b\n\t";
for (int i : x1)
{
std::cout << i << " ";
}
std::cout << "\n";
std::cout << "b - a\n\t";
for (int i : x2)
{
std::cout << i << " ";
}
std::cout << "\n";
std::cout << "intersection\n\t";
for (int i : x3)
{
std::cout << i << " ";
}
}
производит вывод
a - b
1 2
b - a
6 7
intersection
3 4 5
Просто напишите обертку для трех вызовов алгоритмов.
Например
#include <iostream>
#include<tuple>
#include <set>
#include <iterator>
#include <algorithm>
template <class T>
auto comm(const std::set<T> &first, const std::set<T> &second)
{
std::tuple<std::set<T>, std::set<T>, std::set<T>> t;
std::set_difference(first.begin(), first.end(),
second.begin(), second.end(),
std::inserter(std::get<0>(t), std::get<0>(t).begin()));
std::set_intersection(first.begin(), first.end(),
second.begin(), second.end(),
std::inserter(std::get<1>(t), std::get<1>(t).begin()));
std::set_difference(second.begin(), second.end(),
first.begin(), first.end(),
std::inserter(std::get<2>(t), std::get<2>(t).begin()));
return t;
}
int main()
{
std::set<int> a = { 1, 2, 3, 4, 5 };
std::set<int> b = { 3, 4, 5, 6, 7 };
auto t = comm(a, b);
for (auto x : std::get<0>(t)) std::cout << x << ' ';
std::cout << std::endl;
for (auto x : std::get<1>(t)) std::cout << x << ' ';
std::cout << std::endl;
for (auto x : std::get<2>(t)) std::cout << x << ' ';
std::cout << std::endl;
return 0;
}
Выход программы
1 2
3 4 5
6 7