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.

Fei Liu 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?

Use the Source, Luke. Look at the implementation of 'std::set' in
your compiler include directories. Start with <set> header. It is
not guaranteed that those are files, but they usually are.

V

Fei Liu 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?

Fei

I took a reverse engineering approach by testing the blackbox
behavior...Here is what I got and something is a little unexpected here:


#include <set>
#include <iostream>

using namespace std;

void display(const set<int> & s){
cout << "node value: ";
set<int>::const_iterator it = s.begin();
for(;it != s.end(); ++it) cout << " " << *it;
cout << endl;
}

int main(){

set<int> s;
s.insert(4);
s.insert(1);
s.insert(10);
s.insert(2);
s.insert(3);
s.insert(5);

display(s);

s.erase(3);
display(s);

s.insert(3);
display(s);

cout << "node value: ";
set<int>::const_iterator it = s.begin();
while(it != s.end()){
if(*it == 3) s.erase(it++);
else ++it;
if(it != s.end()) cout << " " << *it;
}
cout << endl;
display(s);
}
./test_set_iter
node value: 1 2 3 4 5 10
node value: 1 2 4 5 10
node value: 1 2 3 4 5 10
node value: 2 3 4 5 10
node value: 1 2 4 5 10

It seems like although erase is done correctly but I am getting a '3' in
the fourth row of output. There seems be a incoherence between the
iterator and the state of the iteration...The red black tree is lying at
what node it's currently traversing the tree?!

Fei Liu 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?

Fei

I took a reverse engineering approach by testing the blackbox
behavior...Here is what I got and something is a little unexpected here:


#include <set>
#include <iostream>

using namespace std;

void display(const set<int> & s){
cout << "node value: ";
set<int>::const_iterator it = s.begin();
for(;it != s.end(); ++it) cout << " " << *it;
cout << endl;
}

int main(){

set<int> s;
s.insert(4);
s.insert(1);
s.insert(10);
s.insert(2);
s.insert(3);
s.insert(5);

display(s);

s.erase(3);
display(s);

s.insert(3);
display(s);

cout << "node value: ";
set<int>::const_iterator it = s.begin();
while(it != s.end()){
if(*it == 3) s.erase(it++);
else ++it;
if(it != s.end()) cout << " " << *it;
}
cout << endl;
display(s);
}
./test_set_iter
node value: 1 2 3 4 5 10
node value: 1 2 4 5 10
node value: 1 2 3 4 5 10
node value: 2 3 4 5 10
node value: 1 2 4 5 10

It seems like although erase is done correctly but I am getting a '3' in
the fourth row of output. There seems be a incoherence between the
iterator and the state of the iteration...The red black tree is lying at
what node it's currently traversing the tree?!