J
John
I was wondering why the STL RB Tree implementation is
used when the iterators of map are incremented/decremented
to yield successors and predecessors? This takes O(log n)
time (and a lot of memory thrashing depending on the size
of the tree) whereas just a simple pointer chase would make it O(1).
Is there an easy way to code this in C++ (Threaded red
black tree? ) OR Modify map so that map<>::iterator, ++it/--it
becomes O(1)?
Thanks in advance for your comments,
--j
used when the iterators of map are incremented/decremented
to yield successors and predecessors? This takes O(log n)
time (and a lot of memory thrashing depending on the size
of the tree) whereas just a simple pointer chase would make it O(1).
Is there an easy way to code this in C++ (Threaded red
black tree? ) OR Modify map so that map<>::iterator, ++it/--it
becomes O(1)?
Thanks in advance for your comments,
--j