Wild programming: reproduction MIN and MAX
Author: Andrei Alexandrescu (Tao Zhangzhi translation)
Original source: http://www.cuj.com/documents/s=7996/cujcexp1904alexandr/ In January 1995, Scott Meyers emphasized "Min, Max to C community in C Report magazine" MIN, MAX is a big Challenge, he carefully analyzed MIN, MAX based on macro-based implementation, and the control based on template-based min and max, he got the following conclusions: "For MAX, what is the best way?" Uses a TEVYE Name: "I will tell you: I don't know", based on the above analysis, I have confidence to tell everyone the way of macro implementation, maybe it is the best, but I personally hate: macro. Therefore, if you have any better implementation methods, please tell me quickly. Based on my personal knowledge, this challenge still exists, in this article, I will face this challenge, but before I start, let us recall the pre-generic programming, how to do bad implementation This algorithm is of. I received a lot of emails since "gener
...
IF (! vec.empty ()) {vec.pop_back ();
}
The original idea is to move the last element from the container vector. In a single-threaded environment, this code will run very well, but if you use this code in multithreading, it often occurs, even if you are Empty (), POP_BOCK () has been appropriately synchronized. Therefore, it can be said that the low-level data consistency is protected, but higher levels of data operations are often unstable. At least, according to the above analysis, I started to adhere to my calculation volatile method, which is a good way to detect the POSIX mutex RACE CONDitions. However, if you engage in the memory access rights of multi-process system, then you should first listen to your compiler documentation. You should know what you should do. Kenneth Chiu mentioned a very interesting papers: http://theory.stanford.edu/~freunds/race.ps, pape explained "Type-based Race Detection for Java." Because Java type system only has little restrictions Conditions, this makes the compiler possible with programmers to detect RACE CONDITIONS at compile time. MIN and MAX let us look at the challenges proposed by Scott, based on macro-defined min () as follows: #define min (a, b) ((a) <(b)? (A): (b)) due to it It is a complete model, so it often works well. (As long as this expression is "defined) Unfortunately MIN () always calculates a parameter in the middle twice, so that there are many confusing issues. (Translation: If the call is called, A = 3, b = 5 int C = min (a , b); the result we will get c = 4 results. Obviously it is not what we want) macro is just in the form of functions Asphaps, however, its behavior tends to follow the function. (If you want more related knowledge, then you can check the information about Herb in this area) There is a more effective implementation in the C standard library, which is a template-based solution, as follows: Const T & min (Const T & LHS, Const T & RHS)
{
RETURN LHS? LHS: RHS;
} You can see that the parameters and return values in this scenario are const types, which also leads to a problem. Maybe, you want to add the value of the two values of the two, then, you may write this: Double A, B;
...
Min (a, b) = 2; Based on macro definition min () does not have problems, but if the template is implemented on the template, it will not be so obsolete. Because you can't change the value of the Const variable, just as SCOTT is concerned. Let's update our implementation: T & Min (T & LHS, T & RHS)
{
RETURN LHS? LHS: RHS;
}
However, this is still unsatisfactory. Because the compiler cannot handle the mixed type - a parameter is const, one is Non-Const. For example: INT A;
Short Int B;
...
INT Smallst = min (a, b); // error: can''t Figure Out T
// in Template Instantiation
Needless to say, macro-based min () is in this case again. Based on the template (), you must write: int smallest = min (a, int (b)); // aha, t is int To provide a good min / max, we first make behavior like macros At the same time, to avoid the trouble brought by Macros. Below is a smart implementation: Emplate
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); } In order to unify the two transitions, some special local processing should be performed in MinResult ... Min (a, b); in fact, the above code does not do something else, and if you have a lot of thinking about the type, then this code will make your concept of trees in the forest. Thinking. On the other hand, if you use: int C = min (a, b); then, the compiler will call INT & to translate the temporary variables of the MINRESULT Short Int B; EXTERN FUN (Int); Extern fun (short int); ... Fun (MIN (A, B)); // Error! Don''t Know Which Overload To Invoke! MinResult MIN (L & LHS, R & RHS) {RETURN LHS Template MintYpe (Const L, R) MIN (Const L & LHS, R & RHS) {RETURN LHS 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 functions correspond to four possible combinations between Const and Non-Const. This idea is good, but how should we define MINTYPE? We know that there is a corresponding technical traits, you can use Traits to complete the Mintype such as: #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 true, but you will have to write a lot of bad code. Because there are 14 data types, you will have to compile Mintraits for each combination. In fact, you can simplify this job, just like Macros, but this is not a perfect solution. This program has not been completed, you must take into account the user-defined class. Also, how to call the min () function as the base class, subclass, see the following example: Class Shape { ... Unsigned int area () = 0; } Bool Operator <(Const Shape & lhs) {Return lhs.area () } Class Rectangle: Public Shape {...}; Void Hatch (Shape & Shape) { Rectangle Frame; ... Shape & Smallst = Min (Shape, Frame); ... USE Smallst ... } In fact, if, min () processes Rectangle then it will return a song reference, which is not good. Since Rectangle automatically converts to Shape reference types, so we have to do a lot. At the same time, in the previous example, we can also see that Macro-based min () functions will not work properly, see example: Shape Sizeof (Short Int), Wchar_T, Short Int> :: Result Smallint; Smallint will be the minimum integer type in Wchar_T, Short Int. 3 Typetraits This is a template class. It is used to infer the type, such as judging whether this type is a pointer, this pointer pointing to what variables, etc. We use NonconstType Typetraits 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; } Itself, unsigned Types should be behind Signed Types, Float should be behind. For example, MIN (long, double) then the result should be a double type, because Double in List is behind long (Translator: We know the result should be double) Now, the general algorithm can calculate the min () result type. . If your parameter type is not a reference T, R has the following conditions: 1 Assumption results are R. 2 If R can be hidden to L, the result can be converted to a L-type. 3 If r in the private :: ArithTypes, the re-conversion results are R-type, this step is to handle many mathematical transformations. 4 If you do not introduce a temporary variable, L & can automatically convert to R &, then the result is transformed into R &, which makes it easy to return to Shape &. 5 If the R & can be automatically converted to L &, then the result is converted to L &, this step ensures that MIN (Shape, Frame) returns Shape &. This is a difficult step in this "Does not introduce temporary variables" Transformation between types. " Essentially If the reference of Not-Const T can be converted to NOT-ConST U reference, then t can be converted to U in the case of introducing temporary variables The min and max overloads corresponds to four different combinations of Const and Not-Const parameters, there are four min (), and max () functions overload. In order to avoid the SLICING problem in the Shape / Rectangle example, min () has a different implementation of the A Typename MinMaxtraits MIN (L & LHS, R & RHS) {IF (LHS Template TypeName MinMaxtraits {IF (LHS ... TWO more overloads ... .. Similar Max Implementation ... These two return statements ensure proper transformation and there is no SLICING. These four overload functions can be handled as follows: MIN (A B, C D), MIN (A B, 5). Analysis: Let me see how this new implementation meets the requirements of Mr. Scott Meyers ''. His requirements are as follows: 1 function To perform type checks in language. Obvious min () is met. 2 Support const, non-const parameters. Due to the heavy load of four functions. MIN () supports any combination of the parameters of non-const const. 3 Support different parameter types. MIN () is obviously supporting different types, it has made a lot of intelligence, this is the Macro and simple template that cannot be done. MIN () eliminates the difference between different types. Active Type Transformation. This conversion process is in the hands of Library writer. 4 Do not need to be mandatory, min () does not need. In the case of different pointers (Shape *, Rectangle *) MIN () can also behave well. This is due to the first step of the algorithm. An important feature of MIN () is that it can infer the result type one algorithm, and this algorithm is you can write. If you find what is not satisfied with this algorithm. You can modify itself. Unfortunately, this implementation cannot be passed on some compilers, I know that the code is no problem. If you have any good suggestions, please contact me. Look ahead in anger, I am watching the age of spiritual machines by ray kurzweil [8]. Kurzweil said fully, in 2020, you will use less than $ 1,000 to buy a machine. At that time, people may say "you see, in 2001, those guys were still so difficult, and a guy also said a paper," MIN () is not important, I don't think so, maximize it. Minimize two simple concepts in mathematics, real life. If the program language does not express this simple concept, then explain the depths of the language, there is still a problem. Maybe there may be a child say "Mom, I don't want to learn grammar and words, I just want to learn to write poetry"? Can I succeed? If you wrote a A
