Click here to Skip to main content
13,349,997 members (48,504 online)
Click here to Skip to main content
Add your own
alternative version


28 bookmarked
Posted 15 Aug 2004

Composites-Visitors pattern: the OOP way

, 15 Aug 2004
Rate this:
Please Sign up or sign in to vote.
An implementation of the composite-visitors pattern avoiding the use of rescursive generic code.


This article is the natural evolution of the "comparing coding approach" series, and can be an answer to the corresponding article of Dave_H, with the same subject.

Disclaimer (or ... some opinion about)

This article doesn't want to be a part in a religion battle: I already explained - I hope - that I'm not interested in this kind of religious disputes. My interest is to evaluate the possible alternatives.

What Dave presented is a pretty good and elegant solution fully based on the generic programming techniques, but with the need of some RTTI features to handle polymorphism. I also used those techniques, mainly in code like the one I presented to create W32 reference counting wrappers. Here, I just want to show the "other face of the medal" using mainly RTTI and OOP, with some template decoration. Whenever using one or the other ... mostly depend on the need of the application you are deploying, and ... why not, on your personal opinions.

All those "template based" solution have in common the so called "curiously recurring template pattern": a template class takes as a template parameter a class that is supposed to be derived from the template class itself. This allows the base to call functions that are supposed to be implemented in the derived by casting the base "this" into a derived*. See the cited articles for all the samples. Briefly:

template <class TDerived>
class CBase
    void basefn()
    {   static_cast<TDerived*>(this)->derivedfn();    }

class CDerived: public CBase<CDerived>
    void derivedfn() { /* do something specific here */ }

Another approach, use template derived instead of template bases, like this other article. Briefly:

class CBase
    void basefunction() { /* do something specific */ }

template<class TBase>
class CDecorator: public TBase
    void decorate() { basefunction(); }

The limit of both this approaches is the impossibility to handle runtime polymorphism: objects of different types cooperating in the same data structure.

This situation (as stated in the cited article) requires necessarily RTTI and dynamic_cast.

But here comes the point: stated that you cannot do without V-tables and RTTI descriptors, do you still need CRTP?

After all, it allows to call functions in the derived from a base. But ... this can be done by virtual functions.

So, here I propose a way to implement that paradigm using generic code as a minimum, and most of the code using traditional OOP.

The result is an implementation that is translatable by the compiler as a set of classes. Not code that is re-injected every time a new class requires it.

This makes me able to separate the code of the implementations (to be placed into a library) from the code of the application (to be placed in their respective projects). It will be the linker to bind (various) OBJs into EXE, not the compiler to generate all the code into a single (or few) OBJs.

The main design rules

There are people who consider insane multiple inheritance, but consider "good things" templates with many parameters. I don't see any particular difference between the two: they are perfectly dual. So, I'll use multiple inheritance and multiple parameter templates, mainly referring the "multiple partial implementation" methodology described in the "comparing" article.

The general scheme

In this implementation, I'll follow this general scheme:

General Scheme

I don't want to worry about true or assumed inefficiency of inheritance, virtual bases, or multiple inheritance, rather than template injections. I just want to have a code that can be independently translated as possible, using all the available features to keep the design enough elegant and modular. Performance is not the "key factor", although I will pay an attention to that also.

Object ownership

Since we're going to implement collection of polymorphic objects, we will need to refer them in terms of "pointer to common base". And this leads to the old problem "who owns that object?" (That is: who will have the right to destroy it?)

Although it is not a universal solution, reference counting is a good compromise. In this case, however, I'll not go through more or less complicated policy driven smart pointers, but through a "template and interface" mixing.

Composites - visitors

Composites are objects containing other objects. Their natural aggregation is a tree, but not a sort of std_like::tree<T> (where T elements are unaware of being part of the tree), but a tree composed by tree nodes, where the object themselves are the nodes, and are polymorphic.

Visitors are sort if object iterators, able to walk through the structure and dereference into the hold objects.

Data cast-ers

If the structures are built up in terms of common base pointers, accessing the object components (inside the derived classes) requires a dynamic_cast from the common base into the required components. This (binary) code is clearly different from component to component, so this is a good point where templates have a real advantage: they can generate the code from a common source.


