爲通用樹定義迭代器

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是一個模板，你有指定模板參數，即使它們都可以默認。