set_difference and set_intersection simultaneously

Question

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

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).

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.

Example, by request:

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}

Answer 1

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

Answer 2

There is no such function in STL, but there is set_symmetric_difference() that constructs a sorted sequence of the elements that are present in the first sequence but not present in the second, and those elements present in the second sequence are not present in the first.