Re: How to use set_union algorithm?

From: Buster (noone_at_nowhere.com)
Date: 11/04/03


Date: Tue, 4 Nov 2003 01:06:43 -0000


"Evan" <eed132@psu.edu> wrote in message
news:3f25c666.0311031514.31878364@posting.google.com...
> "John Ericson" <jericwahabison@pacbell.net> wrote in message
news:<7cupb.907$1b4.648@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.