0

ポリモーフィック オブジェクトのツリーがあります。2 つのツリーをトラバースし、ノードを比較する必要があります。ノードのタイプが異なる場合、それらは等しくありません。次の階層を考えてみましょう。

struct Visitor;

struct Base {
  virtual ~Base() = default;
  virtual void accept(Visitor &) = 0;
};
using BasePtr = std::unique_ptr<Base>;

struct A final : Base {
  void accept(Visitor &) override;
  int data;
};
struct B final : Base {
  void accept(Visitor &) override;
  BasePtr child;
};
struct C final : Base {
  void accept(Visitor &) override;
  std::vector<BasePtr> children;
};

struct Visitor {
  virtual void visit(const A &) = 0;
  virtual void visit(const B &) = 0;
  virtual void visit(const C &) = 0;
};

これらの機能を実装する方法を知っています：

bool equalNode(const A &, const A &);
bool equalNode(const B &, const B &);
bool equalNode(const C &, const C &);

この関数をどのように実装する必要があるかについて質問しています:

bool equalTree(const Base *, const Base *);

ビジター パターンをエレガントに使用するequalTreeにはどうすればよいですか?equalNode

4

2 に答える 2

1

Something like

struct RhsVisitor : public Visitor
{
    bool result;
};

struct AEqualVisitor : public RhsVisitor
{
    void visit(const A & rhs) override { result = equalNode(lhs, rhs); }
    void visit(const B &) override { result = false; }
    void visit(const C &) override { result = false; }

    const A & lhs;
};

And similar for B and C

struct LhsVisitor : public Visitor
{
    void visit(const A & a) override { rhsVisitor = std::make_unique<AEqualVisitor>(a); }
    void visit(const B & b) override { rhsVisitor = std::make_unique<BEqualVisitor>(b); }
    void visit(const C & c) override { rhsVisitor = std::make_unique<CEqualVisitor>(c); }

    std::unique_ptr<RhsVisitor> rhsVisitor;
};

bool equalTree(const Base * lhs, const Base * rhs)
{
    LhsVisitor vis;
    lhs->accept(vis);
    rhs->accept(*vis.rhsVisitor);
    return vis.rhsVisitor->result;
};
于 2018-09-05T11:06:46.133 に答える
0

ここには 3 つのアプローチがあります。

1 つ目は、二重ディスパッチを行う必要があることです。一方の側に 1 人の訪問者がいて、もう一方の側に 1 人の訪問者がいます。一方を選択したら、その型をテンプレート パラメーターとして「保存」します。これを使用して、反対側にアクセスできます。

template <typename T>
struct Right : Visitor {
     Right(T const* lhs) : lhs(lhs) { }
     T const* lhs;
     bool result;

     void visit(A const& x) override { visit_impl(x); }
     void visit(B const& x) override { visit_impl(x); }
     void visit(C const& x) override { visit_impl(x); }

     void visit_impl(T const& x) { result = equalNode(*lhs, x); }
     template <typename U> void visit_impl(U const&) { result = false; }
};

struct Left : Visitor {
    Left(Base const* lhs, Base const* rhs) : rhs(rhs) {
        lhs->accept(*this);
    }
    Base const* rhs;
    bool result;

    void visit(A const& x) override { visit_impl(x); }
    void visit(B const& x) override { visit_impl(x); }
    void visit(C const& x) override { visit_impl(x); }

    template <typename U>
    void visit_impl(U const& lhs) {
        Right<U> right(&lhs);
        rhs->accept(right);
        result = right.result;
    }
};

bool equalTree(const Base *lhs, const Base *rhs) {
    return Left(lhs, rhs).result;
}

2 つ目は、ごまかすことです。両側が同じタイプの場合のみ気にするので、単一のディスパッチのみが必要です。

struct Eq : Vistor {
    Eq(Base const* lhs, Base const* rhs) : rhs(rhs) {
        lhs->accept(*this);
    }

    Base const* rhs;
    bool result;

    void visit(A const& x) override { visit_impl(x); }
    void visit(B const& x) override { visit_impl(x); }
    void visit(C const& x) override { visit_impl(x); }

    template <typename U>
    void visit_impl(U const& x) {
        result = equalNode(x, *static_cast<U const*>(rhs));
    }
};

bool equalTree(Base const* lhs, Base const* rhs) {
    if (typeid(*lhs) == typeid(*rhs)) {
        return Eq(lhs, rhs).result;
    } else {
        return false;
    }
}

3 つ目は、OO を介してこれを行うのではなく、代わりにvariant:

using Element = std::variant<A, B, C>;

struct Eq {
    template <typename T>
    bool operator()(T const& lhs, T const& rhs) const {
        return equalNode(lhs, rhs);
    }

    template <typename T, typename U>
    bool operator()(T const&, U const&) const {
        return false;
    }
};

bool equalTree(Element const& lhs, Element const& rhs) {
    return std::visit(Eq{}, lhs, rhs);
}
于 2018-09-05T15:30:35.683 に答える