template syntax for nested classes - custom iterators

[Christopher]

I am trying to implement a generic tree class, as I had mentioned in a
previous post. I want it to be STL like, so I went and researched how
to implement an iterator and copied an example from a page online.


template <class T>
class GenericTree
{
private:

class Node
{
public:
Node(const T & data) {}

// other methods
};

Node * m_root;

public:

// Other methods

class Iterator : std::iterator<std::foward_iterator_tag, T>
{
public:

Iterator(Node * node)
:
m_node(node)
{}

// Other methods

T * operator -> ()
{
return (&*(GenericTree<T>::Iterator)*this);
}

private:

Node * m_node;
};

Iterator begin()
{
return Iterator(m_root);
}

// Other methods
};



When I use it with the following code:

GenericTree<int> tree;
GenericTree<int> Iterator it = tree.begin();
it->() = new int(0);

I get an error:

"expected unqualified-id before '(' token
In member function 'T* GenericTree<T>::Iterator:perator->() [with T
= int]'
Instantiated from here
dependant-name ' GenericTree<T>::Iterator' is a parsed non-type, but
instantiation yields a type
note: say 'typename GenericTree<T>::Iterator' is a type is meant

I assume I need to use the typename keyword somewhere, but am unclear
where. Is my syntax incorrect? Can someone give a correct syntax with
nested template classes?

 

[Fei Liu]

I am trying to implement a generic tree class, as I had mentioned in a
previous post. I want it to be STL like, so I went and researched how
to implement an iterator and copied an example from a page online.


template <class T>
class GenericTree
{
private:

class Node
{
public:
Node(const T & data) {}

// other methods
};

Node * m_root;

public:

// Other methods

class Iterator : std::iterator<std::foward_iterator_tag, T>
{
public:

Iterator(Node * node)
:
m_node(node)
{}

// Other methods

T * operator -> ()
{
return (&*(GenericTree<T>::Iterator)*this);
}

private:

Node * m_node;
};

Iterator begin()
{
return Iterator(m_root);
}

// Other methods
};



When I use it with the following code:

GenericTree<int> tree;
GenericTree<int> Iterator it = tree.begin();
it->() = new int(0);

I get an error:

"expected unqualified-id before '(' token
In member function 'T* GenericTree<T>::Iterator:perator->() [with T
= int]'
Instantiated from here
dependant-name ' GenericTree<T>::Iterator' is a parsed non-type, but
instantiation yields a type
note: say 'typename GenericTree<T>::Iterator' is a type is meant

I assume I need to use the typename keyword somewhere, but am unclear
where. Is my syntax incorrect? Can someone give a correct syntax with
nested template classes?

There is a type mismatch between (&*(GenericTree<T>::Iterator)*this) and
T *. It'd be helpful if you could post a complete sample code.

Another note is I don't think there is something called
std::forward_iterator_tag.

Fei

 

[Martin York]

I am trying to implement a generic tree class, as I had mentioned in a
previous post. I want it to be STL like, so I went and researched how
to implement an iterator and copied an example from a page online.

Note:
There is already a tree class.
It is just hidden from view inside the std::set()

 

[Fei Liu]

Note:
There is already a tree class.
It is just hidden from view inside the std::set()

and std::map, std::multi_map etc...

 

[Christopher]

and std::map, std::multi_map etc...

That's great, but there isn't any info on how to get to it and use it.

 

[Fei Liu]

That's great, but there isn't any info on how to get to it and use it.

hmm what do you mean? everytime you use std::set you are using a tree
implementation beneath it. The essense of a tree is its hierarchical
organization of information and that's captured in set or map for you.

Why don't you tell us why you need a tree other than needing it in a
tree form? boost::graph has a graph implementation that does trees,
forest, or whatnot you want, take a look at it too.

Fei

 

[Christopher]

hmm what do you mean? everytime you use std::set you are using a tree
implementation beneath it. The essense of a tree is its hierarchical
organization of information and that's captured in set or map for you.

Why don't you tell us why you need a tree other than needing it in a
tree form? boost::graph has a graph implementation that does trees,
forest, or whatnot you want, take a look at it too.

Fei

I need a tree for a variety of things. One instance is to maintain a
parent-child relationship where every element can have any number of
children, they in turn can have any number of children, and so-on and
so forth. I need a tree to track that relationship. Its a very
straightforward requirement that might as well be written "I need a
tree".

Using some other data structure that is not a tree won't be very
efficient. I need to be able to do things like:

Insert a subtree (one element also qualifies)
Remove a subtree (one element also qualifies)
Get a bidirectional-iterator to a parent
Get a bidirectional-iterator to a child
Get a bidirectional-iterator to a sibling
iterate preorder, postorder, or breadthfirst
^^ hard part. Traversal is easy, but how does an iterator know
which way it is going next when it doesn't know which way it came
from? Tracking some kind of history crossed my mind, but how to do it
hasn't, when considering that any branch can be any length
and any element can have any number of children. An iterator doesn't
know it just came from the bottom or 2 from the bottom of a branch
that was off of child 9 of some other node that already had its
previous 20 children iterated through. There is a big difference
between traversing a tree all at once and getting handed an iterator
requesting a ++ operation.

Goto depth level X
Find "value x" in the tree
Find the depth of "value x" in the tree
Get a count
etc.

Sure I could use a map, I could use vectors, I could use sets, I could
even use arrays. I could use all kinds of things that aren't trees and
wrap logic around them to make a tree. But adding that logic will most
likely be more inefficient and harder to read than having a tree in
the first place. So, I am rolling my own. Preferably with different
flavors of iterators and some find, for_each, and like methods that
use some kind of provided comparator. I want something more STL like
instead of something that hacks parts of the STL together to make
something non STL like.

The code I am editing already uses maps to track parent-child
relationships and it is quite a mess to follow, especially with
several trees involved and multiple maps per tree. It's a bunch of
yuck.

I was basically looking for resources on tree data structures, as I am
sure others have done this already.

 

[Christopher]

I was basically looking for resources on tree data structures, as I am
sure others have done this already.

[edit] ...In my original post about trees.

In this post at the top of the thread, I did not understand the error
I was getting and desired some clarity on the template syntax.