"Exceptional C Style" Open Pattern Translation (Part 1) / Draft 0.1 / Date 12.25.2004
BY Xie Xuan (Infinitude_CN)
34. Index Tables Difficulty 5
The index table is indeed a useful iDiom and it is a known technique. But how can we effectively achieve this technology ... Not only this, it should be better than "effective", "perfect"?
JG problem
1. Who will benefit from the clear and easy-to-understand code?
Guru problem
2. The following code presents an interesting and useful IDIOM that creates an index table in an existing container. If you need more detailed explanation, please read the original [Hicks00].
Criticize this code and find out:
a) Motion similar to an invalid grammar or a mechanism of Nonportable Convention.
b) Improvements in style, improve the clarity, reuse and maintainability of the code.
// Program sort_idxtbl (¡) to make a permuted array of indes
#include
#include
Template
Struct sort_idxtbl_pair
{
Raiter IT;
INT I;
BOOL Operator <(const sort_idxtbl_pair & s)
{RETURN (* IT) <(* (s.it));
Void set (const raiter & _it, int _i) {it = _IT; i = _i;}
Sort_idxtbl_pair () {}
}
Template
Void sort_idxtbl (raiter first, raiter last, int * pIDxtbl)
{
INT IDST = Last-first;
Typedef st :: vector
V V (IDST);
INT i = 0;
Raiter it = first;
V :: itrator vit = v.begin ();
For (i = 0; IT (* VIT) .SET (IT, I); Std :: sort (v.begin (), v.end ()); INT * PI = PIDXTBL; Vit = v.begin (); For (; vit * Pi = (* VIT) .i; } Main () { INT Ai [10] = {15, 12, 13, 14, 18, 11, 10, 17, 16, 19}; COUT << "##########" << endl; Std :: Vector Int aidxtbl [10]; Sort_idxtbl (vecai.begin (), vecai.end (), AIDXTBL); For (int i = 0; i <10; i ) cout << "i =" << i << ", AIDXTBL [I] =" << AIDXTBL [i] << ", AI [AIDXTBL [I]] =" << Ai [AIDXTBL [i]] << ENDL; COUT << "##########" << endl; } answer Clearness: short admonition 1. Who will benefit from the clear and easy-to-understand code? In short, it is good for everyone. First, the clear code is easier to debug, but also because of the clear, just written code does not have a lot of errors, so the clear code can make your life easier, even in a short period of time. (Related cases, please refer to Article 27 Discussions around "Example 27-3".) In addition, when you reread your code after one month or after a month - you will want the code to be good and actually apply - - You will find it easier to "raise" the clear code, understand what problems. Most programmers believe that all the details of the code in mind and remain even just a few weeks, especially after turning to other work, remembering these more difficult. After a few months or even a few years, even if you are looking at your own code, it is easy to think that it is written by a stranger, although the stranger just follows your personal coding style. It has been said enough to have a profit. Let's take a look at the advantages of someone: maintaining the code will also benefit from the clarity and readability of the code. After all, I want to maintain code maintenance is to "all the god" code. Robert Heinlein, the word "Grok", which means in-depth and complete understanding; here, this word also contains understanding of code itself, the side effects of code, and other The interaction method of the subsystem. All in all, the rewrite code is too easy to introduce new mistakes when there is no fully understood. Clear, understandable code is easier to "whole gods", therefore, the repair of this code is not so fragile, dangerous, and will not introduce "unintentional" side effects. However, the most important thing is that because of all these reasons, your end users will benefit from clear, understandable code: this code has only a few original errors from the beginning; this code is easier to properly maintain And there will be many new errors in the maintenance process. Principle: Under normal circumstances, priority is given to write clear and correct code. In-depth profiling 2. The surface code presents an interesting and useful IDiom that creates an index table in the existing container. If you need more detailed explanation, please read the original [Hicks00]. Criticize this code and find out: a) Motion similar to an invalid grammar or a mechanism of Nonportable Convention. b) Improvements in style, improve the clarity, reuse and maintainability of the code. Let us repeat the big bulls repeatedly: These codes present an interesting and useful IDIOM that creates an index table in the existing container. I often find that the same containers must be accessed in different ways, such as using different order. Therefore, this method is indeed useful: to save data (such as vector After all of these, let's take a look at what we can do with the code of this particular piece. Correct mechanism errors a) Motion similar to an invalid grammar or a mechanism of Nonportable Convention. The first aspect of constructive criticism is the mechanism error in the code. These mechanism errors listed below are unable to be compiled on most platforms. 1. Spell correctly spell the title file name. In this example, the header file Next, consider: Main () 2. Define the main function correctly. This unpredictable main function Signature is never standard C [C 98] style, although as long as the compiler gives the corresponding warning, this is a consistency extension. This main function Signature is valid in Pre-1999 C because there is implicit int rules in Pre-1999 C, but this is in C (from no implicit int) and c99 [c99] (Which as far as I can Tell Didn't merely DepRecate Implicit Int, but actually removed it out is non-standard. For C standards, please see: §3.6.1 / 2: The portable code must define the main as an int main () or int main (int, char * []). §7 / 7 Footnotes 78, and 7.1.5 / 2 footnotes 80: Implicit INT is disabled. Appendix C (Compatibility), Note 7.1.5 / 4: It is clear that naked main () is invalid in C , must be written int Main (). Principle: Do not rely on implicit int; this is not portable C consistent with standards. Special, "void main ()" or only "main ()" never is standard C , although there are still many compilers support them as consistency extensions. COUT << "##########" << endl; 3. Always remember #include you need the type definition header file. This program uses COUT and ENDL but there is no #include In this case, the program has a #include 4. Follow the 36 of more Exceptional C [SUTTER02] about the principle of using the name space (Namespace). For COUT and ENDL, the program must define them in std ::, or write: use std :: cout; using std :: endl ;. Unfortunately, forget the situation of the namespace domain qualifier is still very common - I have to point out that the author has done the correct domain for Vector and Sort, which is very good. Improving style b) Improvements in style will increase the clarity, reuse and maintainability of the code. Crossing mechanism errors, in this code paradigm, some places I personally do in different ways. First, you have to make two points on Helper Struct: Template Struct sort_idxtbl_pair { Raiter IT; INT I; BOOL Operator <(const sort_idxtbl_pair & s) {RETURN (* IT) <(* (s.it)); Void set (const raiter & _it, int _i) {it = _IT; i = _i;} Sort_idxtbl_pair () {} } 5. It is necessary to be constant. In this example, sort_idxtbl_pair :: Operator Principle: Time to implement the correctness of Const. 6. Eliminate redundant code. This program explicitly writes the default constructor of class sort_idxtbl_pair, but it doesn't differ from the version of implicit generated. This looks unnecessary. In addition, sort_idxtbl_pair is the data member is a PUBLIC Structure, although there is a unique SET operation to add some syntactic sugar, but because it is only called, this little extra complexity does not bring too much benefits. . Principle: Avoid code repeat and redundancy. Below, we have entered the core function sort_idxtbl to see: Template Void sort_idxtbl (raiter first, raiter last, int * pIDxtbl) { INT IDST = Last-first; Typedef st :: vector V V (IDST); INT i = 0; Raiter it = first; V :: itrator vit = v.begin (); For (i = 0; IT (* VIT) .SET (IT, I); Std :: sort (v.begin (), v.end ()); INT * PI = PIDXTBL; Vit = v.begin (); For (; vit * Pi = (* VIT) .i; } 7. Select meaningful and appropriate name. In this case, sort_idxtbl is a misleading name because this function is not sorted by an index table ... but creates an index table! On the other hand, the code uses template parameter name raiter to indicate this random access (Random-Access) iTerator, which can be a good score; because this random access feature is required by this version of code, Template parameters named this can be used as a good tip. Principle: Select a clear and meaningful name. 8. Keep consistency. In sort_idxtbl, sometimes variables are set in the for-cycle initialization statement, but sometimes not this. This makes the code more difficult to read, at least for me. Your Mileage May Vary on this One. 9. Eliminate the complexity of Ming Ming. This function is like a lot of local variables! There are three code to be evidence. First, the variable IDST is initialized to last-first, and only once; why not write Last-first-first-first to get rid of this confusion? Second, VECTOR's Iterator - VIT is created, the subscript is already available and can be used as, if this code will be clearer. Third, the local variable IT is initialized to the value of the function parameters, and the value of the function parameters after this is not used; my personal preference is, using the function parameters (even if you change the value of the parameters - completely no problem! ), Rather than introducing another name. 10. Reuse (first part): More use of standard libraries. Now the original program takes a high score because of the multiplex std :: sort - very good. But why don't you use std :: copy, and to manually implement the last loop to complete the copy work? Why do you want to re-use a dedicated sort_idxtbl_pair than std :: pair more comparison functions? In addition to writing simpler, multiplexing also makes your code more readable. Humble Thyself and Reuse! Principles: In any suitable place, understand and use (reuse) standard library facilities rather than yourself. 11. Reuse (second part): Let the implementation itself easier to reuse, so that there is a stone two birds. In the initial code, in addition to the function itself, there is no thing that can be reused. Outer Claus Sort_IDXTBL_PAIR is tightly tiered with its use, it is not "independently reusable). 12. Rear (Part III): Improve Signature. Original Signature Template Void sort_idxtbl (raiter first, raiter last, int * pIDxtbl) With a naked int * pointer points to the output area, I usually avoid this, I agree with the hosted storage space (for example, a vector). But end users must be able to call sort_idxtbl and put the output in a normal array or a vector or something. Then, "can put in any container" will only need an item, isn't it? (See Items 5 and 6.) Template Void Sort_idxtbl (Rain First, Rain Last, Out Result) Principle: Avoid unnecessary type hardcodes to expand the reuse of generic components. 13. Reuse (fourth), or call "Use! = To compare iterator": When you compare iterator, be sure to use! = (Available for various types of Iterator) instead of <(only for Random-Access) Iterator is valid), of course, unless you really have to use it As Scott Meyers is described in paragraph 32 in [Meyers96], "Program in 'future' will" Program in The Future Tense. ") He discussed: (Hereby refer to More Effective C Chinese version) Principle: Try to use! = Rather than 14. Unless you really need the old value, you will use the pre-incremental increment. In such a code, for the Iterator, it should be habitually incremented ( ) to avoid rear increment (i ); see [Sutter00, Article 39]. It is true that in the original code, there may be no essential difference, because Vector The above have covered most important issues. But there are some things that can be criticized, but I don't have to put the attention on these is not very important; for example: the product's code should have the purpose and semantic annotations of the functions, but this Not applicable to the code attached to the magazine, because there will be a better language in the article, more detailed explanation. I deliberately don't criticize the style of the main function (as opposed to the means network, because after all, this main function is just a demo tool, it helps readers understand the configuration of this facility. How to use, and the index table itself is the focus. to sum up Let us change a design on the basis of maintaining the interface of the original code. 40 Limit our criticism to correct the mechanism errors and basic style of the code, then consider the following three improvements. Each version has its own advantages, disadvantages, and style preferences, there is a corresponding explanation in the code annotation. The commonality of these three versions is more clear, more easy to understand, more suitable for transplants - such code should be valuable in your company. // an improved version of the code originally publicly published in [Hicks00]. // #include #include #include // Solution 1 Does Some Basic Cleanup But Still Preserves The General Structure // of the Original's Approach. We're Down To 17 Lines (Even if you count "public:" // and "private:" as lines), WHERE The Original HAD 23. // Namespace solution1 { Template Class sort_idxtbl_pair { PUBLIC: Void Set (const iter & it, int i) {it_ = it; i_ = i;} Bool Operator <(const sort_idxtbl_pair & other) const {RETURN * IT_ <* Other.it_;} Operator int () const {return i_;} Private: ITer IT_; INT i_; } // this function is where nurse of the clarity savings, // where the original had 13.After Each Code Line, I'll show the corresponding // Original Code for Comparison. Prefer to Write Code That IS Clear and Concise, // Not unnecessarily complex or obscure! // Template Void sort_idxtbl (iterin first, iterin last, oreout out) { Std :: vector // int idst = last-first; // typedef st :: vector // v V (IDST); For (int i = 0; i v [i] .set (first i, i); // int i = 0; // raiter it = first; // v :: itrator Vit = v.begin (); // for (i = 0; IT // (* VIT) .SET (IT, I); Std :: sort (v.begin (), v.end ()); // std :: sort (v.begin (), v.end ()); Std :: Copy (v.begin (), v.end (), out); // int * pi = pIDXTBL; // vit = v.begin (); // for (; VIT // * pi = (* VIT) .i; } } // Solution 2 Uses a pair instead of reinventing a pair-like helper class. Now we're // Down to 13 Lines, from the Original 23. of the 14 Lines, 9 Are Purpose-Specific, // and 5 Are Directly Reusable in Other contexts. // Namespace sol ;ion2 { Template Struct comparepair1stderef { Bool Operator () (Const std :: pair {return * a.first <* b.first;} } Template Void sort_idxtbl (iterin first, iterin last, oreout out) { Std :: Vector For (int i = 0; i s [i] = std :: make_pair (first i, i); Std :: sort (s.begin (), s.end (), comparepair1stderef For (int I = 0; i * OUT = S [i] .second; } } // Solution 3 Just Shows A Couple of Alternative Details¡ ªit buys a map to avoid a // Separate Sorting Step, And It Uses Std :: Transform () instead of a handcraft. // Here West Have 15 Lines, But More Are Reusable. This Version Uses more Space // Overhead and probably More Time Overhead Too, SO I Prefer Solution 2, But this // is an esample of finding alternative approaches to a problem. // Namespace solution3 { Template Struct comparedref { BOOL Operator () (Const T & A, Const T & B) Const {RETURN * a <* b;} } Template Struct pair2nd { Const u & operator () (const std :: pair } Template Void Sort_idxtbl (Iterin First, Iterin Last, Iteroutiterout Out) { Std :: MultiMap For (int i = 0; first! = last; i, first) v.insert (std :: make_pair (first, i)); Std :: Transform (v.begin (), v.end (), out, pair2nd } } // i left the test harness essentially unchanged, Except to Demonstrate Putting // the output in an output iterator (instead of necessarily an int *) and useing the // source Array Directly as a container. // #include Int main () { INT Ai [10] = {15, 12, 13, 14, 18, 11, 10, 17, 16, 19}; Std :: cout << "###########" << std :: endl; Std :: Vector // use annother namespace name to test a Different SolutionSolution3 :: Sort_idxtbl (AI, AI 10, AIDXTBL.BEGIN ()); For (int i = 0; i <10; i) Std :: cout << "i =" << i << ", AIDXTBL [I] =" << AIDXTBL [i] << ", AI [AIDXTBL [I]] =" << Ai [AIDXTBL [I]] << std :: endl; Std :: cout << "###########" << std :: endl; } 40 original author ([Hicks00] author) also reported feedback from another reader, and he showed another elegant, but completely different way: he created an object of a similar container, this object covered the original Containers and its Iterator, and allow for iterative access to different sequences.
