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)

Detection

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

Tadeo

For the record, I had thought that the intersection of two sets must have a trivial form. I'm a bit surprised there's no intersection method that deals with set's by default. Either I missed something, or that is a shortcoming of the STL. – Detection

James, the set functions are designed to be used on sets just as much they are to be used on sorted vectors. Merely changing the set to a vector won't solve anything. What's wrong is just the final parameter, which can't be written to. An insert iterator fixes that for a set or a vector. – Hightest

std::set isn't really a set in the mathematical sense. Or at least, it's only partially one. In general, in computer science, a set is simple an unordered collection with no duplicates and a more or less rapid lookup. std::set adds order, but otherwise fulfills this definition. (Pascal did have sets in the mathematical sense, but they were limited to small integers. More like std::bitset.) – Tadeo

@RobKennedy That's an additional problem: with std::vector, you could write something like 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() ). Anyhow, the constraint for s1` and s2 is only that the data be sorted: using std::set is one way to achieve this (and often the simplest and the best), but not the only way. – Tadeo

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

Millihenry

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

Dislimn