You invested your money. Find out what happened.
GreaterThanZero.com


Type Erasure for C++ Iterators

In their book on C++ template metaprogramming, Dave Abrahams and Aleksey Gurtovoy define type erasure as "the process of turning a wide variety of types with a common interface into one type with that same interface."

Perhaps the most widely known and used example of type erasure is boost::function. boost::function is a class template that takes one template argument, a function type. Choosing a function type amounts to choosing a return type and a list of argument types for a function. Suppose we instantiate boost::function as follows:

boost::function < int (int) > foo;

The variable foo can now hold anything that's callable with an int as its only argument, and whose return type is convertible to int. This could be a function pointer, a user-defined functor, the result of a boost::bind, or what have you not. Clearly, this matches the above definition of type erasure.

The relevance of this in the context of object-oriented programming is that an interface can now say to the client programmer: "I need you to give me something that's callable as specified by this here function type. What it really is, I don't care. You can give me different things at run time. Also, you can change your client code so it gives me something other than it did before, and you won't have to recompile me." Or, referring to a return value rather than an argument, an interface could say: "I'll give you something that's callable as specified by this here function type. What it really is, you won't know. It could change at run time. I might also change it at compile time, but don't worry, you won't have to recompile because of that."

When working with C++ iterators, it is often desirable to design interfaces that take or return iterators and have a similar "insensitivity" to the actual, concrete type. In other words, the interface may want to say something like: "I need you to give me an iterator which is a forward iterator or better and which dereferences to an int. What type it really is, I don't care. You can give me different things at run time. Also, you can change your client code so it gives me something other than it did before, and you won't have to recompile me."

I have written a class template any_iterator that does just that. The status of the implementation is as follows: any_iterator is fully functional and is being used in production code. It has been tested under Microsoft VC7.1, Microsoft VC8, Microsoft VC9, Intel 9.1, gcc 3.2.4, gcc 3.4.2, gcc 4.0.3, and gcc 4.1.2. More recent compilers and compiler versions seem to always work, probably because C++ template support has stabilized by now.

The download below contains the .hpp files, HTML documentation, a demo .cpp file, and regression tests with project files and make files for the compilers mentioned above. The HTML documentation can also be viewed online.

Important Caveat: Please note that using the any_iterator—or type erasing classes in general, for that matter—is not without pitfalls. Before you use the any_iterator, be sure to read the warning in the documentation.

Download any_iterator

Revision History

Jul 2010
Bug fix (reported by Edgar Binder): Constructors and create function of any_iterator_wrapper from wrapped iterator must take their argument by const reference (performance!).

Mar 2008
Implemented a workaround for the fact that boost::is_convertible<X, Y>::value is false whenever X and Y are abstract base classes (including the case where X equals Y).

Feb 2008
Bug fix (reported by Sergei Politov): conversion operators and their helper functions must be const members of the class template any_iterator.

Sep 2007
Bug fix in the metafunction that determines whether a given iterator type is suitable for assignment to an any_iterator instantiation.

Aug 2007

  • Refined the rules for assigning concrete iterators to any_iterator variables: cases where operator* would return a reference to a temporary are now caught early and disallowed.
  • Added some more conversions between different any_iterator types.
  • Added HTML documentation to the distibution.

Jan 2007
"Boostified" version created. Syntactic and semantic differences vs. previous version:

  • any_iterator's template arguments are now modeled after boost::iterator_facade
  • any_iterator's constructor from concrete iterators is now explicit, that is, a concrete iterator does not convert to an any_iterator anymore. This is a temporary annoyance that will go away once C++ concepts are available.

Jun 2006
Original version created (experimental).