CODEWITHSUNDEEP
c++virtual-functionsdynamic-cast
Fredrick Baum
Fredrick Baum

Reputation: 109

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

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?

Upvotes: 6

Views: 781

Answers (4)

James Adkison
James Adkison

Reputation: 9602

I usually use a pattern which makes usage of the NVI idiom1,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

1 Non-virtual interface pattern - Wikipedia
2 Virtuality - Herb Sutter

Upvotes: 7

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275545

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.

Upvotes: 0

lorro
lorro

Reputation: 10880

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.

Upvotes: 6

kfsone
kfsone

Reputation: 24259

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.

Upvotes: 0

Related Questions