How Do Those Funky Placeholders Work?

Whenever I learn a new coding technique and try it out at work, it's very interesting to see how rapidly it's adopted throughout the department. One of the fastest to propagate so far is the boost bind library. So much easier to use than the standard library's bind1st or bind2nd adapters and much more flexible. Once you've got the hang of those funny looking placeholders, the bind library is elegant and simple to use, and the initial effort is well rewarded. Your code is clearer to read, easier to understand, quicker to review, quicker to test, it's less likely to contain bugs and is probably more efficient.

In my experience the average developer, by which of course I don't mean you, and certainly not me, when using the bind library for the first time will probably use either too many, too few, or the wrong placeholders; and will put at least one of them in the wrong place. Any of which will result in pages of compiler errors. The average developer will then decide that it's all too difficult, templates are the work of the devil, they haven't got time to read the manual, and they just need to get it working. So they hand code a solution instead and decide to do it properly before review or release, which in all probability never happens.

So I can't decide whether the bind library is intuitive or not. Once you've got the hang of it, it is, but doesn't intuitive mean you don't need to get the hang of it? Can it be true that the more you use the bind library the more intuitive it gets?

Once a developer has `seen the light' he will invariably ask `So how do those funky placeholders work?' In an ideal world you wouldn't concern yourself with the implementation details of a library, you would just use it. However, an understanding of what is going on behind the scenes is useful for several reasons. Firstly, with the error messages the average compiler gives you when you make a typo, it's a big help to have some understanding of what's going on. Secondly, studying the designs developed by experts is always instructive and can help to improve your own designs. Finally, most developers are naturally curious and, once comfortable with the placeholder syntax, often want to know how they work.

This article intends to demonstrate how the bind library's placeholders work by constructing a very basic bind library. It will be modest, very modest, but enough I hope to satisfy your curiosity. The examples are written for clarity above all else, other issues such as efficiency, const correctness, volatility, etc., are not considered. Note also that the function return types are not considered and assumed to be void.

A quick recap

Suppose you have a collection of widgets and you want to perform an action on each of them; you would simply write something like this:

void DoSomething(Widget& widget)
{
  ...
}
for_each(widgets.begin(), widgets.end(),
  DoSomething);

Suppose, however, that you would like to pass each widget to an existing function such as:

void DoSomething(Gadget& gadget, Gizmo& gizmo,
   Widget& widget)
{
  ...
}

The for_each algorithm takes a unary function as its third parameter, which it calls once for each iterator in its range, passing the dereferenced iterator as the single argument to the unary function (see below). Our target function has three parameters, which causes two problems:

• The unary function and the target function have a different number of parameters.
• The dereferenced iterator could map to any one of the target function's parameters.

template<typename InIt, typename UnaryFn>
Fn for_each(InIt first, InIt last, UnaryFn fn)
{
  // perform function for each element
  for(; first != last; ++first)
      fn(*first);
  return fn;
}

Resolving the different number of parameters is done by applying the Fundamental Theory of Software Engineering and adding a level of indirection between the algorithm and the target function. The indirection takes the form of an object, let's call it a binder. The binder's responsibility is to adapt the interface the algorithm calls to the interface of the target function. The binder can be called by for_each because it has a unary operator() , and can call the target function because it's supplied with a pointer to it and the two extra arguments at construction.

Specifying which of DoSomething 's three parameters should be the widget is where placeholders come in. Using the bind library we can simply do this:

for_each(widgets.begin(), widgets.end(),
     bind(&DoSomething, aGadget, aGizmo, _1));

The bind function is passed four arguments: the address of the target function DoSomething , a Gadget object, a Gizmo object and a placeholder _1 . Notice that the order of the second, third and fourth arguments to bind is the same as the order of the arguments to the target function. The placeholder indicates the position of the argument passed to the unary function by for_each . If the signature of DoSomething had expected the widget as the second parameter we would have written:

for_each(widgets.begin(), widgets.end(),
       bind(&DoSomething, aGadget, _1, aGizmo));

The _1 placeholder specifies the mapping of for_each 's single argument to the target signature. For algorithms that expect a unary function you must use a single placeholder, _1 . For algorithms that expect a binary function you must use two placeholders, _1 and _2 . For algorithms that expect a ternary function you must use three placeholders, _1 , _2 and _3 and so on.

For example, adjacent_find is an algorithm that takes a binary function and finds the first instance of two adjacent elements which match a given criteria. If we have a comparison function which takes a third parameter we can bind to it as below:

bool IsEqualWidget(Widget& w1, Widget& w2,
   int tolerance);
adjacent_find(widgets.begin(), widgets.end(),
   bind(IsEqualWidget, _1, _2, 42)); // tolerance = 42

