"John" <we**********@yahoo.com> wrote in message
news:11**********************@o13g2000cwo.googlegr oups.com...
I was wondering why the STL RB Tree implementation is
used when the iterators of map are incremented/decremented
to yield successors and predecessors?
Because the RB tree is also used to do inserts, erases, and
finds?
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).
And in practice, *most* increments and decrements (in a large
tree) are indeed O(1). It's just that every once in a while
you come to the end of a subtree and have to do O(log N)
operations to find the successor. So amortized time complexity
is O(log N).
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)?
You probably could, at the expense of making inserts and erases
even more expensive. They'd have to update two more links
(predecessor and successor) in addition to the existing three
(parent, left subtree, and right subtree). I suspect the
time complexity would still be O(log N), but with a notably
bigger multiplier.
And if you care about memory thrashing, you're bound to get
more of it with five pointers per node instead of three.
The member functions insert and erase also get bigger, so
you increase the chance of code thrashing.
And if you care about implementation bugs (as I do), you're
bound to get more of them when the code has to maintain two
only loosely related data structures instead of one to preserve
tree integrity.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
[ See
http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]