Type erasure techniques

^{(With type erasure, I mean hiding some or all of the type information regarding a class, somewhat like Boost.Any.)}
I want to get a hold of type erasure techniques, while also sharing those, which I know of. My hope is kinda to find some crazy technique that somebody thought of in his/her darkest hour. :)

The first and most obvious, and commonly taken approach, that I know, are virtual functions. Just hide the implementation of your class inside an interface based class hierarchy. Many Boost libraries do this, for example Boost.Any does this to hide your type and Boost.Shared_ptr does this to hide the (de)allocation mechanic.

Then there is the option with function pointers to templated functions, while holding the actual object in a void* pointer, like Boost.Function does to hide the real type of the functor. Example implementations can be found at the end of the question.

So, for my actual question:
What other type erasure techniques do you know of? Please provide them, if possible, with an example code, use cases, your experience with them and maybe links for further reading.

Edit
(Since I wasn't sure wether to add this as an answer, or just edit the question, I'll just do the safer one.)
Another nice technique to hide the actual type of something without virtual functions or void* fiddling, is the one GMan employs here, with relevance to my question on how exactly this works.

---

Example code:

#include <iostream>
#include <string>
 
// NOTE: The class name indicates the underlying type erasure technique
 
// this behaves like the Boost.Any type w.r.t. implementation details
class Any_Virtual{
        struct holder_base{
                virtual ~holder_base(){}
                virtual holder_base* clone() const = 0;
        };
 
        template<class T>
        struct holder : holder_base{
                holder()
                        : held_()
                {}
 
                holder(T const& t)
                        : held_(t)
                {}
 
                virtual ~holder(){
                }
 
                virtual holder_base* clone() const {
                        return new holder<T>(*this);
                }
 
                T held_;
        };
 
public:
        Any_Virtual()
                : storage_(0)
        {}
 
        Any_Virtual(Any_Virtual const& other)
                : storage_(other.storage_->clone())
        {}
 
        template<class T>
        Any_Virtual(T const& t)
                : storage_(new holder<T>(t))
        {}
 
        ~Any_Virtual(){
                Clear();
        }
 
        Any_Virtual& operator=(Any_Virtual const& other){
                Clear();
                storage_ = other.storage_->clone();
                return *this;
        }
 
        template<class T>
        Any_Virtual& operator=(T const& t){
                Clear();
                storage_ = new holder<T>(t);
                return *this;
        }
 
        void Clear(){
                if(storage_)
                        delete storage_;
        }
 
        template<class T>
        T& As(){
                return static_cast<holder<T>*>(storage_)->held_;
        }
 
private:
        holder_base* storage_;
};
 
// the following demonstrates the use of void pointers 
// and function pointers to templated operate functions
// to safely hide the type
 
enum Operation{
        CopyTag,
        DeleteTag
};
 
template<class T>
void Operate(void*const& in, void*& out, Operation op){
        switch(op){
        case CopyTag:
                out = new T(*static_cast<T*>(in));
                return;
        case DeleteTag:
                delete static_cast<T*>(out);
        }
}
 
class Any_VoidPtr{
public:
        Any_VoidPtr()
                : object_(0)
                , operate_(0)
        {}
 
        Any_VoidPtr(Any_VoidPtr const& other)
                : object_(0)
                , operate_(other.operate_)
        {
                if(other.object_)
                        operate_(other.object_, object_, CopyTag);
        }
 
        template<class T>
        Any_VoidPtr(T const& t)
                : object_(new T(t))
                , operate_(&Operate<T>)
        {}
 
        ~Any_VoidPtr(){
                Clear();
        }
 
        Any_VoidPtr& operator=(Any_VoidPtr const& other){
                Clear();
                operate_ = other.operate_;
                operate_(other.object_, object_, CopyTag);
                return *this;
        }
 
        template<class T>
        Any_VoidPtr& operator=(T const& t){
                Clear();
                object_ = new T(t);
                operate_ = &Operate<T>;
                return *this;
        }
 
        void Clear(){
                if(object_)
                        operate_(0,object_,DeleteTag);
                object_ = 0;
        }
 
        template<class T>
        T& As(){
                return *static_cast<T*>(object_);
        }
 
private:
        typedef void (*OperateFunc)(void*const&,void*&,Operation);
 
        void* object_;
        OperateFunc operate_;
};
 
