为通用树定义迭代器

Question

我有这个类叫做“Node”。我一直在考虑将它重命名为“树”，但是任何名称都可以提供更多的意义。这个类实现了一个通用的树形容器。每个节点可以有任意数量的子节点。类的基本头定义如下：

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; 
}; 

我DFSIterator的头部定义是：

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是迭代器对Node<Elem>别名。

我遇到的问题是我想为此树定义迭代器，用户可以用与STL容器类似的方式声明这些迭代器。我在想，把0123de这样的typedef语句可以正常工作。但是，无论何时将这些语句添加到标题中，我都会收到以下错误error C2512<Item>: no appropriate default constructor available.无论我试图去使用它。

所以现在要声明一个迭代器，如果我不想从树的根节点开始，我必须执行类似于DFSIterator<Node<DataMap>> dfsIter = rRootNode.begin();或DFSIterator<Node<DataMap>> dfsIter(rNode);的操作。我想要做的更像Node<DataMap>::dfs_iterator it = rRootNode.begin()。有没有办法做到这一点，我失踪了？

注意：我确实想要更改关于此实现的其他一些内容。我真的不希望用户将节点元素传递给addChild（）方法。我宁愿让用户传递一个指向节点的迭代器。

Answer 1

如果内部节点定义dfs_iterator，那么你可以使用它基本上像你描述：

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: 

    . 
    . 
    . 
}; 

，并使用

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

唯一不同的是，由于dfs_iterator是一个模板，你有指定模板参数，即使它们都可以默认。