Re: How does std::set implement iterator through red black tree?

Fei Liu wrote:


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