Preventing redundant function calls in the presence of diamond inheritance

Question

What's a good strategy for preventing redundant function calls in the presence of diamond inheritance? Specifically, say we have a program:

#include <iostream>

struct A {
    int a;
    A(int a_) : a(a_) {}
    virtual void print() {
        std::cout << "a:  " << a << std::endl;
    }
};

struct B : virtual public A {
    int b;
    B(int a_,int b_) : A(a_), b(b_) {}
    virtual void print() {
        A::print();
        std::cout << "b:  " << b << std::endl;
    }
};

struct C : virtual public A {
    int c;
    C(int a_,int c_) : A(a_), c(c_) {}
    virtual void print() {
        A::print();
        std::cout << "c:  " << c << std::endl;
    }
};

struct D : public B,public C {
    int d;
    D(int a_,int b_,int c_,int d_) : A(a_), B(a_,b_), C(a_,c_), d(d_) {}
    void print() {
        B::print();
        C::print();
        std::cout << "d:  " << d << std::endl;
    }
};

int main() {
    D d(1,2,3,4);
    d.print();
}

When we call d.print(), we get:

a:  1
b:  2
a:  1
c:  3
d:  4

where a has been printed twice. Is there a good way to prevent this? Certainly, we could manually wire the connections with a code like:

#include <iostream>

struct A {
    int a;
    A(int a_) : a(a_) {}
    virtual void print_() {
        std::cout << "a:  " << a << std::endl;
    }
    virtual void print() {
        A::print_();
    }
};

struct B : virtual public A {
    int b;
    B(int a_,int b_) : A(a_), b(b_) {}
    virtual void print_() {
        std::cout << "b:  " << b << std::endl;
    }
    virtual void print() {
        A::print_();
        B::print_();
    }
};

struct C : virtual public A {
    int c;
    C(int a_,int c_) : A(a_), c(c_) {}
    virtual void print_() {
        std::cout << "c:  " << c << std::endl;
    }
    virtual void print() {
        A::print_();
        C::print_();
    }
};

struct D : public B,public C {
    int d;
    D(int a_,int b_,int c_,int d_) : A(a_), B(a_,b_), C(a_,c_), d(d_) {}
    virtual void print_() {
        std::cout << "d:  " << d << std::endl;
    }
    virtual void print() {
        A::print_();
        B::print_();
        C::print_();
        D::print_();
    }
};

int main() {
    D d(1,2,3,4);
    d.print();
}

which correctly outputs

a:  1
b:  2
c:  3
d:  4

but I would like to know if there's a better way. In terms of where this arises, imagine a situation with the objects A, B, C, and D are complicated and need to be able to write themselves to disk. We only want to write the output code for each A, B, C, and D once and it's important that D not write information about A twice.

<---EDIT--->

Here's two more ways of fixing the problem, but they're still kind of obtuse. The first one is from Cristian and involves setting a flag on whether or not A has been printed

#include <iostream>

struct A {
    int a;
    bool have_printed;
    A(int a_) : have_printed(false), a(a_) {}
    virtual void print() {
        if(have_printed) return;
        std::cout << "a:  " << a << std::endl;
        have_printed=true;
    }
    void clear() {
        have_printed=false;
    }
};

struct B : virtual public A {
    int b;
    B(int a_,int b_) : A(a_), b(b_) {}
    virtual void print() {
        A::print();
        std::cout << "b:  " << b << std::endl;
    }
};

struct C : virtual public A {
    int c;
    C(int a_,int c_) : A(a_), c(c_) {}
    virtual void print() {
        A::print();
        std::cout << "c:  " << c << std::endl;
    }
};

struct D : public B,public C {
    int d;
    D(int a_,int b_,int c_,int d_) : A(a_), B(a_,b_), C(a_,c_), d(d_) {}
    void print() {
        B::print();
        C::print();
        std::cout << "d:  " << d << std::endl;
    }
};

int main() {
    D d(1,2,3,4);
    d.clear();
    d.print();
}

This correctly outputs. A second way is more complicated, but may allow the structure to grow. Basically, we separate out the printer from the class and then register a list of printers inside each object. When we want to print, we iterate over the list of printers, which then gives us the correct output. I feel this uses too much machinery, but I'll include in case someone else gets a better idea:

// A simple unary function.  Technically, the stl version doesn't require
// the operator
template <typename A,typename B>
struct unary {
    virtual B operator () (A a) {};
};

struct A {
    // Data
    int a;

    // A list of pointers to unary functions.  We need pointers to unary
    // functions rather than unary functions since we need the printer
    // to be polymorphic.
    std::list < unary<A*,void>* > printers;
    A(int a_);

    // We actually end up allocating memory for the printers, which is held
    // internally.  Here, we free that memory.
    ~A() {
        for(std::list < unary<A*,void>* >::iterator printer
                =printers.begin();
            printer != printers.end();
            printer++
        )
            delete (*printer);
    }

private:
    // Require for the dynamic cast used later
    virtual void ___dummy() {};
};
// Prints out the data for A
struct A_Printer : public unary<A*,void>{
    void operator () (A* a) {
        std::cout << "a:  " << a->a << std::endl;
    }
};
// Adds the printer for a to the list of printers
A::A(int a_) : a(a_) {
    printers.push_back(new A_Printer()); 
}

// Now that the structure is setup, we just need to define the data for b,
// it's printer, and then register the printer with the rest
struct B : virtual public A {
    int b;
    B(int a_,int b_);
};
struct B_Printer : public unary<A*,void>{
    void operator () (A* b) {
        std::cout << "b:  " << dynamic_cast <B*>(b)->b << std::endl;
    }
};
B::B(int a_,int b_) : A(a_), b(b_) {
    printers.push_back(new B_Printer());
}

