为什么类型推导对我的集合交集和集合差异调用不起作用？

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

您需要使用 inserter，因为 set 本身的迭代器始终是不允许修改值的 const 迭代器：

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

Answer 2

原因是 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 而不是：

#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++ 标准有自己的元组 - std::tuple - 从 C++11 开始。

为什么类型推导对我的集合交集和集合差异调用不起作用？

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

c++

stdset

insert-iterator

set-operations

c++11