Generic
Andrei alexandrescu
Foreword
Andrei alexandrescu's article don't need me to say, classic! Because the younger brother is limited, I don't dare to translate, I am afraid that there is a suspicion of my men, I have a good time. ^ _ ^, The friends who are looking forward to publish your experience and discuss together.
Note: This Article Updated September 21, 2000
. The term "conversion" in C describes the process of obtaining a value of one type from a value of another type However, sometimes you need a different kind of conversion: you might need to obtain a value when you have a type, or the other way around. Such conversions are unnatural to C because the world of types and that of values are separated by a thick boundary. In certain circumstances, however, you need to cross the border between the two, and this column discusses how to do that .
Mapping Integers to Types
A surprisingly Simple Template Can Be Very Helpful To Many Generic Programming IDioms:
Template
Struct Int2Type
{
Enum {value = v};
}
Int2Type "generates" a distinct type for each distinct constant integral value passed. This is because different template instantiations are distinct types, so Int2Type <0> is different from Int2Type <1> and so on. In addition, the value that generated the type IS "Saved" in The Enum Member Value.
You might use int2type wherever you need to quickly "Typify" an integral constant. Say, for Example, That You Design a NiftyContainer Class Template.
Template
Class NiftyContainer
{
...
}
NiftyContainer Stores Pointers to T. In Some Member Functions of NiftyContainer, You Need To Clone Objects of Type T. IF T IS A NON-POLYMORPHIC TYPE, You Would SAY:
T * psomeobj = ...
T * pNewObj = new T (* pSomeObj);. With polymorphic types, the story is a bit more complicated, so let's say you establish the convention that all polymorphic types to be used with NiftyContainer must define a Clone virtual function You can then clone Objects like SO:
T * pnewobj = psomeobj-> clone ();
Because your container must be able to accommodate both types, you must implement both cloning algorithms and select the appropriate one at compile time. You then communicate whether or not a type is polymorphic through a boolean (non-type) template parameter of NiftyContainer and rely On The Programmer to Pass The Correct Flag.
Template
Class NiftyContainer
{
...
}
NiftyContainer
NiftyContainer
If the type you store in NiftyContainer is not polymorphic, you can optimize many member functions of NiftyContainer because you can count on constant object size and value semantics. In all these member functions, you need to select one algorithm or another depending on the isPolymorphic template Argument.
At First Glance, It Seems Like You CAN Use A Mere if Statement.
Template
Class NiftyContainer
{
...
Void Dosomething (T * Pobj)
{
IF (ISPOLYMORPHIC)
{
... POLYMORPHIC Algorithm ...
}
Else
{
... Non-Polymorphic Algorithm ...
}
}
}
The problem is that the compiler will not let you get away with this code. For example, if the polymorphic algorithm uses pObj-> Clone, then NiftyContainer :: DoSomething does not compile for any type that does not define a member function Clone . True, it is obvious at compile time what branch of the if statement executes. However, that does not matter to the compiler, which diligently tries to compile both branches, even if the optimizer will later eliminate the dead code. If you try to call DoSomething for NiftyContainer
IT Would Be Nice If The Compiling Dead Code, But That's Not The Case, So What Would Be A SatisFactory Solution?
As it turns out, there are a number of solutions, and Int2Type provides a particularly clean one. It can transform ad-hoc the boolean value isPolymorphic into two distinct types corresponding to isPolymorphic's true and false values. Then you can use Int2Type
The incarnation of the "integral type" idiom is shown below.
Template
Class NiftyContainer
{
Private:
Void Dosomething (T * Pobj, Int2Type
{
... POLYMORPHIC Algorithm ...
}
Void Dosomething (T * Pobj, Int2Type
{
... Non-Polymorphic Algorithm ...
}
PUBLIC:
Void Dosomething (t * pobj) {
DOSMETHING (POBJ, INT2TYPE
}
}
The code is simple and to the point. DoSomething calls a private overloaded function. Depending on the value of isPolymorphic, one of the two private overloads gets called, completing the dispatch. The dummy temporary variable of type Int2Type
NOT SO FAST, SKYWALKER!
Seeing the above, you might think there's a smarter way, by using some of those template specialization tricks. Why is that dummy temporary necessary? There's got to be a better way. Surprisingly, however, Int2Type is very hard to beat in simplicity, generality And Effectiveness.
One Attempt Could Involve Specializing NiftyContainer :: DOSMETHING for Any T And the Two Possible Values of IsPolyMorphic. This is the charter of partial Template Specialization, Right?
Template
Void NiftyContainer
{
... POLYMORPHIC Algorithm ...
}
Template
Void NiftyContainer
{
... Non-Polymorphic Algorithm ...
}
AS Nice As The Code Above Might Look, Alas, It's Not Legal. There Is No Such Thing As Partially Specializing One Member Function of a class template. You can Partially Specialize All of NiftyContainer:
Template
Class NiftyContainer
{
... Non-Polymorphic NiftyContainer ...
}
You Also Can Totally Specialize Dosomething:
Template <>
Void NiftyContainer
{
... Non-Polymorphic Algorithm ...
}
But, oddly, you cannot do anything in between [1].
Another solution might involve using traits [2] and implementing DoSomething outside NiftyContainer (in the traits class). This can be awkward as it segregates part of DoSomething's implementation.A third solution that attempts to still use traits, but tries to keep everything together, would be to define the traits class inside NiftyContainer as a private inner class. to make a long story short, this works, but by the time you manage to implement it, you come to realize just how much better the Int2Type-based idiom is. And Maybe the Nicest Part of It is this You can actually put the little int2type template in a library and document its intended.
TYPE-TO-TYPE MAPPINGS
Consider the function below:
Template
T * CREATE (Const u & arg)
{
Return New T (Arg);
}
Create Makes a New Object, Passing An Argument To ITS Constructor.
Now say there is a rule in your application: objects of type Widget are legacy code and must take two arguments upon construction, the second being a fixed value like -1 You do not have this problem in all classes derived from Widget..
How Can You Specialize Create SO That It Treats Widget Differently from ALL OTHER TYPES? You Cannot Partially Specialize A Function; That IS, You CAN't SAY Something Like:
// illegal code - don't try this at home
Template
Widget * Create
{
Return New Widget (Arg, -1);
}
In Absence of Partial Specialization of Functions, The Only Tool We Have IS, AGAIN, OVERLOADING. WE Might Pass A Dummy Object of Type T And Rely On Overloading.
// an importation of create relying on overloading
Template
T * Create (Const U & Arg, T)
{
Return New T (Arg);
Template
Widget * Create (Const U & Arg, Widget)
{
Return New Widget (Arg, -1);
}
// USE CREATE ()
String * pstr = Create ("Hello", String ());
Widget * pw = crete (100, widget ());
The second parameter of Create serves only for selecting the appropriate overload It also is the trouble with this would-be idiom:. You waste time constructing an arbitrarily complex object that you do not use Even if the optimizer might help you with that,. Nothing Helps if Widget Disables Its Default Constructor.
The proverbial extra level of indirection can help here, too. An idea is to pass T * instead of T as the dummy template parameter. At runtime, you can always pass the null pointer, which is reasonably cheap to construct.
Template
T * Create (Const U & Arg, T *)
{
Return New T (Arg);
}
Template
Widget * Create (const u & arg, widget *)
{
Return New Widget (Arg, -1);
}
// USE CREATE ()
String * pstr = Create ("Hello", (String *) 0);
Widget * pw = crete (100, (widget *) 0);
This Way Is At Best Confusing for Create's Users. TO ETERNALIZE SOLUTION AS An IDiom, We can use a little template Similar to int2type.
Template
Struct Type2Type
{
Typedef t OriginalType;
}
Now You Can Write:
Template
T * Create (const u & arg, type2type
{
Return New T (Arg);
}
Template
Widget * Create (const u & arg, type2type
{
Return New Widget (Arg, -1);
}
// USE CREATE ()
String * pstr = Create ("Hello", Type2Type
Widget * pw = crete (100, type2type
THIS CERTAINLY IS More Explanatory Than AN Alternative Solution. Again, You CAN include Type2Type in a library and document ITENDED USE.DETECTING CONVERTIBILITY AND INHERITANCE
IN Implementing Template Functions and Classes, a Question That Arises Every So Offen IS: Given Two Arbitrary Types B And D, How Can You Detect WHETHER D in HERITS from b or not?
Discovering such relationships at compile time is key to implementing advanced optimizations in generic libraries. In a generic function, you can rely on an optimized algorithm if a class implements a certain interface, without having to apply a dynamic_cast for that.
Detecting inheritance relies on a more general mechanism, that of detecting convertibility. The more general problem that we will solve together is how to detect whether an arbitrary type T supports automatic conversion to an arbitrary type U?
There is a solution to this problem, and it relies on sizeof (You thought the only use for sizeof was as an argument to memset, huh?) There is a surprising amount of power in sizeof;. This is because you can apply sizeof to any expression, no matter how complex, and sizeof returns its size, without actually evaluating that expression at runtime This means that sizeof is aware of overloading, template instantiation, conversion rules -. everything that can take part in a C expression in fact,. SizeOf Is a Complete Facility For Deducing The Type of an Expression; Eventually, SizeOf Throws Away The Expression and Returns You Only The size of its result [3].
The idea of conversion detection relies on using sizeof with overloaded functions You cunningly provide two overloads of a function:. One accepts the type to convert to (U), and the other accepts just about anything else You call the overloaded function with T,. whose convertibility to U you want to determine If the function that accepts a U gets called, you know that T is convertible to U;. if the "fallback" function gets called, then T is not convertible to U.To detect which function gets Called, You Arrange Types of Different Sizes, And Discriminate With Sizeof. The Types Themsels Do Not Matter, As long as the the Have Different Sizes.
Let's First Create Two Types of Different Sizes (Apparently, Char and Long Double Do Have Different Sizes, But That Not Guaranteed by The Standard.) A Foolproof Scheme Would Be The Following:
Typedef char small;
Struct Big {char Dummy [2];
By Definition, SIZEOF (SMALL) IS One. Also, The Size of Big Is Unknown, But It's for Sure Greater Than, Which is The Only Guarantee We need.
Next, WE NEED The Two overloads. ONE Accepts a U and returns, Say, A Small.
Small test (u);
How do you write a function that accepts "anything else"? A template is not a solution because the template would qualify as the best match, thus hiding the conversion. We need a worse match than an automatic conversion. A quick look through the conversion Rules Applied for a Function Call Gives The Ellipsis Match, Which Is The Worst of All - The Bottom of The List. That's Exactly What The Doctor Prescribed.
BIG TEST (...);
(Calling a function with ellipsis with a C object has undefined results, but who cares Nobody actually calls the function It's not even implemented?..) Now we need to apply sizeof to the call of Test, passing it a T:
Const Bool Convexists =
SIZEOF (TEST (TEST (TEST (TEST)) == SIZEOF (SMALL);
That's it! The call of Test gets a default-constructed object, T, and then sizeof extracts that expression's result size. It can be either sizeof (Small) or sizeof (Big), depending on whether the compiler found a conversion or not.
There is one little problem What if T makes its default constructor private In this case, the expression T fails to compile and so does all of our scaffolding Fortunately, there is a simple solution -.?. Just use a strawman function returning a T. In this case, the compiler is happy and so area.
T maket ();
Const Bool Convexists =
SIZEOF (Test (Maket ())) == SIZEOF (SMALL);
(By the Way, ISN 抰 IT Nifty Just How much you can do with finctions, like maket and test, which not only don 抰 do anything, but Which Don Even Really Exist At All?)
NOW That We Have IT Working, Let's Package Everything in a class template That Hides All the details of type meaningless and express.
Template
Class Conversion
{
Typedef char small;
Struct Big {char Dummy [2];
Static Small Test (U);
Static Big Test (...);
T maket ();
PUBLIC:
ENUM {exists =
SIZEOF (TEST ())) == SIZEOF (SMALL)};
}
Now You Can Test The Conversion Template Class by Writing:
int main ()
{
Using namespace std;
cout
<< Conversion
<< Conversion
<< Conversion
This Little Program Prints "1 0 0". Note That, Although Std :: Vector Does Implement a Constructor Taking a size_t, The Conversion Test Returns ZERO BECAUSE THAT CONSTRUCTOR IS Explicit.
We can IMPLEMENT TWO More Constants Inside Conversion:
· Exists2way, Which Says WHETHER THEN ARE CONVERSIONS BETWEEN T AND U I Conversions. This is the case with int AND double, for example, but various user-defined Types CAN IMPLEMENT SUCH TWO-WAY Conversions.
· Sametype, Which is True IF T And U Are The Same Type.
Template
Class Conversion
{
... as Above ...
ENUM {EXISTS2WAY = EXISTS &&
Conversion
ENUM {Sametype = false};
}
We import Sametype Through a Partial Specialization of Conversion.
Template
Class Conversion
{
PUBLIC:
ENUM {EXISTS = 1, EXISTS2WAY = 1, SameType = 1};
}
Hey, What About That Inheritance Detection Thing? The Nicest Part IS, Once E Got The Conversion Thing, Detecting Inheritance IS Easy.
#define supersubclass (b, d) /
(Conversion
! Conversion
Obvious? Maybe still blurred a bit. SUPERSUBCLASS (B, D) evaluates to true if D inherits from B publicly, or if B and D represent the same type. SUPERSUBCLASS does its job by evaluating the convertibility from a const D * to a const B *. There Aren't Ion Three Cases WHEN Const D * Converts Implicitly To Const B *:
· B is The Same Type as D;
· B IS an unambiguous public base of d;
· B is void.
The last case is eliminated by the second test. Accepting the first case (B same as D) is useful in practice, because for practical purposes you can often consider that a class is its own superclass. If you need a stricter test, you can Write It Like So: #define supersubclass_strict (b, d) /
(SuperSubclass (B, D) && / /
! Conversion
? Why does the code add all those const modifiers The reason is that you do not want the conversion test to fail due to const issues Therefore, the code uses const all over the place;. If template code applies const twice (to a type That's Already Const, The Second Const is Ignored. in a nutshell, by using constin supersubclass, we're always on the safe side.
Why SUPERSUBCLASS and not the cuter BASE_OF or INHERITS For a very practical reason: with INHERITS (B, D), I kept forgetting which way the test works - does it test whether B inherits D or vice versa SUPERSUBCLASS (B, D)?? Makes It Clearer (At Least for Me) Which One IS First and Which One IS Second.
Conclusion
The single most important thing about the three idioms presented here is that they are reusable. You can write them in a library and let programmers use them, as opposed to asking them to grasp their intricate inner workings.
Reusability of nontrivial techniques is important Ask people to memorize a complicated technique that helps them do something that they can do in simpler, if a bit more tedious, ways;.. They will not use it Give people a simple black box that does a Little Helpful Wonder; They Might Like IT and Use IT Because It's in A Way "Free."
Int2Type, Type2Type, and especially Conversion belong to a generic utilities library. They extend the compile-time abilities of a programmer, by making important compile-time type inferences.Acknowledgments
If Clint Eastwood asked me "Do you feel lucky?", I'd certainly say I do. This is my third article in a row that benefits from the direct attention, and the great advice, of Herb Sutter himself. Thanks to Tomio Hoshida IN Japan for Spotting a bug and make inSightful Suggestions.
Note: This article Uses Excerpts from Andrei Alexandrescu's Upcoming Book Tentative Titled Modern C Design (Addison-Wesley, 2001).
Notes
[1] There is no concepting partial specialization of functions, a Very Opinion Feature.
[2] Andrei Alexandrescu. "Traits: The else-import", C Report (April 2000).
[3] There is a proposal for adding a typeof operator to C ;.. That is, an operator returning the type of an expression Having a typeof would make much template code easier to write and understand Gnu C already implements typeof as an extension. Obviously, typeof and sizeof share the same backend, because sizeof has to compute the type anyway. [Look for Bill Gibbons? article in an upcoming issue of CUJ, where he will present a nifty way to create an (almost) natural typeof operator in TODAY 抯 Standard C . - MB]
About the Author