For more information and examples see the boost website.

Constructing a basic bind library

I'm going to construct a basic bind library capable of calling the three parameter version of DoSomething shown earlier, once for each of the Widgets in our collection.

The bind function is one of a family of overloaded factory function templates. The responsibility of each of the overloads is to create a specific type of binder. In our example bind is a function template with four parameters: a target function with three parameters and three parameters to pass to it (see below).

template<typename F, typename A1, typename A2,
   typename A3>
binder<F, list3<A1, A2, A3> > bind(F f, A1 a1, A2 a2,
   A3 a3)
{
  typedef typename list3<A1, A2, A3> list_type;
  list_type  list(a1, a2, a3);
  return binder<F, list_type>(f, list);
}

The return type, the binder that bind creates, is of unspecified type in TR1. In this example it is a class template with two parameters. The first parameter is the target function and the second is an argument list.

template<typename F, typename List>
class binder
{
public:
    binder(F f, List  list):f_(f), list_(list)
    {}
    ...
private:
    F f_;
    List  list_;
};

In this example, the binder is instantiated with an instantiation of list3 as a template argument. list3 is one of a family of class templates. Each of list3 's member variables represents a value passed to the original bind function. We have converted the three arguments to bind into an object with three member variables (see below). Notice the ellipsis, we'll be adding more responsibilities to list3 and its siblings shortly.

template<typename A1, typename A2, typename A3>
class list3
{
public:
  list3(A1 a1, A2 a2, A3 a3): a1_(a1), a2_(a2),
   a3_(a3) {}
  ...
private:
  A1 a1_;
  A2 a2_;
  A3 a3_;
};

Now that we have created our binder we need to turn our attention to what it does. The binder sits between the algorithm that we want to use and the function that we want to call. The for_each algorithm expects its third parameter to be a unary function so we must add a templated unary operator() to the binder.

template<typename F, typename List>
class binder
{
public:
    ...    // As previously defined
  template<typename A1>
  void operator()(A1 a1)
  {
    list1<A1> list(a1); // Explanation coming
    list_(f_, list);
  }
};

The operator() creates a list1 (see below) object from its parameter. The list1 object is very similar to list3 but with just one parameter. We now have two lists of parameters, the list object for the argument passed by the algorithm and the list_ member for the arguments passed into bind .

template<typename A1>
class list1
{
public:
  list1(A1 a1): a1_(a1){}
  ...
private:
  A1 a1_;
};

We have to detect which of the arguments passed to the bind function are placeholders and substitute them for the arguments passed by the algorithm. For arguments that are not placeholders we must simply pass the argument to the function to be called. To achieve this we are going to rely on function overloading.

For list3 we have to add the list3::operator() which is called from the unary binder::operator() (see below). In our first example the three member variables of list3 are:

• a1_ - a Gadget , which should be passed as the first argument of f .
• a2_ - a Gizmo , which should be passed as the second argument of f .
• a3_ - a placeholder ( _1 ) indicating that the first parameter in the list1 (a widget) should be passed as the third argument of f .

template<typename A1, typename A2, typename A3>
class list3
{
public:
  ...    // As previously defined
  template<typename F, typename List1>
  void operator()(F f, List1 list1)
  {
    f(list1[a1_], list1[a2_], list1[a3_]);
    // Explanation coming
  }
};

At the moment there is no way to access the data in list1 , we need to add two operator[] s (see below). Notice that one operator[] takes a placeholder<1> and returns the a1_ member (the widget passed by the for_each algorithm). The second operator[] is templated to take any other type and just return the value it is passed.

template<typename A1>
class list1
{
  ...    // As previously defined
  A1 operator[](placeholder<1>) const { return a1_; }
  template<typename T>
  T operator[](T v) const { return v; }
  ...    // As previously defined
};

When list1[a1_] is evaluated it will resolve to the templated operator[] in list1 and simply return the gadget that was passed in. The same process will occur for list1[a2_] with a Gizmo . However, when list1[a3_] is evaluated the non-templated operator[] (placeholder1) will be selected and a widget will be returned. Hence DoSomething will be called with the correct arguments.

Placeholders then aren't really anything special. They are simply a type that allows overload resolution to occur. We need to have a different type for each of the number of placeholders we decide to scale our library to support. A trivial class template instantiated on an integer value will suffice, for example.

template<int I>
class placeholder{};
placeholder<1> _1;
placeholder<2> _2;
placeholder<3> _3;

The example we set out to achieve will now compile and execute correctly - try it. Next try calling a function with different arguments and the widget in a different position. Finally try calling a function with a different number of arguments, it will fail to compile. Can you work out what we need to add to our library? Hint: look in \boost\bind.hpp!