如何使访问者界面适应迭代器界面？

Question

我想知道是否有一个好的设计模式或成语来实现以下内容:

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

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,我们失去控制,并且不能暂时"返回"循环体来执行一个节点的操作.这看起来应该在现实世界的程序中定期出现.知道怎么解决吗？

Answer 1

在一般情况下,我认为这是不可能的,至少不是干净利落的.

至少在通常定义时,迭代器期望处理同类集合.即,迭代器通常定义为:

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

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

Answer 2

我在现实环境中遇到了这个问题，使用提供访问者接口的 R 树实现，而我需要一个迭代器接口。仅当您接受将所有结果存储在集合中时，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;
}