Email	Print Reprint
	add to:
	Del.icio.us Digg Google Furl	Slashdot Y! MyWeb Blink

Copyright (c) 2003 Herb Sutter

The function facility, recently adopted by the C++ standards committee, provides a generalized way of working with arbitrary functions when all you know (or need to know) is their approximate signature. It turns out that this facility enables us to write, among other things, generalized implementations of important design patterns like Observer. Those generalized design patterns, in turn, motivate two small but important extensions to function itself. [Note: In both the two previous columns, I promised to talk about inline in "the next column." Last time I put off inline in order to cover another fun topic, namely private. This time I've again decided to put off inline because I had so much to say about function in my current The New C++ column [1] that it turned into two columns - one to describe function itself (which was the topic of [1]), and one to describe a generalized Observer implementation that uses function and motivates changes and extensions to function (this article). I'm going to stop making promises about inline, but I really do intend to treat it once I stop thinking of even more interesting things to write about.]

In [1], I gave an overview of one of the first two extensions that were approved in October 2002 for the standard library extensions technical report (the "Library TR"): Doug Gregor's proposal for polymorphic function object wrappers. [2] This function facility comes directly from the Boost project [3], an important (and free) collection of C++ libraries available for you to download and try out today.

In brief, the function facility provides a generalized way of working with arbitrary functions when all you know (or need to know) is their signature. In fact, as it turns out, you don't even need to know the target function's exact signature - any target function with a compatible signature, meaning one where the parameter and return types are appropriately convertible, will work just fine. A function can bind to a nonmember function, a member function, or a functor that defines its own operator() and can therefore be called just like a function. (I'm going to use the term "functors" for the latter, instead of the alternative "function objects," to avoid confusion with "function objects" which means objects of the function library facility we're discussing.)

In this article, I'll focus on showing how function lets us simplify and expand the classic Observer pattern. Along the way, I hope to persuade you that Observer (and other patterns like it) compellingly demonstrates not only the usefulness of function, but also why function itself should be further generalized beyond its current state in the draft standard library technical report.

A Motivating Example for function: The Observer Pattern (or, Beyond Singlecast)

