If you want to enforce the restriction starting from the first principles, here's a little tool that will work:
template <class TList, typename T>
struct EnsureOccurence
{
typedef EnsureOccurence<typename TList::tail, T>::Result Result;
};
template <class T, class U >
struct EnsureOccurence<typelist<T, U>, T>
{
typedef T Result; // can be T or whatever
};
If you instantiate:
typedef EnsureOccurence<cons<int, double>::type, double>::Result Test;
then the first specialization gets instantiated and instantiates recursively the same template with the tail of the list. By this point, the second specialization matches and "extinguishes" the recursion.
If, on the other hand, you try to write:
typedef EnsureOccurence<cons<int, double>::type, long int>::Result Test;
then the second specialization of EnsureOccurence never matches; the recursive instantiation exhausts the typelist, by which point the compiler tries to instantiate null_typelist::tail, a type that does not exist.
So here's the revamped templated constructor of Variant:
... inside Variant ...
template <class T>
Variant(const T& val)
{
typedef EnsureOccurence<TList, T>::Result Test;
new(&buffer_[0]) T(val);
static VTable vtbl =
{
&VTableImpl<T>::TypeId,
&VTableImpl<T>::Destroy,
&VTableImpl<T>::Clone,
};
vptr_ = &vtbl;
}
How about the default constructor? There is a temptation to ban it on grounds of minimalism, but a class without a proper default constructor, is, so to say, too "minimalistic." For one thing, you can't store Variants in STL containers.
A decision that makes sense is to initialize the Variant with a default-constructed object whose type is the first type in the typelist. You can't leave the Variant uninitialized, and defining the constructor that way lets the user place the "cheapest" type in the front of the list.
... inside Variant ...
Variant()
{
typedef typename TList::Head T;
new(&buffer_[0]) T(val);
static VTable vtbl =
{
&VTableImpl<T>::TypeId,
&VTableImpl<T>::Destroy,
&VTableImpl<T>::Clone,
};
vptr_ = &vtbl;
}
Eliminating the code duplication between the templated and the default constructor is left as an interesting exercise to the reader.
Using the Fake VTable
Let's see how to expose the functionality offered by VTableImpl to Variant's user. For example, the function that gets the type identifier of a Variant object looks like this:
template <class TList, class Align = AlignedPOD<TList>::Result>
class Variant
{
...
public:
const std::type_info& TypeId() const
{
return (vptr_->typeId_)();
}
...
};
The code accesses the typeId_ pointer to function from vptr_, and invokes the function it points to, in a single shot. Now the function that returns a typed pointer to the contents of the Variant object is only six lines of code away:
... inside Variant ...
template <typename T> T* GetPtr()
{
return TypeId() == typeid(T)
? reinterpret_cast<T*>(&buffer_[0])
: 0;
}
(Well, in the actual implementation, you would write the corresponding const function as well.)
The destructor is even easier:
... inside Variant ...
~Variant()
{
(vptr_->destroy_)(*this);
}
By now we have a nice little core Variant template, able to create and destroy objects properly, as well as extract the data stored in a type-safe manner. The little class is hungry for extensions, as we'll see in the next installment of "Generic<Programming>".
Conclusions
There are several conclusions to draw from this article. One is that, like software projects, articles on software can run over budget. I initially planned to dedicate one column to discriminated unions. After carefully analyzing the level of detail necessary, I was sure (and advertised) two columns for the task. Now I'm forced to dedicate three columns (or more, no promise this time) to the subject.
However, my belief is that the issues are important enough to be described in detail.
Computing alignment portably is hard, but feasible. It never is 100-percent portable. The task reclaims a language feature. Alignment is important to anyone who wants to implement custom seating for generic types (as Variant does) or to deal directly with memory in various other ways.
The fake vtable idiom has you write by hand what a compiler generates automatically — a structure containing pointers to functions. It also prescribes the explicit presence of a pointer (vptr_) to such a vtable in your objects and has you initialize the pointer properly. Templates make it possible to automate vtable generation.
In exchange for your effort, the fake vtable idiom allows you to implement polymorphic behavior for in-situ objects.
Acknowledgement
Many thanks are due to Emily Winch who provided a thorough and helpful review.
Notes
[1] One of Alan Perlis' legendary one-liners.
[2] A. Alexandrescu. "Generic<Programming>: Discriminated Unions (I)," C/C++ Users Journal C++ Experts Forum, <www.cuj.com/experts/2004/alexandr.htm>.
[3] POD stands for Plain Old Data, a type umbrella that covers primitive types and essentially C-like structs/unions, namely (in all excruciating detail): having no user-declared constructors, no private or protected non-static data member, no base classes, no virtual functions, no non-static data members of type pointer to member, non-POD-struct, non-POD-union (or an array of such types) or reference, no user-defined copy assignment operator, and no user-defined destructor.
[4] Search for "align" in the Boost downloadable archive or on the developer mailing list. You can get to both from <www.boost.org>.
[6] The use of virtual function tables is not required, but virtually all C++ implementations use a variation of this mechanism.
[8] A. Alexandrescu. Modern C++ Design (Addison-Wesley Longman, 2001), Chapters 2 and 3.
Andrei Alexandrescu is a Ph.D. student at University of Washington in Seattle, and author of the acclaimed book Modern C++ Design. He may be contacted at www.moderncppdesign.com. Andrei is also one of the featured instructors of The C++ Seminar.
