Associative Container Equality Assessment (STL)

Question

I know that STL associative containers (and other containers are sorted, I would suggest) use sorting criteria to check for equality.

The default sorting criteria for containers is st :: less, so this will do an equality test for the container:

if (! (lhs < rhs || rhs < lhs)) 

or something similar. I had a couple of questions about this ...

First of all, this seems like a strangely inefficient comparison method for equality - why does the STL do it like this? I would expect STL containers to just take an extra default parameter for equality.

My second question is more about evaluating the above if statement. In C ++, how much of this statement will be evaluated (lhs> rhs) was true? Would it stop trying after evaluating the side that failed, thereby saving some efficiency? If so, what part of the expression is evaluated first?

Answer 1

In "Effective STL," Scott Myers discusses this in detail in Item 19 :

Understand the difference between equality and equivalence.

Equality, as you would expect, is based on operator== .

Equivalence "is based on the relative ordering of the values ​​of the object in the sorted range ... Two objects have equivalent values ​​in the container c , if none precedes the other in the sort order c .

Meyers puts it this way:

 !( w1 < w2 ) // it not true that w1 < w2 && // and !( w2 < w1 ) // it not true that w2 < w1 

Meyers then repeats:

This makes sense: two values ​​are equivalent (with respect to some order order) if none precedes the other (according to this criterion).

As for why the STL does this as follows:

Using only one comparison function and using equivalences, as an arbiter of what “same” means, standard associative containers ... avoid the confusion that would arise from mixing the use of equality and equivalence inside standard associative containers.

Read article 19 (which covers more than 6 pages) for yourself to get the full flavor.

Answer 2

Associative containers STL

You mean: C ++ standard sorted associative containers.

I would expect STL containers to just take an extra default parameter for equality.

What would it be? In your tutorial, the red-black tree algorithm instead

 if (x < y) // ... else if (y < x) // ... else // equality 

you will have

 if (x == y) // equality else if (x < y) // ... else // y < x 

so two more comparisons in the worst case.

Responding to comments on this answer: the presence of only an operator with fewer operators makes containers more convenient to use, since there is no need to maintain consistency between smaller and equal. Imagine you have a program that stores floating point numbers. One day, someone decides to replace the function of bitwise equality float_equals , which was just used by some container, as well as their code, by approximate comparison. If this person does not update the float_less function because their code does not use this function, then your container code mysteriously breaks.

(Oh, and in the above code example, a short circuit is applied, as always.)

Answer 3

Regarding the second question: standard lLy evaluation rules for Boolean expressions apply. If the value of LHS || true, RHS is not rated.

Answer 4

C ++ evaluates if () from left to right for your case with ||. Evaluates the left side (lhs <rhs). If this is true and it is not a compound statement (this is not the case in your case), it evaluates the if integer as true without checking the correct side. (Then it really returns a negative value, since there is no one in front of it.) If it is incorrect, then it goes to the right side (rhs <lhs) and evaluates this, and then the whole expression.

Answer 5

First of all, it looks like a strangely inefficient comparison method for equality

Yes, but sorted containers carry out this test relatively rarely.

Using a comparison function like strcmp would be better. Using both less and comparisons will be even better.

In C ++, how much of this statement will be evaluated (lhs> rhs) was true?

In C and C ++, a && b , a || b a || b , a, b , a ? b : c a ? b : c are evaluated from left to right, only with an estimate of the useful right-hand side (except for the overloaded && , || in C ++).

This allows you to use some useful short tests, for example: p != NULL && *p > 2