13

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().
      }
raja
  • 179
  • 1
  • 6

2 Answers2

8

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.

Community
  • 1
  • 1
tomasz
  • 12,574
  • 4
  • 43
  • 54
  • If you are working on a 64 bit machine, an address is 8 bytes. The iterator might well be implemented as a class whose sole data member is a pointer -- and that is exactly how the GNU implementation works. – David Hammen Jul 17 '11 at 11:08
  • David, you're completely right, I've forgotten I'm on 64-bit machine right now. Thanks, I've edited my post. – tomasz Jul 17 '11 at 11:16
6

It's implementation dependent. However, std::set iterators are only invalidated when the iterator is refering to an element that was removed from the set. Therefore, you can think of std::set iterators as nodes in the tree. ++ moves it in one traversal direction of the tree, and -- moves it the other.

Note that iterators are returned by other functions that begin, so their validity is not limited to just begin/end iterating.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
  • 1
    thanks for the reply....but let me put my question in other way..how would you implement increment operation of iterators on std::set if you were asked to do so..suppose internally the nodes are implemented using binary search tree instead of linked list...would you do the inorder traversal of this tree every time on every increment operation ++it..or you will save the order intially and refer to this every time you do ++it – raja Jul 17 '11 at 06:49
  • @raja: You can't implement `std::set` using a simple linked list. Finding an element in a set has to be O(log N), but finding an element in a linked list is O(N). It is necessarily a tree. If a tree node keeps a pointer to its parent node, `it++` can always find the next highest value without a full tree traversal. – MSalters Jul 18 '11 at 09:00