Briefly, the Observer pattern "define[s] a one-to-many dependency between objects so that when one object [the subject] changes state, all its dependents [its observers] are notified and updated automatically." [4] Observer commonly arises in event-driven systems, such as operating systems and GUI environments (e.g., Smalltalk's Model/View/Controller framework), where objects or processes need to respond to state changes elsewhere in the system (e.g., external input) without knowing in advance when they might happen. Allowing such observers to idle and only respond to events as they occur is almost always better than requiring them to perform constant polling, or busy-waiting, just in case an event might have happened since the last time the observers looked in on their subject.

As described in [4] in an object-oriented form, a Subject lets observers register themselves for later callback. The observers inherit from a common base class, and the subject keeps a list of base class pointers. Figure 1 shows the structure of this object-oriented form of Observer:

The code might look something like the following Example 2 (adapting the example in [4]). I've kept Subject's member functions as virtual for consistency with [4], even though it's debatable whether or not that is a generally useful choice.

// Example 2: A sample OO Observer implementation
//
class Subject;

class Observer {
  // ...
public:
  virtual void OnUpdateOf( Subject* ) = 0;
};

class Subject {
  // ...
public:
  virtual void Attach( Observer* o ) { obs_.insert( o ); }
  virtual void Detach( Observer* o ) { obs_.erase( o ); }
  virtual void Notify() {
    for( set<Observer*>::iterator i = obs_.begin(); i != obs_.end(); ++i )
      (*i)->OnUpdateOf( this );
  }
private:
  set<Observer*> obs_;
};

Here's an example use, following [4]:

class ClockTimer : public Subject {
  // ...
  void Tick() {
    // ... timekeeping logic...
    Notify();	// every so often, tick
  }
};

class DigitalClock : /*...*/ public Observer {
  // ...
public:
  DigitalClock( ClockTimer* t ) : timer_(t) { timer_->Attach( this ); }
  ~DigitalClock() { timer_->Detach( this ); }
  void OnUpdateOf( Subject* timer ) { /* query timer and redraw */ }
private:
  ClockTimer* timer_;
};

Note that in this OO version of the pattern, Subjecthas two limitations: First, it is hardwired to be observable only by an object of a type that inherits from Observer. Second, the callback function itself has to have a prescribed name and exact signature. Both of these limitations arise because Subject stores its observers list using object pointers into a fixed hierarchy. How can we remove these limitations? As a first step, we might think we could alleviate the second limitation somewhat by storing a member function pointer, which would theoretically allow the callback function to have any name, although it would still have to have a fixed signature. There are several problems with this approach: First, for the callback functions to be useful they must still be predeclared as pure virtuals in the Observer base class, which means that although the callback gains some name flexibility, it still has to be one of a predefined set of special known names (reminiscent of Henry Ford's famous quote, "you can have any color you want, as long as it's black"). Second, the Subject would have to store the member function pointer not instead of, but in addition to, the object pointer, so that it knows what object to dispatch to. Fortunately, there is a better way.

Generalizing Observer

Even though storing a member function pointer alone doesn't do the trick, note what happens when we store a generalized function:

// Example 3: A generalized Observer pattern
// structure, using function
//
class Subject {
  // ...
public:
  virtual void Attach( function<void (Subject*)> o ) { obs_.push_back(o); }
  virtual void Detach( function<void (Subject*)> o ) { /* ... */ }
  virtual void Notify() {
    for( list<function<void (Subject*)> >::iterator i = obs_.begin(); i != obs_.end(); ++i )
      (*i)( this );
  }
private:
  list<function<void (Subject*)> > obs_;
};

(Aside: You may have noticed that the set is now a list. Ignore that for now; we'll come back to that issue in a moment.) The first, and moderately amusing, thing to note is that the Observer pattern no longer needs a predefined Observer base class. Of course, if you have one, that still works - here's the same example use as in Example 2, with only slight modifications needed:

class ClockTimer : public Subject { // as before
  // ...
  void Tick() {
    // ... timekeeping logic...
    Notify();	// every so often, tick
  }
};

class DigitalClock : /*...*/ public Observer { // still works
  // ...
public:
  DigitalClock( ClockTimer* t ) : timer_(t)
    { timer_->Attach( bind1st( mem_fun( &DigitalClock::OnUpdateOf ), this ) ); }
  ~DigitalClock()
    { timer_->Detach( bind1st( mem_fun( &DigitalClock::OnUpdateOf ), this ) ); }
  void OnUpdateOf( Subject* timer ) { /* query timer and redraw */ }
private:
  ClockTimer* timer_;
};

But the observer no longer needs to inherit from Observer. Further, the callback function could as easily be named anything, rather than just OnUpdateOf. For example:

class Clock2 /*... no inheritance needed...*/ {
  // ...
public:
  Clock2( ClockTimer* t ) : timer_(t)
    { timer_->Attach( bind1st( mem_fun( &Clock2::Ticker ), this ) ); }
  ~Clock2()
    { timer_->Detach( bind1st( mem_fun( &Clock2::Ticker ), this ) ); }
  void Ticker( Subject* timer ) { /* query timer and redraw */ }
private:
  ClockTimer* timer_;
};

Better still, the callback could be anything, even a nonmember function or a functor, and even one whose signature isn't exactly the same but is callable with parameter or return type conversions:

void TickMe( Subject* timer ) { /* query timer and do something */ }

class Tock {
public:
  void operator()( ClockTimer* timer ) // note, not exact match!
    { /* do whatever */ }
};

Tock tock;

ClockTimer ct;
ct.Attach( &TickMe );
ct.Attach( tock );

The possibilities, now, are truly endless: Any callable function or functionlike entity, without limitation, can observe the subject, even if its signature isn't an exact match. Now that's a Subject that's really "observable"! I hope you'll agree that this is a compelling advantage of using function over one of the more hardwired alternatives, and a compelling structural generalization over the original OO structure for Observer described in [4], which originally worked only with a hardwired inheritance hierarchy and a single preset virtual function name and exact signature match.

An Important Limitation of function

Let's take another look at the generalized Observer pattern in Example 3, this time highlighting the rest of the changes that I didn't highlight before:

// Example 3, reprise
//
class Subject {
  // ...
public:
  virtual void Attach( function<void (Subject*)> o ) { obs_.push_back(o); }
  virtual void Detach( function<void (Subject*)> o ) { /* ... */ }
  virtual void Notify() {
    for( list<function<void (Subject*)> >::iterator i = obs_.begin(); i != obs_.end(); ++i )
      (*i)( this );
  }
private:
  list<function<void (Subject*)> > obs_;
};

In Example 2, the Subject stored a set of pointers to observing objects. Using a set, which stores unique elements, automatically made the subect ignore duplicate observers so that the same observer wouldn't be notified multiple times. (If that's not desirable, it would be easy to switch to using a multiset instead.) But function objects can't be put into a set, because a set is an ordered collection that has to be able to compare its elements; specifically, it requires the ability to decide whether one element is less than another, and function objects are not comparable at all, not even for equality which is the simplest comparison you can have. Therefore, in Example 3:

• We can't use a set to store our list of observers, because there is no operator< (or its equivalent) to enable less<> for function objects. We have to use an unordered collection, such as a list, instead. That's mostly a minor annoyance.
• Worse still, we don't have the option of ignoring duplicates in Attach(), because there isn't even an operator== for function objects. We would need at least some way to compare for equality to determine whether the observer was already in the list or not.
• Worst of all, there's no way to implement Detach at all, for the same reason that we can't ignore duplicates in Attach: there's no way to compare two function objects to see if they're equal to one another. In the code as it stands, once you observe, you always observe until the subject goes away.

This lack of comparison operations is one limitation of function, and it is significant. Even without it, function is still pretty useful; even if we only had == (and therefore also !=), it would be extremely useful. For completeness, I'll point out that there is a partial workaround that unfortunately still falls short: Attach could return a cookie or iterator that the caller would be required to store and later pass back to Detach to specify which function to remove from the list. This workaround would enable us to write Detach, but it's not a realistic solution because of two shortcomings, one major and one minor: The major shortcoming is that it doesn't address the second problem of ignoring duplicates, and so it is at best a partial workaround for specifying the identity of a given functionlike entity. The minor shortcoming is that it adds complication; users just want to add and remove functions, and alternative solutions exist (e.g., .NET delegates) that let users do that by simply naming the function, without requiring them to remember an additional magic cookie or token to refer to that function again later.

Suggested Extension #1: Equality Comparison

function could provide equality comparisons (== and !=). These are the minimum needed to allow functions like Attach to ignore duplicates and to make functions like Detach implementable. This section will describe an implementation that I believe is possible, if not perfect. In brief, we want equality comparison to tell us whether calling two functions will cause the same target function to be invoked; in this case of a member function, this includes the object on which the function will be invoked. So the question is: will the two function objects invoke the same nonmember function? the same member function on the same object? the same functor object? Afunction object always internally refers to one of three things: a nonmember function, a standard binder functor, or some other functor. (When it refers to a member function, it does so through a binder like std::bind1st which binds the member function to a particular object, and so the member function case falls into the "standard binder" category.) Further, the function object knows which of the three kinds of things it is storing. This lets us get close to specifying a workable equality comparison between two function objects a and b, using only equality comparisons on function pointers and on objects (all of which are supported in the C++ standard), plus one little extension I'll describe:

• If a and b are not bound to the same type of entity (nonmember function, or functor), they are not equal.
• Else if a and b are each bound to a nonmember function, they are equal if and only if their internally held function pointers have the same type and compare equal.
• Else if a and b are each bound to a functor that is not a standard binder object, they are equal if and only if the objects have the same type and are the same object (i.e., pointers to the objects compare equal). Note that, because by default function will make a copy of its target, if you want two function objects f1 and f2 bound to the same functor obj to compare equal, be sure to use the ref or cref helper which binds a reference to the object instead of taking a copy; that is, write f1 = ref(obj) and f2 = ref(obj), not f1 = obj and f1 = obj.
• Else a and b are each bound to a functor that is a standard binder (including possibly a binder that binds a member function pointer and an object on which it should be invoked), and they are equal if and only if the binder objects compare equal.

That last part requires a small but significant change to the standard (the "little extension" I referred to above): The existing standard binders also need to be extended to support operators == and !=. Fortunately, implementing equality comparison for binders is straightforward in general, because the standard directly supports pointer equality comparison for all pointer types, including all function pointer types. They would just have to be surfaced through the binders. This gets us the rest of the way, because we can specify a workable equality comparison between two binder objects using the same rules as those already described above for function objects, but adding a new case for member function pointers: If the binder objects c and d are each bound to a member function, they are equal if and only if their internally held member function pointers have the same type, and compare equal and both are bound to the same object (the objects they are bound to have the same type and pointers to the objects compare equal). (Note: Other binder libraries, such as the Boost binder library, may not be able to easily provide equality comparison for all operations.) Some of you may be wondering: "If we're going to provide equality comparisons, then why we don't just take another step and allow <, <=, >, and >= too?" We could, but it would require an additional and more significant change to the standard, because the standard currently supports == and != for all pointer types, but only supports <, <=, >, and >= for pointers to nonmember functions and pointers to objects (via less <>) - it does not support those comparisons for pointers to member functions. An arbitrary ordering could be invented, but == and != alone are what's absolutely necessary to enable functions like Attach and Detach above; the incremental gain we get from having the other comparisons probably isn't justified, at least not by this example.

Suggested Extension #2: Multicast Support

The ability to notify multiple observers is key to the Observer pattern. This demonstrates a common use for functions, namely to implement multicast - the ability to remember, and later fire, multiple functions. The good news is that, to get multicast support, we don't need to change function, we only need to build on it. By direct analogy to the Attach and Detach code in Example 3, we can build a multi_function that supports multicast to an abitrary number of compatible functions, with the caveat that as long as function doesn't provide equality comparison we still can't ignore duplicates when adding functions to a multicast set, and we can't remove functions individually from a multicast set. In a moment I'll show a sample implementation of multi_function. But first, let's see what we want the code using it to look like. Example 4(a) shows how using such a multi_function would look in the ideal case (that is, if function supported equality comparison):

// Example 4(a): Using an ideal multi_function,
// if function supports equality comparison
//
int f( int );
int g( int );
char h( long );

multi_function<int(int)> m;
m += f;		// ok, adds f (synonym for "m.add( f );")
m += g;	// ok, adds g (synonym for "m.add( g );")
m += h;	// ok, adds h (synonym for "m.add( h );")
m += g;	// ok, but ignores the duplicate
m -= f;		// ok, removes f (synonym for "m.remove( f );")
m( 42 );	// calls g and h once each (in some order)

Example 4(b) demonstrates using a multi_function built on only function as it exists today:

// Example 4(b): Using a hobbled multi_function,
// if function does not support equality comparison
//
int f( int );
int g( int );
char h( long );

multi_function<int(int)> m;
m += f;		// ok, adds f
m += g;	// ok, adds g
m += h;	// ok, adds h
m += g;	// ok, adds g again because it can't ignore duplicates
m -= f;		// no-op (or error), impossible to implement with the desired semantics
m( 42 );	// calls f once, g twice, and h once (in some order)

Now we can somewhat simplify the generalized Observer from Example 3:

// Example 5: A generalized Observer pattern
// structure, using multi_function
//
class Subject {
  // ...
public:
  virtual void Attach( function<void (Subject*)> o ) { obs_ += o; }
  virtual void Detach( function<void (Subject*)> o ) { obs_ -= o; }
  virtual void Notify() { obs_( this ); }
private:
  multi_function<void (Subject*)> obs_;
};

If your reaction to first Example 3 and then Example 5 was something like, "boy, that sure simplifies Observer," you're right. In fact, you can now fully library-ize the Observer pattern:

// Example 6: A fully generic pattern implementation
//
template<typename F>
class Subject {
public:
  virtual ~Subject() { }		// see [5]
  virtual void Attach( function<F> o ) { obs_ += o; }
  virtual void Detach( function<F> o ) { obs_ -= o; }
protected:
  multi_function<F> obs_;
};

I chose to make the multi_function object protected so that derived classes can access it directly. Protected data is usually a bad thing, but in this case it didn't seem worthwhile to wrap it with a series of templatized Notify functions (one for each number of parameters) which didn't do anything. Well, that was almost too easy: A complete and generalized implementation of the Observer pattern in a handful of lines of code. Well, maybe this doesn't quite cover all possible subjects, because not all subjects will care about overriding these functions - so while we're at it, let's also provide a nonvirtual version:

template<typename F>
class NonvirtualSubject {
public:
  void Attach( function<F> o ) { obs_ += o; }
  void Detach( function<F> o ) { obs_ -= o; }
protected:
  ~NonvirtualSubject() { }	// see [5]
  multi_function<F> obs_;
};

Any class can now make itself observable by simply inheriting from the appropriate instantiation(s) of Subject<>. Whereas all of our examples so far followed the pattern in [4] where the callback to the observing object included a Subject* argument, that's not always needed and now we can choose to make the observer callback signature anything we want:

class ClockTimer : public NonvirtualSubject<void()> {
  // ...
  void Tick() {
    // ... timekeeping logic...
    obs_();	// every so often, tick
  }
};

And, if we want to be observable by different types of observers, we can combine them to boot:

class OtherTimer	: public NonvirtualSubject<void()>
	, public NonvirtualSubject<int(string)> {
  // ...
  void Tick() {
    // ... timekeeping logic...
    NonvirtualSubject<void()>::obs_();	// every so often, tick
  }

  void Tock() {
    // ... whatever logic...
    NonvirtualSubject<int(string)>::obs_( "tock" );	// every so often, tock
  }
};

Cool, slick, and definitely gnarly. But all of this hinges on multi_function, so it's time to consider the final question: What would multi_function's implementation look like?

Implementing multi_function

When implementing multi_function, we have a couple of design choices to make:

• What should operator() return? We could be invoking an arbitrary number of targets, so should we return all of the values? none of them? one or some of them? some calculated value (e.g., for the special case of bool return values, or'ing them all together)? In my view the only viable choices in the general case are "all" or "none." Implementing the "all" choice just requires the equivalent of constructing a container<ReturnType> containing the return values. That's easy enough to code, but it's usually not preferable and I'll demonstrate the "none" choice below.
• Should there be a constructor option to select whether multi_function ignores duplicates or not? Perhaps. I'll just demonstrate an implementation that always ignores duplicates.

Given those choices, here is a sample implementation of multi_function that is not intended to be complete, but to show how it can be done. I've implemented it in terms of the Boost implementation of function, but after the first few lines it's compatible with the draft standard specification of function, including the standard one is in namespace std::tr1 (for now):

// Example 7: multi_function sample implementation
//
#include <list>
#pragma warning(disable:4224)
#pragma warning(disable:4100)
#include <boost/function.hpp>
namespace tr1 = boost;

template<typename F>
class multi_function : public tr1::function<F> {
public:
  typedef std::list<typename tr1::function<F>::result_type> result_type;
  typedef typename tr1::function<F>::allocator_type         allocator_type;

  explicit multi_function() { }

  // the implicitly generated copy constructor,
  // copy assignment, and destructor are fine

  template<typename F2> multi_function( tr1::function<F2> f ) { l_.push_back( f ); }

  // if you have an implementation of function that supports
  // equality comparison, uncomment the calls to remove
  void add   ( tr1::function<F> f ) { /* l_.remove( f ); */ l_.push_back( f ); }
  void remove( tr1::function<F> f ) { /* l_.remove( f ); */ }

  void operator+=( tr1::function<F> f ) { add( f ); }
  void operator-=( tr1::function<F> f ) { remove( f ); }

  void swap( multi_function& other ) { l_.swap( other.l_ ); }
  void clear() { l_.clear(); }

  bool empty() const { return l_.empty(); }
  operator bool() const { return l_.empty(); }

  void operator()() const {
    for( std::list<tr1::function<F> >::const_iterator i = l_.begin(); i != l_.end(); ++i )
      (*i)();
  }

  template<typename T1>
  void operator()( T1 t1 ) const {
    for( std::list<tr1::function<F> >::const_iterator i = l_.begin(); i != l_.end(); ++i )
      (*i)( t1 );
  }

  template<typename T1, typename T2>
  void operator()( T1 t1, T2 t2 ) const {
    for( std::list<tr1::function<F> >::const_iterator i = l_.begin(); i != l_.end(); ++i )
      (*i)( t1, t2 );
  }

  template<typename T1, typename T2, typename T3>
  void operator()( T1 t1, T2 t2, T3 t3 ) const {
    for( std::list<tr1::function<F> >::const_iterator i = l_.begin(); i != l_.end(); ++i )
      (*i)( t1, t2, t3 );
  }

  // etc.

private:
  std::list<tr1::function<F> > l_;
};

template<typename MF1, typename MF2>
void swap( multi_function<MF1>& mf1, multi_function<MF2>& mf2 )
  { mf1.swap( mf2 ); }

template<typename MF1, typename MF2>
bool operator==( const multi_function<MF1>& mf1, const multi_function<MF2>& mf2 ) {
  // if function doesn't provide comparisons, this is unimplementable
  // if function provides op==, this is inefficient: O(N^2) operation
  // if function provides op<, this is efficient: can keep lists sorted, or use a set
  // for now, install a placeholder:
  return false;
}

template<typename MF1, typename MF2>
bool operator!=( const multi_function<MF1>& mf1, const multi_function<MF2>& mf2 )
  { return !( mf1 == mf2 ); }

I took some shortcuts here, but the code is a working example that you can try out today.

Conclusion: Beyond Observer

Observer is only one of several patterns in [4] whose implementation can be generalized using function; two other examples are Strategy and State (for a description of state machines' implementation in terms of plain function pointers, see also More Exceptional C++ Item 35 [6]). In such patterns, replacing calls to a base class virtual function (whose overrides must always have a fixed signature and can only exist in a predefined class subhierarchy) while a call to a function of the same signature still allows all the calls that were allowed before, as well as calls to functions and functors outside the original inheritance hierarchy, and calls to functions with different but compatible signatures. Thus changing the patterns' structure from an object-oriented structure based on virtual function dispatch to a more generic one that does not depend on inheritance hierarchies lets us broaden and extend the usefulness and flexibility of those patterns.

Postscript

After writing this article, I discovered Phil Bass's recent Overload articles [7] on implementing Observer in C++, which independently discovered some of the same things we've covered in this article. The approach [7] does not mention function, and focuses mostly on developing a function-like Event class. It demonstrates a generalized Observer that does not require a monolithic hierarchy rooted at an Observer base class, but the solution still has the drawbacks of being unable to ignore duplicates or detach specific observers by value (it uses the cookie/iterator workaround for the latter).

Acknowledgments

Thanks to Doug Gregor and Peter Dimov for their comments on drafts of this material.

References

[1] H. Sutter. "Generalized Function Pointers" (C/C++ Users Journal, 21(8), August 2003).

[2] D. Gregor. "A Proposal to add a Polymorphic Function Object Wrapper to the Standard Library," ISO/ANSI C++ standards committee paper (ISO/IEC JTC1/SC22/WG21 paper N1402, ANSI/NCITS J16 paper 02-0060).

[3] www.boost.org

[4] E. Gamma, R. Helm, R. Johnson, J. Vlissides. Design Patterns (Addison-Wesley, 1994).

[5] H. Sutter. "Virtuality" (C/C++ Users Journal, 19(9), September 2001). Available online at http://www.gotw.ca/publications/mill18.htm.

[6] H. Sutter. More Exceptional C++ (Addison-Wesley, 2002).

[7] P. Bass. "Implementing the Observer Pattern in C++," Parts 1 and 2 (Overload 52 and 53, December 2002 and February 2003).

About the Author

Herb Sutter (<www.gotw.ca>) is convener of the ISO C++ standards committee, author of the acclaimed books Exceptional C++ and More Exceptional C++, and one of the instructors of The C++ Seminar (<www.gotw.ca/cpp_seminar>). In addition to his independent writing and consulting, he is also C++ community liaison for Microsoft. 1 | 2 Next Page

RELATED ARTICLES No Related Articles		TOP 5 ARTICLES No Top Articles.