STL set intersection and the output

Question

I have a code snippet like this, to be compiled under 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());

As far as I can tell, this supposed to work. However, I get build errors:

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>          ]

For the sake of it, I made explicit template parameter declaration:

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

But I have the same errors. My problem here is that in the second case, if I would pass a const_iterator, it should fail with a conversion error between const_iterator and iterator as the parameter type would not match. What do I missing here? (I know about the "inserter" form of set_intersection but I want to learn what do I do wrong here)

Answer 1

The output argument to a std::set_intersection must be to a mutable value_type. The iterators of std::set never support mutation, since changing the value of an element could change where it belonged in the set. Functions in the group with std::set_iterator are designed to work on sorted sequences, e.g. std::vector.

In your case, you can either replace your std::set with std::vector, sorting them as needed (and possibly using std::lower_bound and insertion to keep them sorted in face of insertion), or use std::insert_iterator( res_set, res_set.end() ).

Answer 2

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

The last parameter should be an output iterator. In your case, it is not, even more, it is immutable (bc. std::set has immutable elements). You should use an insert_iterator instead:

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

Answer 3

res_set.begin() can't be used as the output argument of set_intersection for two reasons:

• The set is empty, and this would try to overwrite existing elements of the set
• You can't modify elements of a set.

Instead, you want an insert_iterator, to insert the new elements into the set:

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