Templated implementation of the Visitor Pattern for C++11

This is an update to the previous post about templating the Visitor pattern.
Templated implementation of the Visitor Pattern for C++03

I won’t repeat the bulk of the post as the examples will be identical.

The new code uses ‘variadic temples’ that were introduced with C++11, and as such, greatly simplifies the code required.

Visitable

  //*****************************************************************
  /// The visitable class for N types.
  //*****************************************************************
  template <typename T1, typename... Types>
  class Visitable : public Visitable<T1>, public Visitable<Types...>
  {
  public:

    using Visitable<T1>::Accept;
    using Visitable<Types...>::Accept;
  };

  //*****************************************************************
  /// The specialised visitable class for 1 type.
    //*****************************************************************
  template <typename T1>
  class Visitable<T1>
  {
  public:

    virtual void Accept(T1&) = 0;
  };
Visitiable

There, that’s it! It is able to handle any number of visitor types and doesn’t require N specialisations of the template.
The change to Visitor is just as radical.

Visitor

  //*****************************************************************
  /// The visitor class for N types.
  //*****************************************************************
  template <typename T1, typename... Types>
  class Visitor : public Visitor<T1>, public Visitor<Types...>
  {
  public:

    using Visitor<T1>::Visit;
    using Visitor<Types...>::Visit;
  };

  //*****************************************************************
  /// The specialised visitor class for 1 type.
  //*****************************************************************
  template <typename T1>
  class Visitor<T1>
  {
  public:

    virtual void Visit(T1&) = 0;
  };
Visitor

Implementing a moving average

Known by many names, such as as Cumulative Moving Average, Rolling Average, Running Average, Moving Mean or Rolling Mean, the object is to update an average value on receipt of a new value over a set window size.

Example:

Imagine we have accumulated 10 values and our window size is 10.
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]
The average of this sequence is (1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10) / 10 = 5.5

We now add a new sample, 11 to the sequence. As the windows size is 10, we drop the first value.

[ 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ]
The average of this sequence is (2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 11) / 10 = 6.5

Now, averaging over 10 samples each time is not that big an issue, but what if it’s 1000 or 10,000? Then, the overhead, both in processing time and storage has statrted to become a little excessive. In the case of 10,000 samples  of ‘double’ we are looking at 10,000 additions + 1 division each time a sample is added and a likely storage requirement of 80,000 bytes!
So we have an algorithm that has processing and storage complexity of O(N).

So let’s look at the problem again.
There are many ways of getting the same average:
[ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] = Average of 5.5
[ 7, 7, 7, 7, 7, 4, 4, 4, 4, 4 ] = Average of 5.5

But what about this?
[ 5.5, 5.5 , 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5, 5.5 ] = Average of 5.5

An average of 5.5 can be got from 10 samples of 5.5. So why store 10 samples? We can simply simulate the original sum just by multiplying the current average by the number of samples!

The calculation of the average for adding a new sample becomes this:

((Old_Average * Sample_Size) + New_Sample) / (Sample_Size + 1)

Now we have 1 multiplication, 2 additions and 1 division.

Our algorithm now has a complexity of O(1).

We can average over as large a sample size as we like and it will always take the same amount of time and use the same amount of storage. We can also change the sample size on-the-fly if we wish.

There is one downside in that the average will not exactly match the original version, as the actual oldest value is not being erased from the sum. But for the performance and storage advantages it may be a perfectly suitable solution. You may find that you will need a slightly smaller sample size with the rolling mean to get similar results.

UPDATE:
The multiplication may be elided by re-arranging the formula.

Old_Average + ((New_Sample – Old_Average) / (Sample_Size + 1))

This may produce a negative interim value, which may be a problem if you are using scaled unsigned integral types for the average value.

C++ wrapper for legacy C arrays

If you are writing in C++ you will sometimes be presented with an array defined by a section of C code. Using C++ you will have got used to having member functions to allow access to a container in a more error free fashion than raw C arrays. Using this template we can create a zero cost wrapper around a C array which will give it an STL style interface. The template has no member variables and has functions that return fixed values that will certainly be optimised away at compile time. The template may be used for access to both const and non-const arrays.

Template parameters may not only be types, but literal integral values too! In this way we can create the object with the array data at compile time.

The signature for the template is as follows. (Using STL naming conventions)

template <typename T, std::size_t SIZE_, T(&ARRAY_)[SIZE_]>
class array_wrapper

The template is given the type of the array, the size of the array (in elements) and the array itself.

An example would be this.

template <typename T, const size_t N>
constexpr std::size_t arraySize(T (&)[N] ){ return N; }