int main(){
        Any_Virtual a = 6;
        std::cout << a.As<int>() << std::endl;
 
        a = std::string("oh hi!");
        std::cout << a.As<std::string>() << std::endl;
 
        Any_Virtual av2 = a;
 
        Any_VoidPtr a2 = 42;
        std::cout << a2.As<int>() << std::endl;
 
        Any_VoidPtr a3 = a.As<std::string>();
        a2 = a3;
        a2.As<std::string>() += " - again!";
        std::cout << "a2: " << a2.As<std::string>() << std::endl;
        std::cout << "a3: " << a3.As<std::string>() << std::endl;
 
        a3 = a;
        a3.As<Any_Virtual>().As<std::string>() += " - and yet again!!";
        std::cout << "a: " << a.As<std::string>() << std::endl;
        std::cout << "a3->a: " << a3.As<Any_Virtual>().As<std::string>() << std::endl;
 
        std::cin.get();
}

All type erasure techniques in C++ are done with function pointers (for behaviour) and void* (for data). The "different" methods simply differ in the way they add semantic sugar. Virtual functions, e.g., are just semantic sugar for

struct Class {
    struct vtable {
        void (*dtor)(Class*);
        void (*func)(Class*,double);
    } * vtbl
};

iow: function pointers.

That said, there's one technique I particularly like, though: It's shared_ptr<void>, simply because it blows the minds off of people who don't know you can do this: You can store any data in a shared_ptr<void>, and still have the correct destructor called at the end, because the shared_ptr constructor is a function template, and will use the type of the actual object passed for creating the deleter by default:

{
    const shared_ptr<void> sp( new A );
} // calls A::~A() here

Of course, this is just the usual void*/function-pointer type erasure, but very conveniently packaged.

Fundamentally, those are your options: virtual functions or function pointers.

How you store the data and associate it with the functions can vary. For example, you could store a pointer-to-base, and have the derived class contain the data and the virtual function implementations, or you could store the data elsewhere (e.g. in a separately allocated buffer), and just have the derived class provide the virtual function implementations, which take a void* that points to the data. If you store the data in a separate buffer, then you could use function pointers rather than virtual functions.

Storing a pointer-to-base works well in this context, even if the data is stored separately, if there are multiple operations that you wish to apply to your type-erased data. Otherwise you end up with multiple function pointers (one for each of the type-erased functions), or functions with a parameter that specifies the operation to perform.

I would also consider (similar to void*) the use of "raw storage": char buffer[N].

In C++0x you have std::aligned_storage<Size,Align>::type for this.

You can store anything you want in there, as long as it's small enough and you deal with the alignment properly.

Stroustrup, in The C++ programming language (4th edition) §25.3, states:

> Variants of the technique of using a single runt-time representation for values of a number of types and relying on the (static) type system to ensure that they are used only according to their declared type has been called type erasure.

In particular, no use of virtual functions or function pointers is needed to perform type erasure if we use templates. The case, already mentioned in other answers, of the correct destructor call according to the type stored in a std::shared_ptr<void> is an example of that.

The example provided in Stroustrup's book is just as enjoyable.

Think about implementing template<class T> class Vector, a container along the lines of std::vector. When you will use your Vector with a lot of different pointers types, as it often happens, the compiler will supposedly generate different code for every pointer type.

This code bloat can be prevented by defining a specialization of Vector for void* pointers and then using this specialization as a common base implementation of Vector<T*> for all others types T:

template<typename T>
class Vector<T*> : private Vector<void*>{
// all the dirty work is done once in the base class only 
public:
	// ...
    // static type system ensures that a reference of right type is returned
	T*& operator[](size_t i) { return reinterpret_cast<T*&>(Vector<void*>::operator[](i)); }
};

As you can see, we have a strongly typed container but Vector<Animal*>, Vector<Dog*>, Vector<Cat*>, ..., will share the same (C++ and binary) code for the implementation, having their pointer type erased behind void*.

See this series of posts for a (fairly short) list of type erasure techniques and the discussion about the trade-offs: Part I, Part II, Part III, Part IV.

The one I haven't seen mentioned yet is Adobe.Poly, and Boost.Variant, which can be considered a type erasure to some extent.

As stated by Marc, one can use cast std::shared_ptr<void>. For example store the type in a function pointer, cast it and store in a functor of only one type:

#include <iostream>
#include <memory>
#include <functional>

using voidFun = void(*)(std::shared_ptr<void>);

template<typename T>
void fun(std::shared_ptr<T> t)
{
    std::cout << *t << std::endl;
}

int main()
{
    std::function<void(std::shared_ptr<void>)> call;

    call = reinterpret_cast<voidFun>(fun<std::string>);
    call(std::make_shared<std::string>("Hi there!"));

    call = reinterpret_cast<voidFun>(fun<int>);
    call(std::make_shared<int>(33));

    call = reinterpret_cast<voidFun>(fun<char>);
    call(std::make_shared<int>(33));


    // Output:,
    // Hi there!
    // 33
    // !
}