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?

Goulder

If you have a fairky important number of branches you may be interested in this SO answer: https://mcmap.net/q/1303135/-c-double-dispatch-for-equals – Chadd

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

Radborne

In what way is a typeid comparison followed by a static cast better than a dynamic cast? Please be concrete. – Colston

@Yakk I updated the answer to try to explain why the advantage of this proposed solution of the code in the question. I'm not really asserting typeid + static_cast is better than dynamic_cast but that it's more maintainable (i.e., changes in the the base class don't impact the derived classes) but of course the OP's use of dynamic_cast doesn't preclude this possibility (e.g., derived class explicitly calling comparison logic in the base class). – Radborne

Note that this solution also bars any derived classes that do not want to compare unequal to their parent (say that add no state). – Colston

@Yakk You're just getting at the fact that two concrete classes of different types cannot compare equal to each other because of the typeid check in the base class (which is also a non-virtual function)? – Radborne

@Yakk Do you think this answer is more harmful than helpful or possibly a wrong path entirely (within the context of the OP's question)? I don't mind deleting the answer. – Radborne

Naw, I was just wanted restrictions/issues to be explicit in the answer. And maybe see if there wqs something I was missing! – Colston

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.

Uprising

How does this answer the question? The OP is just asking if there is a better way to achieve their goal but your answer is "You can make dynamic_cast faster"?. – Radborne

@JamesAdkison: I'm (and Bjarne is) not talking about making dynamic_cast<> faster, but about checking whether a class is the dynamic base of another (i.e., whether dynamic_cast<>) is possible. Let me know if you propose some edits to make it clearer. – Uprising

"how to make dynamic_cast<> as fast as a modulo" -- This statement is what led me to believe your answer is about making dynamic_cast faster. I still don't get how this answer has any relevance to the question but I don't have any suggested edits for you. I'll read the link you posted. – Radborne

I've made a minor edit to reflect that it's not just "making dynamic_cast faster". I do believe it answers the question as to whether there is a different approach the OP could take. – Pompadour

Answer 3

One crude alternative is to simply have every derived class provide a type identifier of your own and compare those.

#include <iostream>
#include <fstream>
#include <string>

class Base {
    virtual const char* type_name() const noexcept = 0;
public:
    Base() {}
    bool is_same_type(const Base* rhs) const noexcept {
        return type_name() == rhs->type_name();
    }
};

class D1 : public Base {
    const char* type_name() const noexcept override { return "D1"; }
public:
    D1() {}
};

class D1D1 : public D1 {
    const char* type_name() const noexcept override { return "D1D1"; }
public:
    D1D1() {}
};

void test(const Base* lhs, const Base* rhs)
{
    std::cout << lhs->is_same_type(rhs) << '\n';
}

int main()
{
    D1 d1;
    D1D1 d1d1;
    test(&d1, &d1d1);
}

The downside is that if I forgot to explicitly add an override in D1D1 it would inherit it's parent's type_name and bogusly claim to be the same type.

Adjudge

Why do you reinvent the wheel? The compiler provides this functionality already! Look up typeid – Actinomorphic

Answer 4

You are failing at the LSP, where the virtual behaviour of the base class can be described by properties of the base class.

In effect, your interface "surface" is a dynamic one that extends unboundedly to all possible derived types of your base class. Someone cannot, for example, create an independant "clone" of one of your types: the exact dynamic type of your base class is part of its behaviour.

There are a number of alternative approaches.

You could store and expose properties in a (possibly active) dynamic dictionary, and compare those.

You could have a finite enumeration of subtypes, and make the subtype of the base part of its interface explicitly, together with a fast cast interface.

You could steal a page from COM, and have a query interface with reference counting that permits cloning by third parties. Then a type can mimic being a derived class by mimicing that interface, not the implementation.

Or you can just accept your interface surface is unbounded and ill specified. Keep using dynamic cast, or typeid (basically equivalent).

The name of your problem is the double dispatch problem, or the double dynamic dispatch problem, if you want to research it further.

Colston