Comparing C ++ Dynamic Object Classes

Question

I want to be able to compare syntax trees for expressions. The Expr base class has a pure virtual compare method for overriding specific subclasses:

 class Expr { public: virtual bool compare(const Expr *other) const = 0; }; 

As an example, let's say NumExpr and AddExpr are two specific subclasses for representing a literal integer expression and a binary expression add, respectively. The first thing the compare method does is use dynamic_cast to make sure the other expression is of the same type:

 class NumExpr : public Expr { int num; public: NumExpr(int n) : num(n) {} bool compare(const Expr *other) const { const NumExpr *e = dynamic_cast<const NumExpr*>(other); if (e == 0) return false; return num == e->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<const AddExpr*>(other); if (e == 0) return false; return left->compare(e->left) && right->compare(e->right); } }; 

I always feel that I am doing something wrong when I use dynamic_cast - is there a better approach for doing dynamic comparisons between objects without using dynamic_cast ?

Using the visitor design template does not solve the RTTI problem (as far as I can tell). An abstract base class for an “expression visitor” might look something like this:

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

The base class for expressions includes a pure virtual accept method:

 class Expr { public: virtual void accept(ExprVisitor& v) = 0; }; 

Subclasses of the specific expression then use double dispatch to invoke the appropriate visit method:

 class NumExpr : public Expr { public: int num; NumExpr(int n) : num(n) {} virtual void accept(ExprVisitor& 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& v) { v.visit(this); }; }; 

When we finally start making comparisons using this mechanism, we still need to use RTTI (as far as I can tell); For example, here is an example visitor class for comparing expressions:

 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<NumExpr *>(expr); result = other != 0 && other->num == e->num; } virtual void visit(AddExpr *e) { AddExpr *other = dynamic_cast<AddExpr *>(expr); if (other == 0) return; ExprCompareVisitor vleft(other->left); e->left->accept(vleft); if (!vleft.getResult()) return; ExprCompareVisitor vright(other->right); e->right->accept(vright); result = vright.getResult(); } }; 

Note that we are still using RTTI ( dynamic_cast in this case).

If we really want to avoid RTTI, we could “collapse our own,” creating unique constants to identify each particular expressive taste:

 enum ExprFlavor { NUM_EXPR, ADD_EXPR }; class Expr { public: const ExprFlavor flavor; Expr(ExprFlavor f) : flavor(f) {} ... }; 

Each concrete type defines this constant accordingly:

 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) {} ... }; 

Then we could use the static_cast and flavor field to avoid RTTI:

 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->flavor == NUM_EXPR && static_cast<NumExpr *>(expr)->num == e->num; } ... }; 

This solution seems to be just replicating what RTTI does under the hood.

Answer 1

Assuming that you do not know the dynamic type of either side at compile time (for example, the static type is the same as the dynamic type), and that you really want to compare two Expr by pointer or link, you will have to make two virtual calls (double send) or use dynamic_cast .

It will look something like this:

 class Expr { public: virtual bool compare(const Expr *other) const = 0; virtual bool compare(const NumExpr *other) const { return false; } virtual bool compare(const AddExpr *other) const {return false;} }; class NumExpr : public Expr { int num; public: explicit NumExpr(int n) : num(n) {} bool compare(const Expr *other) const { return other->compare(this); } bool compare(const NumExpr *other) const { return num == other->num; } }; 

Answer 2

There is a typeid Operator that can be used instead of dynamic_cast for initial type matching.

(src)

Answer 3

You can use RTTI.

 class NumExpr : public Expr { int num; public: NumExpr(int n) : num(n) {} bool compare(const Expr *other) const { if ( typeid(*other) != typeid(*this) ) return false; else { NumExpr *e = static_cast<NumExpr*>(other); return num == e->num; } } };