Visitor Pattern

Working on implementing a SceneGraph, I came across the problem of allowing for operations on each node, without polluting the Node class itself. For example, for debugging purposes, I might want to have each node print out its type. So, I would have a Node.getType function, which returns the type of the node.

But, I wouldn't want to have a Node.printType function that prints its type and also recursively traverses its children to print their types.

The visitor pattern does exactly this. Conceptually, it allows for a virtual function to be added to an entire class hierarchy, without having to put the function within the class hierarchy itself. Below is a example for a usage of the pattern. Note that double-dispatch won't be required in case the class hierarchy places a constraint on the visitors to treat the visited nodes transparently, which is perhaps too much of a restriction. 

#include <iostream>
#include <list>
#include <string>

using namespace std;

class Asteroid;
class MyAsteroid;

class IAsteroidVisitor
{
public:
    virtual void visit(Asteroid&) = 0;
    virtual void visit(MyAsteroid&) = 0;
};

class Asteroid
{
public:
    virtual string getType()
    {
        return "Asteroid";
    }

    virtual void accept(IAsteroidVisitor& visitor)
    {
        visitor.visit(*this);
    }
    
};

class MyAsteroid : public Asteroid
{
public:
    string getType() override
    {
        return "My Asteroid";
    }

    string doFunkyStuff()
    {
        return "I do something the normal asteroid can't!";
    }

    void accept(IAsteroidVisitor& visitor) override
    {
        visitor.visit(*this);
    }
};

class AsteroidList
{
private:
    list<Asteroid*> m_pAsteroidList;
public:
    AsteroidList()
    {
        m_pAsteroidList.push_back(new Asteroid());
        m_pAsteroidList.push_back(new MyAsteroid());
    }

    void accept(IAsteroidVisitor& visitor)
    {
        for (list<Asteroid*>::const_iterator i = m_pAsteroidList.cbegin(); i != m_pAsteroidList.cend(); i++)
        {
            (*i)->accept(visitor);
        }
    }
};

class AsteroidPrintVisitor : public IAsteroidVisitor
{
public:
    void visit(Asteroid& a) override
    {
        cout<<a.getType()<<endl;
    }

    void visit(MyAsteroid &ma) override
    {
        cout<<ma.getType()<<endl;
        cout<<ma.doFunkyStuff()<<endl;
    }
};

int main(int argc, char *argv[])
{
    AsteroidList al;
    AsteroidPrintVisitor p;
    al.accept(p);
    return 0;
}

Static type resolution and double-dispatch

Double dispatch is required due to the same reasons as mentioned  here. The fact that overload resolution is done with the static type leads to issues such as the call to a.collideWith shown below, and double dispatch provides a solution to this - look at the call to s.collideWith(a) and the associated sequence of operations in the subsequent comment.

//Double dispatch as mentioned @ http://en.wikipedia.org/wiki/Double_dispatch
#include <iostream>

using namespace std;

class SpaceShip;
class MySpaceShip;

class Asteroid
{
public:
    virtual void collideWith(SpaceShip&)
    {
        cout<<"Asteroid Collided with SpaceShip";
    }

    virtual void collideWith(MySpaceShip&)
    {
        cout<<"Asteroid Collided with mySpaceShip";
    }
};

class MyAsteroid : public Asteroid
{
public:
    void collideWith(SpaceShip&) override
    {
        cout<<"My asteroid collided with spaceShip";
    }

    void collideWith(MySpaceShip &) override
    {
        cout<<"My asteroid collided with mySpaceShip";
    }
};

class SpaceShip
{
public:
    virtual void collideWith(Asteroid& a)
    {
        a.collideWith(*this);
    }
};

class MySpaceShip : public SpaceShip
{
public:
    void collideWith(Asteroid& a) override
    {
        a.collideWith(*this);
    }
};

int main(int argc, char *argv[])
{
    MyAsteroid m;
    Asteroid& a = m;
    MySpaceShip myS;
    SpaceShip &s = myS;
    a.collideWith(s); //overloading is done by static
                      //type -> vfptr lookup, 
                      //myAsteroid.collideWith(Asteroid&)

    s.collideWith(a); //double-dispatch operates -> 
                      //vfptr lookup, 
                      //myspaceShip.collideWith(Asteroid&), 
                      //typeof(*this) = MySpaceShip,
                      //vfptr lookup, 
                      //myAsteroid.collideWith(MySpaceShip&)
    return 0;
}

Factory Patterns

1. The Parameterized factory:

#include <iostream>

class Shape
{
public:
    virtual void Draw() = 0;
};

class Circle: public Shape
{
public:
    void Draw(){ std::cout<<"Circle::Draw"; }
};

class Square: public Shape
{
public:
    void Draw(){ std::cout<<"Sqaure::Draw"; }
};

enum ShapeType{ Shape_Circle, Shape_Square };

class Factory
{
public:
    static Shape& CreateShape( ShapeType shapeType );
};