Collections are containers of homogeneous types, whose activities do not depend specifically on the hosted types, and where the hosted objects have no knowledge about the fact they are collected. So, collections can have a common interface, but they cannot have a common binary code, since this code depends on the hosted object size. So, templates are really effective as the implementation for that interface. Stated this point, STL collections play their right role, even in OOP applications!

Polymorphic collections, instead, can be implemented in terms of homogeneous collection of pointers to a common base. This consideration can lead to the idea of homogeneous collections as a particular case where a polymorphic collection is "accidentally" populated by objects of the same type. But there is a case when this cannot be done: arrays. Arrays require the homogeneous objects to be stored contiguously. (That is: "this+1" must be the next object, and this cannot be done by storing pointers.) And this is somewhat what makes templates always preferable for those tasks.

Now that all the arguments have been introduced, let's go to describe the proposed implementation.

Data Cast-er and cast-able visitors

Since all composites will live on the heap, a very basic data caster will be a small object having a pointer semantics that inject dynamic type conversion and perform the appropriate assignment by decorating (inheriting) a "castable" class.

struct Ptr, is - so - a "template decorator" for a generic TBase that can be inherited by Ptr, providing it some functions:

template<class T, class TBase> //T dervied from TBase
struct Ptr: public TBase
    //TBase must provide:
    // typedef xxx _TRefType //defines the interface it visit
    //  void _assign(_TRefType* p) //required for assignment
    //  _TRefType* _access() const //required for asignment and dereference
    // void _inc(); //required for ++ operator
    // void _dec(); //required for -- operator
    // _TRefType* _subscript(int); //required for [] operator

    typedef typename TBase::_TRefType _TRefBaseType;
    typedef typename T _TPtrType;


Ptr implements all assignment, copy, conversion, subscripting, dereferencing operators (all the classic operators that can take pointers as parameters) auto-converting _TBaseRefType into _Type by a dynamic_cast mechanism.

In particular:

    friend struct Ptr;
    T* _pCached;
    typedef typename TBase::_TRefType _TRefBaseType;
    typedef typename T _TPtrType;
    struct exception: public XException 
    {}; //the exception of this operations
_TPtrType* _convert() const { return dynamic_cast<_TPtrType*>(_access()); }
Ptr() {_pCached = NULL;}
Ptr(const Ptr& p) { _assign(p._access()); _pCached = p._pCached; }
template<class A, class B>
    Ptr(const Ptr<A,B>& p) { _assign(p._access()); _pCached = _convert(); }
Ptr(_TRefBaseType* p) { _assign(p);  _pCached = _convert();}
Ptr& operator=(const Ptr& p) 
   { _assign(p._access()); _pCached = p._pCached; return *this; }
Ptr& operator=(_TRefBaseType* p) 
   { _assign(p); _pCached = _convert(); return *this; }
template<class A, class B>
   Ptr& operator=(const Ptr<A,B>& p) 
   { _assign(p._access()); _pCached = _convert(); return *this;}

operator _TPtrType*() const { return _pCached; }
_TPtrType* operator->() const 
    {if(!_pCached) ThrowExcp<exception>(); return _pCached; }
_TPtrType& operator*() const 
   {if(!_pCached) ThrowExcp<exception>(); return *_pCached; }
bool operator!() const { return !_pCached;  } //no convertible object available
bool operator~() const { return !_access(); } //no object available
void New() { _assign(new T); _pCached = _convert(); }
template<class I> void New(const I& i) 
   { _assign(new T(i)); _pCached = _convert();}
Ptr& operator++() { _inc(); _pCached = _convert(); return *this; }
Ptr& operator--() { _dec(); _pCached = _convert(); return *this; }
Ptr operator++(int) { Ptr r(*this); _inc(); _pCached = _convert(); return r; }
Ptr operator--(int) { Ptr r(*this); _dec(); _pCached = _convert(); return r; }
_TPtrType& operator[](int i) const 
    { _TPtrType* p = _convert(_subscript(i));
if(!p) ThrowExcp<exception>(); return *p; }

