Thorsten Froehlich <tho### [at] trfde> wrote:
: 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).

  It's true that the operator++ has to make several steps in some cases but
only when it has to go backwards in the tree. When going forward it has to
make just one step. It has to make log(n) steps backwards only once (when
going from the largest item which is smaller than the root item to the
root item). It has to make log(n)/2 steps two times. And so on.
  What is the amortized O()-time for ++ then?

  Btw, using some extra memory it could be possible to avoid all extra steps:
By putting a pointer to the next item in the walk in each item.

-- 
main(i,_){for(_?--i,main(i+2,"FhhQHFIJD|FQTITFN]zRFHhhTBFHhhTBFysdB"[i]
):_;i&&_>1;printf("%s",_-70?_&1?"[]":" ":(_=0,"\n")),_/=2);} /*- Warp -*/

Post a reply to this message