The Artima Developer Community
Sponsored Link

C++ Source
On the Tension Between Object-Oriented and Generic Programming in C++
and What Type Erasure Can Do About It
by Thomas Becker
October 15, 2007

<<  Page 2 of 2

Advertisement

Implementing Type Erasure in C++, with an Emphasis on Iterator Type Erasure

Implementing Type Erasure in C++: A Closer Look at boost::any

Recall that Dave Abrahams and Aleksey Gurtovoy defined type erasure as "the process of turning a wide variety of types with a common interface into one type with that same interface." Now imagine you are designing a set of C++ classes with a common interface from scratch, and you want to be able to treat them as one type with that same interface. Talk about OO programming 101: you would derive your classes from a common base class. And that's exactly the idea behind implementing type erasure in C++. We would like the classes whose type we want to erase to be derived from a common base class. But since these classes already exist, and we must work non-intrusively, we can do this only indirectly, by first placing a wrapper class template around the existing classes. The wrapper class template is under our control, and therefore, we can derive it from a common base class.

A good first example to illustrate all this is boost::any, which provides type erasure for the set of all C++ types that are copiable and destructible. A variable of type boost::any can hold objects of any such type. This example is extreme, but it is also extremely simple, because the common interface of the erased types is empty.

Here is the implementation of boost::any, abbreviated to its bare essentials. The common abstract base class from which the wrapper class template will be derived looks like this:

class placeholder
{
public:
  virtual ~placeholder() {}
  virtual placeholder* clone() const=0;
};

And this is the wrapper class template:

template<typename ValueType>
class holder : public placeholder
{
public:
  holder(ValueType const & value) : held(value) {}
  virtual placeholder* clone() const 
  {return new holder(held);}

private:
  ValueType held;
};

The actual type erasing class any is a handle class that holds a pointer to the abstract base class:

class any
{
public:
  any() : content(0) {}

template
any(ValueType const & value) : content(new holder(value)) {}

any(any const & other) : 
  content(other.content ? other.content->clone() : 0) {}

~any() 
{delete content;}

// Implement swap as swapping placeholder pointers, assignment
// as copy and swap.

private:
  placeholder* content;
};

A typical use of boost::any is to hold objects of vastly different types in an STL container.

Since the common interface of the types that boost::any erases is empty, an object of type boost::any isn't worth very much until one retrieves the held object with its original type. To this end, the real boost::any provides a query function to obtain the typeid of the held object, and safe casts to retrieve the held object. In this one respect, boost::any is not typical of type erasure in general. In those cases where the type erasing class actually has an interface, part of the purpose of the type erasure is to restrict clients to that interface. One should therefore not provide ways to retrieve the original objects with their original types.

It should be clear by now how a type erasing class will handle the implementation of the common interface of the erased types: it will forward its public member functions to the abstract base class, where they exist as pure virtuals. The wrapper class template will implement these pure virtuals by forwarding them to its held object.

As was to be expected, type erasure does not come free of charge. We just saw that calling a member function on a type-erasing object incurs the extra cost of a level of indirection and a virtual function call. Construction and destruction of such an object involves newing and deleting an object. The heap access can sometimes be eliminated if a small object optimization is employed, as is the case with the poly library[7] (more about this very interesting library shortly). If you agree with me that good engineering is not about following dogmas but about choosing sensible trade-offs, then you will also agree that this performance overhead is not per se a problem. It is an aspect to be kept in mind when choosing your trade-offs.

Beyond boost::any

In his original documentation of boost::any[5], Kevlin Henney has pointed out that his any class can be used as a blueprint for more general instances of type erasure: "A similar design, offering more appropriate operators, can be used for a generalized function adaptor, any_function, a generalized iterator adaptor, any_iterator, and other object types that need uniform runtime treatment but support only compile-time template parameter conformance."

The any_function class has since been implemented as boost::function. In the next few sections, I will discuss my attempt at the any_iterator[2]. A similar, independent effort at C++ iterator type erasure is the Adobe Public Library's any_iterator[8]. I will discuss the relationship between their work and mine later.

