help with iterator error

vendtagain · 03-14-2010, 08:16 PM

I am getting an error relating to an iterator from a list that I dont understand.

Code:

std::list<shapeNode*>::iterator ii;
for(ii=childs.begin();ii != childs.end(); ii++)
*ii->drawAll();

where "shapeNode" is derived from "treeNode", and treeNode is

Code:

template<typename T>
class treeNode
{
private:
T Data;
std::list<treeNode*> childs;
};

and shapeNode is

Code:

class shapeNode : public treeNode<shape*>
{
};

The error I'm getting is as follows, also getting the same error for operator!= as well

Code:

error: no match for 'operator=' in 'ii = ((shapeNode*)this)->shapeNode::<anonymous>.treeNode<shape*>::childs. std::list<_Tp, _Alloc>::begin [with _Tp = treeNode<shape*>*, _Alloc = std::allocator<treeNode<shape*>*>]()'

new at using templates, so im wondering if I have some syntax errors, the book I'm using doesn't go too indepth with templates and inheritance.

vendtagain · 03-14-2010, 08:27 PM

I figured it out,
i used:
list<shapeNode*>
when I should have used:
list<treeNode<shape*>*>

vendtagain · 03-14-2010, 08:45 PM

Now i realize since the iterator is of the base class type, I cant use derived class functions, which i need to do. So back to the drawing board...

ta0kira · 03-14-2010, 10:18 PM

Before you go hacking away, think about these few points:

Why are the children tabulated in the base class? There must be some reason tied directly to the structure of the tree. Even if you keep the same pointer type, why not postpone the tabulation until a more refined class? You might eventually want a shapeNode that contains an entirely different structure at some point (e.g. maybe a dead end, maybe a web, etc.) as a branch of the tree.
The pointer type of the children should be as specific as possible while still allowing for the variety of objects in the tree. This ties into the previous point of postponing the tabulation until it's absolutely necessary.
What's the meaning of having children of different types? They all share a base class for a reason, but do they need to be treated differently during traversal? If so, there are two possibilities: a) it can be done with a virtual function, b) you need to call functions using different arguments. If you need different arguments, the traversal function must "know" when to use which arguments and functions. If that's the case, why not embed it in a class, pass a pointer to an object of that class during traversal, then "do the right thing" in the derived class? I've used this pattern very successfully.

In C++, you can only get less specific with a pointer (unless you want to deal with RTTI.) Some people see this as a fundamental flaw, but in most cases (in my experience) if you think about what you're really trying to achieve conceptually, it's just a matter of rethinking how actions come about.

Sometimes a single tree structure isn't suitable for multiple things. For example, the structure that operates the GUI might not be suitable for operating the underlying objects. In those cases, you might consider parallel tree structures, e.g. a GUI tree and a separate object tree, with the objects tied to the GUI node-for-node using pointers.
Kevin Barry

PS I've made a lot of assumptions based on your few words, but I've spent hundreds of hours working on similar problems with traversal of abstract tree structures.

vendtagain · 03-15-2010, 01:10 AM

Thanks for the reply ta0kira, your post gave me a lot to think about and I'm still trying to dissect some of it.
Here's a little more about the the base class, which also should answer some of your questions.

The base class should be able to:
1. add and remove direct children,
2. search its children for a specified value, and also recursively have its children search theirs, traversing the tree till the value is found, when its found it returns a pointer to the specified object
3. find child from given path
4. return a list of its direct children

In addition to the "data" and "children" members there is a string which is the Name or Key, which the traversing functions use.

It seemed natural to make the base class contain the tabulation, and most of the members are implemented with this in mind.

The derived class basically just says it wants to use the base class with its data member of type shape*, plus adds additional functions for interfacing with the Data member, such as Draw(). I would rather not add virtual functions to accommodate for the derived class, as I want to keep the base class generalized(mainly I want to get more familiar with using templates)

Quote:

b) you need to call functions using different arguments. If you need different arguments, the traversal function must "know" when to use which arguments and functions. If that's the case, why not embed it in a class, pass a pointer to an object of that class during traversal, then "do the right thing" in the derived class? I've used this pattern very successfully.

