STL集合的交集及其输出

Question

我有一段代码片段，需要在VC++ 2010下编译。

        std::set<int> s1;
        std::set<int> s2;
        std::set<int> res_set;
        std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), res_set.begin());

据我所知，这应该可以工作。然而，我遇到了构建错误：

c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(4494): error C3892: 'std::_Tree_const_iterator<_Mytree>::operator *' : you cannot assign to a variable that is const
1>          with
1>          [
1>              _Mytree=std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(4522) : see reference to function template instantiation '_OutIt std::_Set_intersection<_InIt1,_InIt2,_OutIt>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt)' being compiled
1>          with
1>          [
1>              _OutIt=std::_Tree_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>,
1>              _InIt1=std::_Tree_unchecked_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>,
1>              _InIt2=std::_Tree_unchecked_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>
1>          ]
1>          c:\program files (x86)\microsoft visual studio 10.0\vc\include\algorithm(4549) : see reference to function template instantiation '_OutIt std::_Set_intersection1<std::_Tree_unchecked_const_iterator<_Mytree>,std::_Tree_unchecked_const_iterator<_Mytree>,_OutIt>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt,std::tr1::true_type)' being compiled
1>          with
1>          [
1>              _OutIt=std::_Tree_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>,
1>              _Mytree=std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>,
1>              _InIt1=std::_Tree_unchecked_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>,
1>              _InIt2=std::_Tree_unchecked_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>
1>          ]
1>          c:\p4r\pkrcode\depot\dev\stats\poker\protype\statserver\achievementmanager.cpp(175) : see reference to function template instantiation '_OutIt std::set_intersection<std::_Tree_const_iterator<_Mytree>,std::_Tree_const_iterator<_Mytree>,std::_Tree_const_iterator<_Mytree>>(_InIt1,_InIt1,_InIt2,_InIt2,_OutIt)' being compiled
1>          with
1>          [
1>              _OutIt=std::_Tree_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>,
1>              _Mytree=std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>,
1>              _InIt1=std::_Tree_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>,
1>              _InIt2=std::_Tree_const_iterator<std::_Tree_val<std::_Tset_traits<int,std::less<int>,std::allocator<int>,false>>>
1>          ]

为了方便起见，我进行了显式的模板参数声明：

std::set_intersection<std::set<int>::const_iterator, std::set<int>::const_iterator, std::set<int>::iterator>(
  s1.begin(), s1.end(), s2.begin(), s2.end(), res_set.begin()
);

但是我遇到了相同的错误。我的问题在于，在第二种情况下，如果我传递一个const_iterator，它应该会因为参数类型不匹配而失败，即const_iterator和iterator之间的转换错误。我在这里错过了什么？（我知道关于set_intersection的“插入器”形式，但我想学习我在这里做错了什么）

- progician

Answer 1

    std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), res_set.begin());

最后一个参数应该是一个输出迭代器。在您的情况下，它不是输出迭代器，更甚者，它是不可变的（因为std::set具有不可变元素）。您应该使用insert_iterator来替代：

    std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), std::inserter(res_set, res_set.end()));

- jpalecek

Answer 2

res_set.begin()不能作为set_intersection的输出参数，有两个原因：

• 集合为空，这将尝试覆盖集合中现有元素
• 无法修改集合的元素。

相反，您需要一个insert_iterator，将新元素插入到集合中：

std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), 
                      std::inserter(res_set, res_set.end()))

- Mike Seymour

Answer 3

std::set_intersection 的输出参数必须是可变的 value_type。由于更改元素的值可能会改变其所属的位置，std::set 的迭代器不支持变异。带有 std::set_iterator 的函数旨在处理排序序列，例如 std::vector。

在您的情况下，您可以用需要的方式替换您的 std::set，将它们排序（并可能使用 std::lower_bound 和插入来保持它们的排序面对插入），或者使用 std::insert_iterator( res_set, res_set.end() )。

- James Kanze

---

记录一下，我曾经认为两个集合的交集必须具有平凡形式。我有点惊讶默认情况下没有处理集合的交集方法。要么我错过了什么，要么这是STL的缺陷。 - progician

James，集合函数旨在与排序向量一样用于集合。仅仅将集合更改为向量并不能解决任何问题。问题在于最终参数，它无法被写入。插入迭代器可以为集合或向量解决这个问题。 - Rob Kennedy

在数学意义上，std::set并不是真正的集合。或者至少它只是部分集合。通常，在计算机科学中，集合仅仅是一个无序的不包含重复元素并具有更快查询能力的集合而已。std::set添加了顺序，但其他方面保持着这种定义。(Pascal确实在数学意义上有所谓的集合，但是它们被限制在小整数范围内。更像是std::bitset)。 - James Kanze

@RobKennedy 这是一个额外的问题：使用 std::vector，你可以编写类似于 res_set.resize( s1.size() + s2.size() ); res_set.erase( std::set_intersection( s1.begin(), s1.end(), s2.begin(), s2.end(), res_set.begin() ), res_set.end() ) 的代码。无论如何，对于 s1 和 s2 的限制只是数据必须排序：使用 std::set 是实现这一点的一种方法（通常也是最简单和最好的方法），但不是唯一的方法。 - James Kanze