ACCU Home page ACCU Conference Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Google+ ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

pinExperiences of Implementing the Observer Design Pattern (Part 3)

Overload Journal #41 - Feb 2001 + Design of applications and programs   Author: Pete Goodliffe

In the previous two columns of this 'accidental' series [Goodliffe1] [Goodliffe2] I presented a number of implementations of the Observer design pattern [Gamma-] in C++. The Observer pattern allows an object (which we will call the Notifier) to multicast events to other interested objects (the Listeners). These interested objects can register or revoke their interest at run time.

Following the prior two articles I have devised a far superior implementation. This implementation is:

  • type safe,

  • flexible,

  • efficient,

  • generic,

  • safe (this is one of the important features here),

  • allows any number of callbacks per interface,

  • allows any number of parameters per callback,

  • comes very close to the original design goal I had in mind: the Java listener interface idiom.

It also uses some advanced C++ idioms that will be interesting for the less experienced C++ programmer to learn about. It is a neat, elegant piece of code. Remember that my application of the Observer pattern is as part of the public API of a C++ library, this motivates some of my design decisions.

I guess that these three articles have been a diary of my voyage of discovery. However, this does not mean that this third instalment necessarily represents the pinnacle of Observer pattern implementation. In the previous articles we have covered some interesting ground, and discovered some of the pitfalls of implementation. Furthermore, some of those implementations may be more appropriate to particular situations than this one.

Other approaches

Before I present the implementation, it would be a good idea to get an overview of what other observer implementations exist and are used in the big wide world. This selection will be by no means complete. For each of the items below I urge you to follow the reference and read the article/documentation. Each of them uses C++ in a deep and clever way to present a useful and simple Observer pattern framework.

Troll Tech's Qt signals/slots [Qt]

This is a novel approach, based on 'signals' (messages) and 'slots' (message destinations). Qt is a very neat GUI library that works on Unix and Win32. The KDE desktop environment is based upon it. I have a lot of respect for their approach. It is very flexible, type safe and certainly inventive. However, it has a number of drawbacks which make it impractical for my use. First, it would necessitate a dependency on a GUI library (which is far too large a dependency for small code libraries). Second, it requires the generation of some implementation code for each class using signals or slots. This 'meta class' code will enlarge the code base[1]. Thirdly, as a consequence of this a meta compilation stage is required to automatically generate this code.

The Qt approach adds extensions to the C++ language (i.e. the signal and slot keywords) to provide a very flexible implementation. However, I am looking to stay strictly within the bounds of standard C++[2].

Rich Hickey article "Callbacks in C++ Using Template Functors" in C++ Report [Hickey]

Hickey has some strong views on what a callback is/should be, some of which I am not sure I agree with. He reviews some of the approaches and describes their shortfalls (interestingly, he slates a simplistic version of what I present below). However, he presents a novel method of using templates to create a type-safe and generic callback system. However, as presented in the article the system is not as flexible as we would like. For example, multiple numbers of callbacks can be stored in a vector and iterated over. However, for each notifying object you have to write attach/detach/iteration code from scratch.

Mark Bartosik article "Encapsulating the Observer Pattern" in C/C++ Users Journal [Bartosik]

Now this is a really nice solution. I will not say too much about it because my implementation is based heavily on Bartosik's work. I include him in this list because I do not deserve credit for what he has already done. Although based on Bartosik's design, this implementation augments his work in several key areas.

I have to say that I was surprised that hardly anyone replied to my calls for other Observer implementations in previous articles. Either people do not have any better implementations (I find that hard to believe), did not read the article (my heart sinks) or could not be bothered (in which case, I now encourage you again to respond - you do not have to write an article, just mail me your code). If you know of any other good implementations provided by off-the-shelf libraries, then please write in to let us know.

The ideal solution

