9

我想知道是否有一个好的设计模式或习惯用法来实现以下内容：

您有一个仅提供访问者界面的现有类，如下所示

class Visitor {
public:
  virtual ~Visitor() { }
  virtual void visit(Node *n) = 0;
};

class Tree {
public:
  void accept(Visitor *v);
};

visit并且您希望有一个可以按如下方式使用的接口，它应该以与访问者调用其函数的顺序相同的顺序遍历树。

for(iterator it(...), ite(...); it != ite; ++it) {
  /* process node */
}

问题似乎是当我们刚刚调用时visit，我们失去了控制，无法暂时“回到”循环体执行一个节点的动作。这看起来应该在现实世界的程序中定期发生。知道如何解决吗？

4

3 回答 3

6

在一般情况下，我认为这是不可能的，至少不是干净的。

至少正如通常定义的那样，迭代器期望处理同构集合。即，迭代器通常定义如下：

template <class Element>
class iterator // ...

...因此特定的迭代器只能与一种特定类型的元素一起使用。对于不同类型，您最多可以做的是创建一个指向基类（指针/引用）的迭代器，并让它处理派生类的对象。

相比之下，像这样写一个访问者是很容易的：

class MyVisitor {
public:
    void VisitOneType(OneType const *element);
    void VisitAnotherType(AnotherType const *element);
};

这可以访问任一OneType或的节点AnotherType，即使两者完全不相关。基本上，您Visit的 Visitor 类中有一个成员函数，用于它能够访问的每种不同类型的类。

从稍微不同的方向来看，迭代器基本上是一种特殊形式的访问者，仅适用于一种类型的对象。您交换了对访问模式的更多控制权，以换取失去访问不相关类型对象的能力。

如果您只需要处理一种类型（尽管一种类型可能是基类，并且访问的对象是各种派生类型），那么显而易见的方法是构建一个访问对象（Tree节点，在你的例子中），当它visit被调用时，它只是将它正在访问的节点的地址复制到一些支持迭代器的集合中：

template <class T>
class Bridge { 
    std::vector<T *> nodes;
public:
    virtual void visit(T *n) { 
        nodes.push_back(n);
    }

    typedef std::vector<T *>::iterator iterator;

    iterator begin() { return nodes.begin(); }
    iterator end() { return nodes.end(); }
};

使用这将是一个两步过程：首先像访问者一样访问节点，然后将感兴趣的节点收集在一起，您可以像访问任何其他提供迭代器的集合一样遍历它们。此时，您的访问模式仅受您在网桥中使用的集合提供的迭代器类的限制。

于 2011-04-01T00:44:15.650 回答
3

我在使用提供访问者接口的 R-tree 实现的真实环境中遇到了这个问题，而我需要一个迭代器接口。上面 Jerry 的建议只有在您可以接受将所有结果存储在集合中时才有效。如果您的结果集很大并且您实际上不需要存储它们，这可能会导致高内存消耗。

一种肯定有效的解决方案是在单独的线程中启动访问者并开始等待条件变量获得结果。当进行访问调用时，您将当前结果存储到共享临时位置，并使用另一个条件变量等待下一个请求。在您自己等待之前，您向调用者（主）线程的条件变量发出信号。然后，实现迭代器接口的调用者可以返回存储在临时位置的值。在下一次迭代期间，它可以向访问者线程的条件变量发出信号，并自行等待下一项。不幸的是，如果您按项目执行此操作，则成本会有些高。您可以缓冲一些项目以提高性能。

我们真正需要的是一个额外的堆栈并在两个上下文之间交替。这种抽象是由协程提供的。在 C++ 中，boost::coroutine 提供了一个干净的实现。下面我包含一个完整的示例，说明如何将访问者模式改编为迭代器模式。

#include <iostream>
#include <boost/bind.hpp>
#include <boost/coroutine/coroutine.hpp>

template<typename Data>
class Visitor
{
public:
  virtual ~Visitor() { }
  virtual bool visit(Data const & data) = 0;
};

template <typename Data>
class Visitable    
{
public:
    virtual ~Visitable() {}
    virtual void performVisits(Visitor<Data> & visitor) = 0;
};

// Assume we cannot change the code that appears above

template<typename Data>
class VisitableIterator : public Visitor<Data>
{
private:
    typedef boost::coroutines::coroutine<void()> coro_t;
public:
    VisitableIterator(Visitable<Data> & visitable)
        : valid_(true), visitable_(visitable)
    {
        coro_ = coro_t(boost::bind(&VisitableIterator::visitCoro, this, _1));
    }
    bool isValid() const
    {
        return valid_;
    }
    Data const & getData() const
    {
        return *data_;
    }
    void moveToNext()
    {
        if(valid_) 
            coro_();
    }
private:
    void visitCoro(coro_t::caller_type & ca)
    {
        ca_ = & ca;
        visitable_.performVisits(*static_cast<Visitor<Data> *>(this));
        valid_ = false;
    }
    bool visit(Data const & data)
    {
        data_ = &data;
        (*ca_)();
        return false;
    }
private:
    bool valid_;
    Data const * data_;
    coro_t coro_;
    coro_t::caller_type * ca_;
    Visitable<Data> & visitable_;
};

// Example use below

class Counter : public Visitable<int>
{
public:
    Counter(int start, int end)
        : start_(start), end_(end) {}
    void performVisits(Visitor<int> & visitor)
    {
        bool terminated = false;
        for (int current=start_; !terminated && current<=end_; ++current)
            terminated = visitor.visit(current);
    }
private:
    int start_;
    int end_;
};

class CounterVisitor : public Visitor<int>
{
public:
    bool visit(int const & data)
    {
        std::cerr << data << std::endl;
        return false; // not terminated
    }
};

int main(void)
{
    { // using a visitor
        Counter counter(1, 100);
        CounterVisitor visitor;
        counter.performVisits(visitor);
    }
    { // using an iterator
        Counter counter(1, 100);
        VisitableIterator<int> iter(static_cast<Visitable<int>&>(counter));
        for (; iter.isValid(); iter.moveToNext()) {
            int data = iter.getData();
            std::cerr << data << std::endl;
        }
    }
    return EXIT_SUCCESS;
}
于 2013-04-28T06:18:16.840 回答
2

在访问者实现中构建遍历逻辑确实不灵活。可以通过访问者组合器完成将遍历复合结构与访问完全分开的有用方法（还有其他论文，请随时使用谷歌搜索）。

这些关于同一主题的幻灯片也可能很有趣。他们解释了如何按照规则获得干净的语法 boost::spirit。

于 2011-04-01T08:56:12.900 回答