STL Member Function Adaptors

Have you ever wished that STL member function adaptors such as mem_fun or mem_fun_ref would let you invoke a method of a class of your choice, instead of invoking methods of objects held in an STL container? The External member function adaptor lets you call a member function through a pointer to an instance of a class of your choice. Unlike the mem_fun family of member function adaptors, the pointer to the object being accessed is not stored in the STL container. Either the mem_fun or mem_fun_ref member function adaptors use the pointer or reference to each separate object held in an STL container to gain access to the desired member function of all the different objects in the container. The precondition for using the mem_fun family of function adaptors is the existence of objects in containers with public methods that can be invoked.

The External member function adaptor, on the other hand, makes no assumptions about the type of items stored in the STL container. The item in the STL container could be a primitive data type such as an integer, or a more complex data type such as a class. Upon creation, the External member function adaptor is provided a pointer to the method to be invoked, as well as a pointer to the object that implements the method. STL algorithms such as for_each and find_if can use this adaptor to invoke the method of this object passing each item stored in the STL container being processed.

The Problem

Consider Figure 1, in which a window uses a layout manager to arrange different shapes on the visible part of the window based on the following:

• Position of other shapes already displayed on the window.

• Layout policy that determines placement and size of the shape shown.

The window notifies the Layout Manager to display the shapes by invoking the ArrangeShapes method. This routine needs to invoke the draw method of each shape in the list with the appropriate position (x,y coordinates and width, height) parameter.

