Effective STL Terms 21

zhaozj2021-02-11  197

Terms 21: Always let comparison functions return to false to equal values

Let me show you some cool things. Create a SET, compare the type with Less_equal, then insert a 10:

Set > sorted by "<="

S.insert (10); // Insert 10

Try now again 10:

sinsert (10);

For this INSERT call, SET must first determine if 10 is already in it. We know that it is, but SET is wood, it must perform check. In order to make it easy to make what happen, we will be called 10A at 10A at the beginning of the SET, and the 10 called 10B that is trying to insert.

SET traverses its internal data structure to find where to insert 10B. Finally, it always checks if 10b is the same as 10A. The associated container is equivalent (see Terms 19), so the SET test 10b is equivalent to 10A. When this test is executed, it is naturally a comparison function using the SET. In this example, it is Operator <= because we specify the comparison function of the set is Less_equal, while less_equal means Operator <=. So, the SET will calculate whether this expression is true:

! (10A <= 10b) &&! (10B <= 10A) // Whether 10A and 10B are equivalent

Oh, 10A and 10B are 10, so 10A <= 10b is definitely true. It is also clear that 10b <= 10A. The above expression is simplified

! (TRUE) &&! (TRUE)

Again is simplified

False && false

The result is of course false. That is, the conclusion drawn by SET is 10A and 10B inequality, so it is not the same, so it is inserted into the side of 10a in the container. In terms of techniques, this practice leads to undefined behaviors, but the usual result is SET to end with two copies of 10 values, that is, it is no longer a set. By using Less_equal as our comparison type, we destroy the container! In addition, any comparison function that returns TRUE to the equal value will do the same thing. According to the definition, equal value is not equivalent! Is it cool?

OK, maybe you are not the same for cool definitions. Even if this is, you still need to make sure that the comparison function you use on the associated container always returns false. However, you need to stay vigilant. The violation of this rule is easy to achieve a surprising consequence.

For example, the Terms 20 describe how to write a comparison function such that the container that accommodates the String * pointer is sorted according to the value of the string, rather than the value of the pointer. That comparison function is sorted in ascending order, but we now assume that you need String * pointer's descending order sorting comparison function. Naturally, it is a codes to be modified. If you are not careful, you may do this, I have already highlighted the part of the Code of Terms 20:

Struct stringptrgreater: // highlight

Public binary_function

Const string *, // Beware, this code is awkward!

Bool> {

BOOL Operator () (const string * ps1, const string * ps2) Const

{

Return! (* ps1 <* ps2); // Only the opposite of the old test;

} // this is not right!

}

The idea here is to reach the result of reach the inverse sequence by reverse the comparative function. Unfortunately, reflect "<" will not give you (you expect) ">", it gives you "> =". You now know because it will return to TRUE to the equal value, which is an invalid comparison function for the associated container.

The type of comparison you really need is this:

Struct stringptrgreater: // For associated containers

Public binary_function

Const string *,

Bool> {

BOOL Operator () (const string * ps1, const string * ps2) Const

{

Return * ps2 <* ps1; // Returns * PS2 is

} / / Greater than * ps1 (that is

}; // The order in which the number of exchanges is exchanged)

To avoid falling into this trap, what you have to remember is the return value of the comparison function indicating whether a value is greater than another in the sort mode defined in this function. The equal value is not the one greater than the other, so the comparison function always returns the equivalent value to false.

Ugh.

I know what you are thinking. You are thinking, "Of course, this is very meaningful for Set and MAP because these containers cannot accommodate the copy. How about MultiSet and MultiMap? Those containers can contain a copy, and those containers may contain copies, so if the container is considered What do you need to pay attention to two values? What do I have to pay? It will store both all, this is what the Multi series container is supported. No problem, right? "

wrong. I want to know why, let's go back to see the original example, but this time it is a MULITSET:

MultiSet > s; // s Still sorting "<="

S.insert (10); // Insert 10A

S.insert (10); // Insert 10B

Now, there is two copies of 10, so we expect that we will get a pair of iterators that point out the range of the two copies. But that is impossible. Equal_Range, although called this name, but does not indicate the range of equal values, but the range of equivalent values. In this example, the comparison functions of S say 10a and 10b are not equivalent, so it is impossible to make them simultaneously in the range indicated by Equal_Range.

Do you understand it? Unless your comparison function always returns false for equal values, you will break all standard associated containers, whether or not they allow storage.

It is technically said that the comparison function for sorting the associated container must define a "strict weak sequenification" on the object they compare. (The comparison function transmitted to the Sort and other algorithms (see Terms 31) also has the same limit). If you are interested in strictly disabled meaning, you can find in many comprehensive STL reference books, such as Josuttis's "THE C Standard Library" [3] (Translation: Chinese translation "C standard library" P176) Austern's "Generic Programming and the STL" (Translation: Chinese translation "generic program design and STL") [4], and SGI STL website [21]. I have never discovered this detail so important, but a strictly deceased requirement directly to this terms. That requirement is that any function that defines a strictly weak sequence-based function must return FALSE when it is incorporated into the same value. Hey! This is this terms!

转载请注明原文地址:https://www.9cbs.com/read-4786.html

New Post(0)