In article <39bab3c5@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:

> Thorsten Froehlich <tho### [at] trfde> wrote:
> : Hmm, lets see, you need (runtimes from the C++ Prog. Lang 3rd Ed. page
> : 464)...
>
> : For inserting:       O(n * log(n))
> : For retrieval:       O(n * log(n))
>
>   By the way, you are wrong here.
>
>   It's true that retrieval is O(n*log(n)), but an operator++() of the
> iterator is O(1), so the retrieval of the whole tree is O(n) in my case.

OK, so Stroustrup is wrong?   Maybe you found try finding out that he is
right for yourself.  Just change your loop to:

  for(wlist_t::iterator i=words.begin();
  i!=words.end();)
  {
    cout << i->first << ": " << i->second << endl;
    i++;
  }

Now set a breakpoint at i++  and step into the function.  Go down until you
find a loop.   If you can't find a loop, I would really like to know which
data structure your library uses to store maps (I assume it is a tree
structure).


     Thorsten


____________________________________________________
Thorsten Froehlich, Duisburg, Germany
e-mail: tho### [at] trfde

Visit POV-Ray on the web: http://mac.povray.org

Post a reply to this message