You cannot iterate over the list using for_each and use mem_fun to bind a position as a parameter since the position changes for each shape. You could iterate over the list using a for loop, compute the new position for each shape, call each shape to draw itself with the appropriate position value, and then update the ShapesAlreadyShown variable. This solution works, but using a for loop to iterate over an STL container has several drawbacks (see Scott Meyers's Effective STL, Item 43). In general, hard-coded loops have the following disadvantages:

• You must study the body of the loop to understand its purpose, instead of using a for_each algorithm. The name of the function passed to the for_each indicates the purpose of the operation.
• They're error prone. For instance, deleting elements from a container from within a loop is tricky, requiring you to take into account the rules each container has for invalidating iterators. Using a find or find_if algorithm to point to the element to be deleted and then erasing the element from the container always works and is safer.

• They do not take advantage of the inherent storage and traversal optimizations implemented by certain containers and are accessible via the find method of the container itself.

• Each time you hard code a loop you duplicate the looping logic.

So what about using a function object? A function object lets you make use of STL algorithms such as for_each and find_if. This function object needs to have access to the Layout Manager's private data. In particular, this object is passed in as a parameter to the layout policy and needs to modify the ShapesAlreadyShown variable; see Listing 1. It isn't good practice to have objects know about their containers and (more importantly) modify data owned by the container. Function objects, when used as parameters to STL algorithms such as for_each, tend to lead to code bloat. In addition, because function objects are separate classes, it is difficult to determine where they should reside. Function objects often end up nested inside the class that owns them, thus cluttering the interface of the class.

The Solution

Using a member function of the class that owns the STL container is the most natural solution. In the previous example, the ArrangeShapes method could iterate over all the shapes (using for_each), invoking the ShowNextShape method and passing as a parameter a pointer to each shape.

bool LayoutManager:: ArrangeShapes()
{
   ...
   for_each(shapes.begin(),shapes.end(),
      extern_mem_fun_(&LayoutManager::ShowNextShape,this));
   ...
}
bool LayoutManager:: ShowNextShape(shape* s)
{
  ...
  //Compute new position based on layout policy
  s->draw(position);
  // Update ShapesAlreadyShown
}

The extern_mem_fun is a member function adaptor that lets algorithms such as for_each and find_if process the elements in a container by invoking a method of a class of your choice and passing each element in the container as a parameter. These member functions have full access to all the data owned by the instance of that class. Contrast the use of extern_mem_fun with the use of function objects. In Listing 1, the function object ShowNextShape needs to be passed as a parameter, the LayoutPolicy by value, and the ShapesAlreadyShown by reference so that this variable can be modified.

Examining Extern_mem_fun in Detail

The extern_mem_fun in Listing 2 is a template function that creates the template function object extern_mem_fun_t. The implementation of extern_mem_fun mimics the standard implementation of mem_fun, which invokes the template function object mem_fun_t. The difference between the two is the additional parameter ClassType* passed to extern_ mem_fun. This parameter is a pointer to an arbitrary object (external to an STL container) that invokes the member function specified in the first parameter. mem_fun, on the other hand, invokes the member function of each object stored inside the STL container. The elegant technique employed by STL uses template functions to deduce the template arguments for a call as opposed to exposing the template function object extern_mem_fun_t directly. Doing so forces users to specify all the template parameters for the function object. This is a detail that users should not have to worry about.

The extern_mem_fun_t in Listing 3 is a template function object that implements the functionality of the external member function adaptor. While the implementation of extern_mem_fun_t might seem similar to that of STL's mem_fun_t, there are some important differences. A snippet of the implementation of mem_fun_t is:

...
(1)    ReturnType(ContainerItemType* pm)();
 ... 
(2)    ReturnType operator()
                (ContainerItemType* p)
{
       return((p->*pm)());
}

Algorithms such as for_each, find_if, and others using the mem_fun function invoke the same member function over each element of an STL container. The pointer to each element in the container is passed into the operator() member function as a parameter. This code assumes that the container stores pointers to objects that implement the member function with the aforementioned signature in (1). Contrast this with the implementation of operator() in extern_mem_fun_t in Listing 3. No assumptions are made about the type of the argument passed into operator(). Algorithms like for_each and find_if, using the extern_mem_fun function, iterate over the elements of the STL container invoking the operator() method and passing each element of the STL container as a parameter. Figure 2 shows how mem_fun is directly responsible for accessing each item in the STL container. In this case, the responsibility for processing the item rests with mem_fun. Figure 3, on the other hand, shows that it is the User Class that is responsible for processing the item. extern_mem_fun delegates this responsibility to this class by invoking the ProcessItem method. In this case, the User Class acts as a mediator that keeps the member function adaptor from explicitly referencing the item in the container, thus promoting a more loosely coupled design. The User Class encapsulates any additional logic needed to process the item stored in the STL container.

The extern_mem_fun_t member function adaptor is particularly useful during the refactoring of classes that overuse loop logic to process elements of STL containers, as well as classes that overuse function objects — especially ones with side effects (function objects that try to access elements of the User Class). extern_mem_fun_t encourages the creation of private/protected member functions to process items stored in the STL container.

In Listing 3, operator ->* is used to invoke a member function through a pointer. To do this, both a pointer to the object that owns the member function and the pointer to the member function itself need to be passed to the extern_mem_fun_t constructor.

Also, the class extern_mem_fun_t inherits from unary_function. This is necessary if you want to make your extern_mem_fun_t adaptable — that is, usable with the function adapters not1, not2, bind1st, and bind2nd. Finally, note that the return type of the member function passed to extern_mem_fun must be nonvoid if you are using Visual C++.

What if you want to pass an additional parameter to the member function that processes items stored in the STL container? The answer is extern_mem_fun1, as shown in Listing 4.

Returning to Figure 3, assume that the method ProcessItem requires an additional parameter (an int) to be passed in so that its signature would look like:

ProcessItem(Item I, int value);

Now you could invoke this method using for_each like this:

for_each(shapes.begin(), shapes.end(),
  bind2nd(extern_mem_fun1(&UserClass::ProcessItem,this), 10)
        );

The extra parameter passed to ProcessItem cannot be a reference type. Defining a reference type parameter causes a reference-to-reference compiler error. This is not a shortcoming of extern_mem_fun1; rather, it happens because bind2nd takes as a parameter a reference data type. The call to bind2nd creates a binder2nd that the Standard defines as follows:

template <class Operation>
class binder2nd
    : public unary_function
                     <typename Operation::first_argument_type,
                            typename Operation::result_type> {
 ...
public:
 binder2nd(const Operation& x,
         const typename Operation::second_argument_type& y);
  ...

If ProcessItem's second_argument_type were a reference type, then the type of y in the constructor would be &&. Because a reference to a reference is illegal in C++, you get a compilation error. The Boost call_traits library (http://www.boost.org/) avoids this problem by using the Boost call_traits templates.

Conclusion

STL algorithms such as for_each and find_if can be used with extern_mem_fun and extern_mem_fun1 to replace error-prone loop logic, as well as eliminate the proliferation of function objects that try to replace the functionality that should be implemented by methods of the class. The extern_mem_fun member function adaptor promotes the natural paradigm where private, protected, and public methods of a class process the private data of the class. The extern_mem_fun class accomplishes this by delegating the responsibility of processing elements in an STL container to a member function of a class that owns the container. The listings presented here, which are downloadable from the CUJ web site (http://www.cuj.com/code/), were compiled using Visual C++ 6.0.

It is important to note that there are binder libraries that offer the functionality of extern_mem_fun, and much more. For example, using Boost::bind, the equivalent (of the example) of extern_mem_fun is:

for_each(shapes.begin(),shapes.end(),
   bind(bind(&LayoutManager::ShowNextShape,
   this,_1),_1));

Boost::bind is a generalization of the standard functions std::bind1st and std::bind2nd. It supports different arity (number of arguments), arbitrary function objects, functions, function pointers, and member function pointers, and is able to bind any argument to a specific value or route input arguments into arbitrary positions. bind does not place any requirements on the function object; in particular, it does not need the result_type, first_argument_type, and second_argument_type standard typedefs.