Re: How to use set_union algorithm?

From: Buster (
Date: 11/04/03

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

"Evan" <> wrote in message
> "John Ericson" <> wrote in message
> > 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, 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.