Set_difference and set_intersection at the same time

Question

I am wondering if there is any tool in the standard library to simultaneously calculate the intersection of a set and establish the difference between two sorted ranges. Something with line caption:

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

Thus, after calling decompose sets , result1 contains all the elements in [first1,last1) that are not in [first2,last2) , result2 contains all the elements in [first2,last2) that are not in [first1,last1) , and result3 contains the whole element that is common in [first1,last1) and [first2,last2) .

Implementation examples of set_difference and set_intersection from cplusplus.com, it looks like they can help me create an efficient implementation that performs only one scan instead of three. If it is in the standard library, I would not want to reinvent the wheel.

Example, on request:

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

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

Answer 1

There is no standard library algorithm that will do this in one scan, but it is easy to write. The following looks correct, and the conclusion 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() , which builds a sorted sequence of elements that are present in the first sequence but not present in the second, and those elements that are present in the second sequence are not in the first.

Answer 3

Here is another alternative using callbacks for maximum flexibility.

 template <class Input1, class Input2 , class FuncAdd, class FuncRm, class FuncSame, class Comp> void set_difference_adv(Input1 firstOld, Input1 lastOld ,Input2 firstNew, Input2 lastNew ,FuncAdd onadded, FuncRm onremoved, FuncSame onsame, Comp comp) { while (firstOld != lastOld && firstNew != lastNew) { if (comp(*firstOld, *firstNew)) { onremoved(*firstOld++); } else if (comp(*firstNew, *firstOld)) { onadded(*firstNew++); } else { onsame(*firstOld++, *firstNew++); } } std::for_each(firstOld, lastOld, onremoved); std::for_each(firstNew, lastNew, onadded); } 

This has the following advantages:

• Output Lists Now Optional
• The output may be of another type (conversion)
• Common elements can be further processed in tandem (additional comparison)

Real World Example:

 int main() { using File = std::pair<std::string, int>; std::vector<File> files1{{"file1", 12}, {"file3", 8}, {"file4", 2}, {"file5", 10}}; std::vector<File> files2{{"file1", 12}, {"file2", 5}, {"file3", 8}, {"file4", 33}}; const auto less = [](const auto& o, const auto& n) { return o.first < n.first; }; std::vector<std::string> addedNames; std::vector<File> changedFiles; set_difference_adv(std::cbegin(files1), std::cend(files1) ,std::cbegin(files2), std::cend(files2) , [&addedNames](const auto& val){ addedNames.push_back(val.first); } //< added (transform) , [](const auto& val) {} //< removed (ignore) , [&changedFiles](const auto& o, const auto& n){ if(n.second > o.second) changedFiles.push_back(n); } //< "same" (further compare) , less ); }