- 注册时间
- 2005-4-8
- 最后登录
- 1970-1-1
|
楼主 |
发表于 2006-7-19 15:25:00
|
显示全部楼层
神来之笔啊，还没看完，可以去买他的《Modern c++ design》，有中译本
连接：http://www.ddj.com/dept/cpp/184403813
Generic Programming:Typelists and Applications
Andrei Alexandrescu
This month's installment of "Generic reintroduces typelists, discusses alternatives for implementing typelist creation, and presents a concrete application of typelists in a real-world problem: visiting a hierarchy that wasn't designed for visitation.
It's not exactly known how it started.
I only can tell my side of the story: I first saw some weird recursive templates in a post on the Usenet newsgroup comp.lang.c++.moderated (highly recommended, by the way). Later, while in desperate need to automate an Abstract Factory implementation, a certain structure started to occupy my mind.
Other people have independently gone through a similar process, because typelists are all over the place, in various flavors. Czarnecki and Eisenecker introduce in [1] a typelist that actually holds constant integral values. The MPL library [2] defines typelists as well, together with a host of algorithms that operate on them. Modern C++ Design also describes a simple typelist implementation and applies it in no less than five generic components (Functor, Visitor, AbstractFactory, StaticDispatcher, and Tuple), not to mention two automatic hierarchy generators (GenScatterHierarchy and GenLinearHierarchy).
By now the usefulness and applicability of typelists is proven, and knowing about them would certainly improve your arsenal of techniques and your understanding of existing and future C++ libraries. At least that smart intern won't catch you in off guard during a water cooler chat. (Provided that your employer would hire interns these days — but well, that's another story.)
This article reintroduces typelists, together with an interesting application for solving a real-world problem. If you can't tell a typelist from a Christmas wish list, you're in the right place. If you absorb like a sponge everything that's going on in C++, you might still find some interesting stuff, so, read on.
So What Is a Typelist?
It's got to be one of those weird template beasts, right? Actually, typelists are so simple, and so devoid of any value (in the most literal sense), that it's actually quite amazing the C++ community didn't put them to work earlier.
template <class H, class T>
struct typelist
{
typedef H head;
typedef T tail;
};
That's really all there is to it! Nothing up my sleeves, really. Nevertheless, with this simple cell you can build typelists of any length, using the tail composition pioneered by LISP a long time ag
typedef typelist<float, typelist<double, long double> >
floating_point_types;
You can do this because a typelist is a type, and as such it can participate as one of the types in a larger typelist. By convention, a typelist can appear in another typelist only in the tail position, not in the head; this makes typelist processing simpler, without reducing flexibility.
We're almost there; we only need to define an ancillary type that marks the end of a typelist (analogous to LISP's nil). Let's call it null_typelist:
class null_typelist {};
So the correct version of the typelist that holds all floating points is:
typedef typelist<float, typelist<double,
typelist<long double, null_typelist> > >
floating_point_types;
Linearizing Typelist Creation: Three SchoolsIt doesn't take a vulture's eye to see that creating typelists becomes extremely awkward beyond only a few elements. All those nested template instantiations and the closing >s that need to have a space between them, to avoid confusion with the >> operator — ah, the joys of C++ parsing — are quite unwieldy.
There are several schools of thought in tackling this problem. Loki [3] relies on macros, which are defined as follows:
#define TYPELIST_1(T1) typelist<T1, null_typelist>
#define TYPELIST_2(T1, T2) typelist<T1, TYPELIST_1(T2) >
#define TYPELIST_3(T1, T2, T3) typelist<T1, TYPELIST_2(T2, T3) >
...
#define TYPELIST_50...
As you see, each macro relies on the previous one. Loki defines such "constructors" for typelists with up to 50 elements. Beyond that limit, you can either define new macros or concatenate typelists programatically.
I should have known better than to use macros. Text transformation is very powerful, but C++'s macro preprocessor is so primitive, that, almost invariably, when you thought you did something actually interesting with it, it comes from behind to bite you.
In this case, the problem is that you cannot use the macros with simple templates, for example:
typedef TYPELIST_2(vector<int, allocator>,
vector<int, my_allocator>)
storage_choices;
The preprocessor can handle parentheses, but not the angle brackets < and >. So, the text inside TYPELIST_2 looks like four parameters to the preprocessor — namely (1) vector<int, (2) allocator>, (3) vector<int, and (4) my_allocator> — not two as intended. Worse, some preprocessors won't even issue an error — they will just silently ignore arguments (3) and (4) and generate a nonsensical expansion that's bound to cause you a headache.
A better solution is to use templates for generating typelists. The idea is as follows:
template <class T1>
struct cons<T1, null_typelist, null_typelist,
null_typelist>
{
typedef typelist<T1, null_typelist> type;
};
template <class T1, class T2>
struct cons<T1, T2, null_typelist, null_typelist>
{
typedef typelist<T1, typelist<T2,
null_typelist> > type;
};
template <class T1, class T2, class T3>
struct cons<T1, T2, T3, null_typelist>
{
typedef typelist<T1, typelist<T2, typelist<T3,
null_typelist> > > type;
};
template <class T1, class T2, class T3, class T4>
struct cons
{
typedef typelist<T1, typelist<T2, typelist<T3,
typelist<T4, null_typelist> > > > type;
};
The example above works for up to four types. You use cons like this:
typedef cons<float, double, long double>::type
floating_point_types;
The cons template relies on partial specialization. When you instantiate cons<float, double, long double>, first the compiler fills in the fourth argument of cons with the default, so it's really about cons< float, double, long double, null_typelist>. Then, the compiler matches this instantiation against the four defined specializations.
The first specialization is not a match because it requires T2 to be null_typelist, while the concrete T2 is double. Similarly, the second specialization fails due to lack of agreement on T3. The third specialization is a valid candidate because it accepts arbitrary types for T1, T2, T3. All bets are not off yet; the compiler also checks the fourth specialization, which matches as well! It accepts arbitrary types for T1, T2, T3, and T4, so it doesn't have any trouble if T4 is null_typelist. But before you can say "compile-time error," a discriminator kicks in: the third instantiation is selected because it is more specialized than the fourth.
The algorithm for deciding "more specialized"-ness is quite complex, but at an intuitive level, a partial specialization of a template is more specialized than another if it is less general (has fewer degrees of freedom). When matching a concrete argument list against several partially specialized versions of a template, the winner is the most specialized version that can still accommodate the arguments. In our example, the third partial specialization of cons wins because it does match the instantiation cons<float, double, long double, null_typelist> and is more specialized than the fourth specialization. That is because the fourth specialization accepts any type for T4, while the third accepts only null_typelist for T4, thus being more specific.
You can extend cons to work with any number of types, but alas, you cannot extend that upper bound unless you do surgery on cons, or, again, if you rely on some preprocessor tricks.
The third approach uses function signatures. Consider the following:
template <class Fun> struct cons;
template <class T1> struct cons<void (*)(T1)>
{
typedef typelist<T1, null_typelist> type;
};
template <class T1, class T2>
struct cons<void (*)(T1, T2)>
{
typedef typelist<T1, typelist<T2,
null_typelist> > type;
};
template <class T1, class T2, class T3>
struct cons< void (*)(T1, T2, T3)>
{
typedef typelist<T1, typelist<T2,
typelist<T3, null_typelist> > > type;
};
template <class T1, class T2, class T3, class T4>
struct cons<void (*)(T1, T2, T3, T4)>
{
typedef typelist<T1, typelist<T2, typelist<T3,
typelist<T4, null_typelist> > > > type;
};
Now if you define a macro like this:
#define TYPELIST(a) cons< void (*)a >::type
then you can write this:
typedef TYPELIST((float, double, long double))
floating_point_types;
Not bad at all ... if you manage to convince people of the beauty of the two sets of parentheses.
Ok, I know I owe some explanations, so here they are. First thing, the void (*)(T1) is a C++ type (no typo, no emoticon in there!): a pointer to function that takes one argument of type T1 and returns void. The type is more familiar in the form void (*Fun)(T1), a construct that actually contains a name in it.
The cons class template is specialized on pointers to functions returning void and taking one, two, three, and four arguments of any type. Then, the macro TYPELIST expands the construct:
TYPELIST((float, double, long double))
int
cons< void (*) (float, double, long double) >::type
which in turn is exactly:
typelist<float, typelist<double,
typelist<long double, null_typelist> > >
As a mini-conclusion to this section, no solution above is perfect; until some language support for variable template arguments is there, you will have to pay a mixed toll in cleanliness, convenience, extensibility, and ease of use.
For the remainder of the article, let's use the second solution — the one with cons<...>::type.
It is time now to put typelists to work. A previous article [4] shows, for example, how to compute the length of a typelist. In the following, we'll see a new application of typelists in real-world problems.
|
|
发表于 2006-7-19 15:23:00
perator=() method uses the overloaded * and ++ operators of DVExpr[url] to store the result of the vector operation: