BOOST Source Code Analysis: Wizard Programming Elf Type_Traits (Rev # 2)
Liu Weipeng
C Louvre (http://blog.9cbs.net/pongba)
motivation
There are three types, assignments, efficiency, so that some code is compiled by using traits.
Dispatch
There is a template function below, assuming an animal containe organization provides it, they accept all homeless poor little animals, so they provide a function to the outside world accept registration. The function looks like this:
Template
Void Acceptanimals (T Animal)
{
... // Do Something
}
However, if they want to break cats and dogs (after all, they are not having a dog and feeding a dog. They may buy a chain for dogs, and the warm cat may not need). A viable method is to provide two functions: AcceptDog and Acceptcat, however, this solution is not elegant (thinking about it, the registrant may have a cat and a dog, so he has to call different functions to register, Moreover, if the species are also increasing, it will lead to an increase in the interface provided, and the registrant has to remember those cumbersome names, which obviously does not only need to remember the name of Accordanimal. If you want to keep this template function and use it as a unique interface provided to the outside, we need some way to get the characteristics of Type T, and use different strategies in accordance with different features. Here we have a second solution:
All animal classes (such as Class Cat, Class Dog) must be internally Typedef to indicate their identity, as the type of identity is as follows:
Struct catch_tag {}; // This is just an empty class, with the purpose of inspiring the function overload, and will explain it later
Struct dog_tag {}; //
Thus, all dogs must be like this:
Class Dog
{
PUBLIC:
// Type (identity) flag, indicating that this is a dog class, if it is a cat class, is typedef cat_tag type;
TYPEDEF DOG_TAG TYPE;
...
}
Then, the animal container organization can provide a function of separating the cat dog inside, like this:
// The second parameter is an unnamed parameter, just to excite the function overload
Template
Void Accept (T Dog, DOG_TAG)
{...}
Template
Void Accpet (T cat, carat_tag) //
{...}
The previous ACCEPT function can be rewritten as follows:
Template
Void Accept (T Animal) // This is the only interface provided to the outside world
{
// If t is a dog class, TypenAme T :: Type is DOG_TAG, then TypenAme T :: type () is a temporary object of a Dog_Tag class, which will call Accept (T, DOG_TAG) according to the rules overloaded according to the function. ), This is the strategy that turns to the dog. If t is a cat, TypenAme T :: type is CAT_TAG, from the above derivation, this will call accept (t, catch_tag), turn to the process of processing the cat, TypeName keyword tells the compiler T :: type is a type Not a static member.
Accept (Animal, TypeName T :: type ()); // # 1
}
All types of derivation, function overload, are completed during the compile period, you almost no time to consume any runtime costs (except for the cost of creating DOG_TAG, CAT_TAG temporary objects, however, this cost may also disappear) Code of readability and maintainability. "But, wait!" You said: "Traits?", TypeName T :: Type is actually traits, just a layer of packaging, if you do some improvements: Template
Struct Animaltraits
{
Typedef T :: Type Type;
}
So, the code at # 1 can be written:
Accept (Animal, TypeName Animaltraits
effectiveness
In order to improve efficiency, take special measures for some situation, such as COPY inside STL, prototype like this:
/ / Copy the elements within the [First, Last) interval to the place starting with DEST
Template
ITerout Copy (Iterin First, Iterout Dest) {
// PTR_Category is used to extract the category of the iterator to optimize appropriately.
Return Copy_opt (First, Last, DEST, PTR_CATEGORY (First);
}
Copy_opt has two versions, one of which is optimized for an array of basic types. If the copy occurs between the char array, then do not need to be assigned to the value, based on the continuity of the distribution of arrays in memory, can be very fast The Memmove function is completed. PTR_CATEGORY has a lot of overload versions that return an empty class such as SCALAR_PTR to the excitation function overload. The original version returns the object of the empty Non_Scalar_ptr. Two versions of Copy_opt are like this:
// Using Memmove
Template
Iterout Copy (Iterin First, Iterin Last, Iterout Dest,
Scalar_ptr)
{...}
// Copy one by part
Template
Iterout Copy (Iterin First, Iterin Last, Iterout Dest,
Non_scalar_ptr)
{...}
In fact, in order to improve efficiency, it is also necessary to dispatch.
Make some code to compile
This may be a decisive code that cannot be compiled by compiled code. Is it possible to compile? Yes, consider the code of std :: pair (in order to make the code, ignore the large part):
Template
Struct Pair
{
T1 first;
T2 Second;
// If T1 or T2 itself is a reference, compile errors, because there is no "referenced reference"
Pair (Const T1 & nfirst, Const T2 & nsecond) // # 2
: first (nfirst), second (nsecond) {}
}
Here you can use a traits (the name of the Boost library is add_reference) to avoid such errors. This traits contains TypeDef, if add_reference
Add_Reference
...
This can be compiled by all types.
Traits in the Boost library
The Traits in Boost is very perfect, which can be divided into the following categories:
1. Primary Type Categorisation (primary type classification)
2. Secondary Type Categorisation (secondary type classification)
3. Type Properties (Type Properties)
4. RELATIONSHIPS BETWEEN TYPES (Type relationship)
5. Transformations Between Types (Type Intergebrees)
6. Synthesizing Types (Type Synthesis)
7. Function Traits (Function Traits)
Since some Traits are just simple templates, they are not introduced, this article only introduces some technical traits. Because Traits definitions often repeats more, this article only analyzes its underlying mechanism if necessary. All source code is taken from the corresponding header file, in order to make the source code, all macro has been expanded. Some platforms may not support template offset due to the TRAITS tips and compilation platform. Here we assume that the compiler is compliant with C standards. On my VC7.0, the following code works and works normally.
Primary type classification
IS_ARRAY (boost / type_traits / is_array.hpp)
definition
/ /
Template
Struct is_Array
{
STATIC const bool value = false;
}
// Offset
Template
Struct Is_Array
{
STATIC const bool value = true;
}
annotation
C standard allows integer expressions as template parameters, the above N is like this. This also illustrates the template parameters in the template offset version (TypenAme T in this example), which is not necessarily the same as the default (TypenAme T of this example), but appears The number of parameters behind the class name is the same as the default number (IS_ARRAY
use
IS_ARRAY
IS_ARRAY
IS_CLASS (... / is_class.hpp)
definition
// Bottom implementation, the reason is that different underlying environments may have different underlying implementations, my compilation environment is VC7.0, and the other underlying achievements are omitted.
Template
Struct is_class_impl
{
Template
Static ... :: yes_type is_class_tester (void (u :: *) (void));
Template
Static const bool value =
...: ICE_AND <
SIZEOF (is_class_tester
...: ICE_NOT <... :: is_union
> :: Value
}
Template
Struct is_class
{
// All implementations are in IS_CLASS_IMP
Static const bool value = IS_CLASS_IMPL
}
annotation
:: boost :: type_traits :: yes_type is a typedef:
TYPEDEF CHAR YES_TYPE;
So sizeof (YES_TYPE) is 1.
:: boost :: type_traits :: no_type is a Struct:
Struct no_type
{
Char Padding [8];
}
So sizeof (no_type) is 8.
These two types are typically used as the return value type of the overload function, which is known from the size of the return value type, which is known to the end, and their definition is located in "Boost / Type_Traits / Detail / Yes_NO_TYPE.HPP".
There are two static functions in IS_CLASS_IMPL, and the first function can be instantiated when the template parameter U is a class, because its parameter type is VOID (u :: *) (void), pointing to a pointer to the member function. The second function has an unstopporated argument list, and the C standard says that the overload version with any parameter list (...) is only matched when all other overload versions cannot match. So, if t is a class, the Void (T :: *) (void) is present, so the overload resolution for IS_CLASS_TESTER
Now pay attention to the expression at # 3:
SIZEOF (is_class_tester
According to the above derivation, if t is class, is_class_tester
A payable place is: In the world of SizeOf, there is no expression that is truly evaluated, the compiler only derives the type of the result of the expression, and then the size of this type is given.
For example, for the SIZEOF (IS_CLASS_TESTER
If the T is not class, the traits will not be compiled. The reason is simple. When T is not class, Void (T :: *) (Void) does not exist at all. However, when using a template, when T is not class, the overload version will not be compiled, the C standard allows the Template that is not used (instantiated). This way, the compiler can only use the second version, which is in our mean.
The second overload version of IS_CLASS_TESTER is template because the first version is template, because in # 3, the call to IS_CLASS_TESTER is like this:
IS_CLASS_TESTER
If the second version is not a template, this call can only be parsed to the call to the IS_CLASS_TESTER template function (ie the first version), so that the overload resolution will not exist.
"Wait!" You realized some questions: "The call to the template function can not explicitly specify the template parameters!" Well, that is, you try to write this:
// Template
Template
Static ... :: yes_type is_class_tester (void (u :: *) (void));
// Non-template
Static ... :: no_type is_class_tester (...);
Then call this line in the # 3 mark:
IS_CLASS_TESTER (0) // It turned out to be IS_CLASS_TESTER
Yes, I have to admit that this does constitute a function of overloading, and it is indeed jealous through compilation, but the result is definitely not what you want. You will find that all types t, is_class
That is, the compiler always calls is_class_tester (..); this is because when there is one or more of the overload versions of the called function, the compiler first wants to instantiate the template function. Overload resolutions, while attempting to instantiate, the compiler will perform template parameters, 0 types are derived by the compiler to INT (0 although it can be assigned to the pointer, the type of 0 cannot be derived as a pointer type, Because the pointer type may have countless, in fact C is a strong type language, the object can only belong to a type), and the parameter type VOID (u :: *) (Void) of the first function cannot match INT (Because if it matches, the template parameter U is derived why?). So the first version instantiation fails, the compiler can only use the second version of the non-template. As a result, it is annoyed. However, if you write IS_CLASS_TESTER
The above uses the function overloaded to reach some purposes in Type_Traits and even more than the entire BOOST database. The primary type classification is also:
Is_void is_integral is_float is_pointer is_reference is_union is_enum is_function
See the documentation provided by Boost.
Secondary type classification
IS_MEMBER_FUNCTION_POINTER (... / is_member_function_point.hpp)
Definition (... / details / is_MEM_FUN_POINTER_IMPL.HPP)
/ / Default version
Template
Struct is_mem_fun_pointer_impl
{
STATIC const bool value = false;
}
// Offset version, match unparalleled member functions
Template
Struct is_mem_fun_point_impl
{
STATIC const bool value = true;
}
/ / Match a member function of a parameter
Template
Struct is_mem_fun_pointer_impl
{
STATIC const bool value = true;
}
... // Other versions are just a bias of the member functions of different parameters, see the source file.
Template
Struct is_mem_function_pointer
{
Static const bool value =
IS_MEM_FUN_POINTER_IMPL
}
annotation
Suppose you have a class x, you judge this:
IS_MEM_FUNCTION_POINTER
Then, the compiler will first derive the template parameter class T plate parameter Class T of IS_MEM_FUNCTION_POINTER to int (x :: *) (int), then pass it to IS_MEM_FUN_POINTER_IMPL, then the compiler is looking for the best match in the latter's off -ger version:
IS_MEM_FUN_POINTER_IMPL
Where R = INT, T = x, t0 = int. And this offset version :: value = true.
The secondary type classification is also:
IS_ARITHMETIC IS_FUNDAMENTAL IS_OBJECT IS_SCALAR IS_COMPOUND
See the documentation provided by Boost.
Type properties
IS_EMPTY (... / is_empty.hpp)
definition
// If t is an empty class, then the size of the school is the size of the derived part, XIZEOF (int) * 256
Template
Struct EMPTY_HELPER_T1
: Public T
{
EMPTY_HELPER_T1 ();
INT i [256];
}
Struct Empty_helper_t2
{
INT i [256];
}; // Size is sizeof (int) * 256
By comparing the size of the above two classes, it is possible to determine if the T is empty, and if they are equal, T is empty. It is not empty.
One worth noting here is: If an empty class E is defined, SIZEOF (E) is 1 (this byte is used to uniquely identify the different objects in the memory. If SizeOf (E) is 0, then It means that different objects have no difference in the location in memory, which is obviously illegal). However, if there is another non-empty class inheritance from E, then the memory of this byte is not required. That is to say, the size of the derived class is equal to the size of the derived part, not plus one byte. / / This auxiliary class is: If T is not class, use the default version If T is class, use the following offset version. It is determined whether T is the work of the class, is made by the IS_CLASS <> Traits mentioned above.
Template
Struct EMPTY_HELPER
{
STATIC const bool value = false;
}
Template
Struct Empty_Helper
{
Static const bool value =
(SIZEOF (EMPTY_HELPER_T1
}
Template
Struct is_empty_impl
{
// remove_cv removes the const volatile properties of T, because the type in the base class cannot have const / volatile modifications.
TypeDef Typename Remove_CV
Static const bool value =
ICE_OR <
EMPTY_HELPER
Boost_is_empty (CVT)
> :: value;
}
annotation
At # 4, if is_class
Otherwise, T is not class, then the default version, the result: value is false.
Is_PolyMorphic (... / is_polymorphic.hpp)
IS_PLYMORPHIC work mechanism is based on a basic fact: a virtual function table pointer (generally referred to as VPTR) in a polymorphic class, which points to a virtual function table (generally referred to as VTBL). The latter saves a series of function pointers that point to virtual functions and runtime type identification information. A virtual function table pointer usually takes up 4 bytes (all pointers in the 32 addressing environment occupies 4 bytes). Conversely, if the class is not a polymorphism, there is no overhead of this pointer. Based on this principle, we can conclude: If the class X is not a polymorphic class (no VTBL and VPTR), if you derive a class y, y only one virtual function, this can cause Sizeof (Y)> Sizeof (X (This is because the first occurrence of virtual functions causes the compiler to add VPTR in Y). Conversely, if the X is originally a polymorphic class, sizeof (y) == sizeof (x) (because in this case, y in Y, inherited VTBL and VPTR, the compiler is only done. Incorporate new virtual functions into the VTBL).
definition
// Use this version when t is class
Template
Struct is_polymorphic_imp1 {
TypeDef Typename Remove_CV
// NCVT is the type of rear after the Const Volatile modifier, because PUBLIC cannot follow this modifier, there is no virtual function in this class.
Struct D1: Public NCVT
{
D1 ();
~ d1 () // throw ();
CHAR PADDING [256];
}
Struct D2: public ncvt // Add a virtual function in D2
{
D2 ();
// Add a virtual function, if NCVT is non-polyure, will cause VPTR to join more 4 bytes
Virtual ~ d2 () // throw ();
CHAR PADDING [256];
}
// If t is a polymorphic class, value is true.
Static const bool value =
(SIZEOF (D2) == SIZEOF (D1));
}
// When T is not class, this version is used.
Template
Struct is_polymorphic_imp2
{
// Since T is not a class, then there is no polymorphism, so it is always false.
STATIC const bool value = false;
}
// This selector selects the way to determine according to the true and false of is_class
Template
Struct is_polymorphic_selector
{
// If IS_CLASS is false, it is determined by is_polymorphic_imp2, which will cause the result to always false.
Template
Struct rebind
{
TYPEDEF IS_POLYMORPHIC_IMP2
}
}
// Use this special version when IS_CLASS is TRUE
Template <>
Struct is_polymorphic_selector
{
// If IS_CLASS is True, it is determined by IS_POLYMORPHIC_IMP1 <>
Template
Struct rebind
{
TYPEDEF IS_POLYMORPHIC_IMP1
}
}
// is_polymorphic is completely implemented
Template
Struct is_polymorphic_imp
{
// Select Selector
Typedef
IS_POLYMORPHIC_SELECTOR
TypeDef TypeName Selector :: Template Rebind
TypeDef TypeName Binder :: Type Imp_Type; // # 9
Static const bool value = IMP_TYPE :: Value;
}
annotation
# 6 If t is class, is_class
Typedef is_polymorphic_selector
This will resolve the second overload version # 7 of IS_POLYMORPHIC_SELECTOR, where the Template Rebind gives the judgment task to IS_POLYMORPHIC_IMP1, so # 8 line Binder is actually IS_POLYMORPHIC_SELECTOR
Typedef
CT_IF
RESULT;
The result is TypeifTrue when compiletimeBool is True, otherwise Result is Typeiffalse. The implementation of CT_IF <> is very simple, and the template is offset. So you write this:
TypedEf Typename Boost :: CT_IF <
IS_CLASS
IS_POLYMORPHIC_IMP1
Is_polymorphic_imp2
> :: Type
IMP_TYPE;
Static const bool value = IMP_TYPE :: Value;
This is compiled and working properly in my VC7.0 environment, but there is a small problem: if T is not a Class, for example, T is an int, then the compiler's type derived will assign IS_POLYMORPHIC_IMP1
And the C standards actually support this approach. However, the practice in the Boost library is more insurance, perhaps in order to meet some old compilers.
Type properties Traits are also:
Alignment_of is_const is_volatile is_pod HAS_TRIVIAL_CONSTRUctor, etc.
Type relationship
Is_base_and_derived (Boost / Type_Traits / IS_BASE_AND_DERIVED.HPP)
definition
Template
Struct BD_HELPER
{
Template
Static type_traits :: yes_type check (d const volatile *, t);
Static type_traits :: no_type check (b const volatile *, int);
}
Template
{
Struct Host
{
/ / The conversion operator works when the object is a const object.
Operator b const volatile * () const;
Operator D const volatile * ();
}
Static const bool value =
SIZEOF (BD_HELPER :: Check (Host (), 0)) // # 10
== SIZEOF (Type_Traits :: Yes_TYPE);
}
The above is the underlying mechanism of IS_BASE_AND_DERIVED. Below I explain the mechanism it as you releaved, assume that there is such a class inheritance system:
Struct b {};
Struct B1: B {};
Struct B2: B {};
Struct D: Private B1, Private B2 {};
Convert D * to B1 * can result in access violations, because the private base class is unable to access, but the following explains why this will not happen.
First come and see some terms:
SC - Standard Conversion
UDC - User-Defined Conversion
A User-defined conversion sequence consists of one SC after following a UDC. Among them, two SCs can be converted to their own conversion (eg: D-> D), and # 10 will hand over a default constructed Host () to BD_HELPER :: Check function.
For Static No_Type Check (B Const Volatile *, Int), we have the following feasible conversion sequences:
Host -> Host Const -> B Const Volatile * (UDC)
or
Host -> D const volatile * (udc) -> b1 const volatile * / b2 const volatile * -> b const volatile * (sc)
For Static Yes_Type Check (D const volatile *, t), we have the following conversion sequence:
Host -> D const volatile * (UDC)
C standard, when choosing the best match function in the overload resolution, only consider the standard conversion (SC) sequence, and this sequence until you encounter a UDC, for the first function, will host -> host const with host - > Host comparison, obviously choose the latter. Because the latter is a true subset of the former. Therefore, we get rid of the first conversion sequence. We get:
C -> D const volatile * (udc) -> b1 const volatile * / b2 const volatile * -> b const volatile * (sc)
VS.
C -> D const volatile * (UDC)
Here, the principle of selecting the shortest sequence is selected, and the latter is selected, which indicates that the compiler does not even consider the multi-path to B, or the access restrictions, so that the conversion erriness and access violations will not happen. The conclusion is if D inherits from B, then choose Yes_TYPE CHECK ().
If D is not inherited from B, the conversion given to the Static NO_TYPE CHECK (B Const Volatile *, int) compiler is:
C -> c const -> b const volatile * (udc)
Getting on Static Yes_TYPE CHECK (D const volatile *, t): c -> d const volatile * (UDC)
These two are good (one UDC), but because STATIC NO_TYPE CHECK (B const volatile *, int) is a non-template function, the compiler is selected. The conclusion is that if D is not inherited from B, then NO_TYPE CHECK ().
In addition, in my VC7.0 environment, if the Host's Operator B const volatile * () const is taken, the result will always be false.
Unfortunately, this understanding is not me, they come from the comments in the Boost source code.
IS_CONVERTIBLE (Boost / Type_Traits / IS_CONVERTIBLE.HPP)
definition
Template
Struct does_conversion_exist
{
Template
Struct Result_
{
// When there is no transformation from from to To, it is called.
Static no_type _m_check (...);
// Call it as long as the transformation exists
Static YES_TYPE _M_CHECK (TO);
// This is just a statement, so it does not take up space and no overhead.
Static from _m_from;
ENUM
{
Value =
SIZEOF (_m_check) == sizeof (Yes_TYPE);
}
}
}
// This is a special version prepared for Void, because you can't declare void _m_from, only Void can "conversion" to Void
Template <>
Struct does_conversion_exist
{
Template
Struct Result_
{
Enum {value = :: boost :: is_void
}
}
// Is_Convertible completely uses the does_conversion_exist for underlying mechanism, so it is slightly.
annotation
DOES_CONVERSION_EXIST also uses the same technology as IS_CLASS_IMPL. So the annotation is omitted. This technology was originally invented by Andrei Alexandrescu.
Finally, Transformations Between Types, synthesizing types, functional traits, and refress Traits, please refer to the document or header file provided by Boost.
Traits is the elves in the generic world: small and exquisite. Traits is also the most subtle things in generic programming, which often depends on the rules, C standards, and magical templates. This also leads to different performances on different platforms, and more common is that there is no job on some platforms. However, since their basis is C standard, the compiler will become more and more standard, so these problems are only temporary. Traits is also one of the basic components of a generic world, which often makes design elegance, exquisite, and perfect.
Directory (expand "Boost Source Analysis" series of articles)