On Sat, 09 Sep 2000 18:46:59 -0500, Thorsten Froehlich wrote:
>In article <39bab424@news.povray.org> , Warp <war### [at] tagpovrayorg>  wrote:
>
>> : No, it is a clear which one is faster, just my notation for the total was
>> : incorrect:  See my later posts explaining it in more detail.
>>
>>   You had another mistake (which I mentioned in another response).
>>
>>   The total retrieval time in my case is O(n), not O(n*log(n)).
>
>No, it is O(log(n)) for each ++ operator, see my other post!

This depends on implementation.  My favorite map (the one I use here) is
O(1) for each ++ operator, at the expense of a bit more bookkeeping at
insertion and deletion time.  The bookkeeping is also O(1), though, so
it's dwarfed by the O(log n) the insert or delete already takes.

Whether implementation is prescribed by STL is something I don't know; I
haven't bothered to learn about STL yet as the compiler I'm forced to use
doesn't implement it (MSVC 1.52, the last 16-bit compiler MS made.  Low-level
programming on Win9x is pretty much required to be 16-bit.)

-- 
Ron Parker   http://www2.fwi.com/~parkerr/traces.html
My opinions.  Mine.  Not anyone else's.

Post a reply to this message