Perhaps the most exciting recent work in the area of type erasure is the poly library by Jaakko Jarvi, Mat Marcus, and Sean Parent. What they do, in the best tradition of generic programming, is to abstract out the commonality of C++ type erasure implementations into a generic mechanism. Their poly library is done in ConceptGCC, the fork of gcc that implements concepts as envisioned by the C++ Standard Committee. Therefore, it may be a while until their generic type erasure will be available to the C++ community at large. Nonetheless, I believe that the poly library will be of critical importance in applied C++ programming, as it will provide the long sought-after reconciliation between the object-oriented and generic programming paradigms.

Implementing Iterator Type Erasure in C++: The any_iterator

Let me begin by reminding you what the original motivation for my any_iterator was: I had a number crunching class that provided to its clients a large number of sequences of numbers. Some of these sequences—the primary ones—were internally stored in STL containers, others—the secondary ones—were calculated from the primary ones on the fly by Boost iterator adaptors. Making clients deal with this zoo of iterator types had caused grief. Therefore, I wanted an iterator that was to be an input iterator—and an input iterator only—that would dereference to a double. This iterator was to be such that it could hold any one of the multitude of iterators that my class was exposing.

It would of course be silly to go for just this special input iterator. Instead, I aimed for a full solution to the C++ iterator type erasure problem. The first issue that one needs to address in a situation like that is the granularity of the type erasure. Clearly, it does not make sense to have a single any_iterator type that can hold just any old C++ iterator.

So what kind of any_iterator types should there be, and what "concrete" iterators should be assignable to them? In order to answer these questions it is useful to do a fast forward and think about the implementation of the any_iterator first. It turns out that we have our work cut out for us here. On the one hand, we know that the overall structure of our implementation will follow the standard type erasure technique as set forth by boost::any. On the other hand, it is clear that an iterator class that one writes in C++ must be Standard conforming, and the Standard conformance will of course be achieved by deriving from boost::iterator_facade[9]. As usual, the devil is in the details, but this high-level description is pretty much all you need to know about the implementation of any_iterator.

Now we are in a position to tackle the issue of the granularity of our iterator type erasure.

Determining the Granularity of the Iterator Type Erasure

The boost::iterator_facade class template that we'll be using to implement the any_iterator takes five template arguments, like this:

template<
  lass Derived, // The derived iterator type being constructed
  class Value,
  class CategoryOrTraversal,
  class Reference = Value&,
  class Difference = std::ptrdiff_t
>
class iterator_facade;

When we derive our any_iterator from this class template, we'll have to decide on values for the second through fifth template arguments. These four types make up the iterator traits in the sense of the Boost iterator library. This suggests that we should have our any_iterator class template take exactly those four template arguments. In other words, there will be exactly one any_iterator type for each set of iterator traits. This design is in keeping with the spirit of the Boost iterator library and it has worked well for us in practice.

The other question in connection with the granularity of the type erasure is which "concrete" iterators should be assignable to an instantiation of the any_iterator class template. Technically speaking, this is the problem of correctly enabling and disabling the templatized converting constructor and assignment operator of the any_iterator class template. To make the solution that I chose plausible to you, let us look at an example of using the any_iterator.

Remember that earlier, we were looking for an input iterator type that would dereference to a double. This iterator type was to be capable of holding STL iterators such as std::vector<double>::const_iterator and std::list<double>::const_iterator. It should also be able to hold all manner of Boost iterators such as transform iterators and zip iterators, as long as they are input iterators and dereference to something that converts to a double. To make the example a bit more interesting, let us assume that we want to expose an iterator with bidirectional traversal capabilities instead of just an input iterator. Given that our any_iterator class template looks like this:

template<
  class Value,
  class CategoryOrTraversal,
  class Reference = Value&,
  class Difference = std::ptrdiff_t
>
class any_iterator;
let's try this for our number iterator:
typedef any_iterator<
  double const,
  boost::bidirectional_traversal_tag
> 
number_iterator;

Notice that I have used the bidirectional traversal tag from the Boost iterator library for the CategoryOrTraversal template parameter. It is possible to use the old-style STL iterator categories such as std::bidirectional_iterator_tag here, but you should prefer the new traversal tags. See the Boost iterator library documentation[10] for more details.