Perhaps the first question we should ask ourselves when designing an implementation of the Observer design pattern is what would we like it to look like? The ideal system would:

  • Be type safe

  • Be really easy to use

  • Be efficient (in terms of both time and space)

  • Does not involve inheritance; this would reduce the coupling in class designs. This requirement could perhaps be relaxed to the extent that listeners should not inherit from a base class, but notifiers may.

  • Allows messages to be passed around with any number of parameters - again in a type safe manner. (Qt allows you to have a listener that does not use every single parameter of a message, but this would be a nice feature, not a requirement; perhaps we could write adaptors).

  • Can connect an event to anything (e.g. a function or member function).

  • Can cope with listener objects being deleted safely; events will not be sent to 'nothing' via a dangling object reference - this only leads to curious core dumps.

  • Similarly, can cope with notifying objects being deleted.

  • Each notifier can send any number of different events (out of a set fixed at compile time).

  • A listener can listen to any number of notifiers, and can register and revoke an interest dynamically, not just at construction/destruction.

  • Can filter out events that are of no interest to the listener (of course, this could be done by the listener if needs be).

This list has been compiled from my requirements and those of the other systems described above. Now, I will admit at this stage that we are not going to be able to provide all of these features. However, we will get pretty close.

What's really wrong with my previous efforts [Goodliffe1] [Goodliffe2]?

  • Complex to use and not entirely intuitive

  • Dual inheritance hierarchy

  • No parameters in events, and only one type of event per Notifier

  • Requires casting = not type safe

What's wrong with Qt?

  • The meta compiler and code bloat

  • All objects have to inherit from a base QObject

What's wrong with Rich Hickey's?

  • Cannot cope with a destination or source object being deleted

  • Cannot have a type with several different notification types conveniently

Design 10

Now we have a good understanding of the problem space, let us see the new implementation. I have deliberately laboured this background information so that when the implementation is presented the reader can see exactly what problems are solved, and therefore why it is so neat.

This approach is based on Bartosik's implementation [Bartosik]. What I chiefly add to his work is object safety: the ability to safely delete either a Notifer or a Listener without your program crashing at some random point in the future when a dangling pointer is dereferenced. I also remove some complications to the core implementation that he provides. These are discussed in the Extensions section later.

First I will describe how to use the framework, then we will see how it is implemented. This is presentation in order of increasing complexity!

How to use the framework

The use of this notifier framework is simple. Using the good old examples of the Exhibitionist and Voyeur classes (which are types of Notifier and Listener, respectively) we would write something like the following. First we forward declare the class that will be sending the events.

class Exhibitionist;

Next we define an interface for this class to call back to. This interface defines the events that the Exhibitionist can send. Note that we must include a typedef describing the type of the Notifier class. This is needed by the implementation of the framework later on. In this example we have only one event. Note that I prefix its name with Exhibitionist_. I have found this to be a useful convention, use it at your discretion.

class ExhibitionistListener {
  public:
    typedef Exhibitionist notifier_type;
    virtual void Exhibitionist_Event (Exhibitionist *src, int data) {}
};

Note that the callback methods are required to be virtual (the system will not work otherwise), and that the method provides a default implementation that does nothing. You could define the method as pure virtual (i.e. write "= 0;" rather than "{}"). Like this, however, you can chose to only handle some events and do nothing for others by being selective in your overriding.

Now that the interface is defined we can implement a Voyeur class in terms of it. This is shown below. Note that the Voyeur inherits from Listener<ExhibitionistListener>. This class inherits from the ExhibitionistListener directly. Therefore the Voyeur can redefine the interface's virtual methods to act on any notifications.

class Voyeur : public Listener<ExhibitionistListener> {
  public:
    void foo(Exhibitionist *e) {
// we want to listen to the Exhibitionist
      attachTo(e);
    }
    virtual void Exhibitionist_Event (Exhibitionist *src, int data) {
      cout << "Moo " << data << '\n';
    }
};

If you call Voyeur::foo the Voyeur will attach itself to the specified Exhibitionist. Whenever this Exhibitionist raises an Exhibitionist_Event then the Voyeur object will receive the event and moo accordingly. The Voyeur can explicitly disconnect itself from an Exhibitionist by calling a detachFrom(Exhibitionist *) method.

So finally it remains for us to see how to implement an Exhibitionist. Again, it is simple.

class Exhibitionist : public Notifier<ExhibitionistListener> {
  public:
    doSomething(){
      notify( &ExhibitionistListener::Exhibitionist_Event, 10);
    }
};

That is it! Now if you call Exhibitionist::doSomething it will send an event to all attached listeners.