Practically, a pure "decorator", referring to the previous scheme. Note that _convert is a dynamic cast from the type provided by the base and the type on that Ptr operates, that is supposed to be somewhat derived from the one provided by the base.

The implementation of Ptr keeps a T* _pChache private value, and performs the type conversion during assignments or copy. All other "read" operators (like *, -> etc.) return the cached value. This contributes to limit the number of casts performed in a normal execution.

Note, also, that - although Ptr is a template - no recursion has been done in its definition.

Reference countable objects

In perfect OOP style, let's start from an interface.

First: interface, for me, is nothing more than an alias for struct. The use of this keyword is, as a consequence, pure suggestion. Although completely empty, it has a v-table, so it's always better to provide them with a virtual destructor. Does nothing ... but it's virtual. Is what is required to let delete to properly work if called with an interface pointer!

A reference countable object can implement IReferable providing a meaning to its abstract functions:

interface IReferable
    virtual void AddRef()=0;
    virtual void Release()=0;
    virtual void Delete()=0;
    virtual ~IReferable() {}

They're all private, since no-one that is not explicit friend should call them directly.

And to have a smart pointer to it, we need a "castable visitor" that translates _assign into Addref and Release.

Since this is specific for IReferable, I defined it as Ireferable::XPtr (internal struct), and made it a friend of IReferable (so that it can call the IReferable function overrides).

struct XPtr //smart pointer to a referable: a TBase for XPtr<TTBASE,>
    void _assign(IReferable* pR);
    IReferable* _access() const;
    typedef IReferable _TRefType;
    IReferable* _pRef;

where _assign is coded as ...

void IReferable::XPtr::_assign(IReferable* pR)
    if(pR) pR->AddRef();
    if(_pRef) _pRef->Release();
    _pRef = pR;

Since we are talking about a stand-alone object, it makes no sense to implement _inc, _dec and _subscript.

Note that AddRef must be called before Release, to be sure that, in case pR == _pRef, the pointed object is not destroyed after the Release.

A smart pointer to IReferable can be obtained as typedef Ptr<IReferable, IReferable::XPtr> PReferable.

In general, given a CSomthingReferable that inherits IReferable, it is possible to define a Ptr<CSomethingReferable, IReferable::XPtr>, whose * and -> operators will automatically cast the held object into a CSomethingReferable.

IReferable implementation: EReferable

To avoid re-implementing the interface on every object, referable object can inherit an implemented IReferable, like EReferable.

It handles a reference counter and implements AddRef and Release by incrementing and decrementing it.

Since we cannot know how complex the inheritance graph for a compound object can be, but since this interface must be only once per instance, virtual inheritance is required.

AddRef and Release are implemented also by calling other virtual "hook" functions, declared as "do nothing", but overridable in the inherited objects: OnAddRef, OnFirstRef, OnRelease, and OnLastRelease.

Now, it is possible to define a referable class by virtually deriving from EReferable and by defining its pointer as Ptr<yourclass, yourclass::XPtr>.

A generic decorator for EReferable: CReferable<U>

For classes or simple types that cannot inherit from EReferable, CReferable does it by inheriting EReferable, hosting an U member, providing U value semantics, and typedef-ining a smart Ptr.

template <class U>
class CReferable: public virtual EReferable
    U _u;
    friend class CReferable;
    CReferable(const CReferable& c) { _u = c._u; }
    CReferable(const U& u) { _u = u; }
    CReferable& operator=(const CReferable& c) { _u = c._u; return *this; }
    CReferable& operator=(const U& u) { _u = u; return *this; }
    operator U&() {return _u;}
    operator const U&() const {return _u;}

    typedef NTypes::Ptr<CReferable, XPtr> Ptr;

Testing unit

Really simple:

using namespace GE_;

typedef NTypes::CReferable<int> CInt;
typedef NTypes::CReferable<double> CDouble;

int _tmain(int argc, _TCHAR* argv[])

        STRACE(trc,1,("Try Block\n"))
        CInt::Ptr pi;

        int r = *pi;
        trc("r = %d\n", r);

        CDouble::Ptr pd = pi; //assign, but cannot convert int* to double*
        double d = *pd; //will throw
        trc("will never reach this message");
    catch(NTypes::XException* pe)
        STRACE(trc,1,("Catch Block\n"))

    trc("End Program\n");
    return 0;


