How to use set_union algorithm?

[Tong Wang]

Suppose I have two sets of strings:
set<string> set1;
set<string> set2;

And I want to compute the union of set1 and set2 and store the result back
into set1, how can I do this?

I tried to use the set_union algorithm in the following way, but it didn't
work for me:

set<string>::iterator f1 = set1.begin();
set<string>::iterator f2 = set2.begin();
set<string>::iterator o1 = set1.begin();
set_union(f1, set1.end(), f2, set2.end(), o1);

Can somebody tell me what's wrong with this? Thanks a lot.

 

[John Ericson]

Suppose I have two sets of strings:
set<string> set1;
set<string> set2;

And I want to compute the union of set1 and set2 and store the result back
into set1, how can I do this?

I tried to use the set_union algorithm in the following way, but it didn't
work for me:

set<string>::iterator f1 = set1.begin();
set<string>::iterator f2 = set2.begin();
set<string>::iterator o1 = set1.begin();
set_union(f1, set1.end(), f2, set2.end(), o1);

Can somebody tell me what's wrong with this? Thanks a lot.

How about set1.insert(set2.begin(), set2.end()); ? For
set_union, the destination range shouldn't overlap either of
the source ranges.

 

[Victor Bazarov]

Suppose I have two sets of strings:
set<string> set1;
set<string> set2;

And I want to compute the union of set1 and set2 and store the result back
into set1, how can I do this?

I tried to use the set_union algorithm in the following way, but it didn't
work for me:

set<string>::iterator f1 = set1.begin();
set<string>::iterator f2 = set2.begin();
set<string>::iterator o1 = set1.begin();
set_union(f1, set1.end(), f2, set2.end(), o1);

Can somebody tell me what's wrong with this? Thanks a lot.

Putting the result into one of the original sets has to be a separate
operation. 'set_union' has a requirement that the resulting range
shall not overlap with either of the original ranges. Try

set<string> newset;
set_union(set1.begin(), set1.end(),
set2.begin(), set2.end(),
newset.begin());
swap(set1, newset);

Victor

 

[Ivan Vecerina]

Hi Victor,
....
| Putting the result into one of the original sets has to be a separate
| operation. 'set_union' has a requirement that the resulting range
| shall not overlap with either of the original ranges. Try
|
| set<string> newset;
| set_union(set1.begin(), set1.end(),
| set2.begin(), set2.end(),
| newset.begin());
I'm afraid this will not work -- even if newset was resized
to accomodate the output, couldn't legally be overwritten this way.
The following might work, though:
set_union( set1.begin(), set1.end(),
set2.begin(), set2.end(),
inserter( newset.begin() ) );

| swap(set1, newset);

As John pointed out, though, using the insert member function of
std::set is likely to be a more efficient approach:
set1.insert( set2.begin(), set2.end() );


Regards,
Ivan

 

[chris]

Suppose I have two sets of strings:
set<string> set1;
set<string> set2;

And I want to compute the union of set1 and set2 and store the result back
into set1, how can I do this?

I tried to use the set_union algorithm in the following way, but it didn't
work for me:

set<string>::iterator f1 = set1.begin();
set<string>::iterator f2 = set2.begin();
set<string>::iterator o1 = set1.begin();
set_union(f1, set1.end(), f2, set2.end(), o1);

Can somebody tell me what's wrong with this? Thanks a lot.

You are overwriting / adding (I'm not sure which one as I'm not familar
with set_union) to set1 as you perform the union.

You will have to create a third set set3, write the union to set3, then
put it back in set1 I'm afraid. Note set (along with most things in the
STL) has a "swap" member function which swaps the contents of two sets,
and should do it quickly and efficently, so after you've assigned to
set3, you can do set1.swap(set3) to get the contents into set1 and this
operation should be very quick.

Chris

 

[Tong Wang]

Hi, there

Thanks for the help. I tried it in the way you suggested, but got all the
following errors (I am using gcc 3.3):