You will note that in the notification we only specify one integer parameter (as well as the actual callback method), although the interface method had two parameters. The framework automatically provides the first parameter as a pointer to the source object. This means that when you define an interface you have to bear this in mind.

Why have I done this? I have found that it is generally useful to know which the source object is when handling a notification. This is especially useful when you are listening to more than one object of the same type. Perhaps this is specific to my application of the pattern (somehow I doubt this).

Although I have not shown it here, the system provides a mechanism for Listeners to be automatically informed of when Notifiers are deleted which is often very useful. However, the real bonus of the whole system is this: if either of the Voyeur or Exhibitionist objects are deleted, the link between them is automatically broken (we will see how later). This is what makes the system simple and safe to use.

Just in case you find it hard to visualise, the hierarchy of classes involved looks something like this (although the Listener<> is in fact inheriting from ExhibitionistListener).

Figure 1.

Strengths/Drawbacks

As you can see, a system of this type is generic (not limited to a few interface types) type safe (parameter types are preserved and C++ conversions can be employed), flexible (allows any number of event types each with any number of parameters, modulo the implicit src pointer), and above all really easy to use (partly due to the safety features provided).

The only major wish-list features we have not provided are the ability to call non-member functions (we can create adaptors to do this) and the freedom from inheritance. However, this latter ideal is not really attainable since you need to inherit from a base class to gain the notification implementation.

How the framework is implemented

Since using the Notifier and Listener classes is deceptively simple there has to be some hairy code making it work in the background. This is where it gets interesting.

In order to show the full implementation we will add functionality a step at a time. The full versions of the Notifier and Listener classes are heavily interdependent in order to implement the safety features. I have ordered some of the following code to aid the reader. You should (hopefully) be able to read from the top down.

The Notifier implementation looks roughly like this:

template <class interface_type> Listener;
template <class interface_type>
class Notifier {
  public:
    typedef Listener<interface_type> listener_type;
    friend listener_type;
  private:
    std::vector<listener_type*> listeners;
  protected:
    template <typename func_type>
    void notify(func_type func);
    template <typename func_type, typename p1_type>
    void notify(func_type func, const p1_type &p1);
    template <typename func_type, typename p1_type, typename p2_type>
    void notify(func_type func, const p1_type &p1, const p2_type &p2);
    virtual ~Notifier();
  private:
// only called by listener_type, returns whether call is valid
    bool attach(listener_type *listener){
      if(find(listeners.begin(), listeners.end(), listener) != listeners.end())
          return false;
      listeners.push_back(listener);
      return true; 
    }
    bool detach(listener_type *listener) {
      if (find(listeners.begin(), listeners.end(), listener)== listeners.end())
         return false;
      listeners.erase(listener);
      return true;
    }
    typedef Notifier<interface_type> self_type;
    typedef typename interface_type::notifier_type c_notifier_type;
    Notifier(const self_type &);
    self_type &operator=(const self_type &);
    void doEvent(const AbstractEvent<interface_type>&);
};

What we have seen above is basically the management of a list of Listener objects. The other interesting point that can be seen is that we have declared a version of the notify method for each number of parameters which we want to support. This is a running theme through the implementation. In the code above we can handle notifications with 0-2 parameters. You can extend the implementation as required[3]. Note that the notify functions are template members. This allows us to provide callback methods with any type of parameters in a type safe way.

Note that the c_notifier_type typedef describes the concrete Notifier type that will inherit from this class. We need this in the implementation later on.

Now to implement the notify methods, we define a template functor (in a similar vein to [Hickey]) to call the appropriate method on the interface_type. We define a simple abstract interface for this functor:

template <class interface_type>
class AbstractEvent {
  public:
    virtual void operator()(interface_type *listener) const = 0;
};

Now we add a doEvent method to the Notifier class interface that iterates over every attached Listener and invokes the functor on it. This is called by each of the notify methods.

void doEvent(const AbstractEvent<interface_type> &event){
  for (size_t i = 0; i < listeners.size(); i++) {
    event(listeners[i]);
  }
}

It is the Event class (that inherits from the AbstractEvent) that does the clever stuff - calling the appropriate interface method. Before showing the class let us see how the notify methods create Event objects. This shows the case of one extra parameter, extend or contract accordingly for the others:

