Как адаптировать интерфейс посетителя к интерфейсу итератора?

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 для каждого различного типа class , который он сможет посещать.

Итератор с несколько иной точки зренияв основном специализированная форма посетителя, которая работает только для одного типа объекта.Вы обмениваетесь немного больше контроля над шаблоном посещения в обмен на потерю способности посещать несвязанные типы объектов.

Если вам нужно иметь дело только с одним типом (хотя этот тип может быть базовым классом, ипосещаемые объекты имеют различные производные типы), тогда очевидным методом будет создание класса «bridge», который посещает объекты (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-дерева, которая обеспечивала интерфейс посетителя, тогда как мне был нужен интерфейс итератора.Предложение Джерри выше работает, только если вы можете согласиться сохранить все результаты в коллекции.Это может привести к высокому потреблению памяти, если ваш набор результатов огромен, и вам не нужно его хранить.

Одно решение, которое наверняка будет работать, - это запустить посетителя в отдельном потоке и начать ждатьусловная переменная для результатов.Когда выполняется вызов посещения, вы сохраняете текущий результат в общем временном местоположении и используете другую условную переменную для ожидания следующего запроса.Вы сигнализируете условную переменную вызывающего (основного) потока, прежде чем подождать самостоятельно.Вызывающая сторона, которая реализует интерфейс итератора, может затем вернуть значение, сохраненное во временном местоположении.Во время следующей итерации он может сигнализировать об условной переменной потока посетителя и самостоятельно ждать следующего элемента.К сожалению, это несколько дорого, если вы делаете это на основе каждого элемента.Вы можете буферизовать некоторые элементы, чтобы улучшить производительность.

Что нам действительно нужно, так это дополнительный стек и чередование между двумя контекстами.Эта абстракция обеспечивается сопрограммами.В 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

Построение логики обхода в реализациях посетителей действительно не является гибким.Удобный способ чистого отделения обходных композитных структур от посещения может быть осуществлен с помощью комбинаторов посетителей (существуют другие статьи, не стесняйтесь их искать в Google).

Эти слайды О той же теме также может быть интересно.Они объясняют, как получить чистый синтаксис а-ля boost::spirit правила.