Can someone point me, please, if where is some algorithms within STL to compute difference and intersection per one call in manner of unix comm utility?
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
}
My current implementation uses 2 calls of 'std::set_difference' and one call of 'std::set_intersection'.
I think this is probably a reasonably efficient implementation:
Features:
a) operates in linear time.
b) works with all ordered container types for input and all iterator types for output.
c) only requires operator<
to be defined on the contained type, as per stl algorithms on sorted ranges.
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++;
}
example:
#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;
}
example output (note that the 'both' target is an unordered set):
1, 2,
5, 3, 4,
6, 7,