Why doesn't type deduction work for my set intersection and set difference invocations?

Question

I am trying to write a small algorithm that finds the common and unique parts of two sets and I want to write it in a generic fashion so I have this little example:

#include "boost/tuple/tuple.hpp"
#include <set>

template <typename InputIt, typename Value = typename std::iterator_traits<InputIt>::value_type>
boost::tuple<std::set<Value>, std::set<Value>, std::set<Value>>
findUniqueAndCommon(InputIt fbegin, InputIt fend, InputIt sbegin, InputIt send)
{
    std::set<Value> setL(fbegin, fend);
    std::set<Value> setR(sbegin, send);

    std::set<Value> uniqueInCatalog1;
    std::set<Value> uniqueInCatalog2;
    std::set<Value> commonInBoth;

    std::set_difference(setL.begin(), setL.end(), setR.begin(), setR.end(), uniqueInCatalog1.begin());
    std::set_difference(setR.begin(), setR.end(), setL.begin(), setL.end(), uniqueInCatalog2.begin());
    std::set_intersection(setL.begin(), setL.end(), setR.begin(), setR.end(), commonInBoth.begin());
    return{ uniqueInCatalog1, uniqueInCatalog2, commonInBoth };
}

int main()
{
     std::set<int> x = {1, 2, 3};
     std::set<int> y = {4, 2, 3};
     findUniqueAndCommon<std::set<int>::iterator>(x.begin(), x.end(), y.begin(), y.end());

}

My question is that why does this function fail to compile? I tried gcc, clang and MSVC and they all fail. Clang's error message can be inspected here:
https://godbolt.org/g/gFZyzo

Thanks a lot.

Answer 1

The reason is that std::set's usual iterator - the one you get with begin() - is not intended for insertion or deletion, only for traversal of what's in the set. Try an std::inserter instead:

#include "boost/tuple/tuple.hpp"
#include <set>

template <typename InputIt, typename Value = typename std::iterator_traits<InputIt>::value_type>
boost::tuple<std::set<Value>, std::set<Value>, std::set<Value>>
findUniqueAndCommon(InputIt fbegin, InputIt fend, InputIt sbegin, InputIt send)
{
    std::set<Value> setL(fbegin, fend);
    std::set<Value> setR(sbegin, send);

    std::set<Value> uniqueInCatalog1;
    std::set<Value> uniqueInCatalog2;
    std::set<Value> commonInBoth;

    std::set_difference(setL.begin(), setL.end(), setR.begin(), setR.end(), std::inserter(uniqueInCatalog1, uniqueInCatalog1.end()));
    std::set_difference(setR.begin(), setR.end(), setL.begin(), setL.end(), std::inserter(uniqueInCatalog2, uniqueInCatalog2.end()));
    std::set_intersection(setL.begin(), setL.end(), setR.begin(), setR.end(), std::inserter(commonInBoth, commonInBoth.end()));
    return{ uniqueInCatalog1, uniqueInCatalog2, commonInBoth };
}

int main()
{
     std::set<int> x = {1, 2, 3};
     std::set<int> y = {4, 2, 3};
     findUniqueAndCommon<std::set<int>::iterator>(x.begin(), x.end(), y.begin(), y.end());
}

Note, though, that:

1. You're creating set copies of ranges; I don't think you really need to do that. Just use the ranges - set_difference and set_intersection actually work on ranges rather than sets.
2. std::sets are kept in-order by default. Do you need them to be ordered before and after running this code? If not, consider a different choice of containers. On the other hand, as @n.m notes, an ordered container is necessary for set_difference and set_intersection.
3. You're iterating over both sets three times instead of just once (which you would with a custom function for doing this on ordered containers).
4. The C++ standard has had its own tuple - std::tuple - since C++11 already.

Answer 2

You need to utilize inserter because iterators of set itself are always const iterators that don't allow value modification:

... associative containers where the value type is the same as the key type, both iterator and const_iterator are constant iterators

#include <tuple>
#include <set>
#include <algorithm>
#include <iterator>

template <
    typename InputIt, 
    typename Value = typename std::iterator_traits<InputIt>::value_type>
std::tuple<std::set<Value>, std::set<Value>, std::set<Value>> findUniqueAndCommon(InputIt fbegin, InputIt fend, InputIt sbegin, InputIt send)
{
    std::set<Value> setL(fbegin, fend);
    std::set<Value> setR(sbegin, send);

    std::set<Value> uniqueInCatalog1;
    std::set<Value> uniqueInCatalog2;
    std::set<Value> commonInBoth;

    std::set_difference(setL.begin(), setL.end(), setR.begin(), setR.end(), ::std::inserter(uniqueInCatalog1, uniqueInCatalog1.end()));
    std::set_difference(setR.begin(), setR.end(), setL.begin(), setL.end(), ::std::inserter(uniqueInCatalog2), uniqueInCatalog2.end()));
    std::set_intersection(setL.begin(), setL.end(), setR.begin(), setR.end(), ::std::inserter(commonInBoth, commonInBoth.end()));
    return{ uniqueInCatalog1, uniqueInCatalog2, commonInBoth };
}

int main()
{
    std::set<int> x = {1, 2, 3};
    std::set<int> y = {4, 2, 3};
    findUniqueAndCommon<std::set<int>::iterator>(x.begin(), x.end(), y.begin(), y.end());
}