 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
llewelly
Guest
|
 Posted: Fri Aug 22, 2003 12:52 pm Post subject: Re: A question on a rb-tree's iterator. |
 |
|
"Dhruv" <dhruvbird (AT) gmx (DOT) net> writes:
| Quote: | Ok, the rb-tree is not a standard interface, or something, but's it's used
by most implementations for implementing the set/multiset class. My
question is on the rb-tree's iterator of libstdc++. Here is the increment
function, which is called by the operator++ of the iterator of rb-tree
implementation. Subject to de-uglification :-)
void
M_increment()
{
if (M_node->M_right != 0)
{
M_node = M_node->M_right;
while (M_node->M_left != 0)
M_node = M_node->M_left;
}
else
{
Base_ptr y = M_node->M_parent;
while (M_node == y->M_right)
{
M_node = y;
y = y->M_parent;
}
if (M_node->M_right != y) //NOTE this condtion [*]
M_node = y;
}
}
Now, I want to know when this condtion will evaluate to true. AFAICS
(which I am wrong), the condition is always false, because y is always
M_Node's parent, so in effect, it can never be M_Node's right child. I am
obviously missing something.
[snip] |
The libstdc++ rb-tree is a 'circular' doubly-linked rb-tree. If a node
does not have a left and / or right child, the pointer for that
child points to a 'sentinel' node. The root node is the sentinel
node's left child. (That's what makes it circular.) The sentinel
node has no right child. The sentinel node is called '_M_header'
in their source.
Now imagine M_Node == root, and root has no childern (a 1 - element
tree) .' Base_ptr y = M_Node->M_parent ' will set y to point at
the sentinel node. The while condition will fail, since root is
the sentinel's left child. The if condition (which you starred)
will be true: since M_node has no right child, M_right will point
at the sentinel node - which is where y points. M_node will then
be set to y, which points at the sentinel node. The sentinel node
doubles as the end() indicator, so this is exactly as desired; if
you have a one element tree, and you increment the iterator
pointing at that one element, the iterator should then be end().
| Quote: |
And also, after looking at this, is there any specification in the
standard about the comelexity of the increment and
decrement operators of a set/multiset/map/multimap's iterator?
|
24.1/8 requires that they be amortized constant time.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Joshua Lehrer
Guest
|
| Posted: Fri Aug 22, 2003 12:59 pm Post subject: Re: A question on a rb-tree's iterator. |
|
|
"Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote
| Quote: | And also, after looking at this, is there any specification in the
standard about the comelexity of the increment and
decrement operators of a set/multiset/map/multimap's iterator?
|
A quick search of this newsgroup finds:
http://tinyurl.com/krsm
------------------------------------------
In article <31c49f0d.0211041455.7625305d (AT) posting (DOT) google.com>, Joshua
Lehrer <usenet_cpp (AT) lehrerfamily (DOT) com> wrote:
| Quote: | According to the spec, incrementing and decrementing bidirectional
iterators must have "amortized constant time."
When iterating through an std::map<K,V>::iterator, each step may take
O(Log(N)) time. Doesn't this violate the constant time requirement?
Or, is it that, while each step may take this time, the total cost of
all N steps will be O(N).
|
Your latter statement is correct. Iteration over an entire std::map is
O(N) so each step is amortized O(1) (even though a single increment can
be up to O(Log(N) time).
--
Howard Hinnant
Metrowerks
-----------------------------------
Joshua Lehrer
factset research systems
NYSE:FDS
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sat Aug 23, 2003 2:58 am Post subject: Re: A question on a rb-tree's iterator. |
|
|
On 21 Aug 2003 13:02:19 -0400, "Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote:
Here we are going up the tree. The important point is that the tree
has a dummy root node with parent to actual root, left to leftmost
node of entire tree and right to rightmost node of entire tree. The
end iterator points to this dummy node.
| Quote: | Base_ptr y = M_node->M_parent;
while (M_node == y->M_right)
{
M_node = y;
y = y->M_parent;
}
|
When we get here, M_node->parent is y and y->right != M_node.
| Quote: | if (M_node->M_right != y) //NOTE this condtion [*]
M_node = y;
|
It seems that we came up from the left to reach y and need to
move M_node up to that point. Consider the special case of a
tree with only one node. We set y to the dummy node as
parent of the real root. Since there is only one real node,
all three of the dummy node's pointers point to it. The while
test passes, M_node moves to the dummy node and y moves to
the root node. y->right is nul exiting the loop. Now we
have M_node in the right place with both its parent and
right equal to y. The test fails and we do not create an
infinite loop by setting M_node back to the real root. This
can also happen when the size is two with the root being the
larger. In the case of moving from the rightmost non-root,
the loop exits with y at the dummy because M_node at the
root is not right of y. The test passes and we move M_node
to the dummy giving end.
| Quote: | And also, after looking at this, is there any specification in the
standard about the comelexity of the increment and
decrement operators of a set/multiset/map/multimap's iterator?
|
Yes, they must be amortized constant time. That means that a complete
traversal must be order N, not that each increment must be order 1. If
you look at a traversal, you will see that each branch is traversed in
both directions. That gives 2(N-1) which is order N. It is a bit
smaller than that because begin jumps to the left most node and those
branches are only traversed once. The worst height of an rb-tree is 2
lg N which means a single increment could chase that many pointers.
Because of the savings on begin at the kth item of the traversal, the
number of pointer chases will be less than 2k. Note that it is
amortized over a forward (or reverse) traversal not over any sequence
of ++, --.
You might also look at operator-- to see how decrementing the end
iterator is handled. You may also find a test on decrementing begin
like that above or just allowing undefined behavior.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Sat Aug 23, 2003 3:27 am Post subject: Re: A question on a rb-tree's iterator. |
|
|
| Quote: | Now, I want to know when this condtion will evaluate to true. AFAICS
(which I am wrong), the condition is always false, because y is always
M_Node's parent, so in effect, it can never be M_Node's right child. I am
obviously missing something.
|
Yes. The fact that the node representing end() for
set's/multiset's/map's/multimap's should not be part of the tree.
You need to somehow go from the right most node to the end node.
| Quote: | And also, after looking at this, is there any specification in the
standard about the comelexity of the increment and
decrement operators of a set/multiset/map/multimap's iterator?
|
Have not checked but at worst, a increment/decrement cannot be more than 2 *
log N steps.
Stephen Howe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dhruv
Guest
|
| Posted: Sat Aug 23, 2003 8:24 am Post subject: Re: A question on a rb-tree's iterator. |
|
|
| Quote: | Now, I want to know when this condtion will evaluate to true. AFAICS
(which I am wrong), the condition is always false, because y is always
M_Node's parent, so in effect, it can never be M_Node's right child. I am
obviously missing something.
|
Sorry, swap all true with false, and all false with true.
-Dhruv.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Dhruv
Guest
|
| Posted: Sat Aug 23, 2003 8:13 pm Post subject: Re: A question on a rb-tree's iterator. |
|
|
On Fri, 22 Aug 2003 22:58:53 -0400, John Potter wrote:
| Quote: | On 21 Aug 2003 13:02:19 -0400, "Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote:
Here we are going up the tree. The important point is that the tree
has a dummy root node with parent to actual root, left to leftmost
node of entire tree and right to rightmost node of entire tree. The
end iterator points to this dummy node.
Base_ptr y = M_node->M_parent;
while (M_node == y->M_right)
{
M_node = y;
y = y->M_parent;
}
When we get here, M_node->parent is y and y->right != M_node.
if (M_node->M_right != y) //NOTE this condtion [*]
M_node = y;
It seems that we came up from the left to reach y and need to
move M_node up to that point. Consider the special case of a
tree with only one node. We set y to the dummy node as
parent of the real root. Since there is only one real node,
all three of the dummy node's pointers point to it. The while
test passes, M_node moves to the dummy node and y moves to
the root node. y->right is nul exiting the loop. Now we
have M_node in the right place with both its parent and
right equal to y. The test fails and we do not create an
infinite loop by setting M_node back to the real root. This
can also happen when the size is two with the root being the
larger. In the case of moving from the rightmost non-root,
the loop exits with y at the dummy because M_node at the
root is not right of y. The test passes and we move M_node
to the dummy giving end.
|
Hey, thanks a lot for the explanation!!!
I think I'm beginning to get the layout a bit. Let me draw it out, so that
you can see if it's correct.
Left-------------------- --------------------Right
^ | | ^
| Quote: | V V |
Minumum value(begin) <- Left <- M_Header -> Right -> Maximum Value(end-1)
V |
Parent
Actual Root
So, that means that end, and the dummy node are the same node, and that
decrementing begin will give end, and incrementing end will give begin(),
but obviously, only for this implementation.
So, basically, that check will always give true except when the iterator
is at the node containing the greatest value, when it fails, and the
iterator stays incremented at end(), which is the same node that has it;s
parent pointer pointing to the real root.
| Quote: |
And also, after looking at this, is there any specification in the
standard about the comelexity of the increment and
decrement operators of a set/multiset/map/multimap's iterator?
Yes, they must be amortized constant time. That means that a complete
traversal must be order N, not that each increment must be order 1. If
you look at a traversal, you will see that each branch is traversed in
both directions. That gives 2(N-1) which is order N. It is a bit
smaller than that because begin jumps to the left most node and those
branches are only traversed once. The worst height of an rb-tree is 2
lg N which means a single increment could chase that many pointers.
Because of the savings on begin at the kth item of the traversal, the
number of pointer chases will be less than 2k. Note that it is
amortized over a forward (or reverse) traversal not over any sequence
of ++, --.
|
I was wondering, that it you want to use say a multimap, and you want all
values that have the same key, how would you ideally go about doing it?
The only way I can think is of is to get the first one using the find
function, and then keep increment until you reach end(), or an iterator
with a non-equal key.
| Quote: | You might also look at operator-- to see how decrementing the end
iterator is handled. You may also find a test on decrementing begin
like that above or just allowing undefined behavior.
|
Yes, I would want to have a look at it, but generally, I'd like to confirm
that it does something like this:
inorder (node)
{
if (node) {
inorder (node->right);
visit (node);
inorder (node->left);
}
}
So, basically, whenever you decrement an iterator, it searches for the
predecessor, and gives it.
Regards,
-Dhruv.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sun Aug 24, 2003 11:27 pm Post subject: Re: A question on a rb-tree's iterator. |
|
|
On 23 Aug 2003 16:13:24 -0400, "Dhruv" <dhruvbird (AT) gmx (DOT) net> wrote:
| Quote: | On Fri, 22 Aug 2003 22:58:53 -0400, John Potter wrote:
I think I'm beginning to get the layout a bit. Let me draw it out, so that
you can see if it's correct.
Left-------------------- --------------------Right
^ | | ^
| V V |
Minumum value(begin) <- Left <- M_Header -> Right -> Maximum Value(end-1)
|
V
Parent
|
V
Actual Root
|
The tabs make it hard to read. Anyway, the only pointers to the
dummy/end node are the one in the tree object and the parent pointer
in the root. Missing children are nul pointers not threads to
anywhere.
| Quote: | So, that means that end, and the dummy node are the same node,
|
Yes.
| Quote: | and that
decrementing begin will give end, and incrementing end will give begin(),
but obviously, only for this implementation.
|
Should not care because both are violations and have undefined behavior.
It happens that incrementing end gives back not front.
| Quote: | So, basically, that check will always give true except when the iterator
is at the node containing the greatest value, when it fails, and the
iterator stays incremented at end(), which is the same node that has it;s
parent pointer pointing to the real root.
|
It will give true except when the root is the greatest value and the
iterator pointing at it is incremented. Since the rb tree is balanced,
the root can only be the greatest when there are one or two items. It
is a very special case.
| Quote: | I was wondering, that it you want to use say a multimap, and you want all
values that have the same key, how would you ideally go about doing it?
|
Equal_range gives the pair of iterators.
| Quote: | The only way I can think is of is to get the first one using the find
function, and then keep increment until you reach end(), or an iterator
with a non-equal key.
|
Find may find any of them. Lower_bound finds the first. Upper_bound
finds the first larger. Equal_range gives both of those.
| Quote: | So, basically, whenever you decrement an iterator, it searches for the
predecessor, and gives it.
|
Yes, both ++ and -- produce inorder traversals. Just remember that
there is no off the front place. Write the reverse traversal correctly
or use a reverse iterator to ease the pain.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