Could you explain this bit a little further?

vendtagain · 03-15-2010, 06:26 AM

I believe I got it working the way it needs to. I added another typename in the template base class template..template<typename T, class T2>..then made the list ..list::<T2*>...and when specifying shapeNode class T2 == shapeNode.
I haven't tested the execution yet as I have some other things to implement before it will work, but the compiler isn't giving me any obscure errors.
Id still like keep in mind other tree implementations for the future, can you explain the following a bit more?

Quote:

b) you need to call functions using different arguments. If you need different arguments, the traversal function must "know" when to use which arguments and functions. If that's the case, why not embed it in a class, pass a pointer to an object of that class during traversal, then "do the right thing" in the derived class? I've used this pattern very successfully.

ta0kira · 03-15-2010, 02:42 PM

Quote:

Originally Posted by vendtagain

Thanks for the reply ta0kira, your post gave me a lot to think about and I'm still trying to dissect some of it.
Here's a little more about the the base class, which also should answer some of your questions.

The base class should be able to:
1. add and remove direct children,
2. search its children for a specified value, and also recursively have its children search theirs, traversing the tree till the value is found, when its found it returns a pointer to the specified object
3. find child from given path
4. return a list of its direct children

I had a nearly identical requirement for my project, and given that all traversal operated iteratively, I just made the tree into a sort of 2-D linked list. Have you used binary trees? It's essentially that, but rather than "left" and "right" children, each node has a pointer to "next" and "first child". "next" and "first child" are accessible via virtual functions, and the actual implementations of the nodes contain a pointer for each. This takes the place of iterators, it actually makes storage more efficient, and traversal works just as it would for a binary tree. Also, you can define recursive functions in the base class that call the same function on "first child" then "next", which will end up traversing the whole branch. It's a little difficult to explain how it works (more difficult than actually doing it,) but if you're curious, look at storage_section and linked_section in http://hparser.berlios.de/.

Quote:

Originally Posted by vendtagain

Could you explain this bit a little further?

If, for example, having a virtual function in the base class that's called on each node isn't an option, this must mean a different function with different arguments must be called for some nodes in the tree. Assuming you're using a single procedure to traverse the tree and execute operations on the node, such a procedure must know when to call those functions. For example:

Code:

struct base
{
    //...
    struct iterator;
    iterator first_child() const;
    iterator end_child() const;
};

struct derived1 : base
{
    void func1(int);
};

struct derived2 : base
{
    void func2(const char*);
};

Suppose for derived1 you needed to call func1 and for derived2 you needed to call func2 during traversal. If the prototypes were the same you could make it a virtual function, but we're discussing the case where you can't. Suppose you were traversing with the function below:

Code:

void traverse(base *bBase)
{
    base::iterator current = bBase->first_child(), end = bBase->end_child();

    while (current != end)
    {
    if      (/*type==derived1*/) current->func1(1);
    else if (/*type==derived2*/) current->func2("hello");
    traverse(current++);
    }
}

This function does something different based on the type of the node, but rather than make that decision in a centralized location (the function,) why not pass an object to a virtual function, then decide what happens in that function in each derived class? There always has to be some common theme when traversing a tree.

Code:

struct traverser
{
    int get_int() const;
    const char *get_str() const;
}

struct base
{
    virtual void update(const traverser*) = 0;
    //... (same as before)
}

struct derived1 : base
{
    void update(const traverser *tTr)
    { if (tTr) tTr->get_int(); }
}

struct derived2 : base
{
    void update(const traverser *tTr)
    { if (tTr) tTr->get_str(); }
}

void traverse(base *bBase)
{
    base::iterator current = bBase->first_child(), end = bBase->end_child();

    traverser trav;

    while (current != end)
    {
    current->update(&trav);
    traverse(current++);
    }
}

I didn't compile all of this, but the essential pattern is there.
Kevin Barry

PS In the example above, the node takes what it needs rather than the traversal function deciding what to give to the node.