(   1).Begin test
(   1)..Try Block
(   1)..r = 5
(   0)...First reference for 002F0FF0
First-chance exception at 0x796be592 in CompVisit.exe: Microsoft C++ exception: 
    GE_::NTypes::IReferable::XPtr>::exception @ 0x0012fbc0.
(   0)...Last release for 002F0FF0
(   1)..Catch Block
(   1).End Program
Il programma "[2100] CompVisit.exe: Nativo" è terminato con il codice 0 (0x0).

Note that the expression pd = pi is legal, since CInt::Ptr and CDouble::Ptr rely on IReferable::XPtr, and both CInt and CDouble are EReferables.

What cannot be done is defeference pd (with something like d = *pd) when the sustained value is not a CDouble: this - by design - throws the exception.

This is clearly a runtime type casting error, not a static casting as with templates. The compiler cannot detect it, but we can support polymorphism, like in this case:

CInt::Ptr pi, pj;
CDouble::Ptr pd;
pd = pi; //legal: both convert to and from IReferable*
pj = pd; //legal: both convert to and from IReferable*
int r = *pj; //legal: pj holds a CInt
pd.New(*pi); //legal: create a CDouble and initialized to a promoted integer
double s = *pd; //legal: pd holds a CDouble

Note that pj receives from pd what it received from pi that created a CInt. What makes pj able to dereference, it is the nature of the sustained IReferable. Not who passes the value.

Composites - Visitors

The behavior of a composite object can be described by one interface: ITreeNode.

interface ITreeNode:
    public virtual IReferable
    virtual ITreeNode* GetFirstChild()=0;
    virtual ITreeNode* GetLastChild()=0;
    virtual int GetChildrenCount()=0;
    virtual ITreeNode* GetParent()=0;
    virtual ITreeNode* GetPrev()=0;
    virtual ITreeNode* GetNext()=0;
    virtual bool SetParent(ITreeNode* pParent,
                 ITreeNode* pPrevious=NULL)=0;
    virtual ~ITreeNode() {}

    typedef NTypes::Ptr<ITreeNode, IReferable::XPtr> Ptr;

    struct XShallowIterate

    typedef NTypes::Ptr<ITreeNode, XShallowIterate> ItShallow;

    struct XDeepIterate

    typedef NTypes::Ptr<ITreeNode, XDeepIterate> ItDeep;


It defines the functions necessary to navigate between parent, children, and siblings, and to setup this kind of structure.

It also defines its own pointer, the iterator for shallow iteration (iterate between siblings) and deep iteration (iterate into the children).

The difference is in the way the _inc and _dec functions are implemented in XShallowIterate and XDeepIterate.

The _subscript function is also implemented as a repetitive iteration.

All that gives the ItShallow and ItDeep iterators, perfectly working ++, -- and [] operators.

Functions for the implementors

Although the supplied functions are enough from an external point of view, they are not sufficient for an implementor: If I want to implement SetParent, I must set my references to my new parent and siblings, but I also have to tell the parent and the siblings to set their references to myself.

To do this, there are two choices:

  • Consider this problem as internal to the implementation: this means that an implemntor must access the data structures for the implementor of the parent and siblings. This can be done using protected members in a class or struct, but this means that all the objects inside the same tree must, use, or derive, from the same implementation.
  • Consider it as external to the implementation, by putting some more functions to the interface. But such functions should not be accessible from other objects than ... the implementors.

The first is probably the "quick and dirty way". The second is the "right way". But there is a problem: how should those functions be declared? They cannot be public, since they must not be called by anyone. But they must be called by other instances of the derived classes. And even the protected way is not good: it makes those functions inaccessible.

Thus, we need a proxy object (XProxy), declared as protected by the interface, but friend of the interface itself, having public functions: only derived classes can get such proxy, and its functions can call the interface protected functions, that will be overridden by the derived implementations.

Note that the model of having empty interfaces defining abstract functions and manipulators, with partial implementations (the Exxx classes) that can be inherited, is redundant: it allows different implementations of the same interface; but if you don't have such needs, you can avoid to define the Ixxx interface, and start your deployment from the Exxx classes directly.

