Andrei alexandrescu
YE_FENG translation
This document
In January 1995, Scott Meyers made a challenge to the C community in the article named "Min, Max and More" [1] in C Report. After carefully analyzing the implementation of the template technology based on macro and representative, he concluded: So what is the best way - the right way - to achieve max? Borrowing Tevye's immortal reputation: "I tell you: I don't know." Facing the above analysis, I am more and more feeling that I can tell people that the way to use macros may be the best, but I hate the macro. If you know an elegant implementation of Max, please let me know. As far as I know, this issue is as challenging as six years ago. This article will try this challenge.
MIN and MAX
Ok, let's take a look at Scott problem. Macro-based MIN usually looks like this:
#define min (a, b) ((a) <(b)? (a): (b))
This macro works very well because it is very common (can support all expressions, as long as the Operator 3]. ) In the C standard library, a template-based solution is provided, simple and effective: Template Const T & Min (Const T & lh, Const T & RHS) { RETURN LHS? LHS: RHS; } You can see that this method uses const in all places (parameters and return values), which is one of its problems. Suppose you want to do something: add a smaller value in the two floats A and B. 2. Then you will want to write this: Double A, B; ... MIN (A, B) = 2; If you use a macro-based min, there is no problem like this, but the template is not ok because you can't modify the const object. Scott pointed out that introducing the second version: Template T & min (T & LHS, T & RHS) { RETURN LHS? LHS: RHS; } It is also unable to be satisfactory because the compiler cannot deal with the mixing situation - the two parameters are Const and the other is not. Moreover, the template does not have a good process of automatic type conversion and promotion, that is, the following code cannot be compiled: Int a; Short Int B; ... Int smallest = min (a, b); // error: can't Figure Out T // in Template Instantiation Needless to say, macro-based MIN can still work well in the case of type conversion. And with template-based methods, you must write: INT Smallst = min (a, int (b)); // aha, t is int Providing a good Min / MAX implementation is: It is similar to the macro, and there is no macro. One (almost) good start Below this smart method is a good example of breaking the way of regulatory thinking: Template Class minResult { L & lhs_; R & rhs_; PUBLIC: Operator L & () {RETURN LHS_ Operator R & () {RETURN LHS_ MinResult (L & LHS, R & RHS): LHS_ (LHS), RHS_ (RHS) {} } Template Class minResult LR & LHS_; LR & RHS_; PUBLIC: Operator LR () {RETURN LHS_ MinResult (LR & LHS, LR & RHS): LHS_ (LHS), RHS_ (RHS) {} } Template MinResult MIN (L LHS, R RHS) { Return MinResult (LHS, RHS); } We need to use some special minResult Based on minResult, the calculation is postponed to a must, only when the results are obtained, will be calculated. such as: INT A, B; ... MIN (a, b); In fact, don't do anything. On the other hand, if you write: INT C = min (a, b); The compiler will call the minResult Although you can fix the problem caused by Const (not mentioned above), MINRESULT-based approach is still unsatisfactory, because there is an unsatisfactory issue. Consider the following code: Int a; Short Int B; EXTERN FUN (Int); Extern fun (short int); ... Fun (MIN (a, b)); // error! Don't know! "Don't Know Which overload to invoke! MaxResult Find a type It should be such a tool that is really able to solve the problem: for two types L and R, the proper type of MIN (L, R) can be obtained. For example, if L is char, R is int, then the result should be int. Suppose we already have such a tool (let us call it mintype), we can get the final solution, the following four functions: Template MinType (L, R) MIN (L & LHS, R & RHS) {RETURN LHS Template MintYpe (Const L, R) MIN (Const L & lHS, R & RHS) {RETURN LHS? LHS: RHS; Template Mintype (L, Const R) MIN (L & LHS, Const R & RHS) {RETURN LHS Template Mintype (Const L, Const R) MIN (Const L & LHS, Const R & RHS) {RETURN LHS These four overloaded MIN correspond to four possible combinations of Const and non-Const parameters. So far, everything goes well. But how do you define MINTYPE? Ok, one of the sacred technologies that can be calculated is traits [4]. Of course, we can get the type of Min: #define minType (L, R) Typename Mintraits Template // Specialization for the L == R Case Template Typedef LR & RESULT; } // Specialization for Bool and char Template <> struct mintraits Typedef char Result; } ... This is feasible, but you have to write very much code. There are 14 types of arithmetic types in C , and you must write a special Mintraits for each combination between them. Then you must also join the const variant. Some techniques can help you simplify this job, such as macros, but this is not a first-class solution. Even so, this program is still incomplete. You must consider pointers and user-defined classes. Also, what should I do if I do MIN for the base class and derived class? For example, you define a Shape class, and define the Operator Class shape { ... Unsigned int area () = 0; } Bool Operator <(Const Shape & LHS, Const Shape & Rhs) { Return lhs.area () } Class Rectangle: Public Shape {...}; Void Hatch (Shape & Shape) { Rectangle Frame; ... Shape & Smallst = Min (Shape, Frame); ... USE Smallst ... } If the MIN called above can calculate the Rectangle derived from Shape and returns a reference to Shape, isn't that good? Because Rectangle's reference can be automatically converted to Shape reference, this is reasonable. However, when you start to do this, your idea has exceeded MIN Hong. For the above example, the min macro does not work correctly because the expression: Shape The two parts will be converted into the same type, so it is equivalent to: shape This is not what we want. In fact, it did a very bad thing - object slice. This article will tell a min's implementation, which allows you to get all the advantages of the macro version, and more. Better, this implementation is also very reasonable - there is only 80 lines of code (including max). Are you interested? Put your coffee in the microwave, let's talk slowly. Loki OKEY, I was lying. The code is only 80 lines, but this does not calculate the class library used. More specifically, I used the Loki, a universal library introduced in the book [5]. In many functions, Loki provides advanced type of manipulation. The LOKI tools used in the min implementation are: Typelists. In addition to saving type rather than values, TypeLists [6] is the same as the usual list. Such as the following statement: TypeDef Typelist_3 (Float, Double, Long Double) FloatingPointTypes; Created a Typelist containing three types, saved in FloatingPointTypes. Give a Typelist (such as floatingpointtypes) and any type t, you can get Typelist in Typelist through a compile time. Loki :: TL :: Indexof The result is equal to 1. If the type is not in Typelist, the result is -1. 2. The second tool we have to use is the SELECT type template, which is described in detail in [7]. Simply, select allows you to select one in two types based on a compile time. E.g: Typedef loki :: select Sizeof (Short Int), Wchar_T, Short Int> :: Result Smallint; Define Smallint as the smallest integer type in Wchar_T and Short Int. 3. Typetraits This class template can make a variety of deduction, such as "this type is a pointer? What type is it pointing?" And so on. We only use the NonConstType type definition in Typetraits. Typetraits 4. Finally, we will use the Conversion class [7], which can detect whether any type can be implicitly converted to another type. Conversion is the basis for implementing the magic of Shape and Rectangle mentioned above. MinMaxTraits class template In order to simplify the type calculation, I have established a simple linear level to list various arithmetic types. Basically I list all arithmetic types in a specific order: for any two arithmetic types, the result of min is the one behind the list. Here is this list (now you don't think of const): Namespace Private { TypedEf Typelist_14 ( Const Bool, Const char, Const Signed Char, Const UNSIGNED Char, Const Wchar_T, Const Short Int, Const Unsigned Short Int, Const Int, Const UNSIGNED INT, Const Long Int, Const UNSIGNED Long Int, Const float, Const Double, Const long double ArithType; } Basically, the non-symbol type is behind the signed type, the size of the size is small, the floating point type is behind the integer type. For example, if you pass a long int and a double to min, the result will be a double type because Double Ports are behind Long Int. Now see the algorithm for the MIN result type. The two non-reference types L and R are given, then the step is this: Assume the Result R. If r can be implicitly converted to L, then change the result to L. If l and r are arithmetic types, and on the priz :: ArithTypes row behind the L, then result is changed to R. This step is used to handle all arithmetic conversions. If L & can be automatically converted to R &, do not need to introduce temporary variables, then result is changed to R &. This step ensures that a call such as MIN (Frame, Shape) returns Shape &. If R & can be automatically converted to L &, do not need to introduce a temporary variable, then result is changed to L &. This step ensures calls such as MIN (Shape, Frame) Returns Shape &. You can see the implementation of MinMaxTraits in the code of the downloaded code. The hardest part of the above algorithm is to determine the "conversion of the temporary variable". Essentially, when a reference to a non-Const can be converted to a reference to a non-constin U, T can convert U without introducing a temporary variable. MIN and MAX overload functions MIN and MAX have four overload functions, corresponding to four combinations of Const and non-Const parameters. In order to prevent the object slice (SLICING) discussed in the above Shape / Rectangle example, Mini Differences and Classic A Template Typename MinMaxtraits MIN (L & LHS, R & RHS) {IF (LHS Template TypeName MinMaxtraits MIN (Const L & LHS, R & RHS) {IF (LHS ... TWO more overloads ... .. Similar Max Implementation ... Two returnographs ensure the correct CS conversion, without generating object slices. The four overload functions covers all mixing, such as min (A B, C D) or MIN (A B, 5). analysis Let's take a look at how this newly developed MIN satisfies the requirements of Scott Meyers. He believes that a good Min / Max implementation should be able to do the following four things: 1. Provide a semantic (including type check) for function calls, not the sense of macro. MIN is clearly available. 2. Support const and non-const parameters (including mixing in the same call). Due to the four overload functions, min supports any combination of Const and non-Const parameters. 3. Support two different types of parameters (of course, meaningful). MIN does support different types of parameters, and there are many intelligence that MIN and simple template methods: MIN will distinguish various arithmetic types and make reasonable conversions. The selection process of type conversion (Private :: ArithTypes) can be controlled by the author of the library. 4. No explicit instantiation is required. MIN does not need to be explicitly instantiated. MIN can also work correctly (even points to different but related types, such as Shape * and Rectangle *). This is due to the first step in the algorithm. A payable function is: MIN uses an algorithm that can be configured to derive the result type, not limited to the pre-defined rules in the type system. If you are not satisfied with the algorithm here, you can make quite do what you want to do, including selection of types. For example, the smallest value of unsigned char and unsigned int is always selected because the value field of unsigned char is included in the unsigned int. By changing the type derivation algorithm, you can do this "smart" type selection. So far, everything is very good, but there is a little detail. Unfortunately, all compilers I can do can compile min. In a fair, each compiler has flipped the ship in different code segments. I am sure that the code is correct because if you combine those compilers, you can compile it. But until now, I have not seen an example of running. So if you can get a newest compiler and you can try this code, please tell me. Look ahead in anger These days I am reading Ray Kurzweil's "The Age of Spiritual Machines" [8]. Kurzweil thinks - and is quite persuasive - you will have the same machine as a human brain with a human brain in the 2020. When I think people - maybe it is my own, I hope only a little old, but smart - after 20 years of reading this article, I can't help but laugh. "Oh, in 2001, this guy will use the most popular programming language at the time, and even this thing that does not require MIN and MAX will also have trouble. Ha, this person also wrote a whole article, used this Directive technology, only MIN and MAX. " Is MIN and MAX not important? I do not think so. Minimum and maximum is two simple concepts in mathematics and real life. If a programming language cannot express the simple concept in mathematics and life, then this language must have a very serious problem. "Mom, I don't care words and literacy, I just want to write poems!" If you have to join some temporary variables, then write "A Some are not right, isn't it? C is not the only thing to be accused. Java and C # - Two new languages that are considered more advanced - the same is completely unable to express MIN and MAX. Because you know, MIN and MAX are not objects. Perhaps the time will be called "object crazy" in the future. Who knows ... I can't help but annoyed: "Programmer, where do you go?" Thank you Thanks to all participants in the usenet, people discussed on Volatile, especially Dave Butenhof, Kenneth Chiu, James Kanze, Kaz Kylheku, Tom Payne, and David Schwartz. bibliography [1] http://www.aristeia.com/papers/c reportcolumn/jan95.pdf [2] http://www.cuj.com/experts/1902/alexandr.htm [3] http://www.gotw.ca/gotw/077.htm [4] A. Alexandrescu. "Traits: The else-if-dam of types," C Report, April 2000. [5] A. AlexandRescu. Modern C Design (Addison-Wesley Longman, 2001). [6] J. Vlissides and A. Alexandrescu. "To code or not to code," C Report, March 2000. [7] A. AlexandRescu. "Generic : Mappings Between Types and Values, "C / C Uses Journals forum, September 2000, http://www.cuj.com/experts/1810/alexandr.htm. [8] R. Kurzweil. The agent of spiritual machine: When Computers Exceed Human Intelligence (Penguin USA, 2000).
