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;
}

示例输出（注意 'both' 目标是一个无序集）：

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

Answer 2

没有一个函数可以做到这一点，您必须调用您提到的三个函数，或者自己编写一些东西。话虽如此，这是我的尝试，但我不确定它是否会比您已经描述的三步法更快

#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

Answer 3

只需为算法的三个调用编写一个包装器即可。

例如

#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

C++ STL 算法类似于 'comm' 实用程序

C++ STL alogrithm like 'comm' utility

c++

algorithm

stl

comm