C++ STL 算法，如 'comm' 实用程序

Question

如果 STL 中的某些算法以 unix comm 实用程序的方式计算每次调用的差异和交集，请有人指点我吗？

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”调用。

Answer 1

我认为这可能是一个相当有效的实现:

特点:

a) 以线性时间运行。

b) 适用于输入的所有有序容器类型和输出的所有迭代器类型。

c) 只需要 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;
}  

示例输出(注意“两者”目标是一个无序集):

1, 2, 
5, 3, 4, 
6, 7,