Menu
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().
}
401
Iterating over a set using iterator. In this method, an iterator itr is created and initialized using begin() function which will point to the first element, and after every iteration, itr points to the next element in a set and it will continue to iterate until it reaches the end of the set.
The iterator is implemented as a pointer to a node, and contains operator overloads for the four usual iterator operations of dereference, increment, comparison, and assignment. in the list class that can be used to insert new data items at arbitrary locations in the list.
Vector's iterators are random access iterators which means they look and feel like plain pointers. You can access the nth element by adding n to the iterator returned from the container's begin() method, or you can use operator [] .
One iterator object is equal to another if they address the same elements in a container. If two iterators point to different elements in a container, then they aren't equal. The first two template operators return true only if both left and right store the same iterator.
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.
88
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