This gives you one level less of flexibility, but makes you able to define functions in terms of Exxx* (rather than Ixxx*) and can avoid the need of proxies.

An ITreeNode implementation: ETreeNode

Since ITreeNode requires IReferable, ETreeNode may inherit ... EReferable, so that its implementation can dominate the IReferable virtual base.

class ETreeNode:
    public virtual ITreeNode,
    public virtual EReferable
    virtual ITreeNode* GetFirstChild();
    virtual ITreeNode* GetLastChild();
    virtual ITreeNode* GetParent();
    virtual ITreeNode* GetPrev();
    virtual ITreeNode* GetNext();
    virtual bool SetParent(ITreeNode* pParent,
                 ITreeNode* pPrevious=NULL);
    virtual void SetFirstChild(ITreeNode* pN);
    virtual void SetLastChild(ITreeNode* pN);
    virtual void SetPrev(ITreeNode* pN);
    virtual void SetNext(ITreeNode* pN);
    virtual bool OnSettingParent(ITreeNode* pParent,
                 ITreeNode* pPrevious) {return true;}
    virtual void OnSettedParent() {}
    ITreeNode::Ptr _pChildFirst, _pChildLast, _pNext;
    ITreeNode *_pParent, *_pPrev; //backpointer don't refcount.
    virtual ~ETreeNode();

Note the difference in the ERrferable design with respect to ETreeNode:

IReferable has all private functions with its private XPtr as a friend and a public Ptr decorating XPtr. This is because I wanted IReferable::Ptr to be the only object that can manipulate the IReferable functions.

ITreeNode has some public functions because I wanted those functions to be accessible from any situation. But it also has some private functions, with a protected proxy as a friend. This is to let only any descendants to be able to get the proxy and to call, through it, its functions.

SetParent is the only function that can modify the structure. It's implemented through two hooks: OnSettingParent and OnSettedParent.

The first returns a bool: if it returns false, the setting of the parent is refused. This gives a chance to implement sort of "compatibility checking" between objects that candidate to be related.

Testing unit and Sample

Let's imagine some shapes, each having a bounding rectangle. A shape can contain other shapes. We can then have various shapes: in particular: rectangle, circles, and groups.

A sample implementation is in "shapes.h".

Each shape has its own properties, and - by default - inherits the properties from the group it belongs.

interface IShape:
    public virtual NTypes::ITreeNode
    //define our own pointers and iterators
    typedef NTypes::Ptr<IShape, XPtr> Ptr;
    typedef NTypes::Ptr<IShape, XShallowIterate> ItShallow;
    typedef NTypes::Ptr<IShape, XDeepIterate> ItDeep;

    //defines our own public functions
    enum e_shapeattributes { attr_linecolor,
         attr_fillcolor, attr_textcolor, attr__count };
    virtual NTypes::UINT GetAttribute(e_shapeattributes a) =0;
    virtual NTypes::UINT GetDeepAttribute(e_shapeattributes a) =0;
    virtual void SetAttribute(e_shapeattributes attr, NTypes::UINT value)=0;
    virtual void GetBound(SRect& r)=0;
    virtual void SetBound(const SRect& r)=0;
    virtual void Invalidate()=0;

GetDeepAttribute should retrieve the required attribute, and - if it finds it is == -1 - get it from the parent group.

IShape is implemented by EShape, that inherits ETreeNode also (to implement ITreeNode).

From EShape derives EGraphicShape, that also inherits IDrawable and overrides the OnSettingParent hook by inhibiting a shape to be set as a child of a non-CGroup object.

Finally, from EGraphicShape, derives CCircle, CRectangle, and CGroup. Each with its own Draw function.

This gives, globally, this inheritance graph:

sample inheritance scheme

Note: I didn't depict the Ptr<...> decorators: any class may have its own, redecorating XPtr, XIt... etc.

I also introduced IDrawer and CDrawer as do-nothing referrables (just to have something that emulates an HDC on an eventual Windows program).

The test code

I didn't deploy a full Windows application to draw picture, since the scope of this article is only to illustrate coding techniques. But a console main can be the following:

