Equality evaluation in associative containers (STL)

Question

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?

Answer 1

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.

Answer 2

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.)