template <typename func_type, typename p1_type>
void Notifier::notify(func_type func, const p1_type &p1){
  typedef Event<interface_type, func_type, c_notifier_type, p1_type> event_type;
  doEvent(event_type(func, static_cast<c_notifier_type*>(this), p1));
}

Although this does not mean much on its own, it will be helpful to bear in mind as you read the definition of the Event class. Again it is declared for 0-2 parameters and may be extended accordingly. The definition of arg_count and num_type follow, with a discussion of the code.

template <class interface_type, typename listener_func,typename p1_type = def_type,
          typename p2_type = def_type>
class Event : public AbstractEvent<interface_type> {
  public:
    explicit Event(listener_func func, const p1_type &p1 = p1_type(),
                   const p2_type &p2 = p2_type())
       : func(func), p1(p1), p2(p2), {}
    virtual void operator()(interface_type *listener) const {
      const unsigned int argCount = arg_count<p1_type>::count
                                  + arg_count<p2_type>::count;
      if (listener) invokeImpl(listener, num_type<argCount>());
    }
  protected:
    template <class T>
    void invokeImpl(T *listener, num_type<0>) const {(void)(listener->*func)(); }
    template <class T>
    void invokeImpl(T *listener, num_type<1>) const {(void)(listener->*func)(p1); }
    template <class T>
    void invokeImpl(T *listener, num_type<2>) const {(void)(listener->*func)(p1, p2);
    }
  private:
    const listener_func func;
    const p1_type       p1;
    const p2_type       p2;
};

The constructor stores the callback method to call and the parameters with which to call it. If you do not instantiate the template class with all the parameter types then a def_type is supplied. This is a dummy type that represents 'not used'. It looks like this:

  class def_type {};

It is the operator() method that works out how many parameter types have been supplied, by using the arg_count class - this works out how many of the template parameters were explicitly specified (the others will be def_type). arg_count looks like this:

  template <typename T> struct arg_count { enum { count=1 }; };
  template <> struct arg_count<def_type> { enum { count=0 }; };

You may like to look at that a little more just to work out how the argCount variable gets to hold the number of func_type parameters that have been specified.

Using this value, operator() selects one of the overloaded invokeImpl methods to call. There is one of these for each of the number of parameters supported (0-2). We use another clever template 'macro' num_type to select only the relevant invokeImpl. The invokeImpls are template member functions when they need not be (after all the T type is already known to be interface_type). This is vital though, since only one of these methods will be valid for each event. The other invokeImpls are ignored by the compiler.

num_type is provided by the following innocuous bit of code:

  template<unsigned> class num_type {};

Now, each invokeImpl method calls the appropriate interface_type member function with the appropriate number of parameters.

Now we have seen the entire trace of execution of a Notifier callback. It quite cunning, and perhaps you will need to read it over a couple of times to really appreciate what is going on (I certainly did to check I wrote it correctly!)

The best bit about all these template shenanigans is that it is all worked out at compile time - it has very little runtime overhead at all (the expense is a little auto-generated code, which has a very small practical cost).

Now let us see what the Listener looks like. (Do not worry, the frightening bit is over now.) The Listener obviously provides a mechanism to attach to and detach from Notifiers. It also remembers which Notifiers it is attached to, so that it can detach from them if it is deleted.

template <class interface_type>
class Listener : public interface_type {
  public:
    typedef Notifier<interface_type> notifier_type;
    typedef typename interface_type::notifier_type c_notifier_type;
    friend notifier_type;
  private:
    std::vector<notifier_type*> notifiers;
  public:
// Now whether attachTo and detachFrom are public or protected is your choice, it 
// depends on how you want to use the API
    void attachTo(notifier_type *notifier) {
      if (notifier->attach(this))notifiers.push_back(notifier);
    }
    void detachFrom(notifier_type *notifier) {
      if (notifiers.erase(notifier)) notifier->detach(this);
    }
  protected:
    virtual ~Listener() {
// This provides some of the 'object safety'
      for (size_t i = 0; i < notifiers.size(); i++) { notifiers[i]->detach(this); }
    }
  private:
    typedef Listener<interface_type> self_type;
    Listener(const self_type &);
    self_type &operator=(const self_type &);
};

