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.

Relevant Pages

  • Re: A C++ Whishlist
    ... > not a reasonable thing to expect from the standard library. ... of the ECMA Script standard you will learn that complexity doesn't stop ... > The simple separation of interface and implementation that header files ...
    (comp.lang.cpp)
  • Re: Remove items from list while enumerating
    ... The runtime complexity would be the same as if you just ... I meant recreating it omitting the removed items. ... insertion point you may have to spend about the same as to perform an ... then the number of resizing operations would be log-base-2. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: Forth and Co - The Return of the Jedi
    ... complexity" of the ANSI standard is rarely visible to users, ... If someone has a problem with that and wants to use Standard Forth, ... Every one of the special compiler words has the ... And then you have one language and not two. ...
    (comp.lang.forth)
  • Re: Forth and Co - The Return of the Jedi
    ... complexity" of the ANSI standard is rarely visible to users, ... The most obvious case is that commands are in interpreted pidgin while definitions are in the compiled language. ... label "Interpretation: Interpretation semantics for this word are ...
    (comp.lang.forth)
  • Re: when EXACTLY is virtual mechanism used?
    ... a virtual member function, the concrete function is chosen in accordance ... > connection with pointers or references, and (&obj) is a pointer. ... > know that the compiler can be smart enough to see that the dynamic ... The standard doesn't go into implementation details in this case. ...
    (comp.lang.cpp)