Thorsten Froehlich wrote:
> 
> 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?
	I don't know what Stroustrup said, but according to the STL
documentation here: http://www.sgi.com/Technology/STL/trivial.html 

> The complexity of operations on trivial iterators is guaranteed to be amortized
constant time. 


-- 

* Doctor Jekyll had something * mailto:ber### [at] inamecom
* to Hyde...                  * http://www.enst.fr/~jberger
*******************************

Post a reply to this message