Avoid RTTI when dealing with pairs of objects

Question

I saw a few questions about avoiding RTTI, but mine seems to be a bit more specific. Here is an example case:

struct Base {};

struct A : Base {};
struct B : Base {};
struct C : Base {};

std::vector<Base*> vec;

I want to do something on all possible (unordered) pairs of objects in the vector (if the vector has 3 elements, with 0 and 1, 0 and 2, 1 and 2). The pseudo-code for what I want is something like:

if e1 is A and e2 is A:
    behavior1(e1, e2)
elif e1 is A and e2 is B:
    behavior2(e1, e2)
elif ...

Lots of people say that RTTI is bad design, but could it be avoided here? And is there a more efficient way than doing all these if/elif?

Mm, what do you mean with "pair of objects" in a `vector`? Shouldn't it be a `std::vector>` ? — Xaqq, Aug 02 '13 at 09:26
Mm... Speaking in terms of mathematical sets, I want to execute a function on all pairs of (vec x vec). For example imagine that Base is Shape, A is Triangle, B is Square, etc, and I want to get all objects that overlap in vec. I'm not sure if I'm clear here. — Philippe, Aug 02 '13 at 09:33

score 2 · Accepted Answer · answered Aug 02 '13 at 09:36

Whether you choose to use or avoid RTTI is really more about common sense. While it may be considered good design to strive to avoid it, occasionally you just want to get something done and move on.

If you only have a couple of class types to deal with, you could get rid of the if/else if and have a simple table of function pointers. Use a virtual function in each type to add weight to the index used to look up the correct function to call:

struct Base
{
    virtual int  GetWeight() const = 0;
};

struct A : Base
{
    virtual int  GetWeight() const    { return 1; }
};

struct B : Base
{
    virtual int  GetWeight() const    { return 2; }
};

struct C : Base
{
    virtual int  GetWeight() const    { return 4; }
};


static void (*MyBehaviours)( Base*, Base* )[] = { &behaviour1, &behaviour2, ... };

MyBehaviours[ e1->GetWeight() + e2->GetWeight() ]( e1, e2 );

This seems like a good idea, though I was thinking of simplifying it putting a map, function> instead of that array and that trick with powers of two and addition ^^ Thanks! — Philippe, Aug 02 '13 at 09:48
It's a bit demotivating to me when answers get accepted to quickly, especially when there's some variance in the answers and no voting. This removes value for future SO users, because the question will practically just shrivel in a corner before actually having been discussed. — sehe, Aug 02 '13 at 10:00
Man, typing on an iPhone is slow... You beat me to it. Good job. — Nik Bougalis, Aug 02 '13 at 10:09

sehe · Answer 2 · 2013-08-02T10:53:54.517

This is a prime usecase for binary variant visitation.

This shifts runtime polymorphism somewhat to static polymorphism (though a type-discriminant is still being used inside boost::variant, but this does not use or require RTTI).

Note also, how you don't absolutely need to add separate cases for all combinations: I've demonstrated using template behaviour implementations for the case where

arguments are of the same actual type ("identical")
no other overload existed