This will actually go a long way. The following will compile and work fine:

number_iterator number_it;

std::vector<double> number_vector(42, 43.0);
number_it = number_vector.begin();
double d = *number_it;

std::list<double> number_list(42, 44.0);
number_it = number_list.begin();
d = *number_it;

However, if we try to assign to our number iterator a transform iterator which, upon dereferencing, multiplies by 100.0, we run into trouble.

number_it = boost::make_transform_iterator(
  number_vector.begin(),
  boost::bind(std::multiplies<double>(), _1, 100)
);

My any_iterator's assignment operator is not enabled for this assignment, and you will get an error message such as:

binary '=': no operator found which takes a right-hand operand of type...

Why is it that I disallow this? Our number iterator currently has a reference type of double const&. The transform iterator's reference type is double. Dereferencing the number iterator is implemented by forwarding to the wrapped transform iterator. The conversion would work fine: double converts to double const&. But the number iterator's operator* would be returning a reference to a temporary local variable. If you follow the good practice of treating compiler warnings as errors, you will most likely catch that, but I don't want to be responsible for that. Therefore, I don't even let you go there.

The solution is easy: our choice of traits for the number iterator was not quite right.

What we really want is this:

typedef any_iterator<
  double const, // Value
  boost::bidirectional_traversal_tag,
  double const // Reference
> 
number_iterator;

Now all of the assignments above will compile and work. Note that the old STL-style iterator categories would not have allowed us to do this: in the STL, the reference type of a bidirectional iterator must be a reference. The new Boost iterator traversal tags give us more degrees of freedom in this regard.

It is now also possible to start with a vector of floats, like this:

std::vector<float> float_vector(42, 43.0);
number_it = float_vector.begin();

This would not have been allowed either before, when the any_iterator's reference type was double const& instead of double const. The reason is that somewhere deep inside of operator*, there was a conversion from float const& to double const&, which results in the creation of a temporary. The any_iterator's operator* would have returned a reference to that temporary. So the bad news is that these references to local temporaries can creep up on you in unexpected ways. The good news is that my any_iterator will catch these situations for you and disallow the respective assignments and copies.

It turns out that the exact rules by which an any_iterator instantiation decides which iterator types to accept for wrapping are quite subtle. But before we go into the details, let me point out that in practice, there is very little need to study these rules. One is not very likely to make mistakes in this respect. For example, it is clear that an any_iterator like our number_iterator, having bidirectional traversal category, will not accept something that's a forward iterator only, like an iterator into a singly linked list. That would not make sense. Similarly, our number_iterator would not accept anything that dereferences to something that does not convert to a double. There is no way for that to be meaningful. So really, using the any_iterator is just as easy as it looks in the examples above. But for completeness' sake, and for the fun of it, let us study the rules anyway.

Suppose that some_any_iterator is an instantiation of the any_iterator class template with value type, traversal tag, reference type, and difference type equal to AnyItValue, AnyItTraversal, AnyItReference, and AnyItDifference, respectively. Assume further that some_iterator is an iterator type with value type, traversal tag, reference type, and difference type equal to ItValue, ItTraversal, ItReference, and ItDifference, respectively. Then a variable of type some_any_iterator will accept an object of type some_iterator if and only if the following four conditions are met:

  1. ItValue converts to AnyItValue.
     
  2. ItTraversal and AnyItTraversal are equal, or the former is derived from the latter. This means that some_iterator's traversal category is equal to or better than that of some_any_iterator.
     
  3. The following are all true:
     
    • ItReference converts to AnyItReference.
       
    • If AnyItReference is a reference, then so is ItReference.
       
    • If AnyItReference and ItReference are both references, then the following is true: after stripping const qualifiers and references from AnyItReference and ItReference, the two are either the same, or the former is a base class of the latter.
       
    The second and third of the three conditions above ensure that no situation is allowed where some_any_iterator's operator* would return a reference to a temporary.
     
  4. If some_any_iterator's traversal category is random access, then ItDifference and AnyItDifference are convertible to each other both ways. Here, we need convertibility in both directions because the difference type occurs as an argument type as well as a result type of iterator operators.

This settles the issue of the granularity of our iterator type erasure. The only thing that remains to be discussed is convertibility between different any_iterator types.

