c++ - 为通用树定义迭代器

Question

我有一个名为“Node”的类。我一直在考虑将它重命名为“树”，但是这两个名字都差不多。此类实现通用树容器。每个节点可以有任意数量的 child 。类的基本头定义如下:

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 的 header 定义是:

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 容器的方式声明它。我在想把 typedef 语句写成 typedef DFSIterator<Node<Elem>> dfs_iterator;会工作正常。但是每当我将这些语句添加到标题中时，我都会收到以下错误 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

如果你在 Node 中定义了 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 是一个模板，你必须指定模板参数，即使它们都可以默认。