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();
}

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.