question on pair in <utility>

[subramanian100in]

Suppose left and right are two pair<T1, T2> objects.

Then
'left < right'
returns
left.first < right.first || !(right.first < left.first) && left.second
< right.second.

Suppose left.first is NOT less than right.first.

Then isn't the subexpression '!(right.first < left.first)' equivalent
to 'left.first == right.first' ?

Is there any reason for mentioning like '!(right.first < left.first)'
instead of
'left.first == right.first' ?

Kindly clarify.

Thanks
V.Subramanian

 

[Jeff Schwab]

Suppose left and right are two pair<T1, T2> objects.

Then
'left < right'
returns
left.first < right.first || !(right.first < left.first) && left.second
< right.second.

Suppose left.first is NOT less than right.first.

Then isn't the subexpression '!(right.first < left.first)' equivalent
to 'left.first == right.first' ?

Is there any reason for mentioning like '!(right.first < left.first)'
instead of
'left.first == right.first' ?

operator< is generally the first operator defined for a given type,
since the standard containers and algorithms default to std::less.
operator==(a, b) is then defined as !(a < b) && !(b < a). Using
operator< in the first place will therefore tend to be a little more
efficient.

 

[James Kanze]

Not if one of the types involved doesn't define an operator==.

operator< is generally the first operator defined for a given
type, since the standard containers and algorithms default to
std::less. operator==(a, b) is then defined as !(a < b) &&
!(b < a). Using operator< in the first place will therefore
tend to be a little more efficient.

For many types, an operator== can be implemented at far less
runtime cost than an operator<. If operator== is implemented, I
would expect it to be at least as fast as operator<, and in many
cases faster. On the other hand, it's quite conceivable that a
type implements operator< (in order to serve as a key in a
standard associative container), and not operator==. I
personally don't consider this good design, but the standard
library takes the policy of systematically requiring as little
as possible---functions which use order *never* call operator==.

 

[Jeff Schwab]

Not if one of the types involved doesn't define an operator==.



For many types, an operator== can be implemented at far less
runtime cost than an operator<.

I didn't say it couldn't be, just that it often isn't. operator== can
be defined in terms of operator<, but the reverse is not true; so, if
you need both, you either have to define operator== in terms of
operator<, or you have to implement them both manually and be careful to
keep them in sync. While the (typically) constant-factor speed-up
*might* be worth the increased risk of bugs, I would certainly wait for
a profiler to tell me so.

 

[James Kanze]

I didn't say it couldn't be, just that it often isn't.

That doesn't correspond to what I've actually seen in industry.
Most of the time, operator== gets implemented first, and the
relationship operators much later, only as needed, since for
most types, equality has meaning, but ordering doesn't. In the
end, operator< gets implement, if it does get implemented, with
arbitrary semantics, uniquely for the associative containers of
the STL.

And operator== can often be implemented significantly faster: on
a string, for example, you'll start by comparing the lengths.

operator== can be defined in terms of operator<, but the
reverse is not true; so, if you need both, you either have to
define operator== in terms of operator<, or you have to
implement them both manually and be careful to keep them in
sync.

Typically, both will be defined in terms of some named function:
compare(), or isEqual() (if there is a better algorithm for
equality). (Typically, one would hope, they will be implemented
using the Barton and Nackman trick, so all you have to do is
derived from the correct template instantiation, to get them
automatically.)

While the (typically) constant-factor speed-up *might* be
worth the increased risk of bugs, I would certainly wait for a
profiler to tell me so.

It's not a question of speed up:

bool operator==( MyType const& lhs, MyType const& rhs )
{
return lhs.compare( rhs ) == 0 ;
}

bool operator<( MyType const& lhs, MyType const& rhs )
{
return lhs.compare( rhs ) < 0 ;
}

The algorithm is in the compare() function, and will be equally
fast for both cases. (My own implementation of the
ComparisonOperators template base class uses a little bit of
meta programming to use isEqual() for == and !=, if it exists,
since if both isEqual and compare exist, compare will never be
slower.)

I don't think I've ever seen operator== implemented in terms of
operator<. I don't think it even occurs to most implementors to
do so.

 

[Jeff Schwab]

That doesn't correspond to what I've actually seen in industry.
Most of the time, operator== gets implemented first, and the
relationship operators much later, only as needed, since for
most types, equality has meaning, but ordering doesn't. In the
end, operator< gets implement, if it does get implemented, with
arbitrary semantics, uniquely for the associative containers of
the STL.

What you've said about the arbitrary semantics is certainly true. It is
common to define operator< to be as fast as possible, while
distinguishing objects that are not == in a consistent, so that the
objects can be stored in a std::set. (Of course, comparison according
to specific criteria are also common, e.g. comparing (x,y) points in
y-major order.) I don't think I've ever seen operator== defined *before*
operator<, and if I did, I would hope that the idea of replacing its
(often non-trivial) definition with a one-liner like !(a < b || b < a)
would at least be considered.

And operator== can often be implemented significantly faster: on
a string, for example, you'll start by comparing the lengths.

If there is a compelling performance reason, it can make sense to have a
separate operator==. That does not seem to be the common case, however.
Taking your example: Do you actually know that it is faster to check
lengths first, or have you only assumed it? Supposed that strings
commonly begin with any of thirty different characters (including case
distinctions), but have only ten common lengths. A traditional,
lexicographical comparison may be faster without the a priori
"optimization" of checking lengths. (Of course, operator== might still
be faster than two calls to operator<, but probably not compellingly so.)

Typically, both will be defined in terms of some named function:
compare(), or isEqual() (if there is a better algorithm for
equality). (Typically, one would hope, they will be implemented
using the Barton and Nackman trick, so all you have to do is
derived from the correct template instantiation, to get them
automatically.)

