CODEWITHSUNDEEP
c++templatestreegeneric-programming
c.hughes
c.hughes

Reputation: 294

defining iterators for a generic tree

I have this class called "Node". I've been considering renaming it "Tree", but either name makes about as much sense. This class implements a generic tree container. Each node can have any number of children. The basic header definition of the class is as follows:

template<class Elem>
class Node
{
public:
    Node();
    ~Node();
    Node(const Elem& value);
    Node(const Node& rNode);
    const Elem& operator*() const;
    Elem& operator*();
    Elem* operator->();
    void operator=(const Elem& rhs);
    Node* addChild(const Elem& value);
    Node* addChild(Node childNode);
    Node* addChild(Node* pChildNode);
    HRESULT removeNode(DFSIterator<Node>& iter);

    template <class Node, class List, class Iter> friend class DFSIterator;

private:
    bool hasChild() const;

    Node* m_pParentNode;
    Elem m_value;
    std::vector<Node*> m_childList;
    static std::set<Node*> sNodeSet;
};

The header definition of my DFSIterator is:

template<class Item, 
         class List = std::vector<Item*>, 
         class Iter = typename std::vector<Item*>::iterator>
class DFSIterator
{
public:
    DFSIterator(Item& rRootNode);
    ~DFSIterator();
    DFSIterator* begin();
    DFSIterator* operator++();
    Item& operator*() const;
    Item* operator->() const;
    bool operator!=(const DFSIterator& rhs) const;
    bool isDone() const;
    operator bool() const {return !isDone();}

private:
    template <class Node> friend class Node;

    void initChildListIterator(Item* currentNode);

    bool m_bIsDone;
    Item* m_pRootNode;
    Item* m_pCurrentNode;
    ChildListIterator<Item>* m_pCurrentListIter;
    std::map<Item*, ChildListIterator<Item, List, Iter>*>  m_listMap;
};

Item is the iterator's alias for Node<Elem>.

The problem I am having is that I want to define iterators for this tree that the user can declare in a similar way to STL containers. I was thinking that putting typedef statements like typedef DFSIterator<Node<Elem>> dfs_iterator; would work fine. But whenever I add those statements into the header, I get the following error error C2512<Item>: no appropriate default constructor available. Wherever I try to go and use it.

So right now, to declare an iterator I have to do something like DFSIterator<Node<DataMap>> dfsIter = rRootNode.begin(); or DFSIterator<Node<DataMap>> dfsIter(rNode); if I don't want to start at the root node of the tree. What I want to be able to do is something more like Node<DataMap>::dfs_iterator it = rRootNode.begin(). Is there a way to do this that I am missing?

Note: I do want to change a few other things about this implementation. I don't really want the user to be passing a node element to the addChild() method. I'd rather have the user pass an iterator that is pointing to a node.

Upvotes: 1

Views: 556

Answers (1)

Vaughn Cato
Vaughn Cato

Reputation: 64308

If you define dfs_iterator inside Node, then you can use it basically like you describe:

template<class Elem>
class Node
{
public:
    typedef Node<Elem> Item;

    template<
        class List = std::vector<Item*>, 
        class Iter = typename std::vector<Item*>::iterator
    > class dfs_iterator;

     .
     .
     .
};

template<class Elem>
template<class List, class Iter>
class Node<Elem>::dfs_iterator
{
public:

    .
    .
    .
};

and use

Node<DataMap>::dfs_iterator<> it = rRootNode.begin();

The only difference is that since dfs_iterator is a template, you have to specify the template parameters, even though they both can be defaulted.

Upvotes: 1

Related Questions