Fei Liu <feiliu@aepnetworks.com> wrote:
This is a little more advanced topic. I am trying to understand why erase
on a set implemented through red black tree only invalidates the iterator
being erased? It'd seem to me when the RBTree needs to be re-balanced, the
ordering of iteration may change...What gives?
It works because set iterators are dumb. An iterator is just a pointer
to a node; it doesn't remember how it got there and has no plan where
to go next. When incremented, it will check the links to the surronding
nodes and act accordingly; and this will get you to the node with the
next higher key, no matter how the tree is balanced, as long as it is in
a well-defined state.
If one thread iterates while another is rebalancing, things might go
wrong because the tree may be in an interim ill-defined state (think
of a monkey jumping towards a branch that suddenly swivels to the
other side of the trunk while the poor animal is in mid air). So you
need to synchronize if several threads use a std::set: simultaneously.