C++ dynamic object class comparison
<p>I want to be able to compare syntax trees for expressions. The base class <code>Expr</code> has a pure virtual <code>compare</code> method for concrete subclasses to override:</p>

<pre><code>class Expr {
public:
  virtual bool compare(const Expr *other) const = 0;
};
</code></pre>

<p>As an example, say <code>NumExpr</code> and <code>AddExpr</code> are two concrete subclasses for representing a literal integer expression and a binary add expression respectively. The first thing each <code>compare</code> method does is use <code>dynamic_cast</code> to make sure the <code>other</code> expression is of the same type: </p>

<pre><code>class NumExpr : public Expr {
  int num;
public:
  NumExpr(int n) : num(n) {}
  bool compare(const Expr *other) const {
    const NumExpr *e = dynamic_cast&lt;const NumExpr*&gt;(other);
    if (e == 0) return false;
    return num == e-&gt;num;
  }
};

class AddExpr : public Expr {
  Expr *left, *right;
public:
  AddExpr(Expr *l, Expr *r) : left(l), right(r) {}
  bool compare(const Expr *other) const {
    const AddExpr *e = dynamic_cast&lt;const AddExpr*&gt;(other);
    if (e == 0) return false;
    return left-&gt;compare(e-&gt;left) &amp;&amp; right-&gt;compare(e-&gt;right);
  }
};
</code></pre>

<p>I always feel like I am doing something wrong when I use <code>dynamic_cast</code> -- 
is there a more appropriate approach to perform dynamic comparisons between objects
without using <code>dynamic_cast</code>?</p>

<p>Using the <a href="http://en.wikipedia.org/wiki/Visitor_pattern" rel="nofollow">visitor design pattern</a> does <em>not</em> solve the need for RTTI (as far as I can tell). The abstract base class for an "expression visitor" might look something like this:</p>

<pre><code>class NumExpr;
class AddExpr;

class ExprVisitor {
public:
  virtual void visit(NumExpr *e) {}; // "do nothing" default
  virtual void visit(AddExpr *e) {};
};
</code></pre>

<p>The base class for expressions includes a pure virtual <code>accept</code> method:</p>

<pre><code>class Expr {
public:
  virtual void accept(ExprVisitor&amp; v) = 0;
};
</code></pre>

<p>The concrete expression subclasses then use <strong>double dispatch</strong> to invoke the appropriate <code>visit</code> method:</p>

<pre><code>class NumExpr : public Expr {
public:
  int num;
  NumExpr(int n) : num(n) {}
  virtual void accept(ExprVisitor&amp; v) {
    v.visit(this);
  };
};

class AddExpr : public Expr {
public:
  Expr *left, *right;
  AddExpr(Expr *l, Expr *r) : left(l), right(r) {}
  virtual void accept(ExprVisitor&amp; v) {
    v.visit(this);
  };
};
</code></pre>

<p>When we finally get to performing the expression comparisons using this mechanism, we <em>still</em> need to use RTTI (as far as I can tell); For example,  here is a sample visitor class for comparing expressions:</p>

<pre><code>class ExprCompareVisitor : public ExprVisitor {
  Expr *expr;
  bool result;
public:
  ExprCompareVisitor(Expr *e) : expr(e), result(false) {}
  bool getResult() const {return result;}

  virtual void visit(NumExpr *e) {
    NumExpr *other = dynamic_cast&lt;NumExpr *&gt;(expr);
    result = other != 0 &amp;&amp; other-&gt;num == e-&gt;num;
  }

  virtual void visit(AddExpr *e) {
    AddExpr *other = dynamic_cast&lt;AddExpr *&gt;(expr);
    if (other == 0) return;

    ExprCompareVisitor vleft(other-&gt;left);
    e-&gt;left-&gt;accept(vleft);
    if (!vleft.getResult()) return;

    ExprCompareVisitor vright(other-&gt;right);
    e-&gt;right-&gt;accept(vright);
    result = vright.getResult();
  }
};
</code></pre>

<p>Note we are still using RTTI (<code>dynamic_cast</code> is this case). </p>

<p>If we truly wish to avoid RTTI we could "roll our own" be creating unique constants to identify every concrete expression flavor: </p>

<pre><code>enum ExprFlavor {
  NUM_EXPR, ADD_EXPR
};

class Expr {
public:
  const ExprFlavor flavor;
  Expr(ExprFlavor f) : flavor(f) {}
  ...
};
</code></pre>

<p>Each concrete type would set this constant appropriately:</p>

<pre><code>class NumExpr : public Expr {
public:
  int num;
  NumExpr(int n) : Expr(NUM_EXPR), num(n) {}
  ...
};

class AddExpr : public Expr {
public:
  Expr *left, *right;
  AddExpr(Expr *l, Expr *r) : Expr(ADD_EXPR), left(l), right(r) {}
  ...
};
</code></pre>

<p>Then we could use <code>static_cast</code> and the <code>flavor</code> field to avoid RTTI:</p>

<pre><code>class ExprCompareVisitor : public ExprVisitor {
  Expr *expr;
  bool result;
public:
  ExprCompareVisitor(Expr *e) : expr(e), result(false) {}
  bool getResult() const {return result;}

  virtual void visit(NumExpr *e) {                                                                
    result = expr-&gt;flavor == NUM_EXPR &amp;&amp; static_cast&lt;NumExpr *&gt;(expr)-&gt;num == e-&gt;num;
  }
  ...
};
</code></pre>

<p>This solution seems like I am just replicating what the RTTI is doing under the hood.</p>
