C++ STL alogrithm like'comm'utility

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'调用和1次'std :: set_intersection'调用。

Answer 1

我觉得这可能是一个合理有效的实现：

特点：

一）以线性时间运行。

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, 

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