c++algorithmstlcomm

C++ STL alogrithm like 'comm' utility


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'.


Solution

  • 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,