时间戳

首页 > 解决方案 > 优雅地比较 C++ 中的多态树

c++ - 优雅地比较 C++ 中的多态树

问题描述

我有一棵多态对象树。我需要遍历两棵树并比较节点。如果节点具有不同的类型，则它们不相等。考虑这个层次结构：

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访问者模式？

标签： c++c++17visitor-patternmultiple-dispatch

解决方案

就像是

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

和类似B的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;
};

推荐阅读