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.
September 01, 2003
URL:http://www.drdobbs.com/windows/generalizing-observer/184403873
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.
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, Subject
has 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.
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 function-like
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.
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 subject
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:
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.
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.
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 function-like 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.
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 function
s
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:
a
and b
are not bound to the same type of entity (nonmember
function, or functor), they are not equal.
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.
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
.
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.
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 function
s, with the caveat that as
long as function doesn't provide equality comparison we still can't ignore duplicates
when adding function
s to a multicast set, and we can't remove function
s
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?
When implementing multi_function
, we have a couple of design choices to
make:
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.
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.
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.
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).
Thanks to Doug Gregor and Peter Dimov for their comments on drafts of this material.
[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).
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.
Copyright (c) 2003 Herb Sutter
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.