Почему вычитание типа не работает для моего вызова пересечения набора и набора различий?

Question

Я пытаюсь написать небольшой алгоритм, который находит общие и уникальные части двух наборов, и я хочу написать его в общем виде, поэтому у меня есть небольшой пример:

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

}

Мой вопрос заключается в том, почему эта функция не компилируется? Я пробовал gcc, clang и MSVC, и все они терпят неудачу. Сообщение об ошибке Clang можно проверить здесь:
https://godbolt.org/g/gFZyzo

Большое спасибо.

Answer 1

Причина в том, что std::set обычный итератор - тот, который вы получаете с begin() - не предназначен для вставки или удаления, только для обхода того, что находится в наборе. Попробуйте std::inserter вместо:

#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());
}

Обратите внимание, что:

1. Вы создаете множество копий диапазонов; Я не думаю, что тебе действительно нужно это делать. Просто используйте диапазоны - set_difference а также set_intersection на самом деле работают на диапазонах, а не наборы.
2. std::set по умолчанию хранятся в порядке. Нужно ли их заказывать до и после запуска этого кода? Если нет, рассмотрите другой выбор контейнеров. С другой стороны, как отмечает @nm, заказанный контейнер необходим для set_difference а также set_intersection,
3. Вы выполняете итерации по обоим наборам три раза, а не один раз (что вы сделали бы с помощью пользовательской функции для выполнения этого на заказанных контейнерах).
4. Стандарт C++ имеет собственный кортеж - std:: tuple - начиная с C++11.

Answer 2

Вы должны использовать inserter потому что итераторы set сами по себе всегда являются константными итераторами, которые не допускают изменения значения:

... ассоциативные контейнеры, в которых тип значения совпадает с типом ключа, оба iterator а также const_iterator постоянные итераторы

#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());
}