That is not really too hair raising. There is one member function that I have left out, which I now present. This is the mechanism by which a Listener can be automatically informed when a Notifier is deleted.

The Listener declares a protected method using the c_notifier_type typedef:

  virtual void Notifier_Deleted(c_notifier_type *notifier) {}

This can be reimplemented by concrete Listener classes (for example, the Voyeur class) if they want to know when their Notifier is deleted. The Voyeur would override Notifier_Deleted(Exhibitionist *src), for example.

This is called by a private Listener method, which is in turn called by the Notifier destructor. This is why the notifier_type is a friend of the Listener class. Here is the final private Listener method:

  void NotifierImpl_Deleted(c_notifier_type *src) {
    notifiers.erase(static_cast<notifier_type*>(src));
    this->Notifier_Deleted(src);
  }

Finally, we see how the Notifier destructor calls this:

template <interface_type>
virtual Notifier::~Notifier(){
  for (size_t i = 0; i < listeners.size(); i++){
    listeners[i]->NotifierImpl_Deleted(static_cast<c_notifier_type*>(this));
  }
}

This completes the description of the implementation of the Observer pattern. It involves some fairly complex C++ code, so you may want to go over it again. Whilst it is a lot to take in, it is in fact a really elegant and neat solution. The Getting the Code section at the end of this article describes where you can download the complete implementation. You may find this useful.

Note that in my 'real' version the implementation classes (Event, def_type et al) which clutter the global namespace unnecessarily have been hidden (slightly) within an Impl namespace. This prevents the user from becoming unnecessarily caught up in the implementation details. It also contains another slight modification, described in the next section.

Tailoring it to the real world

Now that is such a neat solution there must surely be a drawback.

When I first started using this implementation in the TSE3 library [Goodliffe3] in place of the earlier version presented in the previous article [Goodliffe2] I was somewhat shocked to see how much my code grew by. We all know the old adages about templates leading to code bloat, however, such large file size increases were pretty hard to comprehend.

<colgroup> <col> <col></colgroup> <tbody> </tbody>
TSE3 library prior to new implementation ~ 5 Mb
TSE3 library after new implementation ~ 16 Mb

Table 1.

If this was the consequence of using this new approach then it could simply not be justified.

So I began an investigation into what was going on. When compiling small stand-alone programs I could not find a significant difference in file size, and it was this that lead me to discover what the real problem was.

The TSE3 library is built under Linux as a set of shared libraries (using gcc 2.95.2). Each of these shared libraries exports a table of symbol names (i.e. function, class and variable names) that is used to dynamically link a program against it. Small test programs do not have such a table of information.

The small test programs were optimised by the compiler so that all the template tomfoolery shown above was reduced to a few basic instructions. However, despite these optimisations also being performed for the library code, each version of the Notifier and Listener class (i.e. each class which derives from them - in TSE3 there are a lot of these) introduced a bunch of new names into the external linkage table.

The problem names did not come from the Observer implementation, though. They came from our dearly loved standard C++ library. At first I was using std::set rather than std::vector and many, many names of instantiated std::sets were polluting the symbol table. Since STL containers have a number of template parameters (themselves templates), the single mention of a set of a Notifier type which is also itself a template type leads to a name which is easily around 300 characters long. I experimented with some different STL containers to see what difference was made:

<colgroup> <col> <col></colgroup> <tbody> </tbody>
std::set ~ 16 Mb
std::vector ~ 8.2 Mb
std::list ~ 8.9 Mb

Table 2.

So having found the problem it seemed pretty hard to avoid. I have found a solution. However, it is quite embarrassing. Welcome to Pete's minimalist template-free, type-free container class. Yes, I cast all pointers to void*!

class void_list {
  public:
    void_list();
    ~void_list();
    bool push_back(void *p); // no insertion of duplicate entries
    bool erase(void *p);
    unsigned int size();
    void *operator[](unsigned int index);
  private:
    class impl;
    impl *pimpl;
};

The void_list implementation is hidden behind a Pimpl class [Sutter], and this implementation is in terms of a std::vector. I leave the implementation (basic as it is) as an exercise for the reader.

