Doubts about the decrement function of the RB-Tree iterator

Question

I'm writing a STL-like container library js-sdsl in Js mode.

There is a question about the decrement function (forward function of the iterator) in STL RB-Tree.

When I insert two different values into the Tree from small to large, I will get an RB-Tree with the following structure:

Among them, the Root node and the Header node are parents and children of each other, and the left and right nodes of the Header node point to the two inserted values respectively, and the smaller value will become the Root node, and the larger value will become the right child node of Root.

At this point, when the iterator pointing to the Root node is decremented, the following steps will be taken:

1. Judging that it is not currently a Header node, go to step 2;
2. Judging that the left child node of the current pointer is empty, go to step 3;
3. Determine that the current node (Root) is the left child node of the parent node (Header) (note that at this time, the LeftMost of the Header points to the smallest node in the tree, that is, Root), so move the pointer to the parent node (Header), and repeat step 3 until no more If the conditions are met, go to step 4;
4. Obviously, because the Root node and the Header node are parents and children of each other, the pointer finally points to the Root node after step 3.

In the end, the following code should fall into an infinite loop:

set<int> st { 1, 2 };
for (auto it = st.rbegin(); it != st.rend(); ++it) {
    cout << *it <<endl;
}

But actually, the above code works fine, I'm confused, I don't see any special handling in the STL code, I'm not proficient in C++, can anyone help me solve this problem?

Grateful!

Why above code works fine

Answer 1

I think you misunderstood how the std::reverse_iterator works: when the overloaded operator* is called, the underlying iterator is decremented and then dereferenced. More details can be found at std::reverse_iterator.

The loop should be interpreted in the following way:

1. At first loop, the iterator, that is currently rbegin(), is dereferenced, that means the underlying iterator is decremented and then dereferenced. Since the iterator points to the sentinel node (Header), the decrement function moves it to its right child node, that is the rightmost node by definition.
2. At second loop, the updated iterator is dereferenced, that means the underlying iterator is decremented and then dereferenced. Since the iterator points to an external node, its left child node is null and then the decrement function moves it to its parent node (Root).
3. Finally, since the updated iterator is now equal to the rend(), that is the root node, the loop is broken.

Effectively, your observation about the decrement of the begin() iterator is right: if it is decremented, it refers again to itself.