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では制御不能になり、一時的にループ本体に「戻って」1 つのノードのアクションを実行できないことです。これは、実際のプログラムでは定期的に発生するはずです。それを解決する方法はありますか？

4

3 に答える 3

6

一般的なケースでは、少なくともきれいにではないと思います。

少なくとも通常定義されているように、反復子は同種のコレクションを処理することを期待しています。つまり、イテレータは通常次のように定義されます。

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

...そのため、特定のイテレータは特定の 1 つのタイプの要素のみを処理できます。異なる型を操作するためにできることのほとんどは、基本クラスへの (ポインター/参照) へのイテレーターを作成し、派生クラスのオブジェクトを処理できるようにすることです。

対照的に、次のようなビジターを作成するのは非常に簡単です。

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

OneTypeこれは、またはのいずれかのノードを訪問できますAnotherType。2 つが完全に無関係であってもです。基本的に、 Visitor クラスには、アクセスできるさまざまなタイプのクラスVisitごとに 1 つのメンバー関数があります。

少し異なる方向から見ると、イテレータは基本的に、1 つのタイプのオブジェクトに対してのみ機能するビジターの特殊な形式です。無関係なタイプのオブジェクトを訪問する能力を失う代わりに、訪問パターンをもう少し制御できます。

1 つのタイプのみを処理する必要がある場合 (ただし、その 1 つのタイプが基本クラスであり、アクセスされたオブジェクトがさまざまな派生型である場合)、明白な方法は、オブジェクト (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(); }
};

これを使用するには、2 段階のプロセスがあります。まず、訪問者が通常行うようにノードにアクセスします。次に、イテレータを提供する他のコレクションと同じように、関心のあるノードをまとめて反復処理できます。その時点で、訪問パターンは、ブリッジで使用するコレクションによって提供されるイテレータのクラスによってのみ制限されます。

于 2011-04-01T00:44:15.650 に答える
3

この問題は、ビジター インターフェイスを提供する R ツリー実装を使用した実際の設定で発生しましたが、イテレータ インターフェイスが必要でした。上記の Jerry の提案は、すべての結果をコレクションに保存できる場合にのみ機能します。結果セットが巨大で、実際には保存する必要がない場合、メモリの消費量が多くなる可能性があります。

確実に機能する解決策の 1 つは、ビジターを別のスレッドで起動し、条件変数で結果を待ち始めることです。訪問呼び出しが行われると、現在の結果を共有の一時的な場所に保存し、別の条件変数を使用して次の要求を待ちます。自分で待機する前に、呼び出し元 (メイン) スレッドの条件変数にシグナルを送ります。イテレータ インターフェイスを実装している呼び出し元は、一時的な場所に格納されている値を返すことができます。次の反復中に、ビジター スレッドの条件変数を通知し、次のアイテムを待機することができます。残念ながら、これをアイテムごとに行うと、多少コストがかかります。一部のアイテムをバッファリングして、パフォーマンスを向上させることができます。

本当に必要なのは、追加のスタックと、2 つのコンテキストを交互に切り替えることです。この抽象化は、コルーチンによって提供されます。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

訪問者の実装でトラバーサル ロジックを構築することは、実際には柔軟ではありません。ビジターコンビネーターを介して、複合構造のトラバースをビジターから明確に分離する便利な方法があります (他の論文もあります。Google で検索してください)。

同じトピックに関するこれらのスライドも興味深いかもしれません。彼らは、ルールに沿ったきれい な構文を取得する方法を説明していboost::spiritます。

于 2011-04-01T08:56:12.900 に答える