How does the Iterator in set works

Question

I was wondering how would the iterators set in c++'s STL works. I guess the set is implemented using binary search tree, that means the iterators does inorder traversal of this tree. But my question is that,when does they do this traversing, at the very beginning when we do like it= s.begin() and store the traversed pointers in kind of stack internally and refer only this data structure on every increment in the iterator or the increment in the iterator does a new inorder traversal on the tree.

I mean when we initialize like

     set<int>  s;
     set<int>::iterator it;

 //and then use it like:

      for(it = s.begin(); it!=s.end(); )
      {
           dosth();
           ++it;     // does this do a inorder traversal of the tree again to find the next 
                     // node or it gets the next node in the tree by reading the internal
                    // data structure(of inorder traversal) which is created when we do   s.begin().
      } 

Answer 1

That's an interesting question. As Nicol pointed out, it's implementation dependent and while implementing own set you have to decide whether you favor smaller iterators or faster traversal (you can put more data into iterators to speed it up).

On my platform (64-bit) std::set<T>::iterator is of 8-byte size, what suggests it just keep pointer to the actual node. If the set is implemented using some kind of tree, then the incrementing of iterator is definitely not an O(1) operation and needs traversing of up to log(N) additional nodes (if talking about balanced tree). I've also checked the speed of ++it operation for different nodes and it's not constant what suggest extra traversals. It's completely fine for general-purpose set container, as it meets the expectation of tree traversal complexity and people generally assume iterators to be as small as possible. If you implement standard recursive tree traversal it's exactly the same, you just hide extra node visits on stack.

Take a look at Implementing an iterator over a binary search tree to get more details about implementing your own tree iterator.