I have also shown how you can still mix "classical" runtime-polymorphism by showing the overload that takes Base, A (accepting A,B,C,... in combination with a second argument of type A (or derived).

Finally, note that this approach allows you to overload on rvalue-ness, const-ness, volatility as well.

#include <iostream>
#include <boost/variant.hpp>
#include <string>

struct Base {};

struct A: Base {};
struct B: Base {};
struct C: Base {};

typedef boost::variant<A, B, C> MyType;

struct MyBehaviour : boost::static_visitor<std::string>
{
    template <typename T>
    std::string operator()(T const&, T const&) const { return "identical"; }

    std::string operator()(A const&, B const&) const { return "A, B"; }
    std::string operator()(A const&, C const&) const { return "A, C"; }

    std::string operator()(Base const&, A const&) const { return "[ABC], A"; }

    std::string operator()(Base const&, Base const&) const { return "Other"; }
};

int main()
{
    MyBehaviour f;

    MyType a = A{},
           b = B{},
           c = C{};

    std::cout << boost::apply_visitor(f, a, b) << "\n";
    std::cout << boost::apply_visitor(f, a, c) << "\n";

    std::cout << boost::apply_visitor(f, a, a) << "\n";
    std::cout << boost::apply_visitor(f, b, b) << "\n";
    std::cout << boost::apply_visitor(f, c, c) << "\n";

    std::cout << boost::apply_visitor(f, c, a) << "\n";

    std::cout << boost::apply_visitor(f, c, b) << "\n";
}

See it Live on Coliru, output:

A, B
A, C
identical
identical
identical
[ABC], A
Other

This is a very nice feature I didn't know about. Hopelessly I can't apply it here because this involves (if I'm right) to have a std::vector in my example and I want to be able to add other structs which inherit from Base without changing the vector or MyType. But thanks anyway, I learnt something :) — Philippe, Aug 02 '13 at 09:59

minicaptain · Answer 3 · 2013-08-02T09:46:31.933

0

I think you can use a cache of map:

map<string, func*>;

func* is functional pointer which can point to a function behavior(A,B) or behavior(A,C) or behavior(B, C)

when you create a object of A and B insert(make_pair(AB, behavior(A,B)) and the same for B and C, when you want use a A and B objects you can fetch from the map,and the same for B and C.

edited Aug 02 '13 at 09:46

answered Aug 02 '13 at 09:33

minicaptain

1,196
9
16

The problem here is how do you call that function without knowing if the object is A or B? – Philippe Aug 02 '13 at 09:54

doron · Answer 4 · 2013-08-02T09:39:25.300

0

Add the following to base:

virtual void behaviour(Context& context) = 0;

The implement for all derived classes.

If you can make the context the same for all calls to behaviour you should be able to eliminate any need to RTTI checks. Each implementation can use whatever it needs from context.

edited Aug 02 '13 at 09:39

answered Aug 02 '13 at 09:34

doron

27,972
12
65
103

The behaviour is different according to the type of both the objects (I edited the question to show that behaviour takes arguments) – Philippe Aug 02 '13 at 09:35
I added a context parameter. – doron Aug 02 '13 at 09:41
But how do you fill-in Context according to the types of the two objects (which are Base*)? – Philippe Aug 02 '13 at 09:54
Contexts must have a superset of all the possible data that will be used by any imlementation of behaviour. This might be just a struct of pointers. The overloaded method can then choose to use the bits that it needs. – doron Aug 02 '13 at 10:09

ogni42 · Answer 5 · 2013-08-02T09:42:18.553

0

Make behaviour() call virtual functions in your A, B, C objects to perform the specific work.

struct Base 
{
    virtual doSomething(){};
};

struct A : Base 
{
    virtual doSomething(){  };
};
struct B : Base 
{
    virtual doSomething(){};
};

std::vector<Base*> vec;

void performOperation(Base* a, Base* b)
{
   a->doSomething(a, b);
   b->doSomething(a, b);
}

int myFunction
{
    // ... code to select a pair of objects omitted
    performOperation(a, b);
}

edited Aug 02 '13 at 09:42

answered Aug 02 '13 at 09:35

ogni42

1,232
7
11

The problem of double dispatch is that if we add a struct D, we must update A, B and C, I want to avoid that. – Philippe Aug 02 '13 at 09:38
you are right, i already saw that flaw and edited. Esp. because virtual functions already seem sufficient. – ogni42 Aug 02 '13 at 09:42
Even now, doSomething must be implemented with A* and B* for both structures A and B, you forgot to put the parameters in your code – Philippe Aug 02 '13 at 09:44

Avoid RTTI when dealing with pairs of objects

5 Answers5

Linked