// See the discussion for B
struct C : virtual public A {
    int c;
    C(int a_,int c_);
};
struct C_Printer : public unary<A*,void>{
    void operator () (A* c) {
        std::cout << "c:  " << dynamic_cast <C*>(c)->c << std::endl;
    }
};
C::C(int a_,int c_) : A(a_), c(c_) {
    printers.push_back(new C_Printer());
}

// See the discussion for B
struct D : public B,public C {
    int d;
    D(int a_,int b_,int c_,int d_);
};
struct D_Printer : public unary<A*,void>{
    void operator () (A* d) {
        std::cout << "d:  " << dynamic_cast <D*>(d)->d << std::endl;
    }
};
D::D(int a_,int b_,int c_,int d_) : A(a_), B(a_,b_), C(a_,c_), d(d_) {
    printers.push_back(new D_Printer());
}

// This actually prints everything.  Basically, we iterate over the printers
// and call each one in term on the input.
void print(A* a) {
    for(std::list < unary<A*,void>* >::iterator printer
            =a->printers.begin();
        printer != a->printers.end();
        printer++
    )
        (*(*printer))(a);
}

int main() {
    D d(1,2,3,4);
    // This should print 1,2,3,4
    print(&d);
}

<---EDIT 2--->

tmpearce had a good idea to accumulate all of the information in a hash table prior to assembling it. In this way, it's possible to check if the individual information has been created yet and prevent redundancies. I think this is a good idea when the information can be assembled easily. If this is not the case, a slight variation may work, which combines the ideas of tmpearce and Cristian. Here, we pass around a set (or hashtable, or whatever) that keeps track of whether or not a function has been called. In this way, we can check whether or not some function has been computed. It doesn't require perpetual state, so it should be safe to call multiple times:

#include <iostream>
#include <set>

struct A {
    int a;
    A(int a_) : a(a_) {}
    virtual void print_(std::set <std::string>& computed) {
        if(computed.count("A") > 0) return;
        computed.insert("A");
        std::cout << "a:  " << a << std::endl;
    }
    void print() {
        std::set <std::string> computed;
        print_(computed);
    }
};

struct B : virtual public A {
    int b;
    B(int a_,int b_) : A(a_), b(b_) {}
    virtual void print_(std::set <std::string>& computed) {
        A::print_(computed);
        if(computed.count("B") > 0) return;
        computed.insert("B");
        std::cout << "b:  " << b << std::endl;
    }
};

struct C : virtual public A {
    int c;
    C(int a_,int c_) : A(a_), c(c_) {}
    virtual void print_(std::set <std::string>& computed) {
        A::print_(computed);
        if(computed.count("C") > 0) return;
        computed.insert("C");
        std::cout << "c:  " << c << std::endl;
    }
};

struct D : public B,public C {
    int d;
    D(int a_,int b_,int c_,int d_) : A(a_), B(a_,b_), C(a_,c_), d(d_) {}
    virtual void print_(std::set <std::string>& computed) {
        B::print_(computed);
        C::print_(computed);
        if(computed.count("D") > 0) return;
        computed.insert("D");
        std::cout << "d:  " << d << std::endl;
    }
};

int main() {
    D d(1,2,3,4);
    d.print();
}

In any case, I'll mark this problem off as solved. Though, I'd always like to hear additional answers.

Answer 1

My approach would sort of combine the ones you've mentioned. I'd make the virtual method do something a bit different:

class A
{
   public:
   virtual void getInfo(std::map<std::string,std::string>& output)
   {
      if(output.count("A") == 0)
      {
         output["A"] = "a: 1";
      }
   }
   void print()
   {
      std::map<std::string,std::string> m;
      getInfo(m); //virtual method (most derived will be called)
      std::map<std::string,std::string>::iterator iter = m.begin();
      for(; iter!=m.end(); ++iter)
      {
         std::cout<<iter->second();
      }
   }
};

class B : public A
{
   virtual void getInfo(std::map<std::string,std::string>& output)
   {
      A::getInfo(output);
      if(output.count("B") == 0)
      {
         output["B"] = "b: 2";
      }
   }
};

print is now a non-virtual method that uses getInfo to populate a container, then iterates over it display/save the output. Each class can thus check to make sure the container doesn't already contain the desired output for that level of the inheritance chain before writing and adding the string to the container.

Answer 2

I'd add a private flag to A struct (and to B and C if diamond extends beyond one level) and checking it & marking it as already traversed. This would also help in more complicated (nested) diamond patterns.

Like this:

struct A {
    int a;
    A(int a_) : a(a_) {traversed = false;}
    virtual void print() {
        if (traversed) return;
        std::cout << "a:  " << a << std::endl;
        traversed = true;
    }
private:
    bool traversed;
};

Answer 3

Only one class constructs the virtual base (the most derived, D) so I would ensure only one class prints the A object, and like its construction, make it happen first (possibly important if you're writing objects to disk.)

You could add a void* argument to A's constructor and store it in a member of A. Each derived class would construct the virtual base as A(a, this).

Add a new member function to A, do_print(void*) and have every derived class call do_print(this) instead of A::print(). The do_print(void*) function compares its argument with the stored void* passed to the A ctor and only prints if it's the same. This relies on every derived class having a distinct address, which will be true if all the classes are non-empty, but if that assumption holds it ensures only the most derived object prints the virtual base.