CODEWITHSUNDEEP
c++stliterator
Evgeny Eltishev
Evgeny Eltishev

Reputation: 603

Tree-container iterator interface

I am making my own STL-like container - tree with any number of children

template<typename Type>
class Node
{
    Type value;
    Iterator AddChild(const Type & value);
    void Remove(const Iterator & where);
    ...
};

I decided that iterator's operator* should return value of current node, but what should return operator->? Currently, it returns Node<Type>* and it very useful in such situations 

Node<int>::Iterator it = tree.begin();
it->AddChild(4);

But my mentor said me, that operator-> should return Type*. What is STL-like way to access Node's methods? Something like it.Ref().MyMethod() doesn't look good.

Upvotes: 2

Views: 217

Answers (3)

shakurov
shakurov

Reputation: 2518

Your mentor is right, the return type of operator->() should be Type*.

The big idea behind iterators is that they are just smart pointers to some locations inside the container. You can alter the value stored at that location (by assigning to *it) or access its members, but to do more drastic (i.e. structural) changes to container contents, you have to have direct access to the container itself.

That's why in STL, there are no node's methods. Instead, there're container's methods (and also algorithms) that accept iterators as arguments.

In other words, the STL way of doing what you're trying to do is:

Node<int>::Iterator it = tree.begin();
tree.AddChild(it, 4);

Upvotes: 4

Jan Hudec
Jan Hudec

Reputation: 76236

The programmer expects it->method to be equivalent to (*it).method, so the operator-> should return pointer to the same thing that operator* returns reference to. Normally that should be the value of the iterator, because that's the expected way to get at the value.

You can expose methods of the node as methods of the pointer, i.e. called as it.method, but it's somewhat confusing and in most cases it would require extra data in the iterator compared to methods of the container taking iterator as argument. That's why STL always uses methods of the container taking iterator. E.g. container.insert(iterator, value) inserts value after iterator.

Upvotes: 0

n. m. could be an AI
n. m. could be an AI

Reputation: 119847

operator-> should return YourTree::value_type* and operator* should return YourTree::value_type&. (Actually a YourTree::pointer and YourTree::reference, but these are normally just aliases for * and & of the value type). Note the consistency. Without it, the standard algorithms will not work.

It is up to you to decide what the value_type is. It could well be Node if you want. This however can be confusing and hard to implement consistently. I would leave it as Type.

Upvotes: 1

Related Questions