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

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

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

1

c++c++11 insert-iterator set-operations stdset

Решение

Другие решения

Вы должны использовать 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());
}

2

Источник

Accepted Answer

Причина в том, что 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());
}

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

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

2