Conversion between Different any_iterator Types

Instantiations of the any_iterator class template are Standard conforming iterators. Therefore, according to what we have so far, it would be possible to assign an object of one any_iterator type to a variable of another any_iterator type, as long as the traits of the two any_iterator types are compatible for type erasure:

std::vector<double> vect;
std::vector<double>::iterator vit;
any_iterator<double, std::random_access_iterator_tag> rit;
rit = vit;

any_iterator<double, std::forward_iterator_tag> fit;
fit = rit;

The iterator fit now holds a copy of rit, which in turn holds the concrete vector iterator vit. All operations will go through two levels of indirection. It would certainly be a legitimate design decision to just leave it to that and never think another thing about it. However, it bothered me that clients could end up with nesting levels greater than 1 and perhaps not even be aware of it. Therefore, I made it so that an assignment or construction of one any_iterator from another is possible only if the two are of the exact same type. Instead, I added a few conversion operators which behave nicely, copying the wrapped iterator rather than increasing the nesting depth. The upside of this is that now you know that your nesting depth will never be greater than 1, no matter what you do. The downside is that the rules for the new conversions end up being a bit more restrictive than the rules for assignment to an any_iterator. Here's how it works:

Let ait_source and ait_target be two different instantiations of the any_iterator class template. Then there is a conversion from ait_source to ait_target if and only if either:

or

The deeper reason why I have to require the value types, reference types, and difference types to be equal is that in C++, convertibility is not transitive: If T1 converts to T2 and T2 converts to T3, it does not follow that T1 converts to T3. Therefore, if I were to require only that the value type of ait_source convert to the value type of ait_target, the wrapped iterator of an ait_source object might not be suitable for wrapping by an ait_target object.

Mundane Uses of the any_iterator

The any_iterator was originally invented for the purpose of alleviating problems that arise when the OO and generic programming paradigms coexist. I have since found numerous more mundane applications in small, everyday programming tasks. Here's an example.

I recently had to write a small piece of code that iterated over a vector of things and did some processing with each element. Moreover, there was a runtime condition that specified whether ordinary iteration or reverse iteration was to be used. Needless to say, I wasn't going to deal with the direction of the iteration myself. That's the whole point of having iterators and reverse iterators. Therefore, my code was going to look something like this:

// some_vector is an STL vector of type some_vector_type
if(!reverseIteration)
{
  some_vector_type::iterator begin = some_vector.begin();
  some_vector_type::iterator end = some_vector.end();
  // Do what needs to be done from begin to end
 }
else
{
  some_vector_type::reverse_iterator begin = some_vector.rbegin();
  some_vector_type::reverse_iterator end = some_vector.rend();
  // Do what needs to be done from begin to end
}

The annoying part is that now, the "Do what needs to be done" part operates on iterators of unrelated types. Short of the abomination of duplicating the code, that forces me to use a templatized function to do what needs to be done. In many cases, that may be just fine and dandy. Still, I must say that I hate this kind of situation with a vengeance. The fact that the ordinary iterator and the reverse iterator have unrelated types, which never felt very natural in the first place, deprives me of the freedom to choose my function nesting level the way I see fit.

Iterator type erasure saves. Below is how you can use an any_iterator if you do not wish to use a function template to implement the "Do what needs to be done" part. Here, you can also see a little convenience metafunction called make_any_iterator_type at work. This metafunction, which comes with my any_iterator, takes an iterator type as its argument and produces an instantiation of the any_iterator class template with the same iterator traits. In other words, it allows you to create an any_iterator type "by example."

typedef 
make_any_iterator_type<
  some_vector_type::iterator
>::type local_iter_type;

local_iter_type begin;
local_iter_type end;
if(!reverseIteration)
{
  begin = some_vector.begin();
  end = some_vector.end();
}
else
{
  begin = some_vector.rbegin();
  end = some_vector.rend();
}
// Do what needs to be done from begin to end

Regardless of how often I am going to prefer the second solution over the first, I find it rather comforting to have the choice available to me.

Other Attempts at C++ Iterator Type Erasure

As I mentioned earlier, there is an any_iterator class template in the Adobe Public Library, which was developed independently from my any_iterator. It is clear from the documentation that their effort is very similar to mine. However, they currently label their work as "an experiment." This is probably the reason why the documentation is not very specific. Therefore, I am not sure how exactly our efforts relate when it comes to the more subtle design decisions. It would of course be possible to find out more by studying their source code or playing with their class. However, I am reluctant to spend that kind of time and effort as long as their work is considered experimental and may therefore change anytime.

My guess would be that the design decisions that the Adobe Library people made are very similar to mine and possibly better. For now, my any_iterator gives you the advantage of being well-documented and being usable by just downloading a few header files, rather than having to install a third party library. But if and when the Adobe people upgrade their work from "experimental" to "officially supported," you're probably better off going with something that has the full support of a dedicated group of very smart people.

Outlook: C++ Concepts and the any_iterator

The implementation of class templates such as any_iterator will benefit enormously from the introduction of concepts into the C++ Standard. If you are unfamiliar with this proposed language addition, a good place to start is the article on the poly library by Jaakko Jarvi, Mat Marcus, and Sean Parent. Section 2 of the article is a lucid and succinct introduction to concepts. The poly library that is described in the rest of their paper is in fact a great case study in applying concepts. The paper also has an excellent list of references on C++ concepts.

Please read on only if you are interested in how C++ concepts will replace and improve current workarounds that are based on the SFINAE principle. If you do not want to dig that deep—and there is nothing wrong with that attitude—skip right ahead to the acknowledgements, and you are done with reading this article!

Of all the additions to the C++ language that are currently in the pipeline, C++ concepts is probably the most important and far-reaching one. Concepts will add an enormous amount of structure, clarity, expressiveness, and convenience to generic programming in C++. The any_iterator is special in this respect because it is a rare example of a class template where C++ concepts will do more than just simplify and improve the code. There is actually something fairly important that I cannot do right now, but will be able to do with concepts. In other words, the point that I will be making in the rest of this article is this: C++ concepts are not only a better and more convenient alternative to the workarounds that we currently use. Rather, some of today's workarounds are positively broken and we need concepts to fix them.

We saw earlier that one of the main issues with the any_iterator was to enable and disable the converting constructor and assignment operator in such a way that only certain compatible "concrete" iterators are allowed for construction and assignment to the any_iterator. In today's C++, this is achieved with boost::enable_if[11], which I will assume you are familiar with. My any_iterator's assignment operator, for example, currently looks like this:

template<class WrappedIterator>
typename boost::enable_if<
  detail::is_iterator_type_erasure_compatible<
    WrappedIterator, 
    any_iterator
  >,
  any_iterator
>::type &
operator=(WrappedIterator const & wrapped_iterator)
{
  any_iterator tmp(wrapped_iterator);
  swap(tmp);
  return *this;
}

Here, is_iterator_type_erasure_compatible is a fairly complex metafunction that implements the rules for assigning "concrete" iterator types to any_iterator types. Thanks to boost:enable_if, this is actually a rather elegant and readable solution. Moreover, the error message that you get when you try to assign an iterator of incompatible type to an any_iterator is not one of those cryptic, endlessly nested template error messages. Your compiler will simply say something like:

binary '=': no operator found which takes a right-hand operand of
type...

But the fact remains that this is a workaround. I had to ponder over a lot of those awful template error messages until I had it all working on each of the three compilers that I currently support. In the shiny new world of concepts, I will be able to express my condition is_iterator_type_erasure_compatible directly in the language as what it is, namely, a property of types. I will be defining a concept that will most likely look something like this:

auto concept IteratorTypeErasureCompatible<
  typename SourceIterator,
  typename TargetIterator
> : Iterator(SourceIterator) && Iterator(TargetIterator)
{
  requires 
  Convertible(
    SourceIterator::value_type, 
    TargetIterator::value_type
  ) 
  &&
  Convertible(
    SourceIterator::reference_type, 
    TargetIterator::reference_type
  ) 
  &&
  (! Reference(TargetIterator::reference_type) || 
     Reference(SourceIterator::reference_type)
  ) 
  &&
  // ...
  
};

The any_iterator's assignment operator will then look like this:

template<class WrappedIterator>
requires IteratorTypeErasureCompatible<
  WrappedIterator, 
  any_iterator
>
any_iterator& operator=(WrappedIterator const & wrapped_iterator)
{
  any_iterator tmp(wrapped_iterator);
  swap(tmp);
  return *this;
}

Rather obviously, this is an enormous step forward from the workaround using SFINAE, traits, and template metaprogramming. Moreover, the error message for a bad assignment is going to improve a bit. It will now give a reason for the failure to assign, namely, the violation of the concept IteratorTypeErasureCompatible.

Things get a lot more interesting if we try to do the same thing for the converting constructor from wrapped iterator. After looking at the assignment operator, you would expect that converting constructor to look something like this:

template<class WrappedIterator>
any_iterator(
  WrappedIterator const & wrapped_iterator,
  typename boost::enable_if<
    detail::is_iterator_type_erasure_compatible<
      WrappedIterator, 
      any_iterator
    >
  >::type* dummy = NULL 
)
{
  // construct an any_iterator that wraps wrapped_iterator
}

There is nothing wrong with that code as it stands. And yet, under some Standard-conforming compilers, this sets into motion a long, circuitous chain of events at the end of which we'll find desaster.

Suppose that with the above definition of the converting constructor, we try to construct an any_iterator from something that is not even an iterator, like an STL pair of two integers:

std::pair<int, int> p(42, 42);

typedef any_iterator<
  double, 
  std::random_access_iterator_tag
> any_ra_iterator;

any_ra_iterator ra_it(p);

Needless to say, we want this construction to fail, and we're hoping for a nice, simple error message from the compiler. So what's going to happen? As the compiler encounters the boost::enable_if in the constructor, it will evaluate the metafunction call:

is_iterator_type_erasure_compatible<
  std::pair<int, int>, 
  any_ra_iterator
>

I never showed you the details of is_iterator_type_erasure_compatible, but we know that it is the conjunction of a bunch of conditions such as "the value type of the first argument converts to the value type of the second argument." Therefore, one of the things that the compiler encounters deep, deep down in this metafunction evaluation is this:

std::iterator_traits<std::pair<int, int> >::value_type

This template instantiation will fail, because STL pairs are not iterators and thus have no value type. So, overall, substituting the type std::pair<int, int> for the template parameter WrappedIterator of our any_iterator's converting constructor failed. That's not an error, says SFINAE, and hence, this constructor just isn't there. We would expect a one-line error error message like:

error: cannot convert from std::pair<_Ty1,_Ty2> to any_iterator<...

Under some compilers, that's exactly what happens. Other compilers will barf up a pile of horrible template errors at the center of which lies this:

error : 'value_type' : is not a member of 'std::pair<_Ty1,_Ty2>' 
with _Ty1 = ...

The reason is that the version of the SFINAE principle that the Standard requires is, in point of fact, rather lame. SFINAE is required to kick in only if the substitution failure occurs at the very top of the template instantiation stack. In our case, the substitution failure is way down on the stack. Some compilers voluntarily apply SFINAE in this case as well, but nobody is required to do so.

Ok, so what kind of a problem have we seen so far? Almost none at all. The only bad thing is that when we try to construct an any_iterator from something that is not even an iterator in the first place, then some compilers give us an ugly error message instead of a nice one. Big deal. Ugly error messages abound in today's C++ programming with templates.

Everything would be quite alright if it weren't, of all things, a converting constructor that barfs up the ugly error message instead of politely disabling itself. Consider what happens if we ask whether std::pair<int, int> is convertible to the any_iterator:

typedef any_iterator<
  double, 
  std::random_access_iterator_tag
> any_ra_iterator;

bool b = boost::is_convertible<
  std::pair<int, int>, 
  any_ra_iterator
>::value;

One of the things that the metafunction boost::is_convertible will do is to look for a converting constructor of any_ra_iterator that takes an std::pair<int, int> as its argument. In doing so, it will encounter the compile error that we discussed earlier. Therefore, the code above will not compile.

Now that's really bad. For a while, I tried to kid myself into thinking that one could live with that, but no. A type which can cause a compile error when it is used as the second argument to boost::is_convertible is evil. In particular, if a class has a non-explicit, templatized converting constructor, then the mere act of substituting for the template argument must not cause a compile error. The reason why this principle is important is this: if a class violates the principle, then the compiler can encounter an error while it is building a function overload set. Even though the offending constructor may end up not being used in the situation for which the overload set is built, just creating the overload set causes a compile error. That is pure evil if I ever saw it. In fact, this is the exact reason why the SFINAE principle exists in the first place.

My problem here is that the substitution failure occurs deep down on the template instantiation stack, where the SFINAE principle as required by the Standard does not apply. It is not possible to fix things so that the failure occurs at the top of the stack. To do that, I would need a metafunction is_iterator, or has_iterator_traits, or some such thing. Such a metafunction does not exist, and it is impossible to write one (try it).

Once we'll have concepts in C++, all this is going to go away. Just take one look at the concept IteratorTypeErasureCompatible that I outlined earlier. The very first thing that it requires is that WrappedIterator is an iterator at all. If that's not the case, the concept is not modeled, and all is well.

For now, I could see no alternative but make the constructor that constructs an any_iterator from a wrapped iterator explicit and replace the enable_if with a static assert. I really hated to do that, but for the life of me, I can't see any other way out until there will be concepts in C++. What this means is that for now, a wrapped iterator never converts to an any_iterator. There are only two ways to get a "concrete" iterator object into an any_iterator variable: either by ordinary assignment, as in:

std::vector<int> vect;
any_iterator<int, std::forward_iterator_tag> ait;
ait = vect.begin();

or using explicit construction:

std::vector<int>;
any_iterator<
  int, 
  std::forward_iterator_tag
> ait_1(vect.begin()); // fine

any_iterator<
  int, 
  std::forward_iterator_tag
> ait_2 = vect.begin(); // error, requires non-explicit ctor

Please, C++ Standard committee and compiler vendors, give us concepts! We're in a lot of pain here!

Acknowledgements

I am greatly indebted to Dave Abrahams, Christopher Baus, Fred Bertsch, Don Harriman, and Thomas Witt, who have helped me in more ways than I can recall. All remaining errors and inadequacies, both in this article and in my any_iterator implementation, are mine.

Share your opinion

Have an opinion about Tension between Object-Oriented Programming and Generic Programming?

Discuss this article in the Articles Forum topic, On the Tension between Object-Oriented and Generic Programming in C++, and What Type Erasure Can Do about It.

References

[1] Bjarne Stroustrup's definition of C++
http://www.research.att.com/~bs/glossary.html#GC++

[2] Download my any_iterator (with documentation and regression tests)
http://thbecker.net/free_software_utilities/type_erasure_for_cpp_iterators/IteratorTypeErasure.zip

[3] An interview with Alexander Stepanov
http://www.stlport.org/resources/StepanovUSA.html

[4] Dave Abrahams' and Aleksey Gurtovoy's book on C++ template metaprogramming
http://boost-consulting.com/mplbook/

[5] boost::any
http://www.boost.org/doc/html/any.html

[6] boost::function
http://www.boost.org/doc/html/function.html">

[7] Article on the poly librar by Jaakko Jarvi, Mat Marcus, and Sean Parent
http://homepages.fh-regensburg.de/~mpool/mpool07/proceedings/5.pdf

[8] Adobe Public Library's any_iterator
http://opensource.adobe.com/classadobe_1_1any__iterator.html">

[9] boost::iterator_facade
http://www.boost.org/libs/iterator/doc/index.html#iterator-facade-and-adaptor

[10] Boost new style iterators
http://www.boost.org/libs/iterator/doc/index.html#new-style-iterators

[11] boost::enable_if
http://www.boost.org/libs/utility/enable_if.html>

About the Author

Thomas Becker is a scientific software engineer at Zephyr Associates, Inc. in Lake Tahoe, Nevada, where he works on financial analytics software. He is a former columnist for the now defunct C/C++ Users Journal. You can reach him at thomas at styleadvisor dot com. To find out more about Thomas, visit his homepage at thbecker.net

<<  Page 2 of 2


Sponsored Links



Google
  Web Artima.com   
Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us