473,326 Members | 2,813 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

How to use set_union algorithm?

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.
Jul 19 '05 #1
8 13826
"Tong Wang" <wa******@seas.upenn.edu> wrote in message
news:bo***********@netnews.upenn.edu...
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.
Jul 19 '05 #2
"Tong Wang" <wa******@seas.upenn.edu> wrote...
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
Jul 19 '05 #3
Hi Victor,
"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:cdupb.94997$Tr4.257267@attbi_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
Jul 19 '05 #4
Tong Wang wrote:
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

Jul 19 '05 #5
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>::operator=(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>::operator=(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>::operator=(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>::operator=(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

"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:cdupb.94997$Tr4.257267@attbi_s03...
"Tong Wang" <wa******@seas.upenn.edu> wrote...
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

Jul 19 '05 #6
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.
"Ivan Vecerina" <NONE_use_form@website_to_contact_me> wrote in message
news:3f******@news.swissonline.ch...
Hi Victor,
"Victor Bazarov" <v.********@comAcast.net> wrote in message
news:cdupb.94997$Tr4.257267@attbi_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

Jul 19 '05 #7
"John Ericson" <je************@pacbell.net> wrote in message news:<7c***************@newssvr25.news.prodigy.com >...
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.
Jul 19 '05 #8

"Evan" <ee****@psu.edu> wrote in message
news:3f**************************@posting.google.c om...
"John Ericson" <je************@pacbell.net> wrote in message news:<7c***************@newssvr25.news.prodigy.com >...
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?


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.
Jul 19 '05 #9

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
by: Jack Smith | last post by:
Hello, any help appreciated with following problem. I figured out the algorithm (I think), just having trouble proving it is optimal. Suppose we are given n tasks each of which takes 1 unit...
16
by: cody | last post by:
I have to write an algorithm with must ensure that objects are put in buckets (which are always 4 in size). The objects have two properties: A and B. It is not allowed that in a bucket are objects...
10
by: bpontius | last post by:
The GES Algorithm A Surprisingly Simple Algorithm for Parallel Pattern Matching "Partially because the best algorithms presented in the literature are difficult to understand and to implement,...
32
by: Cmorriskuerten | last post by:
HI, is this is this solution to test if a number is a prime number or not: /* * Is n a prime number? * Return TRUE (1): n is a prime number * Return FALSE (0): n is a *not* a prime number...
113
by: Bonj | last post by:
I was in need of an encryption algorithm to the following requirements: 1) Must be capable of encrypting strings to a byte array, and decyrpting back again to the same string 2) Must have the same...
4
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event...
2
by: Julio C. Hernandez Castro | last post by:
Dear all, We have just developped a new block cipher called Raiden, following a Feistel Network structure by means of genetic programming. Our intention now consists on getting as much feedback...
0
by: aruna | last post by:
hey guys i earlier had very valuable responses from you all for base64 encoding algorithm.so thank for that. so now i need your assistance to do a float encoding algorithm. you may wonder why i'm...
1
by: almurph | last post by:
Hi everyone, Concerning the Needleman-Wunsch algorithm (cf. http://en.wikipedia.org/wiki/Needleman-Wunsch_algorithm) I have noticed a possible loop. Inside the algorithm there is an...
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.