CODEWITHSUNDEEP
c++stl
John Humphreys
John Humphreys

Reputation: 39294

Equality evaluation in associative containers (STL)

I'm aware that STL associative containers (and other containers being sorted I would guess) use the sorting criterion to test for equality.

The sorting criterion for containers defaults to st::less, so that would make the equality test for a container:

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

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

First of all, it seems like a strangely inefficient way to compare for equality - why does the STL do it like this? I would have expected STL containers to just take an extra default parameter for equality instead.

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

Upvotes: 9

Views: 1741

Answers (5)

ScarletAmaranth
ScarletAmaranth

Reputation: 5101

C++ evaluates if() left to right for your case with ||. Evaluates left side (lhs < rhs) - If it's true and it's not a compound statement (it's not in your case), it evaluates the whole if as true without checking the right side. (Then indeed returns negated value since there's not in front of it.) If it's false then it moves on to the right side (rhs < lhs) and evaluates that and then the whole expression.

Upvotes: 0

Fred Foo
Fred Foo

Reputation: 363567

STL associative containers

You mean: standard C++ sorted associative containers.

I would have expected STL containers to just take an extra default parameter for equality instead.

What would that achieve? In your textbook red-black tree algorithm, instead of

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

you'd have

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

so still two comparisons in the worst case.

Responding to the comments to this answer: having only a less-than operator to supply makes the containers substantially easier to use, since there's no need to maintain consistency between less-than and equals. Let's imagine you have a program storing floating point numbers. One day, someone decides to replace the bitwise-equality float_equals function, that just happened to be used by some container but also by their code, by an approximate comparison. If that person doesn't update the float_less function, because their code doesn't use that function, then your container code mysteriously breaks.

(Oh and in the example code shown, short-circuiting applies, as always.)

Upvotes: 5

curiousguy
curiousguy

Reputation: 8268

First of all, it seems like a strangely inefficient way to compare for equality

Yes, but sorted containers do this test relatively rarely.

Using a compare function like strcmp would be better. Using both less-than and compare would be still better.

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

In C and in C++, a && b, a || b, a, b, a ? b : c are evaluated left-to-right, with only the useful right part evaluated (except for overloaded &&, ||, , operators in C++).

This allows several useful short tests like: p != NULL && *p > 2

Upvotes: -2

Gnawme
Gnawme

Reputation: 2389

In "Effective STL," Scott Meyers has an extensive discussion about this in Item 19:

Understand the difference between equality and equivalence.

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

Equivalence "is based on the relative ordering of object values in a sorted range... Two objects have eqivalent values in a container c if neither precedes the other in c's sort order."

Meyers expresses it this way:

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

Meyers then restates:

This makes sense: two values are equivalent (with respect to some ordering criterion) if neither precedes the other (according to that criterion.)

As for why the STL does it this way:

By using only a single comparison function and by employing equivalence as the arbiter of what it means to be "the same," the standard associative containers... avoid the kind of confusion that would arise from mixing uses of equality and equivalence within standard associative containers.

Read Item 19 (which spans the better part of 6 pages) for yourself to get the full flavor.

Upvotes: 18

thiton
thiton

Reputation: 36049

Regarding the second question: Standard C lazy evaluation rules for boolean expressions apply. If the LHS of || is true, the RHS is not evaluated.

Upvotes: 3

Related Questions