c++ - set_difference 和 set_intersection 同时进行

Question

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

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) 中, 和 result3包含 [first1,last1) 中常见的所有元素和 [first2,last2) .

set_difference 的示例实现和 set_intersection 从 cplusplus.com 看来，他们可以帮助我创建一个只执行一次扫描而不是三个扫描的高效实现。但是，如果它在标准库中，我不想重新发明轮子。

示例，按要求:

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

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

Answer 1

没有标准库算法可以在单次扫描中完成，但它很容易编写。以下内容看起来正确并且输出有意义 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;
}