如何使访问者接口适应迭代器接口？

Question

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

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

类访客{
民众：
  虚拟 ~Visitor() { }
  虚拟无效访问（节点*n）= 0；
};

类树{
民众：
  无效接受（访客*v）；
};

并且您希望有一个可以按如下方式使用的接口，该接口应该按照访问者调用其 visit 函数的顺序迭代树。

for(迭代器 it(...), ite(...); it != ite; ++it) {
  /* 进程节点 */
}

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

Answer 1

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

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

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

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

相比之下，编写这样的访问者非常容易：

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

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

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

如果您只需要处理一种类型（尽管一种类型可能是基类，并且访问的对象具有各种派生类型），那么显而易见的方法是构建一个访问对象的“桥梁”类（<代码>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;
}

Answer 3

在访问者实现中构建遍历逻辑确实不灵活。可以通过访问者组合器<来干净地分离遍历复合结构和访问。 /a> （还有其他论文，请随意谷歌搜索）。

这些关于同一主题的幻灯片您可能也会感兴趣。他们解释了如何获得干净的语法 à la boost::spirit 规则。