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>::it erator f1 = set1.begin();
set<string>::it erator f2 = set2.begin();
set<string>::it erator 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]

Re: How to use set_union algorithm?

"Tong Wang" <wangtong@seas. upenn.edu> wrote in message
news:bo5ojj$4l9 3$1@netnews.upe nn.edu...[color=blue]
> 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[/color]
the result back[color=blue]
> into set1, how can I do this?
>
> I tried to use the set_union algorithm in the following[/color]
way, but it didn't[color=blue]
> work for me:
>
> set<string>::it erator f1 = set1.begin();
> set<string>::it erator f2 = set2.begin();
> set<string>::it erator o1 = set1.begin();
> set_union(f1, set1.end(), f2, set2.end(), o1);
>
> Can somebody tell me what's wrong with this? Thanks a lot.
>
>[/color]

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

[Victor Bazarov]

Re: How to use set_union algorithm?

"Tong Wang" <wangtong@seas. upenn.edu> wrote...[color=blue]
> 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>::it erator f1 = set1.begin();
> set<string>::it erator f2 = set2.begin();
> set<string>::it erator o1 = set1.begin();
> set_union(f1, set1.end(), f2, set2.end(), o1);
>
> Can somebody tell me what's wrong with this? Thanks a lot.[/color]

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]

Re: How to use set_union algorithm?

Hi Victor,
"Victor Bazarov" <v.Abazarov@com Acast.net> wrote in message
news:cdupb.9499 7$Tr4.257267@at tbi_s03...
....
| 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
--

http://ivan.vecerina.com

[chris]

Re: How to use set_union algorithm?

Tong Wang wrote:
[color=blue]
> 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>::it erator f1 = set1.begin();
> set<string>::it erator f2 = set2.begin();
> set<string>::it erator o1 = set1.begin();
> set_union(f1, set1.end(), f2, set2.end(), o1);
>
> Can somebody tell me what's wrong with this? Thanks a lot.
>
>[/color]

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]

Re: How to use set_union algorithm?

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_i terator<std::st ring, const std::string&, const
std::string*>,
_InputIter2 = std::_Rb_tree_i terator<std::st ring, const std::string&,
const
std::string*>, _OutputIter = std::_Rb_tree_i terator<std::st ring, 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_str ing<_CharT,
_Traits, _Alloc>& std::basic_stri ng<_CharT, _Traits,
_Alloc>::operat or=(const std::basic_stri ng<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_trait s<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_str ing<_CharT,
_Traits, _Alloc>& std::basic_stri ng<_CharT, _Traits,
_Alloc>::operat or=(const std::basic_stri ng<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_trait s<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_str ing<_CharT,
_Traits, _Alloc>& std::basic_stri ng<_CharT, _Traits,
_Alloc>::operat or=(const std::basic_stri ng<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_trait s<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(_In putIter, _InputIter, _OutputIter,
std::input_iter ator_tag) [with _InputIter =
std::_Rb_tree_i terator<std::st ring, const std::string&, const
std::string*>,
_OutputIter = std::_Rb_tree_i terator<std::st ring, 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_aux 2(_InputIter,
_InputIter, _OutputIter, __false_type) [with _InputIter =
std::_Rb_tree_i terator<std::st ring, const std::string&, const std::string*>,
_OutputIter = std::_Rb_tree_i terator<std::st ring, 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_i terator<std::st ring, const std::string&, const std::string*>,
_OutputIter = std::_Rb_tree_i terator<std::st ring, 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_i terator<std::st ring, const std::string&, const std::string*>,
_OutputIter = std::_Rb_tree_i terator<std::st ring, 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(_Inpu tIter, _InputIter,
_OutputIter) [with _InputIter = std::_Rb_tree_i terator<std::st ring, const
std::string&, const std::string*>, _OutputIter =
std::_Rb_tree_i terator<std::st ring, 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_i terator<std::st ring, const std::string&, const std::string*>,
_InputIter2 = std::_Rb_tree_i terator<std::st ring, const std::string&, const
std::string*>, _OutputIter = std::_Rb_tree_i terator<std::st ring, 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_str ing<_CharT,
_Traits, _Alloc>& std::basic_stri ng<_CharT, _Traits,
_Alloc>::operat or=(const std::basic_stri ng<_CharT, _Traits, _Alloc>&)
[with
_CharT = char, _Traits = std::char_trait s<char>, _Alloc =
std::allocator< char>]' discards qualifiers
make: *** [test_set.o] Error 1



"Victor Bazarov" <v.Abazarov@com Acast.net> wrote in message
news:cdupb.9499 7$Tr4.257267@at tbi_s03...[color=blue]
> "Tong Wang" <wangtong@seas. upenn.edu> wrote...[color=green]
> > 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[/color][/color]
back[color=blue][color=green]
> > into set1, how can I do this?
> >
> > I tried to use the set_union algorithm in the following way, but it[/color][/color]
didn't[color=blue][color=green]
> > work for me:
> >
> > set<string>::it erator f1 = set1.begin();
> > set<string>::it erator f2 = set2.begin();
> > set<string>::it erator o1 = set1.begin();
> > set_union(f1, set1.end(), f2, set2.end(), o1);
> >
> > Can somebody tell me what's wrong with this? Thanks a lot.[/color]
>
> 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
>
>[/color]

[Tong Wang]

Re: How to use set_union algorithm?

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

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


"Ivan Vecerina" <NONE_use_form@ website_to_cont act_me> wrote in message
news:3fa676d4@n ews.swissonline .ch...[color=blue]
> Hi Victor,
> "Victor Bazarov" <v.Abazarov@com Acast.net> wrote in message
> news:cdupb.9499 7$Tr4.257267@at tbi_s03...
> ...
> | 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
> --
> http://ivan.vecerina.com
>
>[/color]

[Evan]

Re: How to use set_union algorithm?

"John Ericson" <jericwahabison @pacbell.net> wrote in message news:<7cupb.907 $1b4.648@newssv r25.news.prodig y.com>...[color=blue]
> How about set1.insert(set 2.begin(), set2.end()); ? For
> set_union, the destination range shouldn't overlap either of
> the source ranges.[/color]

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]

Re: How to use set_union algorithm?


"Evan" <eed132@psu.edu > wrote in message
news:3f25c666.0 311031514.31878 364@posting.goo gle.com...[color=blue]
> "John Ericson" <jericwahabison @pacbell.net> wrote in message[/color]
news:<7cupb.907 $1b4.648@newssv r25.news.prodig y.com>...[color=blue][color=green]
> > How about set1.insert(set 2.begin(), set2.end()); ? For
> > set_union, the destination range shouldn't overlap either of
> > the source ranges.[/color]
>
> I'd be worried about efficiency. Does anyone know how set_union is
> typically implemented?[/color]

The typical implementer knows. Seriously, though, the complexity is
specified in the standard, 23.3.5.2 para 4.
[color=blue]
> 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,[/color]

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).
[color=blue]
> 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.[/color]

It has a very good index.

Regards,
Buster.