/mnt/eniac/home3/c/cis570/install/gcc-3.3/bin/g++ -c test_set.cc
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algo.h:
In
function `_OutputIter std::set_union(_InputIter1, _InputIter1,
_InputIter2,
_InputIter2, _OutputIter) [with _InputIter1 =
std::_Rb_tree_iterator<std::string, const std::string&, const
std::string*>,
_InputIter2 = std::_Rb_tree_iterator<std::string, const std::string&,
const
std::string*>, _OutputIter = std::_Rb_tree_iterator<std::string, const
std::string&, const std::string*>]':
test_set.cc:43: instantiated from here
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algo.h:
3667: error: passing
`const std::string' as `this' argument of `std::basic_string<_CharT,
_Traits, _Alloc>& std::basic_string<_CharT, _Traits,
_Alloc>:perator=(const std::basic_string<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]' discards qualifiers
test_set.cc:43: instantiated from here
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algo.h:
3671: error: passing
`const std::string' as `this' argument of `std::basic_string<_CharT,
_Traits, _Alloc>& std::basic_string<_CharT, _Traits,
_Alloc>:perator=(const std::basic_string<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]' discards qualifiers
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algo.h:
3675: error: passing
`const std::string' as `this' argument of `std::basic_string<_CharT,
_Traits, _Alloc>& std::basic_string<_CharT, _Traits,
_Alloc>:perator=(const std::basic_string<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]' discards qualifiers
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algobas
e.h: In
function `_OutputIter std::__copy(_InputIter, _InputIter, _OutputIter,
std::input_iterator_tag) [with _InputIter =
std::_Rb_tree_iterator<std::string, const std::string&, const
std::string*>,
_OutputIter = std::_Rb_tree_iterator<std::string, const std::string&,
const
std::string*>]':
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algobas
e.h:260: instantiated from `_OutputIter std::__copy_aux2(_InputIter,
_InputIter, _OutputIter, __false_type) [with _InputIter =
std::_Rb_tree_iterator<std::string, const std::string&, const std::string*>,
_OutputIter = std::_Rb_tree_iterator<std::string, const std::string&, const
std::string*>]'
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algobas
e.h:303: instantiated from `_OutputIter std::__copy_ni2(_InputIter,
_InputIter, _OutputIter, __false_type) [with _InputIter =
std::_Rb_tree_iterator<std::string, const std::string&, const std::string*>,
_OutputIter = std::_Rb_tree_iterator<std::string, const std::string&, const
std::string*>]'
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algobas
e.h:323: instantiated from `_OutputIter std::__copy_ni1(_InputIter,
_InputIter, _OutputIter, __false_type) [with _InputIter =
std::_Rb_tree_iterator<std::string, const std::string&, const std::string*>,
_OutputIter = std::_Rb_tree_iterator<std::string, const std::string&, const
std::string*>]'
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algobas
e.h:349: instantiated from `_OutputIter std::copy(_InputIter, _InputIter,
_OutputIter) [with _InputIter = std::_Rb_tree_iterator<std::string, const
std::string&, const std::string*>, _OutputIter =
std::_Rb_tree_iterator<std::string, const std::string&, const
std::string*>]'
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algo.h:
3681: instantiated from `_OutputIter std::set_union(_InputIter1,
_InputIter1, _InputIter2, _InputIter2, _OutputIter) [with _InputIter1 =
std::_Rb_tree_iterator<std::string, const std::string&, const std::string*>,
_InputIter2 = std::_Rb_tree_iterator<std::string, const std::string&, const
std::string*>, _OutputIter = std::_Rb_tree_iterator<std::string, const
std::string&, const std::string*>]'
test_set.cc:43: instantiated from here
/mnt/eniac/home3/c/cis570/install/gcc-3.3/include/c++/3.3.1/bits/stl_algobas
e.h:228: error: passing
`const std::string' as `this' argument of `std::basic_string<_CharT,
_Traits, _Alloc>& std::basic_string<_CharT, _Traits,
_Alloc>:perator=(const std::basic_string<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_traits<char>, _Alloc =
std::allocator<char>]' discards qualifiers
make: *** [test_set.o] Error 1

 

[Tong Wang]

It is the INSERTER that I need to add to make it work. The exact syntax is
"inserter(newset, newset.begin())". Thanks, Ivan.

I need these algorithm functions because I need to perform other set
operations, like set difference.

 

[Evan]

How about set1.insert(set2.begin(), set2.end()); ? For
set_union, the destination range shouldn't overlap either of
the source ranges.

I'd be worried about efficiency. Does anyone know how set_union is
typically implemented? Repeatedly inserting probably has to search
through the set to find the insertion place for each element even if
it doesn't need to be added, while I suspect set_union makes sure that
it won't be a duplicate before actually inserting. I could be wrong
though. And there's almost certainly nothing mandidated by the
standard regarding this.

 

[Buster]

"John Ericson" <[email protected]> wrote in message

I'd be worried about efficiency. Does anyone know how set_union is
typically implemented?

The typical implementer knows. Seriously, though, the complexity is
specified in the standard, 23.3.5.2 para 4.

Repeatedly inserting probably has to search
through the set to find the insertion place for each element even if
it doesn't need to be added,

But the version of the insert member function above has the
same complexity if, for example, both maps use the same
comparison function (23.1.2, Table 69).

while I suspect set_union makes sure that
it won't be a duplicate before actually inserting. I could be wrong
though. And there's almost certainly nothing mandidated by the
standard regarding this.

It has a very good index.

Regards,
Buster.