A del_fun Function Adaptor for STL Containers

Copyright © 2003-2008 Wesley Steiner

23-Feb-08


This article presents a C++ template definition (del_fun) that automatically applies the C++ delete operator to polymorphic pointer elements of an STL container object when invoked via iterative STL functions such as for_each.

Introduction

Under ideal conditions STL containers are designed to hold class objects (instances of C++ classes). This greatly simplifies our job as C++ programmers by having the compiler automatically take care of all object copy, assignment and cleanup that occurs as a result of the application of STL functions. Unfortunately this convenience is not available for containers of pointers and containers of pointers occur frequently in C++ when polymorphic objects are involved.

Containers of Pointers

One of the first things you learn as an STL programmer is that declaring a container of polymorphic objects doesn't work, you must use a container of pointers to polymorphic objects. As an example consider the following all to familiar polymorphic class hierarchy:

class Shape {
   public:
   virtual void Draw() = 0; // makes this an abstract class
};

class RectangleShape : public Shape {
   public:
   virtual void Draw() { /* implements drawing */ };
};

class CircleShape : public Shape {
   public:
   virtual void Draw() { /* implements drawing */ };
};

Here Shape is an abstract base class of RectangleShape and CircleShape which are concrete derived classes that implement the pure virtual Draw method. In order to use these shape objects in an STL container we must define a container of pointers to the base Shape class as follows:

vector<Shape*> container;

Then you can populate the container with concrete objects derived from this abstract base class like this:

container.push_back(new RectangleShape);
container.push_back(new RectangleShape);
container.push_back(new CircleShape);

Keep in mind when using STL containers of pointers that all of your concrete classes must be safe for copying and assignment but that's another story for another day.

A First Solution

For now lets assume you are using your containers of pointers and now its time to end your application and cleanup resources. As mentioned above STL containers take care of deleting resources when the container goes out of scope. In the above example the container object will automatically release the memory used by each element, a Shape*, when it goes out of scope. However the objects that the elements point to are not destroyed. Destroying the objects pointed to are your responsibility.

Early adopters of the STL library, myself included, usually solved this as follows:

...
for (size_t i = 0; i < container.size(); ++i) {
   delete container[i]; // deletes the object pointed to
}
container.clear(); // clears the pointers

A Better STL Style Solution

Quickly we learned that writing our own loops to iterate over an STL container was reinventing the wheel and, more importantly, inviting an opportunity to introduce bugs. The STL solution is to use the for_each function as follows:

void del_shape(Shape* a_shape) {
   delete a_shape;
}
...
for_each(container.begin(), container.end(), del_shape);
container.clear(); // clears the pointers

A common, and valid, complaint with this solution is that you need to write a one-line function to do the delete for every type of base object class. Once again this gets tedious and is prone to errors. In a perfect world what you really want to do is call the delete operator in place like this:

for_each(container.begin(), container.end(), delete);

Unfortunately, as much as we would like it too, the above line of code will not compile and rightly so if you look at the definition of for_each.

template<class _II, class _Fn> inline
_Fn for_each(_II _F, _II _L, _Fn _Op)
   {for (; _F != _L; ++_F)
   _Op(*_F);
   return (_Op); }

Reading past the cryptic nature of STL code we can see that the for_each function iterates over the elements of the container and applies the _Op argument, via a function call, with the element as its argument. The trick used throughout STL involves the use of Function Adaptors or Functors. Functors are C++ classes that implement a function operator, operator(), to execute the body of the function. In our case the code to be executed is the call to the delete operator on the pointer value of each container element.

A Specialized Functor Solution

When developing C++ template solutions I find it is often easier to first write a solution for a specific type and then generalize it later with templates.

Lets start by writing a specialized Shape functor that we can pass to the for_each function that will do the job of calling the delete operator on the pointer argument:

struct del_shape_t
{
   del_shape_t& operator()(Shape* p)
   {
      delete p;
      return *this;
   }
};

del_shape_t del_shape()
{
   return del_shape_t();
}

...

for_each(container.begin(), container.end(), del_shape());

Here the purpose of the del_shape function is to return a functor class, del_shape_t, which when invoked inside the for_each loop will apply the del_shape_t::operator() method on the argument. The body of del_shape_t::operator() simply calls the delete operator as desired.

Of course this example only works for containers of Shape* elements. In order to make this more useful we need to generalize it for any pointer element types by using templates.

A Generalized Functor Solution

In order to generalize the above functor for use with any pointer types we simply replace the Shape type with a template parameter as follows:

template<class T>
struct del_fun_t
{
   del_fun_t& operator()(T* p) {
     delete p;
     return *this;
   }
};

template<class T>
del_fun_t<T> del_fun()
{
   return del_fun_t<T>();
}

The purpose of the del_fun function is to return an instance of a del_fun_t object which is passed to the for_each function.

All we need to do now is include the pointer type as a template parameter in the call to for_each as follows:

for_each(container.begin(), container.end(), del_fun<Shape>());

Now we have a functor that will apply the delete operator to any pointer type. This functor does with templates what we would need to do explicitly.

Conclusion

The del_fun function can be used anywhere a functor argument is needed in STL. The same pattern can be adopted to invoke other C++ operators or functionality as necessary.

Bibliography

Scott Meyers, Effective STL: 50 Specific Ways to Improve Your Use of the Standard Template Library (Addison-Wesley, 2001)

Scott Meyers, Effective C++: Second Edition, 50 Specific Ways to Improve Your Programs and Designs (Addison-Wesley, 1998)