Using this void_list in the Notifier and Listener classes (with appropriate casts) brought the library size down dramatically. Note that since the library code is doing the casting, not the user, and since the code has been carefully checked to be correct, the implementation can still be reasonably called 'type-safe'.

<colgroup> <col> <col></colgroup> <tbody> </tbody>
void_list ~ 5 Mb

Table 3.

Having used this framework heavily for over three months now, there are a number of other experiences which should be noted.

  1. If you call a notify with wrong parameters, the compiler errors can be somewhat cryptic, steeped in reams of template language, only to be interpreted by the bold of heart. Maybe new compiler technology will fix this.

  2. Being a multiple Notifier involves some syntax overhead. With the version of gcc I am using (2.95.2) not specifying which notify causes the compiler to bomb completely. It can be worked around by specifying an explicit function (e.g. Notifier<ExhibitionistListener>::notify(...) ). I am not sure whether the compiler should actually be able to deduce the correct member function, but I am pretty sure it should. I need a language lawyer to tell me.

Extensions

  1. One possible extension to this system is providing a delayed callback when the notify method is called. This may avoid some re-entrancy problems and reduce overhead in some cases, for example in the case where an event handler may itself cause several other notifications to be raised. It may also prevent infinite looping if only one notification is buffered at a time. It also, however, imposes some overhead (OS timer events have to be set up) - this may be OK for GUI updates, maybe not so good for other more real-time notifications.

  2. With multiple threads accessing the Notifier and Listener objects, some locking is required to ensure correct operation.

Conclusions

In the previous article I suggested that it is impossible to construct the perfect Observer pattern implementation. The version presented here is certainly much better than my previous efforts, however at a cost (mainly a slight growth in code size).

Which kind of implementation of the Observer design pattern you use will largely depend on your needs. Different implementations are tailored to different circumstances, and need varying degrees of trade-off between factors such as speed, type safety, simplicity, public visibility, and code size.

I hope that this article has been useful, and once again invite people to respond with their 'killer' Observer pattern implementations. This time I promise that I shall try not to write a forth article in the series. We will see...

Getting the code

The implementation code for this article is available as a part of the TSE3 library, available from http://TSE3.sourceforge.net. Get the 0.0.18 version for the code to match this article[4]. See the file src/tse3/Notifier.h in the source archive for the implementation. There is online documentation for the Notifier class at

http://TSE3.sourceforge.net/doc/api/TSE3__Notifier.html.

The library also shows some heavy duty use of the mechanism to prove it really works.

References

[Goodliffe1] Pete Goodliffe. Experiences of Implementing the Observer Design Pattern (Part 1). In: Overload 37, 2000.

[Goodliffe2] Pete Goodliffe. Experiences of Implementing the Observer Design Pattern (Part 2). In: Overload 38, 2000.

[Gamma-] Gamma, Helm, Johnson, Vlissades. Design Patterns - Elements of Reusable Object-Oriented Software. Addison-Wesley, 1995. ISBN: 0201633612.

[Qt] Trolltech. The Qt Library. http://www.trolltech.com

[Hickey] Rich Hickey. Callbacks in C++ Using Template Functors. 1994. In: C++ Report, February 1995. Available from: http://www.bestweb.net/~rhickey/functor.html

[Bartosik] Mark Bartosik. Encapsulating the Observer Pattern. In: C/C++ Users Journal, October 1998. Available from: http://www.cuj.com/archive/1610/feature.html

[Goodliffe3] Pete Goodliffe. Trax Sequencer Engine Version 3. Available from: http://TSE3.sourceforge.net/

[Sutter] Herb Sutter. Guru of the Week #24. Available from: http://www.peerdirect.com/Resources /gotw024.html (Also in: Herb Sutter. Exceptional C++. Addison-Wesley, 2000. ISBN: 0-201-61562-2.)



[1] More so than the code generated in my implementation.

[2] As an aside, however, I have used the Qt library to implement a program that uses my library with the Notifier framework. The two systems can be successfully used alongside each other.

[3] In my real implementation I support 0-4 parameters. Any more and you begin to ask yourself whether the callbacks are providing the right information.

[4] I have butchered the purity of the design somewhat in later versions to slightly improve performance. These modifications may be interesting for the reader to look at.

Overload Journal #41 - Feb 2001 + Design of applications and programs