If such a comparison function already exists, then of course it makes
sense to use it, but I have not found this to be the most common
situation. (It was once upon a time; I vaguely remember defining
operators in terms of strcmp...)

We also don't always get to define the types we're comparing. I have
recently been working with a library that provides a lot of useful data
types, but does not provide comparators for them. Users of the library
frequently define special-purpose comparison functions for use with
std::sort, std::set, etc.

It's not a question of speed up:

bool operator==( MyType const& lhs, MyType const& rhs )
{
return lhs.compare( rhs ) == 0 ;
}

bool operator<( MyType const& lhs, MyType const& rhs )
{
return lhs.compare( rhs ) < 0 ;
}

The algorithm is in the compare() function, and will be equally
fast for both cases. (My own implementation of the
ComparisonOperators template base class uses a little bit of
meta programming to use isEqual() for == and !=, if it exists,
since if both isEqual and compare exist, compare will never be
slower.)

I don't think I've ever seen operator== implemented in terms of
operator<. I don't think it even occurs to most implementors to
do so.

Huh? It's very common. For example:
http://www.boost.org/libs/utility/operators.htm#arithmetic

It's interesting that you hope programmers "typically" use
Barton/Nackman, but you don't think it would occur to them to define
comparison operators in terms of each other.

I seem to vaguely recall an older version of GCC (2.95?) generating
operators automatically, but newer versions don't seem to do it. Maybe
it was some other library I was using at the time...

 

[James Kanze]

[...]

What you've said about the arbitrary semantics is certainly
true. It is common to define operator< to be as fast as
possible, while distinguishing objects that are not == in a
consistent, so that the objects can be stored in a std::set.

It's even more common to not define operator< at all, since it's
very common to have no natural ordering over the type, and most
applications still use hash tables, rather than std::set. Even
in places where std::set has replaced older hash tables, it's
usual to only implement operator< on an "as needed" basis. Or
even more often, provide a special comparison operator to be
used, rather than operator<, since an operator< which doesn't
implement a true less than relationship is confusing to the
users.

(Of course, comparison according to specific criteria are also
common, e.g. comparing (x,y) points in y-major order.)

That's a different case, but it doesn't really apply much to the
sort of things I work on. In fact, in many cases, it's almost
the opposite: there's no real logical ordering, but because the
identity is represented as an integral type (e.g. serial
number, etc.), we get an operator< which is (logically speaking)
arbitrary for free.

I don't think I've ever seen operator== defined *before*
operator<, and if I did, I would hope that the idea of
replacing its (often non-trivial) definition with a one-liner
like !(a < b || b < a) would at least be considered.

That is, quite frankly, crazy. First and foremost, you write
code to be read; that's *not* the intuitive definition of
equality in most peoples minds, and qualifies as obfuscation.
Except in exceptional cases, such an implementation of
operator== wouldn't get past code review.

If there is a compelling performance reason, it can make sense
to have a separate operator==. That does not seem to be the
common case, however.

Well, readability is of course the first consideration.
Comparing lengths improves readability by allowing a simpler
loop (or direct use of std::equals, today). In this case,
readability works with performance: a simpler loop is not only
easier to read, it will be faster (since I'll have one less
condition to test each time through).

Taking your example: Do you actually know that it is faster
to check lengths first, or have you only assumed it?

To tell the truth, I just picked an example out of my hat. The
code *is* easier to read and to understand if you check the
lengths first---a loop comparing two sequences of equal length
is simpler than one comparing sequences of possibly unknown
length.

Supposed that strings commonly begin with any of thirty
different characters (including case distinctions), but have
only ten common lengths. A traditional, lexicographical
comparison may be faster without the a priori "optimization"
of checking lengths. (Of course, operator== might still be
faster than two calls to operator<, but probably not
compellingly so.)

But implementing operator== in terms of operator< would still be
obfuscation.

If such a comparison function already exists, then of course
it makes sense to use it, but I have not found this to be the
most common situation. (It was once upon a time; I vaguely
remember defining operators in terms of strcmp...)

Most places where I've worked, coding guidelines have imposed
it. In a lot of cases, the operators didn't really get
implemented until later, long after isEqual(). And of course,
compare() has been a standard idiom for ages, for a number of
reasons. (Note that it is still present in std::string.)

We also don't always get to define the types we're comparing.

Nope. That's why all of the functions and containers which
depend on ordering have forms where you can supply an arbitrary
comparison function. In cases where I expect a type to be used
as an index, but there is no logical ordering, I'll normally
provide an additional type which establishes the arbitrary
ordering, rather that operator<.

I have recently been working with a library that provides a
lot of useful data types, but does not provide comparators for
them. Users of the library frequently define special-purpose
comparison functions for use with std::sort, std::set, etc.

Huh? It's very common. For
example:http://www.boost.org/libs/utility/operators.htm#arithmetic

Boost is hardly an example of what "typical" programmers do.

It's interesting that you hope programmers "typically" use
Barton/Nackman, but you don't think it would occur to them to
define comparison operators in terms of each other.

It's not "hope"---it's what I've actually seen in practice.
The Barton and Nackman trick has been around a lot longer than
the STL. And using it allows writing code in a more natural
fashion.

I seem to vaguely recall an older version of GCC (2.95?)
generating operators automatically, but newer versions don't
seem to do it. Maybe it was some other library I was using at
the time...

I don't remember this (and I've been using g++ off and on since
1.49), although it may have been present without my realizing
it. I rather doubt it was as late as 2.95, however---by that
time (and long before that, in fact), standards conformance had
become very important to the g++ developers.