Re: How to use set_union algorithm?
From: Buster (noone_at_nowhere.com)
Date: Tue, 4 Nov 2003 01:06:43 -0000
"Evan" <firstname.lastname@example.org> wrote in message
> "John Ericson" <email@example.com> 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, 188.8.131.52 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.