I have the following operator< that is supposed to sort first by a value, then by another value:
inline bool operator < (const obj& a, const obj& b)
{
if(a.field1< b.field1)
return true;
else
return a.field2 < b.field2;
}
I have the feeling this is incorrect and that you can't do that without another third comparaison test on the members variables, but I can't find any example where this doesn't work.
So whould this really sort as expected?
thanks
edit :
I would have coded it as :
inline bool operator < (const obj& a, const obj& b)
{
if(a.field1< b.field1)
return true;
else if(a.field1> b.field1)
return false;
else
return a.field2 < b.field2;
}
are there any differences? I'm asking because I know mine is correct from experience but also longer than the first one
I'd like to do it all by myself..
You should only compare the values of Obj::field2
if the values of Obj::field1
are equal.
The easy-to-understand way:
/* This will meet the requirements of Strict-Weak-Ordering */
if (a.field1 != b.field1) return a.field1 < b.field1;
else return a.field2 < b.field2;
The correct (recommended) way:
The "correct" way of implementing it uses only operator<
to compare the fields, the below looks more complicated than it really is.
It will however yield the same result as the easy-to-understand example previously written.
return a.field1 < b.field1 || (
!(b.field1 < a.field1) && a.field2 < b.field2
);
There must be a way of implementing operator<
without causing a lot of headache?
C++11
You can use std::tuple
from the STL which already have operator<
for multiple fields defined, such as in the below example.
#include <utility>
...
inline bool
operator< (Obj const& lhs, Obj const& rhs)
{
return std::tie (lhs.field1, lhs.field2) < std::tie (rhs.field1, rhs.field);
}
C++03
If your compiler doesn't have support for C++11 yet and you only need to compare two fields from each object you could use std::pair
instead.
The reason for std::make_pair
is the same as in the previous example using std::tie
.
#include <utility>
...
inline bool
operator< (Obj const& lhs, Obj const& rhs)
{
return std::make_pair (lhs.field1, lhs.field2)
< std::make_pair (rhs.field1, rhs.field2);
}
using std::pair
will require copies of the members to be created, which in some circumstances is undesirable.
Is this really recommended practise?
See the below question/answers for more information, but to sum it up; the c++11 approach doesn't cause that much overhead and it's very simple to implement.
- Implementing comparision operators via 'tuple' and 'tie', a good idea?
Think of what happens if a.field1
is greater than b.field1
but a.field2
is less than b.field2
. In that circumstance, you compare based solely on field2
which is not what you want.
You only want to bring field2
into play where the field1
fields are equal, so what you're looking for is something like (pseudo-code):
if a.field1 < b.field1: return true
if a.field1 > b.field1: return false
# field1s is equal here.
return a.field2 < b.field2
No. You need to also catch (a.field1 > b.field1)
.
This is not a strict weak ordering, because it would give (1,2) < (2,1)
, but also (2,1) < (1,2)
.
Here's a version that relies on the logical short-circuit rule to avoid explicit branching
template<typename T>
bool operator< (T const& a, T const& b)
{
return (
( a.field1 < b.field1 ) || (( a.field1 == b.field1 ) &&
( a.field2 < b.field2 ))
);
}
This assumes that your primitive type of field1
has an operator==
. It becomes tedious to type this for more than 2 fields, but you could use std::lexicographical_compare
if your class obj
stores the fields inside an std::array<T, N>
for some type T
and size N
template<typename T, int N>
struct obj
{
std::array<T, N> field;
};
bool operator< (obj const& a, T const& b)
{
return std::lexicographical_compare(
a.field.begin(), a.field.end(),
b.field.begin(), b.field.end()
);
}
Note that there is a draft paper N3326 that discusses adding operators ==
and <
automatically for class types.