Looking for a pattern to avoid using dynamic_cast in implementation of a virtual function

Question

My problem is this: I have an interface root class with several concrete branch classes. In application code, there exists a vector of pointers to the root class. There are several places where I need to loop over all the elements in the vector and compare them against a given instance:

// Application Code
void compare_loop(Root *r, std::vector<Root*> vec) {
    for (auto v : vec) {
        if (r->compare(v)) {
            // Do something to v
        }
    }
}

My initial approach was to make "compare" a virtual function in the Root class:

// Class Definition
class Root {
public:
    Root(double bar) : Bar(bar) {};

    virtual bool compare(Root *r) = 0;

protected:
    double Bar;
};

class BranchA : public Root {
public:
    BranchA(double bar, double baz) : Root(bar), BazA(baz) {};

    bool compare(Root *r) override;

protected:
    double BazA;
};

class BranchB : public Root {
public:
    BranchB(double bar, int baz, bool foo) : Root(bar), BazB(baz), Foo(foo) {};

    bool compare(Root *r) override;

protected:
    int BazB;
    bool Foo;
};

The issue is that the implementation of the "compare" function should always evaluate to false if the argument is not of the same concrete type, and otherwise depends on the member variables specific to BranchA/BranchB. With a single virtual member function, the only way I could think of implementing this is to attempt a dynamic_cast:

// Implementation
bool BranchA::compare(Root *r) {
    BranchA* branch = dynamic_cast<BranchA*>(r);

    if (branch == nullptr) {
        return false;
    }
    else {
        // Do some complicated comparison based on BranchA members
        return (Bar < branch->Bar) && (BazA < branch->BazA);
    }
}

bool BranchB::compare(Root *r) {
    BranchB* branch = dynamic_cast<BranchB*>(r);

    if (branch == nullptr) {
        return false;
    }
    else {
        // Do some complicated comparison based on BranchB members
        return (Bar > branch->Bar) && (BazB > branch->BazB) && (Foo == branch->Foo);
    }
}

This doesn't seem like the most elegant approach to me, but I'm not sure. I would like to know if there is a different approach I could take in the Class Definition and Implementation which would produce the same results without changing the Application Code. Or, is this an instance where the use of dynamic_cast is appropriate?

Answer 1

I usually use a pattern which makes usage of the NVI idiom^1,2. A cast is still required but it's a astatic_cast not a dynamic_cast. The static_cast avoids the extra cost associated with a dynamic_cast and is guaranteed to be safe (see code comments).

However, I'm not saying this solution is any faster than the OP's code, since is still uses a typeid check as well as a dynamic dispatch of the isEqual function.

The main advantage here over the code in the question is that changes in the comparison logic of the base class does not impact the implementation of the derived classes, of which there could be many.

Example Code

#include <iostream>
#include <memory>
#include <vector>

class Root
{
public:
    explicit Root(double bar) : Bar(bar) {}

    // Base class must have a virtual destructor for deletion through
    // the base pointer to work properly
    virtual ~Root() {}

    bool operator==(const Root& other) const
    {
        // Make sure the two types being compared are the same derived type
        return (typeid(*this) == typeid(other)) &&
            // Compare all state associated with the base class
            (Bar == other.Bar) &&
            // Dispatch comparison to the derived implementation to finish
            // the comparison
            isEqual(other);
    }

private:
    // Guaranteed to only be dispatched by operator== if 'other' is the
    // same type as '*this'
    virtual bool isEqual(const Root &other) const = 0;

    double Bar;
};

class BranchA : public Root
{
public:
    BranchA(double bar, double baz) : Root(bar), BazA(baz) {}

private:
    virtual bool isEqual(const Root& other) const override
    {
        // static_cast is safe since the Base class guarantees it won't
        // call this function unless 'other' and '*this' are the same type
        const BranchA& branch = static_cast<const BranchA&>(other);
        return (BazA == branch.BazA);
    }

    double BazA;
};

class BranchB : public Root
{
public:
    BranchB(double bar, int baz, bool foo) : Root(bar), BazB(baz), Foo(foo) {}

private:
    virtual bool isEqual(const Root& other) const override
    {
        // static_cast is safe since the Base class guarantees it won't
        // call this function unless 'other' and '*this' are the same type
        const BranchB& branch = static_cast<const BranchB&>(other);
        return (BazB == branch.BazB) && (Foo == branch.Foo);
    }

    int BazB;
    bool Foo;
};

void compare_loop(const Root &r, const std::vector<std::unique_ptr<Root>>& vec)
{
    for (const auto& v : vec)
    {
        if (r == *v)
        {
            std::cout << "Equivalent\n";
        }
        else
        {
            std::cout << "Different\n";
        }
    }
}

int main()
{
    BranchA root(1.0, 2.0);

    std::vector<std::unique_ptr<Root>> branches;
    branches.push_back(std::make_unique<BranchA>(root));
    branches.push_back(std::make_unique<BranchA>(1.0, 1.0));
    branches.push_back(std::make_unique<BranchB>(1.0, 2.0, true));

    compare_loop(root, branches);

    return 0;
}

Example Output

Equivalent
Different
Different

Live Example

---

¹Non-virtual interface pattern - Wikipedia
²Virtuality - Herb Sutter

Answer 2

Bjarne Stroustrup has an excellent publication on how to produce something equivalent to a dynamic_cast<> that can be as fast as a modulo. It's available here: http://www.stroustrup.com/fast_dynamic_casting.pdf

The basic idea is, you assign a pair of ints to each class. First one is a distinct prime for each class, second is the product of the second of each base classes times first of current class. If source::second % target::first == 0, the dynamic_cast<> will succeed. It's good for a lot of things: fast dynamic_cast<>, diamond detection, greatest common subtype of a set of elements, abstract visitor and multiple dispatch, etc.