// Mutable array.
int data[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

typedef array_wrapper<int, arraySize(data), data> WrappedData;

WrappedData wrappedData;

// Immutable array.
extern const int cdata[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

typedef array_wrapper<const int, arraySize(data), cdata> WrappedCData;

WrappedCData wrappedCData;

Elements would now be able to be accessed in the same way as other STL containers.

WrappedData::const_reverse_iterator itr = wrappedData.crbegin();

while (itr != wrappedData.crend())
{
    Print(*itr++); // Prints the array in reverse order.
}

size_t size = wrappedData.size();

int lastItem = wrappedData.back();

wrappedData.fill(0);

And now the code.

First we have the template declaration, internal types and constants.

template <typename T, std::size_t SIZE_, T(&ARRAY_)[SIZE_]>
class array_wrapper
{
public:

  typedef T                                     value_type;
  typedef std::size_t                           size_type;
  typedef T&                                    reference;
  typedef const T&                              const_reference;
  typedef T*                                    pointer;
  typedef const T*                              const_pointer;
  typedef T*                                    iterator;
  typedef const T*                              const_iterator;
  typedef std::reverse_iterator<iterator>       reverse_iterator;
  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;

  // Indexes for positions in the array.
  enum
  {
    SIZE     = SIZE_,
    MAX_SIZE = SIZE_,
    FRONT    = 0,
    BACK     = SIZE - 1,
    BEGIN    = 0,
    END      = SIZE,
    RBEGIN   = SIZE - 1,
    REND     = -1
  };

Next, the ability to get references to the front and back elements of the array.

  //*************************************************************************
  /// Returns a reference to the first element.
  //*************************************************************************
  reference front()
  {
    return *&ARRAY_[FRONT];
  }

  //*************************************************************************
  /// Returns a const reference to the first element.
  //*************************************************************************
  constexpr const_reference front() const
  {
    return *&ARRAY_[FRONT];
  }

  //*************************************************************************
  /// Returns a reference to the last element.
  //*************************************************************************
  reference back()
  {
    return *&ARRAY_[BACK];
  }

  //*************************************************************************
  /// Returns a const reference to the last element.
  //*************************************************************************
  constexpr const_reference back() const
  {
    return *&ARRAY_[BACK];
  }

Now the ability to get the start address of the array.

  //*************************************************************************
  /// Returns a pointer to the first element of the internal storage.
  //*************************************************************************
  pointer data()
  {
    return &ARRAY_[BEGIN];
  }

  //*************************************************************************
  /// Returns a const pointer to the first element of the internal storage.
  //*************************************************************************
  constexpr const_pointer data() const
  {
    return &ARRAY_[BEGIN];
  }

We now define the set of member functions that enable iterators to traverse forwards and backwards through the array.

  //*************************************************************************
  /// Returns an iterator to the beginning of the array.
  //*************************************************************************
  iterator begin()
  {
    return &ARRAY_[BEGIN];
  }

  //*************************************************************************
  /// Returns a const iterator to the beginning of the array.
  //*************************************************************************
  constexpr const_iterator begin() const
  {
    return &ARRAY_[BEGIN];
  }

  //*************************************************************************
  /// Returns a const iterator to the beginning of the array.
  //*************************************************************************
  constexpr const_iterator cbegin() const
  {
    return &ARRAY_[BEGIN];
  }

  //*************************************************************************
  /// Returns an iterator to the end of the array.
  //*************************************************************************
  iterator end()
  {
    return &ARRAY_[END];
  }

  //*************************************************************************
  /// Returns a const iterator to the end of the array.
  //*************************************************************************
  constexpr const_iterator end() const
  {
    return &ARRAY_[END];
  }

  //*************************************************************************
  // Returns a const iterator to the end of the array.
  //*************************************************************************
  constexpr const_iterator cend() const
  {
    return &ARRAY_[END];
  }

  //*************************************************************************
  // Returns an reverse iterator to the reverse beginning of the array.
  //*************************************************************************
  reverse_iterator rbegin()
  {
    return reverse_iterator(&ARRAY_[END]);
  }

  //*************************************************************************
  /// Returns a const reverse iterator to the reverse beginning of the array.
  //*************************************************************************
  constexpr const_reverse_iterator rbegin() const
  {
    return const_reverse_iterator(&ARRAY_[END]);
  }

  //*************************************************************************
  /// Returns a const reverse iterator to the reverse beginning of the array.
  //*************************************************************************
  constexpr const_reverse_iterator crbegin() const
  {
    return const_reverse_iterator(&ARRAY_[END]);
  }

  //*************************************************************************
  /// Returns a reverse iterator to the end of the array.
  //*************************************************************************
  reverse_iterator rend()
  {
    return reverse_iterator(&ARRAY_[BEGIN]);
  }

  //*************************************************************************
  /// Returns a const reverse iterator to the end of the array.
  //*************************************************************************
  constexpr const_reverse_iterator rend() const
  {
    return const_reverse_iterator(&ARRAY_[BEGIN]);
  }

  //*************************************************************************
  /// Returns a const reverse iterator to the end of the array.
  //*************************************************************************
  constexpr const_reverse_iterator crend() const
  {
    return const_reverse_iterator(&ARRAY_[BEGIN]);
  }

We also define operator [] members, plus at() member functions for STL compatibility.

  //*************************************************************************
  /// Returns a reference to the indexed value.
  //*************************************************************************
  reference operator[](size_t i)
  {
    return ARRAY_[i];
  }

  //*************************************************************************
  /// Returns a const reference to the indexed value.
  //*************************************************************************
  constexpr const_reference operator[](size_t i) const
  {
    return ARRAY_[i];
  }

  //*************************************************************************
  /// Returns a reference to the indexed value.
  //*************************************************************************
  reference at(size_t i)
  {
    return ARRAY_[i];
  }

  //*************************************************************************
  /// Returns a const reference to the indexed value.
  //*************************************************************************
  constexpr const_reference at(size_t i) const
  {
    return ARRAY_[i];
  }

We also have a safe way of interrogating the size of the array.

  //*************************************************************************
  /// Returns the size of the array.
  //*************************************************************************
  constexpr size_t size() const
  {
    return SIZE;
  }

  //*************************************************************************
  /// Returns the maximum possible size of the array.
  //*************************************************************************
  constexpr size_t max_size() const
  {
    return MAX_SIZE;
  }

Finally we define a couple of useful modifier member functions.

  //*************************************************************************
  /// Fills the array.
  //*************************************************************************
  void fill(const T& value)
  {
    std::fill(begin(), end(), value);
  }

  //*************************************************************************
  /// Swaps the contents of arrays.
  //*************************************************************************
  template <typename U, U(&ARRAYOTHER)[SIZE_]>
  typename std::enable_if<std::is_same<T, U>::value, void>::type
    swap(etl::array_wrapper<U, SIZE_, ARRAYOTHER>& other)
  {
    for (size_t i = 0; i < SIZE; ++i)
    {
      std::swap(ARRAY_[i], other.begin()[i]);
    }
  }

To complete the set of functionality we define a set of comparison free functions and a swap().

  //*************************************************************************
  /// Equality for array wrappers.
  //*************************************************************************
  template <typename TL, typename TR, std::size_t SIZEL, std::size_t SIZER, TL(&ARRAYL)[SIZEL], TR(&ARRAYR)[SIZER]>
  bool operator == (const array_wrapper<TL, SIZEL, ARRAYL>& lhs,
                    const array_wrapper<TR, SIZER, ARRAYR>& rhs)
  {
    return (SIZEL == SIZER) && std::equal(lhs.begin(), lhs.end(), rhs.begin());
  }

  //*************************************************************************
  /// Inequality for array wrapper.
  //*************************************************************************
  template <typename TL, typename TR, std::size_t SIZEL, std::size_t SIZER, TL(&ARRAYL)[SIZEL], TR(&ARRAYR)[SIZER]>
  bool operator != (const array_wrapper<TL, SIZEL, ARRAYL>& lhs,
                    const array_wrapper<TR, SIZER, ARRAYR>& rhs)
  {
    return !(lhs == rhs);
  }

  //*************************************************************************
  /// Less-than for array wrapper.
  //*************************************************************************
  template <typename TL, typename TR, std::size_t SIZEL, std::size_t SIZER, TL(&ARRAYL)[SIZEL], TR(&ARRAYR)[SIZER]>
  bool operator < (const array_wrapper<TL, SIZEL, ARRAYL>& lhs,
                   const array_wrapper<TR, SIZER, ARRAYR>& rhs)
  {
    return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
  }

  //*************************************************************************
  /// Greater-than for array wrapper.
  //*************************************************************************
  template <typename TL, typename TR, std::size_t SIZEL, std::size_t SIZER, TL(&ARRAYL)[SIZEL], TR(&ARRAYR)[SIZER]>
  bool operator > (const array_wrapper<TL, SIZEL, ARRAYL>& lhs,
                   const array_wrapper<TR, SIZER, ARRAYR>& rhs)
  {
    return rhs < lhs;
  }

  //*************************************************************************
  /// Less-than-equal for array wrapper.
  //*************************************************************************
  template <typename TL, typename TR, std::size_t SIZEL, std::size_t SIZER, TL(&ARRAYL)[SIZEL], TR(&ARRAYR)[SIZER]>
  bool operator <= (const array_wrapper<TL, SIZEL, ARRAYL>& lhs,
                    const array_wrapper<TR, SIZER, ARRAYR>& rhs)
  {
    return !(lhs > rhs);
  }

  //*************************************************************************
  /// Greater-than-equal for array wrapper.
  //*************************************************************************
  template <typename TL, typename TR, std::size_t SIZEL, std::size_t SIZER, TL(&ARRAYL)[SIZEL], TR(&ARRAYR)[SIZER]>
  bool operator >= (const array_wrapper<TL, SIZEL, ARRAYL>& lhs,
                    const array_wrapper<TR, SIZER, ARRAYR>& rhs)
  {
    return !(lhs < rhs);
  }

  //*************************************************************************
  /// Swap.
  //*************************************************************************
  template <typename T, std::size_t SIZE, T(&ARRAYL)[SIZE], T(&ARRAYR)[SIZE]>
  void swap(array_wrapper<T, SIZE, ARRAYL>& lhs,
            array_wrapper<T, SIZE, ARRAYR>& rhs)
  {
    lhs.swap(rhs);
  }

The Embedded Template Library

Why did I start it?

I wrote the Embedded Template Library (ETL), and all the others I have written over the years, because I’m lazy.
Yes, lazy! But in a good way I believe. See here.

Don’t Re-invent The Wheel

I hate having to code yet another variation of the same thing in a slightly different way time and and time again.
Reinventing the wheel every time is daft for many reasons.

Code bloat

Multiple instances of slight variations of a theme results in an increase in code size due to no commonality of functionality.

Testing, more testing or no testing

Are all the variants tested to the same degree? Are some even tested at all?

Variable functionality

Not all the variants are going to have the same level of functionality, or the same API. Ad-hoc solutions are invariably only going to solve the little bit of the problem that was needed at the time.

No collective knowledge base

Without commonality every new variant has to be learned. The underlying principles may be understood (i.e. Linked list), but each implementation has to be understood separately, along with its particular caveats and foibles. Documentation is likely to be patchy.

Octopus code

The application is liable to have a close coupling with the solution. For example, I’ve often seen code using linked lists directly accessing the node pointers. Ad-hoc solutions are liable to have lazy (the bad kind) implementations.

The Beginnings

I’ve been working with software that has had deterministic requirements for most of my programming career. Some of the latest ones involved image processing and feature extraction from objects passing a camera on a conveyor. The objects travelled fast and the gaps between them were small. For example, I once designed software for mail sorting machines where mail items could be travelling of speeds up to 4 metres per second with gaps of around 40mm. Finishing the processing on time was paramount, as a late result would cause the mail item to end up in the ‘hand sort’ bin. For a run of 30,000 mail items you don’t really want that sort of thing happening very often! As we were writing the application in C++ the STL was a very useful library to draw from, but one part of it has issues when used in conjunction with real-time applications.

The containers.

Virtually all of the containers in the STL, by default, get storage from the heap. This is a bit of a no-no for real-time software as the allocation and release of memory from the default heap is somewhat non-deterministic. There are a couple of tricks that can be done to try to alleviate the issues, such as reserving the size of vectors upfront, but it can only get you so far.

There are a few ways in which the programmer can try to get around them.

Create your own replacement for malloc/new

By writing a super optimised global malloc/new replacement you may be able to get the worst case times down to something acceptable for your application. You may have to address issues raised by multiple threads accessing the memory allocator concurrently. But what happens at run-time if the heap becomes too fragmented or you run out of heap space? In my experience it will crash during the demo in front of the customer.

Create your own STL allocator

One solution is to create an allocator similar to the malloc/new replacement, along with its threading, fragmentation and free space issues.

Another is to allow the allocator to contain its own fixed sized storage. This is a solution I used successfully for a while, but there turned out to be issues when porting between compilers, even versions of the same compiler. In the end I abandoned this idea.

Create a new set of STL like containers

Although a lot more work than custom STL allocators, creating a set of custom containers, specifically optimised for operating on internally declared contiguous blocks of memory, can bring great performance advantages. It also has the advantage of being more amenable to static analysis; All of the memory that may be used in a container is declared up front. This is very handy for allowing the application fail on the developer’s desk at compile time, instead in front of the customer at run-time.

Before I started to write the ETL I had built up a collection of ideas, sample code and early versions of containers, but they were not organised in any sort of library. Whenever I looked for the sort of library that met my specifications I could never find anything that really matched. All of the ones that I found were either limited in scope, or would drop back to using the heap when the initial reserved capacity was exceeded. I decided that the best course was to gather together all of my ideas and experiments and build them into the sort of library that I would want to find myself. I assumed that there were others out there that were also searching for the same sort of thing.

At the time, the chance of finding an embedded compiler that supported C++11 or above was fairly remote. I once talked to Keil back in 2014 about C++11 support and at the time the answer was basically “don’t hold your breath”. So I decided that the library must be compatible with C++03. As there were some very useful additions in C++11 I also decided to reverse engineer as many as were practical.

Requirements

MIT licence

Have you ever come across what looks like the perfect library, only to find it’s GPL and therefore unusable in your company? I want anyone to be able to use it, how they like.

Just don’t say you wrote it (unless you did).

Cross platform

I want it to work on all targets and platforms.

C++03 compatibilty

As I said before, C++11 and above was not always an option for embedded compilers back then. For many it still isn’t.

No dynamic memory allocation

All storage is allocated either at compile time or on the stack. The library should not use the heap at all.

No RTTI required

Lowers the overhead.

Very little use of virtual functions

I’m not one of those that thinks virtual functions are the root of all evil in embedded software. Sometimes they are extremely useful and the alternative would be clunky and awkward and sometimes just C++ virtuals in another form. At other times a slightly different technique can eliminate a lot of them with little pain. They should be used only when they are absolutely necessary for the required functionality.

A set of fixed capacity containers

A fixed capacity version of all of the standard containers, plus a few useful extra ones. As the storage for the container types is allocated as a contiguous block, they are extremely cache friendly.

Reduced container code size through use of base classes dependant on type only

A technique sometimes known as ‘hoisting’. There is a top level class that knows type and size. This inherits from a class that contains functionality that is only interested in the type. This may also inherit from a base class that is both type and size agnostic.

Templated compile time constants

Helper templates that calculate constants at compile time. Sometimes useful when included inside another template.
i.e. When an internal constant is Log2 of a non-type template parameter constant.

Templated design pattern base classes

I say, let the templated boiler plate code do the work.

Frameworks for message routing, finite state machines and task scheduling

When have you not needed something like this for any non-trivial application, especially for bare bones systems? Don’t reinvent the wheel every time.

Reverse engineered C++ 0x11 features (type traits, algorithms, containers etc.)

There’s some useful stuff in the later releases of the STL.

Type-safe smart enumerations

A way of reducing many hard to find bugs where a constant from one enum is used where another was expected.

Type-safe typedefs + constants

See above.

8, 16, 32 & 64 bit CRC, checksums & hash functions

We’ve written them, so you don’t have to.

Variants (a type-safe union)

No more messing with unions and/or void*

Choice of asserts, exceptions, error handler or no checks on errors

How you repond to errors is up to you. The ETL does not dictate.

Many utilities for template support

Allowing you the ability to set types and constants according to the template parameters, allowing static asserts to perform concept checks.

Unit tested

So we can avoid accidently breaking anything.

Easy to read and documented source

But we all do this anyway don’t we?

Free email support

That’s what I would want, so that’s what you get.

Continuous integration testing

Every push is automatically unit tested, just in case we messed up and didn’t do our job properly (Perish the thought!)

Conclusion

The Embedded Template Library has been available on git for several years now and I’ve had great feedback from users and potential users from around the globe.
The ETL has been improved immeasurably by their input and I can’t thank them enough, especially Ryan Lindeman who did sterling work creating the map and set containers.

The ETL is at a good point at the moment, so I’m taking a little time off from adding any major new features (and I have several ideas in the pipeline) while I work on this blog and try to make a start at writing an ebook. I’ve not decided on a title as yet, but I intend it to be a sort of cook-book of C++ template techniques, especially tailored towards embedded and real-time platforms. A lot of the information in it will draw from the work in the ETL.

There are four types of programmer

Their is a story about a German general that declared that there were four kinds of people, only three of which he wanted in his army.

Here’s my take on it from a programmer’s angle.
 
Intelligent Lazy
Intelligent lazy people hate having to reinvent a solution to a problem that has already been solved. Moreover they don’t always go for the first solution that comes to mind. They would prefer the best solution; the one that means you don’t have to go through all of the problem solving work all over again when a slight variation turns up. They’re the ones that build a generic library with built-in extensibility. It will probably conform to SOLID principles. Their downside is that they may have a tendency to over engineer things at times.
 
Intelligent Active
These people are productive and can come up with working solutions in a short amount of time. They’re great when you need a quick and dirty solution. The downside is that that’s what you may get a lot of the time. A mixture of Intelligent Lazy & Intelligent Active in some proportion may be useful as they will tend to temper each other’s excesses.
Or they may just annoy each other like crazy.
 
Stupid Lazy
These sort of people aren’t really smart enough to be superstar programmers, but, given clear enough instructions, can be fairly productive. Just don’t ask them to design a new framework. They won’t design one on their own as they don’t tend to take the initiative.
 
Stupid Active
These are the dangerous ones! They don’t really know what they’re doing, but either they think they do or just have a go anyway. These are the ones that make you groan with despair at code review time. They write brittle code, they write complex code with subtle bugs. They leave chaos in the code base they persists for years, if not forever.
 
I like to think that I come under the Intelligent Lazy label. One of the things I really hate when writing software is having to do the same, or something almost the same, over and over again. The first thing I think when presented with a problem that requires a specific set of functionality is “Is this a specific case of a more generic problem?”. Surprisingly, I can say “yes” more often than you would expect. Even if not all of the problem can be seen as generic, there are almost certainly parts that are. In every job I’ve had I’ve left an extensive code library behind me.

Largest / Smallest. Part 2

In the last post i showed you how to implement a ‘Largest’ traits template using pre-C++11.
In this post I will show you how to do the same using variadic templates.

First we declare the ‘bare’ template. It tells the compiler that ‘Largest’ take an unknown number of template parameters.

template <typename... Types>
struct Largest {};

Next, we create helper templates as we did before. In fact they are identical.

// Declaration.
template <const bool Boolean, typename TrueType, typename FalseType>
struct ChooseType;

// Specialisation for 'true'.
// Defines 'type' as 'TrueType'.
template <typename TrueType, typename FalseType>
struct ChooseType<true, TrueType, FalseType>
{
  typedef TrueType type;
};

// Specialisation for 'false'. 
// Defines 'type' as 'FalseType'.
template <typename TrueType, typename FalseType>
struct ChooseType<false, TrueType, FalseType>
{
  typedef FalseType type;
};

The main part of the template is very similar to before, but this time we just use the ellipsis as the type list.

typedef typename ChooseType<(sizeof(T1) > sizeof(typename Largest<Types...>::type)), // Boolean
                             T1,                                                     // TrueType
                             typename Largest<Types...>::type>                       // FalseType
                             ::type type;                                            // The largest type of the two.

Finally, as before we need a ‘stopper’ definition to tell the compiler when we’ve reached the end.

template <typename T1>
struct Largest<T1>
{
  typedef T1 type;
};

Putting it all together again we get…

template <typename... Types>
struct Largest {};

template <typename T1, typename... Types>
struct Largest<T1, Types...>
{
private:

  // Declaration.
  template <const bool Boolean, typename TrueType, typename FalseType>
  struct ChooseType;

  // Specialisation for 'true'.
  // Defines 'type' as 'TrueType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<true, TrueType, FalseType>
  {
    typedef TrueType type;
  };

  // Specialisation for 'false'. 
  // Defines 'type' as 'FalseType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<false, TrueType, FalseType>
  {
    typedef FalseType type;
  };

public:

  // Set 'type' to be the largest of the first parameter and any of the others.
  // This is recursive.
  typedef typename ChooseType<(sizeof(T1) > sizeof(typename Largest<Types...>::type)), // Boolean
                               T1,                                                     // TrueType
                               typename Largest<Types...>::type>                       // FalseType
                               ::type type;                                            // The largest type of the two.                                        
};

template <typename T1>
struct Largest<T1>
{
  typedef T1 type;
};

How It’s Used

template typename T1, typename T2, typename T3>
struct Buffer
{
  char buffer[sizeof(typename Largest<T1, T2, T3>::type)];
};

This variation has the advantage that it can handle any number of type, up to the capacity of the compiler.

You no doubt see that an additional template to handle smallest should be a trivial task.
Other additions to the templates could include the min/max size and alignment as traits.

Largest / Smallest. Part 1

Sometimes, when multiple types are sent as template parameters, some information about the types needs to be interrogated to be able to configure another property of the template. The STL’s type traits header does a good job of supplying many of the more useful ones, but there is room for extension. Say, for instance, the template implements a type of variant container; a type of smart union. The container may store one of several types declared in the template parameter list. We need to allocate storage for this, but how determine the size?

template typename T1, typename T2, typename T3>
struct Buffer
{
	char buffer[???]; // Wouldn't it be nice to have something simple here,
	                  // rather than manually typing a lot of nested sizeof() boilerplate?
};

We can use template meta programming to help us here.

Here I will show you two variations; one for pre C++11 compilers that don’t support variadic templates and one for those that do.

Let’s say that we want to be able to handle up to four types. The ‘= void’ allows one, two, three or four types to be specified.

template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
strut Largest
{
};

First, let’s create a helper template to determine the largest of two types.

// Declaration.
template <const bool Boolean, typename TrueType, typename FalseType>
struct ChooseType;

// Specialisation for 'true'.
// Defines 'type' as 'TrueType'.
template <typename TrueType, typename FalseType>
struct ChooseType<true, TrueType, FalseType>
{
  typedef TrueType type;
};

// Specialisation for 'false'. 
// Defines 'type' as 'FalseType'.
template <typename TrueType, typename FalseType>
struct ChooseType<false, TrueType, FalseType>
{
  typedef FalseType type;
};

These templates will define their ‘type’ to either that of TrueType or FalseType dependent on the condition supplied.

Next we create a recursive typedef that chooses the largest type between the first template parameter type and all of the rest. We typedef ‘all of the rest’ for clarity.

// Define 'LargestOther' as 'Largest' with all but the first parameter. 
typedef typename Largest<T2, T3, T4>::type LargestOther;

Now the recursive bit.

typedef typename ChooseType<(sizeof(T1) > sizeof(LargestOther)), // Boolean
                             T1,                                 // TrueType
                             LargestOther>                       // FalseType
                             ::type type;                        // The largest type of the two.

The compiler will recursively parse the template until there is one type to test. Here we need something to stop the compiler attempting to parse any further.
What we do is to add a specialisation for the final single type.

//***************************************************************************
// Specialisation for one template parameter.
//***************************************************************************
template <typename T1>
struct Largest<T1,   void, void, void>
{
  typedef T1 type;

  enum
  {
    size = sizeof(type)
  };
};

Putting this all together we get…

template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
  struct Largest
{
private:

  // Declaration.
  template <const bool Boolean, typename TrueType, typename FalseType>
  struct ChooseType;

  // Specialisation for 'true'.
  // Defines 'type' as 'TrueType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<true, TrueType, FalseType>
  {
    typedef TrueType type;
  };

  // Specialisation for 'false'. 
  // Defines 'type' as 'FalseType'.
  template <typename TrueType, typename FalseType>
  struct ChooseType<false, TrueType, FalseType>
  {
    typedef FalseType type;
  };

public:

  // Define 'LargestOther' as 'Largest' with all but the first parameter. 
  typedef typename Largest<T2, T3, T4>::type LargestOther;

  // Set 'type' to be the largest of the first parameter and any of the others.
  // This is recursive.
  typedef typename ChooseType<(sizeof(T1) > sizeof(LargestOther)), // Boolean
                               T1,                                 // TrueType
                               LargestOther>                       // FalseType
                               ::type type;                        // The largest type of the two.
};

//***************************************************************************
// Specialisation for one template parameter.
//***************************************************************************
template <typename T1>
struct Largest<T1, void, void, void>
{
  typedef T1 type;
};

How It’s Used

template typename T1, typename T2, typename T3>
struct Buffer
{
	char buffer[sizeof(typename Largest<T1, T2, T3>::type)];
};

The number of types that can be handled is easily increased.

This is the technique used in the Embedded Template Library to implement largest/smallest traits.

In the next post I’ll show you how to achieve the same with variadic templates.

Templated implementation of the Observer Pattern

The purpose of this template is to simplify the creation of classes that implement the Observer Pattern and attempt to eliminate certain runtime errors by turning them into compile time errors. The pattern consists of two template classes. Observer and Observable.

Observable

The class derived from this will be observed by classes derived from Observer. It keeps a list of registered observers and will notify all of them with the raised notifications.
It is parameterised by a supplied observer type.

void AddObserver(TObserver& observer)
Registers an observer with the observable class.

void RemoveObserver(TObserver& observer)
Unregisters an observer.

void ClearObservers()
Unregister all of the observers.

size_type NumberOfObservers()
Gets the number of registered observers.

template <typename TNotification>
void NotifyObservers(TNotification n)

Notifies all of the registered observers with the notification ‘n’.

  template <typename TObserver>
  class observable
  {
  public:

    typedef size_t size_type;

    typedef std::vector<TObserver*> ObserverList;

    //*****************************************************************
    /// Add an observer to the list.
    //*****************************************************************
    void AddObserver(TObserver& observer)
    {
		  // See if we already have it in our list.
      typename ObserverList::const_iterator i_observer = std::find(observer_list.begin(),
                                                                   observer_list.end(),
                                                                   &observer);

		  // Not there?
      if (i_observer == observer_list.end())
      {
        // Add it.
        observer_list.push_back(&observer);
      }
    }

    //*****************************************************************
    /// Remove a particular observer from the list.
    //*****************************************************************
    void RemoveObserver(TObserver& observer)
    {
      // See if we have it in our list.
      typename ObserverList::iterator i_observer = std::find(observer_list.begin(),
                                                             observer_list.end(),
                                                             &observer);

      // Found it?
      if (i_observer != observer_list.end())
      {
        // Erase it.
        observer_list.erase(i_observer);
      }
    }

    //*****************************************************************
    /// Clear all observers from the list.
    //*****************************************************************
    void ClearObservers()
    {
      observer_list.clear();
    }

    //*****************************************************************
    /// Returns the number of observers.
    //*****************************************************************
    size_type NumberOfObservers() const
    {
      return observer_list.size();
    }

    //*****************************************************************
    /// Notify all of the observers, sending them the notification.
    /// TNotification is the notification type.
    //*****************************************************************
    template <typename TNotification>
    void NotifyObservers(TNotification n)
    {
      for (size_t i = 0; i < observer_list.size(); ++i)
      {
        observer_list[i]->Notification(n);
      }
    }

  private:

    /// The list of observers.
    ObserverList observer_list;
  };

Observer

This template may take up to N notification types.
Each notification type will generate a pure virtual ‘notification’ function. The class that inherits from this must define all of the ‘Notification’ function overloads otherwise the object will remain abstract and will not compile. This ensures that no notification overload can be omitted.

The example below gives the derived observer class the capacity to handle four notification types. A script may be used to generate code that can handle any number of types.
The method that the notification parameter is passed to the notification handler is specified in the template type parameter.
i.e. If the notification is to be passed as const reference to a strut called ‘Info’ then the template type parameter would be declared as const Info&.

//*********************************************************************
  /// The Observer interface for four notification types.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1, typename T2  = void, typename T3  = void, typename T4  = void>
  class Observer
  {
  public:
    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
    virtual void Notification(T2) = 0;
    virtual void Notification(T3) = 0;
    virtual void Notification(T4) = 0;
  };

  //*********************************************************************
  /// The Observer interface for three notification types.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1, typename T2, typename T3>
  class Observer<T1, T2, T3>
  {
  public:

    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
    virtual void Notification(T2) = 0;
    virtual void Notification(T3) = 0;
  };

  //*********************************************************************
  /// The Observer interface for two notification types.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1, typename T2>
  class Observer<T1, T2>
  {
  public:

    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
    virtual void Notification(T2) = 0;
  };

  //*********************************************************************
  /// The Observer interface for one notification type.
  ///\ingroup Observer
  //*********************************************************************
  template <typename T1>
  class Observer<T1>
  {
  public:

    virtual ~Observer() {}
    virtual void Notification(T1) = 0;
  };

In use

First we define three different notification types.

//*****************************************************************************
// Notification1
//*****************************************************************************
struct Notification1
{
  // Some data.
};

//*****************************************************************************
// Notification2
//*****************************************************************************
struct Notification2
{
  // Some data.
};

//*****************************************************************************
// Notification3
//*****************************************************************************
struct Notification3
{
  // Some data.
};

Next we declare the base observer type.
Note that Notification1 is passed by value, Notification2 is passed by reference and Notification3 is passed by const reference.

//*****************************************************************************
// The observer base type.
// Declare what notifications you want to observe and how they are passed to 'notification'.
// Notification1 is passed by value.
// Notification2 is passed by reference.
// Notification3 is passed by const reference.
//*****************************************************************************
typedef Observer<Notification1, Notification2&, const Notification3&> ObserverType;

Now we define an observable class that that can be observed by classes derived from ObserverType

//*****************************************************************************
// The concrete observable class.
//*****************************************************************************
class Observable1 : public Observable<ObserverType>
{
public:
  
  Notification1 data1;
  Notification2 data2;
  Notification3 data3;

  //*********************************
  // Notify all of the observers.
  //*********************************
  void SendNotifications()
  {
    notify_observers(data1);
    notify_observers(data2);
    notify_observers(data3);
  }
};

Let’s now define two observer classes. Both are able to accept notifications Notification1, Notification2 and Notification3.

//*****************************************************************************
// The first observer type.
// If any one of the overloads is missing or a parameter declaration is incorrect
// then the class will be 'abstract' and will not compile.
//*****************************************************************************
class Observer1 : public ObserverType
{
public:

  //*******************************************
  // Notification1 is passed by value.
  //*******************************************
  void notification(Notification1 n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification2 is passed by reference.
  //*******************************************
  void notification(Notification2& n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification3 is passed by const reference.
  //*******************************************
  void notification(const Notification3&)
  {
    // Do something with n.
  }
};

//*****************************************************************************
// The second observer type.
// If any one of the overloads is missing or a parameter declaration is incorrect
// then the class will be 'abstract' and will not compile.
//*****************************************************************************
class Observer2 : public ObserverType
{
public:

  //*******************************************
  // Notification1 is passed by value.
  //*******************************************
  void notification(Notification1 n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification2 is passed by reference.
  //*******************************************
  void notification(Notification2& n)
  {
    // Do something with n.
  }

  //*******************************************
  // Notification3 is passed by const reference.
  //*******************************************
  void notification(const Notification3&)
  {
    // Do something with n.
  }
};

Now the test code.

// The observable objects.
Observable1 observable1;

// The observer objects.
Observer1 observer1;
Observer2 observer2;

observable1.AddObserver(observer1);
observable1.AddObserver(observer2);

// Send the notifications.
observable1.SendNotifications();

A version of this framework can be found as part of the Embedded Template Library, an open source C++ library distributed under the MIT licence.

Templated implementation of the Visitor Pattern

Introduction

There are probably many of you out there who, like me, have investigated the possibilities that templates and template meta-programming can bring to your code.

After having some success with templated image and image algorithm classes, I turned my attention to seeing whether some of the design patterns I use could be encapsulated in the same way. Investigation on the web revealed that template meta-programming could play a part in achieving this.

An article on Dr Dobbs introduced me to typelists and some of the meta-programming techniques, with the Visitor pattern used as an example.

Unfortunately, I soon found that Visual C++ was not entirely happy with the syntax used and it took some time before I managed to get a version that didn’t give the compiler indigestion! That didn’t last long, though. Instantiating my first Visitor object caused the compiler to generate the dreaded “Internal compiler error. Try simplifying your code”. Well, I gave up at that point, deciding I had better things to do with my life than battling my compiler. So, I decided to try and achieve the similar objective to the Visitor example without meta-programming.

Anyone unfamiliar with the Visitor pattern should read this first.

The objective of the Dr Dobbs example was merely to remove a small amount of boilerplate code and ensure that all handling omissions in all code would be flagged at compile time.

The use of this technique in the Visitor pattern may seem somewhat trivial, but I hope that you may find the methods used useful in more complex situations, despite it not being as ‘cool’ as using typelists and meta-programming.

How It Works

The purpose of these classes is to create a Visitor base class with pure virtual Visit functions for each supplied type. Any derived class that tries to instantiate an object from it will then be forced to supply an overridden version for each and every Visit function.

Similarly the Visitable class defines pure virtual Accept function for each supplied visitor type.

The framework is based on two template classes; Visitor & Visitable.

Visitable

Classes that should be visitable should derive from the Visitable template class. The classes that may visit should be defined in the template type parameter list.
Here I have defined a template and specialisations to accept up to 4 visitor types.

//*****************************************************************
/// The visitable base class for four visitor types.
//*****************************************************************
template <typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
class Visitable
{
public:

  virtual void Accept(T1&) = 0;
  virtual void Accept(T2&) = 0;
  virtual void Accept(T3&) = 0;
  virtual void Accept(T4&) = 0;
};

//*****************************************************************
/// The visitable base class for three visitor types.
//*****************************************************************
template <typename T1, typename T2, typename T3>
class Visitable<T1, T2, T3>
{
public:

  virtual void Accept(T1&) = 0;
  virtual void Accept(T2&) = 0;
  virtual void Accept(T3&) = 0;
};

//*****************************************************************
/// The visitable base class for two visitor types.
//*****************************************************************
template <typename T1, typename T2>
class Visitable<T1, T2>
{
public:

  virtual void Accept(T1&) = 0;
  virtual void Accept(T2&) = 0;
};

//*****************************************************************
/// The visitable base class for one visitor type.
//*****************************************************************
template <typename T1>
class Visitable<T1>
{
public:

  virtual void Accept(T1&) = 0;
};

Visitor

Classes that should be able to visit visitable classes should derive from the Visitor template class. The types that the visitor expects to support should be defined in the template type parameter list.

Here I have defined a template and specialisations to accept up to 16 types types. It may seem like it would be an onerous task to modify this to accept any N types, but the repetitive nature of the code lends itself perfectly to generation via a script.

//*****************************************************************
/// The visitor base class for sixteen types.
//*****************************************************************
template <typename T1,         typename T2  = void, typename T3  = void, typename T4  = void,
          typename T5  = void, typename T6  = void, typename T7  = void, typename T8  = void,
          typename T9  = void, typename T10 = void, typename T11 = void, typename T12 = void,
          typename T13 = void, typename T14 = void, typename T15 = void, typename T16 = void>
  class Visitor
{
public:

  virtual void Visit(T1&) = 0;
  virtual void Visit(T2&) = 0;
  virtual void Visit(T3&) = 0;
  virtual void Visit(T4&) = 0;
  virtual void Visit(T5&) = 0;
  virtual void Visit(T6&) = 0;
  virtual void Visit(T7&) = 0;
  virtual void Visit(T8&) = 0;
  virtual void Visit(T9&) = 0;
  virtual void Visit(T10&) = 0;
  virtual void Visit(T11&) = 0;
  virtual void Visit(T12&) = 0;
  virtual void Visit(T13&) = 0;
  virtual void Visit(T14&) = 0;
  virtual void Visit(T15&) = 0;
  virtual void Visit(T16&) = 0;
};

//*****************************************************************
/// The visitor base class for fifteen types.
//*****************************************************************
template <typename T1,  typename T2,  typename T3,  typename T4,
          typename T5,  typename T6,  typename T7,  typename T8,
          typename T9,  typename T10, typename T11, typename T12,
          typename T13, typename T14, typename T15>
  class Visitor<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10, T11, T12, T13, T14, T15>
{
public:

  virtual void Visit(T1&) = 0;
  virtual void Visit(T2&) = 0;
  virtual void Visit(T3&) = 0;
  virtual void Visit(T4&) = 0;
  virtual void Visit(T5&) = 0;
  virtual void Visit(T6&) = 0;
  virtual void Visit(T7&) = 0;
  virtual void Visit(T8&) = 0;
  virtual void Visit(T9&) = 0;
  virtual void Visit(T10&) = 0;
  virtual void Visit(T11&) = 0;
  virtual void Visit(T12&) = 0;
  virtual void Visit(T13&) = 0;
  virtual void Visit(T14&) = 0;
  virtual void Visit(T15&) = 0;
};

//*****************************************************************
// The same pattern is repeated for each decreasing number of parwameters until...
//*****************************************************************

//*****************************************************************
/// The visitor base class for one type.
//*****************************************************************
template <typename T1>
class Visitor<T1>
{
public:

  virtual void Visit(T1&) = 0;
};

How It’s Used

I’ll use the good old ‘Shape’ example so loved by many.

First, you create the base for your ‘Shape’ visitor.

//*****************************************************************
// Pre-declare the shapes.
//*****************************************************************
class Square;
class Circle;
class Triangle;

//*****************************************************************
// The shape visitor base class.
// Pure virtual 'Visit' functions will be defined for the Square,
// Circle, and Triangle types.
//*****************************************************************
class ShapeVisitor : public Visitor<Square, Circle, Triangle>
{
};

Then, you define the ‘Shape’ base class. It derives from the Visitable class that defines a pure virtual ‘Accept’ function that accepts a ShapeVisitor.

//*****************************************************************
// The shape base class.
//*****************************************************************
class Shape : public Visitable<ShapeVisitor>
{
};

Next, you define the shapes ‘Square’, ‘Circle’, and ‘Triangle’. Each overrides the ‘Accept’ function that calls the visitor with itself as a parameter.

//*****************************************************************
// The square class
//*****************************************************************
class Square : public Shape
{
  void Accept(ShapeVisitor& visitor)
  {
    visitor.Visit(*this);
  }
};

//*****************************************************************
// The circle class
//*****************************************************************
class Circle : public Shape
{
  void Accept(ShapeVisitor& visitor)
  {
    visitor.Visit(*this);
  }
};

//*****************************************************************
// The triangle class
//*****************************************************************
class Triangle : public Shape
{
  void Accept(ShapeVisitor& visitor)
  {
    visitor.Visit(*this);
  }
};

Now that you have the framework in place, you can do something with it. Here’s an example that creates ‘Draw’ and ‘Serialise’ visitors and applies them to a vector of Shape objects.

//*****************************************************************
// The 'draw' visitor.
//*****************************************************************
class DrawVisitor : public ShapeVisitor
{
public:
    void Visit(Square& square)
    {
        std::cout << "Draw the square\n";
    }

    void Visit(Circle& circle)
    {
        std::cout << "Draw the circle\n";
    }

    void Visit(Triangle& triangle)
    {
        std::cout << "Draw the triangle\n";
    }
};

//*****************************************************************
// The 'serialise' visitor.
//*****************************************************************
class SerialiseVisitor : public ShapeVisitor
{
public:
    void Visit(Square& square)
    {
        std::cout << "Serialise the square\n";
    }

    void Visit(Circle& circle)
    {
        std::cout << "Serialise the circle\n";
    }

    void Visit(Triangle& triangle)
    {
        std::cout << "Serialise the triangle\n";
    }
};

Now we define the actual visitors and a container for shapes.

//*****************************************************************
// The actual visitors.
//*****************************************************************
DrawVisitor      draw_visitor;
SerialiseVisitor serialise_visitor;

//*****************************************************************
// The list of shapes.
//*****************************************************************
std::vector<Shape*> shape_list;

The following is a utility function to apply a visitor to the list of shapes.

//*****************************************************************
// The Apply a visitor.
//*****************************************************************
void Apply(ShapeVisitor &visitor)
{
  for (std::vector<Shape*>::size_type i = 0; i < shape_list.size(); ++i)
  {
    // Send the visitor to the shape.
    shape_list[i]->Accept(visitor);
  }  
}

And now the code to test in all.


//*****************************************************************
// Main
//*****************************************************************
int main()
{
  // Create some shapes.
  Square   square;
  Circle   circle;
  Triangle triangle;

  // Add them to the vector
  shape_list.push_back(&square);
  shape_list.push_back(&circle);
  shape_list.push_back(&triangle);

  // Apply the visitors.
  Apply(draw_visitor);
  Apply(serialise_visitor);

  return 0;
}

The output from the example is as follows…

Draw the square
Draw the circle
Draw the triangle
Serialise the square
Serialise the circle
Serialise the triangle

A version of this framework can be found as part of the Embedded Template Library, an open source C++ library distributed under the MIT licence.

Designing an efficient and low resource messaging framework. Part 3

In the last post I showed how to shrink the vtable overhead and reduce the coupling of the framework.
This time I shall show how to reduce the vtable hit even further using another technique called the Curiously Recurring Template Pattern or CRTP. This oddly name pattern is a way of replacing runtime virtual calls with compile time dispatch. It achieves this by passing the derived class type as a template type parameter to the base class.

template <typename TDerived>
class Base
{
};

class Derived : public Base<Derived>
{
};

By the use of this technique, the base class can be informed of its concrete type at compile time. This allows the base type to directly call member functions in the derived type thereby avoiding an indirect call though the vtable. If the called functions are deemed suitable by the compiler, then they may well be inlined too.

template <typename TDerived>
class Base
{
  void FunctionBase()
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    derived.FunctionDerived()
  }
};

class Derived : public Base<Derived>
{
  void FunctionDerived()
  {
  }
};

This is the technique that we will use for the third version of the messaging framework.
The messages are defined in the same way as before.

class IMessage
{
public:

  IMessage(int id)
    : messageId(id)
  {
  }

  int GetMessageId() const
  {
    return messageId;
  }

private:

  const int messageId;
};

template <int ID_>
class Message : public IMessage
{
public:

  Message()
    : IMessage(ID_)
  {
  }

  enum
  {
    ID = ID_
  };
};

// Message 1.
class Message1 : public Message<1>
{
};

// Message 2.
class Message2 : public Message<2>
{
};

// Message 3.
class Message3 : public Message<3>
{
};

// Message 4.
class Message4 : public Message<4>
{
};

As is the base message processor interface.

class IMessageProcessor
{
public:

  virtual void Receive(const IMessage& msg) = 0;
};

The difference now is in the definitions of the templated message handlers. The derived message processor type is passed as a template type parameter and used to cast the ‘this’ pointer to the true concrete type, allowing direct calls to the handler functions.

template <typename TDerived, typename T1, typename T2 = void, typename T3 = void, typename T4 = void>
class MessageProcessor : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
      case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
      case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
      case T3::ID: derived.Handle(static_cast<const T3&>(msg)); break;
      case T4::ID: derived.Handle(static_cast<const T4&>(msg)); break;
      default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1, typename T2, typename T3>
class MessageProcessor<TDerived, T1, T2, T3, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
    case T3::ID: derived.Handle(static_cast<const T3&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1, typename T2>
class MessageProcessor<TDerived, T1, T2, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    case T2::ID: derived.Handle(static_cast<const T2&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

template <typename TDerived, typename T1>
class MessageProcessor<TDerived, T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    default: derived.Unhandled(msg); break;
    }
  }
};

The derived message processors are very similar to before, with the exception that the derived class is passed as template type parameter to the base.

class Processor1 : public MessageProcessor<Processor1, Message4, Message2, Message1, Message3>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor1 : Message1\n";
  }

  void Handle(const Message2& msg)
  {
    std::cout << "Processor1 : Message2\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor1 : Message3\n";
  }

  void Handle(const Message4& msg)
  {
    std::cout << "Processor1 : Message4\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor1 : Unhandled IMessage\n";
  }
};

class Processor2 : public MessageProcessor<Processor2, Message3, Message1>
{
public:

  void Handle(const Message1& msg)
  {
    std::cout << "Processor2 : Message1\n";
  }

  void Handle(const Message3& msg)
  {
    std::cout << "Processor2 : Message3\n";
  }

  void Unhandled(const IMessage& msg)
  {
    std::cout << "Processor2 : Unhandled IMessage\n";
  }
};

We now have a message framework where the processor classes contain just one virtual function and where calls to the handler functions are direct.

The tests are defined exactly as in every previous version of the framework, as is the output.

int main()
{
  Processor1 p1;
  Processor2 p2;

  Message1 m1;
  Message2 m2;
  Message3 m3;
  Message4 m4;

  p1.Receive(m1); // "Processor1 : Message1"
  p1.Receive(m2); // "Processor1 : Message2"
  p1.Receive(m3); // "Processor1 : Message3"
  p1.Receive(m4); // "Processor1 : Message4"

  p2.Receive(m1); // "Processor2 : Message1"
  p2.Receive(m2); // "Processor2 : Unhandled IMessage"
  p2.Receive(m3); // "Processor2 : Message3"
  p2.Receive(m4); // "Processor2 : Unhandled IMessage"

  return 0;
}

Processor1 : Message1
Processor1 : Message2
Processor1 : Message3
Processor1 : Message4
Processor2 : Message1
Processor2 : Unhandled IMessage
Processor2 : Message3
Processor2 : Unhandled IMessage

Chain Of Responsibility

If the ability to set a successor message processor is added to IMessageProcessor, the framework is then able to implement the Chain Of Responsibility design pattern.


// IMessageProcessor base class
IMessageProcessor* pSuccessor;

void SetSuccessor(IMessageProcessor& successor)
{
  pSuccessor = &successor;
}

// Derived message processor class
template <typename TDerived, typename T1>
class MessageProcessor<TDerived, T1, void, void, void> : public IMessageProcessor
{
public:

  void Receive(const IMessage& msg)
  {
    TDerived& derived = static_cast<TDerived&>(*this);

    switch (msg.GetMessageId())
    {
    case T1::ID: derived.Handle(static_cast<const T1&>(msg)); break;
    default:
	{
	  if (pSuccessor)
	  {
	    pSuccessor->Receive(msg);
      }
	  else
	  {
	    derived.Unhandled(msg); break;
	  }
    }
  }
};

A version of this framework can be found as part of the Embedded Template Library, an open source C++ library distributed under the MIT licence.

Download the example code