Shape& Factory::CreateShape( ShapeType type )
{
    switch ( type )
    {
    case Shape_Circle: return *new Circle();
        break;
    case Shape_Square: return *new Square();
        break;
    default: break;
    }
}

int main()
{
    Shape& s=Factory::CreateShape( Shape_Circle );
    s.Draw();
    return 0;
}

Disadvantages: Adding a new type of shape will need changes in the Factory method.

Getting around by the use of templates, we have:

#include <iostream>

class Shape
{
public:
    virtual void Draw() = 0;
};

class Circle: public Shape
{
public:
    void Draw(){ std::cout<<"Circle::Draw"; }
};

class Square: public Shape
{
public:
    void Draw(){ std::cout<<"Sqaure::Draw"; }
};

template <class T>
class Factory
{
public:
    static Shape& CreateShape();
};

template <class T>
/*static*/ Shape& Factory<T>::CreateShape()
{
    return *new T();
}

int main()
{
    Shape& s=Factory<Circle>::CreateShape();
    s.Draw();
    return 0;
}

There we have a much more concise version using the power of templates.

Virtual Functions

Consider the following:

#include <iostream>

using namespace std;

class A
{
public:
    virtual void func1( int a ){ cout<<"A::func1"; }
    virtual void func2( int i=20  ){ cout<<i; }
};

class B: public A
{
public:
    void func1( float a ){ cout<<"B::func1"; }
    void func2( int i=40 ){ cout<<i; }
};

int main(int argc, char* argv[])
{
    A* pb=new B;
    pb->func1(1);
    pb->func2();
    return 0;
}

Can you guess the output for the same?

pb->func1(1) => A::func1!! This is so, because, B::func1 hides( as a result of overloading) A::func1, rather then override it. And in C++, overload resolution is done on the static type, as it is done at compile time.

pb->func2() => 20!! This is so because, although B::func2 is called, the compiler picks up the default value from the base class. So, default values should be the same down the class hierarchy.

As an aside, the C++ standard states that built in conversions have more priority then user defined conversions.

Source: http://www.gotw.ca/gotw/005.htm

C++ variable assignment

Consider the following:

class A
{
int a;
public:
A(){a=0;}
A(int b):a(b){}
A(const A& a1){ a=a1.a; }
A& operator=( const A& a1){ a=a1.a; return *this; }
};

1) A a; => Constructor is invoked

2) A b=a; => Copy constructor is invoked.

A c;
c=b; => Assignment operator is invoked.

A a=10; =>Constructor is invoked to create a temporary A object. Then a's copy constructor is invoked.

Source: Guru of the day 1

Of constants and R and L values

 

RValue: A value that can appear on the right of an expression only
LValue: A value that can appear on the left of an expression. An LValue is converted to an RValue implicitly. The vice-versa does not hold.

An important point: only LValues can be bound to references to non-constants. A temporary object is a RValue.

Consider the following:

#include <iostream>

using namespace std;

class A
{
public:
    ~A(){ cout<<"A"; }
};

class B: public A
{
public:
    ~B(){ cout<<"B"; }
};

B factory()
{
    B temp;
    return temp;
}


int main()
{
    const A& obj = factory();
    return 0;
}
    

This is valid in standard C++, as the const used along with the reference forces the life of the temporary object to the end of the scope of the block rather than the scope of the expression (which is generally the case for temporaries). The const in necessary for performing the above magic. Note here, we have no need for a virtual destructor too!!

Source: http://herbsutter.com/2008/01/01/gotw-88-a-candidate-for-the-most-important-const/

Restricting template types: Requiring member functions

It is desired that a class parametrized by, say a single type argument, T, only be instantiated by types that provide a particular function ( say void foo() )

// T must have void T::foo()  

template <class T>   
class RequireFoo   
{   
} 

A petty solution:

template <class T>   
class RequireFoo   
{   
public:   
   ~RequireFoo(){ void (T::*fptr)() = &T::foo; }   
};

The above solution will throw a compiler error if non foo having class is used as a parameter.

A much cooler solution: Move this check out to a template class

template <class T>   
class CheckFoo   
{   
public:   
   CheckFoo(){ void (T::*fptr) = &T::foo; }   
} 
  
template< class T >  
class RequireFoo: CheckFoo<T>   
{   
} 

Here, the responsibility of checking for foo is checked in base class CheckFoo's constructor which is automatically called when RequireFoo is instantiated.
Ideas from: http://www.gotw.ca/publications/mxc++-item-4.htm

Complete Code:

#include <iostream>

class HasFoo
{
public:
  void foo(){}
};

class NoFoo
{
};

template <class T>
class CheckFoo
{
public:
  CheckFoo(){    void (T::*fptr)() = &T::foo;    }
};

template <class T>
class RequireFoo: CheckFoo<T>
{
public:
};

int main()
{
  RequireFoo< HasFoo > t;
  return 0;
}