int _tmain(int argc, _TCHAR* argv[])
    STRACE(trc, 1, ("Begin test\n"))

    //create a drawing
    NApp::CGroup::Ptr pDrawing;
    //add in it teo circles
    new NApp::CCircle(pDrawing, NApp::SRect(10,10,60,60));
    new NApp::CCircle(pDrawing, NApp::SRect(80,10,140,60), 0, 7);
    //create a subgroup
    NApp::CGroup* pSubDraw = new NApp::CGroup;
    pSubDraw->SetParent(pDrawing); //palce it into the drawing
    pSubDraw->SetAttribute(NApp::CGroup::attr_linecolor, 4);

    //add two rectangles in the subgroup
    new NApp::CRectangle(pSubDraw, NApp::SRect(20,70,130,120));
    new NApp::CRectangle(pSubDraw, NApp::SRect(20,125,130,150), 5);

    NApp::CDrawer::Ptr pDrw; pDrw.New();

    std::cout << "\nPress any key ...\n";
    trc("End Program\n");
    return 0;

that gives the following debug trace:

(   1).Begin test
(   0)..First reference for 002F10E0
(   0)..First reference for 002F11A8
(   0)..First reference for 002F1278
(   0)..First reference for 002F29D0
(   0)..First reference for 002F2A98
(   0)..First reference for 002F2B68
(   0)..First reference for 002F2C38
(   2)..Drawing class GE_::NApp::CGroup at 3084512
(   2)...Drawing class GE_::NApp::CGroup at 3090896
(   2)....Drawing class GE_::NApp::CRectangle at 3091304
(   2)....Drawing class GE_::NApp::CRectangle at 3091096
(   2)...Drawing class GE_::NApp::CCircle at 3084920
(   2)...Drawing class GE_::NApp::CCircle at 3084712
(   1).End Program
(   0)..Last release for 002F2C38
(   0)...002F2C38 suicide
(   0)..Last release for 002F10E0
(   0)...002F10E0 suicide
(   0)....Last release for 002F29D0
(   0).....002F29D0 suicide
(   0)......Last release for 002F1278
(   0).......002F1278 suicide
(   0)........Last release for 002F11A8
(   0).........002F11A8 suicide
(   0)......Last release for 002F2B68
(   0).......002F2B68 suicide
(   0)........Last release for 002F2A98
(   0).........002F2A98 suicide

and the following output:

Drawing group at 002F10E0 ...

Drawing group at 002F29D0 ...

Drawing rectangle at 002F2B68
        Line color = 5 Fill color = 2 Text color = 3
        placement: (20,125,130,150)

Drawing rectangle at 002F2A98
        Line color = 4 Fill color = 2 Text color = 3
        placement: (20,70,130,120)

end drawing group at 002F29D0 ...

Drawing circle at 002F1278
        Line color = 0 Fill color = 7
        placement: (80,10,140,60)

Drawing circle at 002F11A8
        Line color = 1 Fill color = 2
        placement: (10,10,60,60)

end drawing group at 002F10E0 ...

Press any key ...

Note: "Drawing" has been implemented by writing messages on

<P>The code has been grouped into a static library and two projects using it.</P>
<P>The library is named LTypes, and the projects CompVisit and ReferableTest.</P>
<P>Of course, I don't pretend the projects to be useful to something. I hope this illustration can be used as a sample where multiple virtual inheritance and dominance can be used as valid substitute of templates, allowing a more "modular" code that can be compiled separately.</P>


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Emilio Garavaglia
Italy Italy
Born and living in Milan (Italy), I'm an engineer in electronics actually working in the ICT department of an important oil/gas & energy company as responsible for planning and engineering of ICT infrastructures.
Interested in programming since the '70s, today I still define architectures for the ICT, deploying dedicated specific client application for engineering purposes, working with C++, MFC, STL, and recently also C# and D.

You may also be interested in...

Comments and Discussions

GeneralNice article Pin
Simon Hughes19-Aug-04 5:30
memberSimon Hughes19-Aug-04 5:30 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Terms of Use | Mobile
Web02 | 2.8.180111.1 | Last Updated 16 Aug 2004
Article Copyright 2004 by Emilio Garavaglia
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid