In this article, Thomas Becker combines generic and object-oriented programming to create a type-safe, heterogeneous iterator: any_iterator:

http://www.artima.com/cppsource/type_erasure.html

What do you think of the author's any_iterator?

How do you ensure binary compatibility across compile-unit boundary while using vtable as a type-erasure mechanism?
Are you assuming that the client code and the library code is using the same compiler? Because if they're not, there's no way this would work.

Besides, could the fake vtable idiom solve this problem across different compilers?

The any_iterator is a class template that resides in a header file. You are not linking to a library when you use it. It's all plain old straightforward C++. There is no linker trickery going on here.

What I meant was:

// in a lib
any_iterator<...> f() { ... }

// client code
void g()
{
any_iterator<...> iter = f();
int value = *iter;
}

assuming the lib and the client code are compiled using different compilers.

Would the above code work?

I must admit that I have never tried to compile different parts of a program on different compilers, and I don't believe I would recommend for anybody to do that. What I can tell you is this: whatever problems you will encounter are not specific to the any_iterator class template. Take any one of the iterator adaptors in the Boost iterator library, such as boost::transform_iterator. These are class templates that are derived from boost:iterator_facade, just like the any_iterator. Whatever problems you may encounter with the any_iterator, you would encounter the same problem with boost::transform_iterator. There is nothing specific to my any_iterator class in this respect.

First of all, it's not type erasure, it's structural subtyping: the original type is wrapped into another type which presents a common interface to the world through a base class which is used by users of that code. No types are erased.

Secondly, it's so fundamental that I don't understand why 2 pages are needed for the presentation. You want to wrap something into something else? simple:

1) make an interface.
2) make a template implementation class which inherits from above interface.
3) make a wrapper for said interface with value semantics to use in the code.

Thirdly, I don't like iterators with indirect calls where they are not really needed. Iterating should be easy. This solution only accounts for the fact that C++ lacks anonymous functions and for_each can not be used as it was meant to be.

As for C++ concepts, yeah, they are nice (type classes for C++! yeah!), but the C++ world has more severe problems than that (lack of garbage collection, lack of anonymous functions, lack of type deduction for lvalues, lack of a good standard library etc). I guess the C++ committee folks choose to do whatever they like instead of what we need.

Type erasure is the C++ way of achieving structural subtyping. Given that C++ is a strongly typed language, having structural subtyping is anything but fundamental - in fact it is quite amazing that it works.

As for the rest, blah, blah, blah.





Anyway, I ran into the is_iterator trap a short time ago. Consider this overload set:

template <typename T>
data_holding_object<T> make_dho();

template <typename Iterator>
data_holding_object<
typename std::iterator_traits<Iterator>::value_type
>
make_dho(Iterator first, Iterator last);


Harmless, right? I want an empty dho, I create one using make_dho<int>() (the actual situation in my library is more complex; directly using the data_holding_object type is impractical). I want a pre-filled one, I create one using make_dho(v.begin(), v.end()).

Well ... except that creating the overload set fails in GCC 4. (Haven't tested other compilers yet.) make_dho<int>() fails to compile.
I got quite creative trying to implement is_iterator. I thought I had a solution that works using lazy_enable_if - only to realize that the enable_if simply failed always, not just for non-iterators.



On the other hand, my type erasure in the same library works beautifully. Being able to write source<int> instead of a type that would fill 5 lines and have only a single virtual call per operation as overhead is really nice.

Great article, Thomas. It was an easy read, despite the relatively advanced nature of the material.

You might recall that I emailed you a while back about a similar implementation I had come up with. In fact I just this moment discovered that my second follow-up is *still* sitting in my outbox for some reason, after many months of lying dormant! I sincerely apologise for this; it wasn't my intention to be rude.

For anyone that is interested, my opaque_iterator<> can be found here: http://www.mr-edd.co.uk/?page_id=43

It's much the same idea, but I designed it coming from a different direction, that of reducing the compile time dependencies associated with stuff like the boost iterator adaptors. Type-erasure was achieved almost as an unconscious by-product.

>>
I got quite creative trying to implement is_iterator.
<<

I'm glad to hear that I am not the only one who banged his head against that one... :-]

I really should have mentioned your work in the references to my article, Edd. Sorry I forgot! It is true that we're coming from somewhat different directions, but the connection is clearly there.

Goodness gracious, type erasure re-interpreted as object-oriented programming! Now I'm waiting for an article that proclaims void* as the new way to do polymorphism.

My approach to type erasure in general and the any_iterator in particular was motivated mostly by problems that arose in practical, commercial software engineering. You can find a more stringent scientific explanation of the relationship between generic programming, object oriented programming, and type erasure in the article by Mat Marcus, Jaakko Jarvi, and Sean Parent on their poly library:

http://homepages.fh-regensburg.de/~mpool/mpool07/proceedings/5.pdf

They have chosen not to use the term "type erasure" at all, but that's not something that we should argue about. Consensus on terminology is something that takes time to evolve.

Hi,

Based on your early implementation, I've implemented my own any_iterator for a few years.
If interested, see any_range @ http://p-stade.sourceforge.net/oven/doc/html/index.html
any_iterator/range introduces recursive ranges.


Regards,

--
Shunsuke Sogame

Thanks for the link. That seems like a good idea, to have an any_range based on the any_iterator. I was not aware of your work (it didn't occur to me to google for any_range), or else I would have mentioned it in my article.

Ok, reply to myself:

>They have chosen not to use the term "type erasure" at
> all,

I'm beginning to understand why some people are not happy with the term "type erasure." It does sound a bit like "making things typeless." Perhaps the person who posted the root message to this thread was a victim of this misunderstanding when he likened type erasure to using void*. (See, no matter what someone says, there is always some value in it.) Hm, what would be a better term? How about NIRP, for "non-intrusive runtime polymorphism" :o)