Re: How does std::set implement iterator through red black tree?
On 2007-06-28 21:36, Fei Liu wrote:
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?!
Yes, I was a bit stumped too first, but it's because you print the
element in the iteration before you chech *it == 3, so first you print
3, then you take another turn in the loop and erase it. So there's
nothing wrong with the code, it just does not do what you thought it
would, try walking through the code with a debugger and you'll see.
--
Erik Wikstr?m