set_difference 和 set_intersection 同时进行 [英] set_difference and set_intersection simultaneously

问题描述

我想知道标准库中是否有任何工具可以同时计算两个排序范围之间的集合交集和集合差.带有以下签名的东西:

I'm wondering if there is any facility in the standard library to simultaneously compute the set intersection and set difference between two sorted ranges. Something with a signature along the lines of:

template <class Input1, class Input2, 
          class Output1, class Output2, class Output3>
Output3 decompose_sets (Input1 first1, Input1 last1,
                        Input2 first2, Input2 last2,
                        Output1 result1, Output2 result2,
                        Output3 result3 );

这样在调用 decompose sets 之后，result1 包含 [first1,last1) 中所有不在 [first2,last2), result2 包含 [first2,last2) 中所有不在 [first1,last1) 中的元素code> 和 result3 包含所有在 [first1,last1) 和 [first2,last2) 中通用的元素.

Such that after a call to decompose sets, result1 contains all the elements in [first1,last1) which are not in [first2,last2), result2 contains all the elements in [first2,last2) which are not in [first1,last1), and result3 contains all element which are common in [first1,last1) and [first2,last2).

set_difference 和 的示例实现来自 cplusplus.com 的 href="http://www.cplusplus.com/reference/algorithm/set_intersection/" rel="noreferrer">set_intersection 似乎他们可以帮助我创建一种只执行一次而不是三次扫描的高效实现.但是，如果它在标准库中，我不想重新发明轮子.

The example implementations of set_difference and set_intersection from cplusplus.com seem like they can help me to create an efficient implementation which performs only one scan instead of three. If it's in the standard library, though, I'd hate to reinvent the wheel.

示例，应要求:

给定两个集合 a={0, 1, 2, 3, 4} 和 b={2, 4, 5, 6} 那么我想构建以下三个集合:

Given two sets a={0, 1, 2, 3, 4} and b={2, 4, 5, 6} then I would like to build the following three sets:

• only_a = {0,1,3}
• only_b = {5,6}
• common = {2,4}

推荐答案

没有标准的库算法可以在一次扫描中完成，但很容易编写.以下看起来是正确的，输出是有意义的在 ideone.com 上.

There's no standard library algorithm that will do it in a single scan but it's easy to write. The following looks correct and the output makes sense here on ideone.com.

template <class Input1, class Input2,
            class Output1, class Output2, class Output3>
Output3 decompose_sets(Input1 first1, Input1 last1,
                    Input2 first2, Input2 last2,
                    Output1 result1, Output2 result2,
                    Output3 result3)
{
    while (first1 != last1 && first2 != last2) {
        if (*first1 < *first2) {
            *result1++ = *first1++;
        } else if (*first2 < *first1) {
            *result2++ = *first2++;
        } else {
            *result3++ = *first1++;
            ++first2; // skip common value in set2
        }
    }
    std::copy(first1, last1, result1);
    std::copy(first2, last2, result2);
    return result3;
}

这篇关于set_difference 和 set_intersection 同时进行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！