如何迭代另一个类中的容器？

Question

我已经遇到过这个问题几次，想知道是否有一个简单的方法或模式可以用来解决它。

想象一个树结构，其中每个节点都包含一个指向子节点的指针的 STL 容器（向量）。我希望客户端代码能够遍历这棵树，并迭代子容器以访问其他部分。

我的问题是，我想维护节点的封装，同时让客户端轻松查看该节点的所有子节点。我还想确保，如果客户端获得对树中根节点的常量引用，那么对树的后续部分的所有访问也是常量的。

我应该尝试为我的节点类型创建一个迭代器类，让节点方法返回向量迭代器，还是我缺少更优雅的模式？

编辑：我想再次强调，虽然我看到了一些好的想法，但我有指向其他节点的指针容器。返回 vector::const_iterator 不会阻止客户端调用节点上的非常量方法。它仅保护指针本身不指向不同的对象。

Answer 1

像这样的东西通常就足够了：

class node 
{
public:
    typedef std::vector<node> node_list;
    typedef node_list::const_iterator const_iterator;

    const_iterator begin() const { return children_.begin(); }
    const_iterator end() const { return children_.end(); }

private:
    node_list children_;
}

这允许您更改底层容器类型，而无需更改迭代节点子节点的代码。

这样做的缺点是它会泄漏实现细节，因为使用 node::const_iterator 的代码知道它是一个随机访问迭代器（因为 std::vector:: const_iterator > 是一个随机访问迭代器），因此您可能很难切换到不支持随机访问的容器。

如果您希望能够自己控制迭代器类别，您可能需要创建自己的迭代器类来提供您想要提供的确切行为。

Answer 2

这不是对您问题的直接答案，而是一种替代方法。您可以通过注册回调函子来控制反转，而不是让客户端代码运行该节目。例如：

// Derive from this class to create a visitor
class AbstractVisitor
{
public:
    virtual void operator() (const T &) = 0;
};


// Your recursive data-structure class
class MyClass
{
public:
    void walk(AbstractVisitor &v) const
    {
        // Call the client callback
        v(payload);
        for (std::vector<MyClass>::const_iterator it = children.begin();
             it != children.end(); ++it)
        {
            // Recurse
            it->walk(v);
        }
    }

private:
    T payload;   // Some sort of payload associated with the class
    std::vector<MyClass> children;
};


// You could have different visitor classes to do different things
class MyVisitor : public AbstractVisitor
{
public:
    virtual void operator() (const T &t)
    {
        // Do something with t
    }
}


int main()
{
    MyClass m;
    MyVisitor v;
    ...
    m.walk(v);
}

完成封装！

Answer 3

为了遍历整个树，您必须创建自己的迭代器类，对于仅遍历子树，您可以安全地返回向量迭代器。